원조 Apriori 알고리즘의 성능 한계를 극복하기 위해, 효율성을 개선한 다양한 변형 알고리즘이 제안되었습니다. 대표적인 최적화 기법으로는 해시 기반 기법, 트랜잭션 축소, 분할(Partitioning), 샘플링(Sampling) 네 가지가 있습니다.
1. 해시 기반 기법 (Hash-based Technique)
해시 기반 기법은 후보 k-항목집합(Ck, k > 1)의 크기를 줄여 후보 생성 단계의 부담을 덜어주는 방식입니다.
예를 들어, 데이터베이스의 각 트랜잭션을 스캔하면서 후보 1-항목집합 C1로부터 빈발 1-항목집합 L1을 생성할 때, 각 트랜잭션에 포함된 2-항목집합을 만들어 해시 테이블 구조의 여러 버킷(bucket)으로 매핑(hash)하고, 해당 버킷의 카운트를 증가시킬 수 있습니다. 이렇게 하면 지지도가 낮은 항목집합을 조기에 걸러내어 후보 집합의 규모를 획기적으로 축소할 수 있습니다.
2. 트랜잭션 축소 (Transaction Reduction)
빈발 k-항목집합을 하나도 포함하지 않는 트랜잭션은 빈발 (k+1)-항목집합 역시 포함할 수 없다는 원리를 활용합니다.
따라서 이러한 트랜잭션은 표시해 두거나 삭제하여 이후 스캔 대상에서 제외할 수 있습니다. j-항목집합(j > k)을 탐색하기 위한 데이터베이스의 후속 스캔에서는 해당 트랜잭션이 더 이상 필요하지 않기 때문에, 스캔해야 할 데이터량이 반복적으로 줄어들어 전체 처리 속도가 향상됩니다.
3. 분할 기법 (Partitioning)
분할 기법은 단 두 번의 데이터베이스 스캔만으로 빈발 항목집합을 마이닝할 수 있는 방법으로, 두 단계로 진행됩니다.
1단계: 지역 빈발 항목집합 도출
알고리즘은 데이터베이스 D의 트랜잭션을 서로 겹치지 않는 n개의 파티션으로 나눕니다. D 전체의 최소 지지도 임계값이 min_sup이라면, 각 파티션의 최소 지지도 카운트는 min_sup × 해당 파티션의 트랜잭션 수로 계산됩니다.
각 파티션 내부에서 모든 빈발 항목집합을 발견하는데, 이를 지역 빈발 항목집합(local frequent itemsets)이라고 합니다. 이 과정에서는 각 항목집합에 대해 그 항목들을 포함하는 트랜잭션의 TID(트랜잭션 ID)를 기록하는 특수 데이터 구조를 활용합니다. 덕분에 데이터베이스를 단 한 번만 스캔하여 k = 1, 2, ...에 대한 모든 지역 빈발 k-항목집합을 찾아낼 수 있습니다.
지역 빈발 항목집합이 전체 데이터베이스 D 관점에서도 빈발한다고 보장할 수는 없습니다. 그러나 D에서 빈발할 가능성이 있는 항목집합은 반드시 최소한 하나의 파티션에서는 빈발 항목집합으로 나타나야 합니다. 따라서 모든 파티션에서 얻은 지역 빈발 항목집합들의 집합이 곧 D에 대한 전역 후보 항목집합(global candidate itemsets)이 됩니다.
2단계: 전역 빈발 항목집합 확정
D에 대한 두 번째 스캔을 수행하여 각 후보 항목집합의 실제 지지도를 평가하고, 이를 통해 최종적인 전역 빈발 항목집합을 확정합니다.
4. 샘플링 기법 (Sampling)
샘플링 접근법의 핵심 아이디어는 주어진 데이터 D에서 무작위 표본(random sample) S를 추출한 뒤, D 전체가 아니라 S에서 빈발 항목집합을 탐색하는 것입니다.
이 방법은 일정 수준의 정확성을 희생하는 대신 처리 효율을 크게 높일 수 있습니다. 표본 S의 크기를 조정하여 S에 대한 빈발 항목집합 탐색이 주 메모리(main memory) 안에서 완료되도록 하면, 전체 과정에서 S의 트랜잭션을 단 한 번만 스캔하면 됩니다. 대용량 데이터 환경에서 특히 유용한 기법입니다.