다단계 연관 규칙 마이닝이란?
다단계(multilevel) 연관 규칙 마이닝은 지지도-신뢰도(support-confidence) 프레임워크를 기반으로 수행됩니다. 이 접근 방식은 하향식(top-down) 전략을 사용하는데, 개념 계층(concept hierarchy)의 가장 높은 수준(수준 1)에서 빈발 항목집합의 개수를 집계하기 시작하여, 점차 더 구체적인 하위 수준으로 내려가면서 Apriori 알고리즘으로 더 이상 빈발 항목집합을 찾을 수 없을 때까지 반복합니다.
데이터 일반화와 개념 계층
데이터는 저수준 개념을 개념 계층의 상위 개념 또는 조상(ancestor) 개념으로 대체함으로써 일반화할 수 있습니다. 개념 계층은 루트(root)가 작업 관련 데이터(task-relevant data)인 트리 구조로 표현되며, 계층의 각 노드는 검토된 항목 또는 항목집합을 나타냅니다.
대표적인 응용 분야: 장바구니 분석
다단계 연관 규칙의 대표적인 응용 분야는 장바구니 분석(market basket analysis)입니다. 이는 고객의 구매 습관을 파악하기 위해 함께 자주 구매되는 항목들의 집합을 찾는 과정으로, 앞서 설명한 개념 계층 구조 안에서 표현됩니다.
계층 인코딩 트랜잭션 테이블
다단계 데이터베이스를 다룰 때는 원래의 트랜잭션 테이블 대신 계층 정보가 인코딩된(hierarchy-encoded) 트랜잭션 테이블이 필요합니다. 예를 들어 전체 항목이 아니라 '식품'처럼 특정 부분에만 관심이 있는 경우에 유용합니다. 관심 영역에 해당하는 데이터만 먼저 수집한 뒤, 그 작업 관련 집합 위에서 반복적으로 분석을 수행할 수 있기 때문입니다. 이렇게 하면 트랜잭션 테이블의 각 항목은 숫자의 시퀀스 형태로 인코딩됩니다.
최소 지지도 설정 방식별 탐색 전략
어떤 추상화 수준에서든 빈발 항목집합을 찾는 방법에는 여러 가지가 있으며, 대표적으로 '모든 수준에 동일한 최소 지지도 적용', '하위 수준에 감소된 최소 지지도 적용', '수준별 독립 탐색' 방식이 사용됩니다.
1. 모든 수준에 동일한 최소 지지도 적용
균일한(uniform) 최소 지지도 임계값을 사용하면 탐색 절차가 크게 단순해집니다. 여기서는 '조상이 자손의 상위집합(superset)'이라는 지식을 활용한 최적화 기법을 적용할 수 있습니다. 즉, 어떤 항목의 조상이 최소 지지도를 만족하지 않으면, 그 항목을 포함하는 항목집합은 아예 검사하지 않고 건너뛰는 것입니다.
다만 이 방식의 주요 단점은, 추상화 수준이 낮은 항목들은 높은 수준의 항목들보다 발생 빈도가 낮은 경우가 많다는 점입니다. 따라서 상위 수준에 맞춘 임계값은 하위 수준의 의미 있는 패턴을 놓치게 만들 수 있습니다.
2. 하위 수준에 감소된 최소 지지도 적용
각 추상화 수준마다 고유한 최소 지지도 임계값을 두는 방식입니다. 추상화 수준이 낮아질수록 임계값도 작아집니다. 감소된 지지도로 다단계 연관 규칙을 마이닝할 때의 탐색 범주는 다음과 같습니다.
수준별 독립(level-by-level independent): 완전한 폭 우선(full breadth) 탐색 방식으로, 빈발 항목집합에 대한 배경지식을 가지치기(pruning)에 활용합니다. 부모 노드가 빈발한지 여부와 관계없이 각 노드를 모두 검사합니다.
단일 항목 기반 수준 간 필터링(level-cross filtering by single item): i번째 수준의 어떤 항목은, 그것의 (i-1)번째 수준 부모 노드가 빈발한 경우에 한해서만 검사됩니다.
k-항목집합 기반 수준 간 필터링(level-cross filtering by k-itemset): i번째 수준의 어떤 항목집합은, 그것에 대응하는 (i-1)번째 수준의 k-항목집합 부모가 빈발한 경우에 한해서만 검사됩니다.
마무리
정리하면, 다단계 연관 규칙 마이닝은 개념 계층을 따라 하향식으로 빈발 패턴을 탐색하는 기법으로, 최소 지지도 임계값을 수준별로 어떻게 설정하느냐에 따라 탐색 효율과 발견되는 패턴의 품질이 달라집니다. 실무에서는 데이터의 특성과 분석 목적에 맞게 균일 지지도 방식과 감소 지지도 방식을 적절히 선택하는 것이 중요합니다.