연관 규칙 클러스터링 시스템이란?
연관 규칙 클러스터링 시스템(Association Rule Clustering System)은 대량의 데이터에서 유용한 연관 규칙을 효율적으로 도출하기 위한 방법론입니다. 이 시스템은 크게 빈닝(Binning)과 빈발 술어 집합 찾기(Finding Frequent Predicate Sets)라는 두 가지 핵심 단계로 구성됩니다.
1단계: 빈닝(Binning)
정량적 속성(quantitative attributes)은 해당 도메인을 나타내는 매우 넓은 범위의 값을 가질 수 있습니다. 예를 들어, 나이와 소득을 각각 축으로 하는 2차원 그리드를 상상해 보면, 나이의 모든 가능한 값이 한 축의 고유한 위치를 차지하고, 소득의 모든 가능한 값 역시 다른 축의 고유한 위치를 차지하게 됩니다.
이렇게 되면 그리드가 지나치게 커져 관리가 어렵습니다. 따라서 그리드를 관리 가능한 크기로 유지하기 위해, 정량적 속성의 영역을 구간(interval)으로 분할합니다. 이 구간들은 마이닝 단계에서 서로 결합될 수 있다는 점에서 강력한 장점을 가집니다. 이러한 분할 과정을 빈닝(binning)이라고 부르며, 이때 각 구간은 하나의 “빈(bin)”으로 취급됩니다.
세 가지 대표적인 빈닝 전략
동일 폭 빈닝(Equal-width binning) − 각 빈의 구간 크기가 모두 동일한 방식입니다. 구현이 간단하고 직관적이라는 장점이 있습니다.
동일 빈도 빈닝(Equal-frequency binning) − 각 빈에 거의 동일한 수의 튜플(tuple)이 할당되도록 구간을 나누는 방식입니다. 데이터가 치우쳐 있을 때 유용합니다.
클러스터링 기반 빈닝(Clustering-based binning) − 정량적 속성에 대해 클러스터링을 수행하여, 다양한 거리 측정 기준으로 판단했을 때 인접한 데이터 포인트들을 같은 빈으로 그룹화하는 방식입니다.
ARCS에서의 빈닝 적용
ARCS(An Association Rule Clustering System)는 동일 폭 빈닝을 사용하며, 각 정량적 속성에 대한 빈 크기는 사용자가 직접 입력합니다. 이후 두 정량적 속성의 가능한 모든 빈 조합에 대한 2차원 배열이 생성됩니다.
배열의 각 셀은 규칙 우변(right-hand side)에 위치한 범주형 속성의 각 클래스에 해당하는 카운트 분포(count distribution)를 담고 있습니다. 이러한 데이터 구조를 미리 구축해 두면 작업 관련 데이터를 단 한 번만 스캔하면 된다는 큰 장점이 있습니다. 또한 동일한 2차원 배열을 재사용하여, 같은 두 정량적 속성에 기반한 범주형 속성의 다양한 값에 대한 규칙들을 생성할 수 있습니다.
2단계: 빈발 술어 집합 찾기(Finding Frequent Predicate Sets)
모든 범주에 대한 카운트 분포를 포함하는 2차원 배열이 구축되면, 이를 스캔하여 최소 지지도(minimum support)와 최소 신뢰도(minimum confidence)를 동시에 만족하는 빈발 술어 집합(frequent predicate sets)을 발견합니다.
알고리즘은 그리드를 검사하면서 규칙들이 형성하는 직사각형 클러스터(rectangular clusters)를 탐색합니다. 이 과정에서 규칙 클러스터 내부에 등장하는 정량적 속성의 빈들은 서로 결합될 수 있으며, 이를 통해 정량적 속성의 동적 이산화(dynamic discretization)가 자연스럽게 이루어집니다.
직사각형 클러스터의 한계와 개선 방안
앞서 설명한 그리드 기반 방식은 원래의 연관 규칙들이 직사각형 영역으로 클러스터링될 수 있음을 보여줍니다. 다만 클러스터링을 수행하기 전에 스무딩(smoothing) 기법을 적용하여 데이터 속의 노이즈(noise)와 이상값(outlier)을 제거하는 것이 좋습니다. 그 이유는 직사각형 클러스터가 정보를 지나치게 단순화(oversimplify)할 수 있기 때문입니다.
이러한 한계를 극복하기 위해 더 일반적인 정량적 연관 규칙을 발견할 수 있는 비그리드 기반(non-grid-based) 접근법이 제안되었습니다. 이 방식에서는 여러 개의 정량적 속성과 범주형 속성이 규칙의 좌변이나 우변 어느 쪽에도 자유롭게 배치될 수 있습니다.
비그리드 기반 접근법에서는 정량적 속성을 동일 빈도 빈닝을 사용해 동적으로 분할하고, 이후 파티션들은 부분 완전성(partial completeness) 측정값에 기반하여 결합됩니다. 부분 완전성 지표는 파티셔닝 과정에서 손실되는 정보의 양을 정량화함으로써, 데이터 손실을 최소화하면서 적절한 수준의 분할을 유지하도록 도와줍니다.
마무리
연관 규칙 클러스터링 시스템은 빈닝을 통해 방대한 정량적 데이터를 효율적으로 압축하고, 2차원 배열 기반의 카운트 분포를 활용해 빈발 패턴을 신속히 찾아냅니다. ARCS의 그리드 기반 방식부터 비그리드 기반의 일반화된 접근법까지, 데이터의 특성과 분석 목적에 맞는 적절한 전략을 선택하는 것이 성공적인 연관 규칙 마이닝의 열쇠입니다.