네거티브 패턴 마이닝 기법이란?
데이터 마이닝에서 드물게 나타나는 패턴(infrequent pattern)을 추출하기 위해 개발된 초기 기법은 모든 아이템을 대칭 이진 변수(symmetric binary variable)로 간주합니다. 이 접근법은 트랜잭션 데이터를 부정 아이템(negative item)으로 보강하여 이진화하는 방식으로 진행됩니다.
원본 데이터에 부정 아이템을 추가하면 각 트랜잭션은 긍정 아이템과 부정 아이템을 모두 포함하게 됩니다. 여기에 Apriori와 같은 기존 빈발 항목집합(frequent itemset) 생성 알고리즘을 적용하면 일부 네거티브 항목집합(negative itemset)을 도출해낼 수 있습니다.
대칭 이진 가정의 한계
다만 이러한 접근이 가능하려면 일부 변수만 대칭 이진 변수로 다루어야 한다는 전제가 필요합니다. 즉, 소수의 아이템 부정(negation)만을 포함하는 네거티브 패턴에 대해서만 유효합니다. 만약 모든 아이템을 대칭 이진 변수로 취급하면 문제는 계산적으로 매우 어려워지는데, 그 이유는 다음과 같습니다.
1. 탐색 공간의 급격한 확장
각 아이템에 해당하는 부정 아이템을 추가하면 아이템 수가 두 배로 늘어납니다. 원본 데이터셋의 아이템 수를 d라 할 때, 탐색해야 할 항목집합 격자(lattice)의 크기는 2d가 아니라 그보다 훨씬 더 커지게 됩니다.
2. 지지도 기반 가지치기의 실효성 상실
부정 아이템이 추가되면 지지도(support) 기반 가지치기(pruning)는 더 이상 효율적으로 작동하지 않습니다. 임의의 변수 x에 대해 x 또는 x' 중 하나는 반드시 50% 이상의 지지도를 갖기 때문입니다. 따라서 지지도 임계값을 50%로 높게 설정하더라도 전체 아이템의 절반이 빈발(frequent) 상태가 됩니다.
임계값이 50%보다 낮아지면 빈발 아이템과 이들을 포함하는 항목집합이 크게 늘어납니다. Apriori가 채택한 지지도 기반 가지치기는 대부분의 항목집합 지지도가 낮을 때만 효과적인데, 이 조건이 깨지면서 빈발 항목집합의 수가 기하급수적으로 증가합니다.
3. 트랜잭션 폭의 증가
부정 아이템을 추가하면 각 트랜잭션의 폭(width)도 함께 늘어납니다. 원본 데이터셋에 d개의 아이템이 있다고 가정해 봅시다. 장바구니 분석(market basket) 데이터처럼 희소(sparse)한 데이터셋에서는 각 트랜잭션의 실제 폭이 d보다 훨씬 작은 경우가 일반적입니다.
따라서 최대 트랜잭션 폭 wmax에 의해 제한되는 빈발 항목집합의 최대 크기도 상대적으로 작게 유지됩니다. 그러나 부정 아이템이 포함되면 트랜잭션의 폭은 d까지 확대됩니다. 어떤 아이템은 트랜잭션에 존재하거나 존재하지 않거나 둘 중 하나이기 때문입니다.
최대 트랜잭션 폭이 wmax에서 d로 커지면 빈발 항목집합의 수가 급격히 폭증합니다. 결국 기존 알고리즘들은 규모가 큰 데이터셋에 적용될 때 성능 저하 또는 실패에 직면하게 됩니다.
대안: 긍정 아이템 지지도 기반 계산
앞서 언급한 무차별 대입(brute-force) 방식은 방대한 수의 긍정 및 부정 패턴에 대한 지지도를 일일이 계산해야 하므로 계산 비용이 매우 큽니다. 이를 해결하기 위한 또 다른 접근법은 데이터셋을 부정 아이템으로 보강하는 대신, 연관된 긍정 아이템들의 지지도를 활용해 네거티브 항목집합의 지지도를 간접적으로 산출하는 것입니다. 이 방법은 탐색 공간을 크게 줄여 계산 효율성을 개선할 수 있습니다.