선험적(Apriori) 알고리즘의 개요
Apriori(선험적) 알고리즘은 1994년 R. Agrawal과 R. Srikant가 개발한 기념비적인 데이터 마이닝 알고리즘으로, 불리언 연관 규칙(Boolean association rules)을 위한 빈번한 항목집합(frequent itemsets)을 발견하는 데 사용됩니다. 이 알고리즘의 이름인 'Apriori'는 알고리즘이 빈번한 항목집합의 속성에 대한 사전 지식을 활용한다는 사실에서 유래했습니다.
Apriori 알고리즘은 단계별 탐색(level-wise search)이라 불리는 반복적 방법을 사용합니다. 이 방식에서는 k-항목집합(k-itemsets)을 탐색하여 (k+1)-항목집합을 찾아냅니다.
단계별 탐색(Level-wise Search)의 진행 과정
먼저, 데이터베이스를 훑어 각 항목의 등장 횟수를 집계하고 최소 지지도(minimum support)를 만족하는 항목들을 추출하여 빈번한 1-항목집합의 집합을 찾습니다. 이 결과 집합은 L1로 표기합니다.
다음으로, L1을 이용해 빈번한 2-항목집합의 집합인 L2를 찾고, 다시 L3를 찾는 식으로 반복합니다. 이 과정은 더 이상 빈번한 k-항목집합을 발견할 수 없을 때까지 계속됩니다. 각 Lk를 찾으려면 데이터베이스 전체를 한 번씩 완전히 스캔해야 한다는 점에 유의해야 합니다.
Apriori 속성(Apriori Property)
빈번한 항목집합 생성의 효율을 높이기 위해, Apriori 알고리즘은 Apriori 속성이라 불리는 핵심 특성에 의존합니다. 이 속성은 탐색 공간(search space)을 크게 줄여주는 역할을 합니다.
Apriori 속성: 빈번한 항목집합의 모든 비어 있지 않은 부분집합(nonempty subsets) 또한 반드시 빈번해야 한다.
이 속성은 다음과 같은 관찰에 기반합니다. 정의에 따라, 어떤 항목집합 I가 최소 지지도 임계값(min_sup)을 만족하지 못하면 I는 빈번하지 않습니다. 즉, P(I) < min_sup입니다.
여기서 항목 A를 항목집합 I에 추가하면, 그 결과로 생긴 항목집합(I ∪ A)은 I보다 더 자주 나타날 수 없습니다. 따라서 I ∪ A 역시 빈번하지 않으며, P(I ∪ A) < min_sup가 성립합니다.
반단조성(Antimonotone)
이 속성은 반단조적(antimonotone) 특성에 속합니다. 어떤 집합이 특정 검사(test)를 통과하지 못하면, 그 집합의 모든 상위집합(superset) 역시 같은 검사를 통과하지 못한다는 의미입니다. 이 속성이 '검사 실패'라는 관점에서 단조적(monotonic)이기 때문에 '반단조적'이라고 불립니다.
후보 항목집합 생성: 조인 단계와 가지치기 단계
Apriori 알고리즘은 Lk를 찾기 위해 조인(join)과 가지치기(prune)라는 두 단계 과정을 거칩니다.
1. 조인 단계(The Join Step)
Lk를 찾기 위해, Lk−1을 자기 자신과 조인하여 후보 k-항목집합(candidate k-itemsets)의 집합을 생성합니다. 이 후보 집합은 Ck로 표기합니다. 예를 들어 l1과 l2가 Lk−1에 속한 항목집합일 때, 표기법 li[j]는 li의 j번째 항목을 의미합니다(예: l1[k−2]는 l1의 뒤에서 두 번째 항목을 나타냄).
2. 가지치기 단계(The Prune Step)
Ck는 Lk의 상위집합(superset)입니다. 즉, Ck의 멤버 중 일부는 빈번하지 않을 수 있지만, 모든 빈번한 k-항목집합은 Ck 안에 포함되어 있습니다. 데이터베이스를 스캔하여 Ck에 있는 각 후보의 등장 횟수를 계산하면 Lk를 결정할 수 있습니다. 등장 횟수가 최소 지지도 횟수(minimum support count)보다 작지 않은 후보들은 정의상 빈번하므로 Lk에 속하게 됩니다.
다만 Ck는 매우 커질 수 있으므로, 이후 계산량도 상당히 커질 수 있다는 점을 고려해야 합니다. 이러한 이유로 Apriori 속성을 활용한 가지치기가 알고리즘의 효율성을 좌우하는 핵심 요소가 됩니다.