지원 계산(Support Counting)의 정의
지원 계산은 apriori-gen 함수의 후보 가지치기(candidate pruning) 단계를 통과한 각 후보 항목집합(candidate itemset)이 데이터셋에 등장하는 빈도, 즉 지원도(support)를 결정하는 절차입니다. 연관 규칙 분석에서 지원 계산은 가장 계산 집약적인 단계 중 하나로, 효율적인 구현이 전체 알고리즘 성능에 큰 영향을 미칩니다.
지원 계산의 두 가지 기본 방법
1. 트랜잭션과 후보 항목집합의 전수 비교
첫 번째 방법은 각 트랜잭션을 모든 후보 항목집합과 하나씩 비교하여, 해당 트랜잭션에 포함된 후보들의 지원도 카운트를 갱신하는 것입니다. 그러나 이 방법은 계산 비용이 매우 크며, 특히 트랜잭션의 수와 후보 항목집합의 수가 많아질수록 비효율성이 급격히 커진다는 단점이 있습니다.
2. 트랜잭션 내 항목집합 열거
두 번째 방법은 각 트랜잭션에 포함된 항목집합들을 직접 열거하고, 이를 바탕으로 대응되는 후보 항목집합의 지원도 카운트를 갱신하는 것입니다. 예를 들어 {1, 2, 3, 5, 6}의 다섯 개 항목을 포함하는 트랜잭션 t가 있다고 가정하면, 이 트랜잭션에는 크기 3인 항목집합이 C(5,3) = 10개 존재합니다.
열거된 항목집합 중 일부는 분석 대상인 후보 3-항목집합과 일치할 수 있으며, 이 경우 해당 후보의 지원도 카운트가 증가합니다. 반면 어떤 후보와도 일치하지 않는 부분집합은 무시해도 무방합니다.
체계적인 항목집합 열거 방법
트랜잭션 t에 포함된 3-항목집합을 체계적으로 열거하는 방법을 살펴보겠습니다. 각 항목집합이 사전순(lexicographic order)으로 항목을 유지한다고 가정하면, 가장 작은 항목부터 먼저 정의하고 이후 더 큰 항목들을 순서대로 정의하는 방식으로 항목집합을 열거할 수 있습니다.
예를 들어 t = {1, 2, 3, 5, 6}인 경우, t에 포함된 모든 3-항목집합은 항목 1, 2 또는 3으로 시작해야 합니다. 항목 5나 6으로 시작하는 3-항목집합을 만드는 것은 불가능한데, 그 이유는 t에서 5 이상의 값을 가진 항목이 두 개뿐이기 때문입니다.
이러한 접두사(prefix) 구조는 트랜잭션에 포함된 항목집합을 일관되게 열거하는 방법을 보여줍니다. 즉, 가장 왼쪽 항목부터 가장 오른쪽 항목까지 한 항목씩 차례로 정의해 나가는 방식입니다.
열거된 각 3-항목집합이 기존 후보 항목집합과 일치하는지 확인할 수 있으며, 일치하는 후보가 있다면 해당 후보의 지원도 카운트를 증가시킵니다.
해시 트리를 활용한 효율적인 지원 계산
Apriori 알고리즘에서는 후보 항목집합을 여러 버킷(bucket)으로 나누어 해시 트리(hash tree)에 저장합니다. 지원 계산 과정에서 각 트랜잭션에 포함된 항목집합들 역시 적절한 버킷으로 해싱됩니다. 따라서 트랜잭션 내 각 항목집합을 모든 후보 항목집합과 비교하는 대신, 동일한 버킷에 속한 후보 항목집합과만 비교하면 되므로 탐색 범위가 크게 줄어듭니다.
트리의 각 내부 노드는 h(p) = p mod 3이라는 해시 함수를 사용하여 현재 노드의 어느 분기를 따라갈지 결정합니다. 예를 들어 항목 1, 4, 7은 3으로 나눈 나머지가 같기 때문에 동일한 분기(가장 왼쪽 분기)로 해싱됩니다. 모든 후보 항목집합은 최종적으로 해시 트리의 리프 노드(leaf node)에 저장됩니다.