아프리오리(Apriori) 알고리즘은 장바구니 분석 등에서 ‘자주 함께 구매되는 상품 집합’을 찾기 위해 고안된 대표적인 연관 규칙 탐색 알고리즘입니다. --- ## 1. 주요 개념 ## 데이터 마이닝 주요 지표 ### 지지도 (Support) 전체 거래 중 특정 아이템 집합이 포함된 비율 $ \text{support}(A) = \frac{\#(\text{transactions containing } A)}{\#(\text{total transactions})} $ ### 신뢰도 (Confidence) 규칙 $A \Rightarrow B$가 성립할 확률 $ \text{confidence}(A \Rightarrow B) = \frac{\text{support}(A \cup B)}{\text{support}(A)} $ ### 향상도 (Lift) 두 아이템의 독립성 대비 규칙의 강도 $ \text{lift}(A \Rightarrow B) = \frac{\text{confidence}(A \Rightarrow B)}{\text{support}(B)} $ --- ## 2. 알고리즘 흐름 1. **1차 빈발 항목 집합 구하기** - 전체 거래에서 아이템별 지지도를 계산 - 최소 지지도(`min_support`) 이상인 단일 아이템 집합을 `L1`에 저장 2. **k차 후보 집합 생성 (Candidate Generation)** - 이전 단계 빈발 집합 `L_{k-1}`에서 서로 다른 두 집합을 합쳐 크기 k인 후보 집합 `C_k` 생성 - 예: `{A, B}` 와 `{A, C}` → `{A, B, C}` 3. **가지치기(Prune)** - 후보 집합의 모든 (k−1)-부분집합이 `L_{k-1}`에 있어야 함 - 그렇지 않으면 지지도 계산 없이 배제 4. **지지도 계산 및 빈발 집합 필터링** - `C_k`의 각 후보에 대해 전체 거래를 스캔해 지지도 계산 - `min_support` 이상인 것만 `L_k`에 남김 5. **반복 종료 조건** - `L_k`가 비어 있으면 종료 - 그렇지 않으면 단계 2로 돌아가서 k ← k+1 진행 --- ## 3. 의사코드 (Pseudocode) ```text Apriori(transactions, min_support): L1 = { frequent 1-itemsets } k = 2 while L_{k-1} ≠ ∅: C_k = apriori_gen(L_{k-1}) for t in transactions: for candidate in C_k: if candidate ⊆ t: count[candidate] += 1 L_k = { c ∈ C_k | count[c] / |transactions| ≥ min_support } k += 1 return ⋃_k L_k ``` 함수 `apriori_gen(L)` 은 `L` 내 집합들을 조합하고, 부분집합 검사로 가지치기(prune)하는 역할을 합니다. --- ## 4. 장단점 및 활용 사례 - **장점** - 단순하고 이해하기 쉬운 탐색 전략 - 가지치기 기법으로 불필요한 후보를 줄여 계산 효율성 확보 - **단점** - 거래 수나 아이템 수가 많아지면 후보 집합 폭발(Candidate Explosion) - 디스크 I/O가 많아질 수 있음 - **활용 사례** - 마케팅: 고객 구매 패턴 분석 - 웹 로그 분석: 페이지 방문 연관성 탐색 - 바이오인포매틱스: 유전자 발현 패턴 간 연관성 탐색