데이터 마이닝 (연관규칙, Apriori 알고리즘)

[apriori 알고리즘?]

apriori 알고리즘은 데이터 마이닝과 연관 규칙 학습 분야에서 매우 유용한 알고리즘 중 하나입니다. 이 알고리즘은 주어진 데이터 세트에서 항목 간의 연관성을 파악하는 데 사용됩니다. 특히, 많은 트랜잭션이 있는 데이터베이스에서 발견된 빈번한 항목 집합(frequent itemset)을 찾아내는 데 초점을 맞추고 있습니다.

아래에서 apriori 알고리즘의 작동 방식과 주요 단계를 설명하겠습니다:

1. 지지도(Support) 설정:
   • 사용자가 지정한 임계값(min_support)을 사용하여 빈번한 항목 집합을 결정합니다. 지지도는 특정 항목 집합이 데이터 세트 내에서 등장하는 비율을 의미합니다. 일반적으로 이 값은 0과 1 사이의 실수로 표현됩니다.
2. 1-항목집합 생성:
   • 모든 항목들로 구성된 모든 가능한 단일 항목 집합을 생성합니다.
3. 최초 빈번한 항목 집합 찾기:
   • 데이터 세트를 스캔하여 각 항목이 얼마나 자주 나타나는지 계산합니다.
   • 지지도가 사용자가 설정한 임계값을 넘는 항목들로만 빈번한 항목 집합을 형성합니다.
4. 항목 집합 확장:
   • 1-항목집합에서 발견된 빈번한 항목들을 사용하여 더 큰 크기의 항목 집합을 생성합니다.
   • 예를 들어, 2-항목집합은 두 개의 항목을 포함하는 항목 집합을 의미합니다.
5. 빈번한 항목 집합 찾기:
   • 데이터 세트를 다시 스캔하며, 새롭게 생성된 항목 집합의 지지도를 계산합니다.
   • 지지도가 임계값을 넘는 항목 집합만을 남겨둡니다.
6. 계속 확장:
   • 위의 단계를 반복하여 더 큰 크기의 빈번한 항목 집합을 생성합니다.
   • 더 이상 빈번한 항목 집합을 찾을 수 없을 때까지 이 과정을 반복합니다.
7. 연관 규칙 생성:
   • 모든 빈번한 항목 집합으로부터 가능한 모든 연관 규칙을 생성합니다.
   • 연관 규칙은 두 부분으로 구성됩니다: 규칙의 선행절(antecedent)과 규칙의 후행절(consequent).
   • 예를 들어, {사과, 우유} -> {빵}은 사과와 우유를 구매한 고객이 빵을 구매할 확률을 의미합니다.
8. 규칙 평가:
   • 생성된 연관 규칙들을 평가하여 흥미로운 규칙들을 선별합니다.
   • 대표적으로 지지도, 신뢰도, 향상도라는 세 가지 지표가 사용됩니다.
     • 지지도: 규칙의 전체 발생 빈도
     • 신뢰도: 선행절과 후행절 간의 연관성 정도
     • 향상도: 규칙의 신뢰도를 단순히 각 항목의 개별 발생 확률로 나눈 값으로, 1보다 크면 우연적인 규칙보다 유의미한 규칙을 의미
9. 결과 제공:
   • 흥미로운 규칙들을 사용자에게 제공하거나 원하는 분석에 활용합니다.

apriori 알고리즘은 효율적인 방식으로 빈번한 항목 집합과 연관 규칙을 찾아내는데 사용되며, 상업적으로 매우 유용합니다. 그러나 큰 데이터 세트에서는 계산 비용이 증가하여 성능 문제가 발생할 수 있습니다. 이러한 문제를 극복하기 위해 개선된 알고리즘들이 제안되기도 합니다.