닫힌 빈번 항목집합 마이닝의 기본 접근법
가장 단순한(naïve) 방법은 전체 빈번 항목집합을 모두 추출한 뒤, 이미 발견된 빈번 항목집합의 진부분집합(proper subset)이면서 동일한 지지도를 가지는 항목집합들을 제거하는 것입니다.
그러나 이 방식은 길이 100짜리 빈번 항목집합 하나를 얻기 위해서도 2100−1개에 달하는 빈번 항목집합을 모두 생성해야 하며, 그 후에야 중복 항목집합 제거 작업을 시작할 수 있습니다. 따라서 권장되는 기법은 마이닝 단계에서 곧바로 닫힌 빈번 항목집합을 탐색하는 것입니다. 이를 위해서는 마이닝 과정에서 해당 항목집합이 닫힌 항목집합임을 확인하는 즉시 탐색 공간을 가지치기(pruning)해야 하며, 대표적인 가지치기 전략은 다음과 같습니다.
1. 아이템 병합(Item Merging)
빈번 항목집합 X를 포함하는 모든 트랜잭션이 항목집합 Y도 포함하되, Y의 진상위집합은 포함하지 않는다면 X∪Y는 빈번 닫힌 항목집합을 형성합니다. 따라서 X는 포함하지만 Y는 포함하지 않는 항목집합을 추가로 탐색할 필요가 없습니다.
2. 부분항목집합 가지치기(Sub-itemset Pruning)
빈번 항목집합 X가 이미 발견된 빈번 닫힌 항목집합 Y의 진부분집합이고 support_count(X) = support_count(Y)라면, X와 집합 열거 트리(set enumeration tree)에서 X의 모든 후손들은 빈번 닫힌 항목집합일 수 없으므로 가지치기할 수 있습니다.
3. 아이템 스킵(Item Skipping)
닫힌 항목집합의 깊이 우선(depth-first) 마이닝에서는 각 단계마다 헤더 테이블과 투영 데이터베이스에 연결된 접두어 항목집합 X가 존재할 수 있습니다. 어떤 지역적 빈번 아이템 p가 여러 단계의 여러 헤더 테이블에서 동일한 지지도를 가진다면, 더 상위 단계의 헤더 테이블에서 p를 안전하게 제거할 수 있습니다.
폐쇄성 검사(Closure Checking)
새로운 빈번 항목집합이 발견될 때마다 다음 두 가지 폐쇄성 검사를 수행해야 합니다.
- 상위집합 검사(Superset Checking) − 새로 발견된 빈번 항목집합이, 동일한 지지도를 가지는 기존 닫힌 항목집합의 상위집합인지 검사합니다.
- 하위집합 검사(Subset Checking) − 새로 발견된 항목집합이, 동일한 지지도를 가지는 기존 닫힌 항목집합의 하위집합인지 검사합니다.
효율적인 구현 방법
분할 정복(divide-and-conquer) 구조 하에서 아이템 병합 가지치기를 적용하면 상위집합 검사가 자연스럽게 내장되므로, 이를 명시적으로 구현할 필요가 없습니다. 빈번 항목집합 X∪Y가 X보다 나중에 발견되면서 X와 동일한 지지도를 가진다면, X∪Y는 반드시 X의 투영 데이터베이스 안에 존재했어야 하고, 아이템 병합 과정에서 이미 생성되었을 것이기 때문입니다.
반면 하위집합 검사를 지원하기 위해서는 압축 패턴 트리(compressed pattern-tree)를 구축하여 마이닝된 닫힌 항목집합들의 집합을 관리할 수 있습니다. 이 패턴 트리는 FP-tree와 메커니즘이 유사하지만, 발견된 모든 닫힌 항목집합이 해당 트리의 가지에 명시적으로 저장된다는 점이 다릅니다.