Apriori 알고리즘과 빈발 항목집합 생성
Apriori 알고리즘은 빈발 항목집합(frequent itemset) 생성 과정에서 발생하는 조합적 폭발(combinatorial explosion) 문제를 가장 효과적으로 해결한 알고리즘입니다. Apriori 원리를 활용해 지수적으로 증가하는 탐색 공간을 크게 줄임으로써 이를 실현합니다. 그러나 상당한 성능 향상에도 불구하고, 거래 데이터셋(transaction dataset)을 여러 번 반복해서 읽어야 하기 때문에 상당한 I/O 오버헤드가 발생한다는 단점이 있습니다.
또한 거래의 폭(항목 수)이 커질수록, 특히 밀도 높은(dense) 데이터셋에서는 Apriori 알고리즘의 성능이 크게 저하될 수 있습니다. 이러한 한계를 극복하고 알고리즘의 효율성을 높이기 위해 다양한 개선 기법들이 제안되었습니다.
아래에서는 이러한 방법들을 상위 수준에서 살펴보겠습니다.
1. 항목집합 격자(Itemset Lattice) 탐색
빈발 항목집합에 대한 탐색은 항목집합 격자(lattice) 구조 위에서의 순회(traversal)로 볼 수 있습니다. 알고리즘이 채택하는 탐색 전략에 따라 빈발 항목집합 생성 단계에서 격자 구조를 어떤 방식으로 순회할지가 결정됩니다. 격자 내 빈발 항목집합의 분포 형태에 따라 어떤 탐색 방법이 더 유리한지가 달라지므로, 상황에 맞는 전략 선택이 중요합니다.
2. 일반→특수 탐색 vs 특수→일반 탐색
일반→특수(General-to-Specific) 탐색
Apriori 알고리즘은 일반→특수 방식의 탐색 접근법을 사용합니다. 즉, 빈발 (k-1)-항목집합들의 쌍을 결합하여 후보 k-항목집합을 생성하는 방식입니다. 이 방법은 빈발 항목집합의 최대 길이가 너무 길지 않은 경우에 효율적으로 동작합니다.
특수→일반(Specific-to-General) 탐색
반면 특수→일반 탐색 방식은 더 일반적인 빈발 항목집합을 찾기 전에, 더 구체적(길이가 긴)인 빈발 항목집합부터 먼저 탐색합니다. 이 방법은 빈발 항목집합의 경계(border)가 격자 하단 부근에 위치하는 밀도 높은 거래 데이터베이스에서 최대 빈발 항목집합(maximal frequent itemset)을 찾는 데 특히 유용합니다.
Apriori 원리를 활용하면 최대 빈발 항목집합의 일부 부분집합을 가지치기(pruning)할 수 있습니다. 구체적으로, 어떤 후보 k-항목집합이 최대 빈발임이 확인되면 길이가 k-1인 부분집합들을 검사할 필요가 없습니다. 반대로 후보 k-항목집합이 비빈발(infrequent)이라면, 다음 반복 단계에서 해당 집합의 모든 k-1 크기 부분집합을 검사해야 합니다.
양방향(Bidirectional) 탐색
또 다른 방법은 일반→특수 탐색과 특수→일반 탐색을 결합하는 것입니다. 이 양방향 접근법은 후보 항목집합을 저장하기 위해 더 많은 메모리 공간이 필요하지만, 빈발 항목집합의 경계를 신속하게 파악하는 데 도움이 됩니다.
3. 동치 클래스(Equivalence Classes)
격자 순회를 바라보는 또 다른 관점은 격자를 서로 겹치지 않는 노드 그룹(동치 클래스)으로 먼저 분할하는 것입니다. 빈발 항목집합 생성 알고리즘은 하나의 동치 클래스 내에서 빈발 항목집합을 먼저 탐색한 후, 다른 동치 클래스로 이동하는 방식으로 진행합니다.
Apriori 알고리즘이 사용하는 단계별(level-wise) 접근법은 항목집합의 크기를 기준으로 격자를 분할하는 것으로 볼 수 있습니다. 즉, 더 큰 크기의 항목집합으로 넘어가기 전에 모든 빈발 1-항목집합을 먼저 찾는 방식입니다. 또한 동치 클래스는 항목집합의 접두사(prefix) 또는 접미사(suffix) 레이블을 기준으로 정의할 수도 있습니다.