CLIQUE란 무엇인가?
CLIQUE는 고차원 데이터 공간에서 차원 증가(dimension-growth) 방식의 부분 공간 클러스터링을 위해 최초로 제안된 알고리즘입니다. 차원 증가 방식의 부분 공간 클러스터링에서는 클러스터링 과정이 1차원 부분 공간에서 시작하여 점차 더 높은 차원의 공간으로 확장되어 나갑니다.
CLIQUE는 각 차원을 격자(grid) 구조처럼 분할하고, 셀(cell)에 포함된 데이터 포인트의 수를 기준으로 해당 셀이 '밀집(dense)' 상태인지 여부를 판단합니다. 이러한 특성 때문에 CLIQUE는 밀도 기반 클러스터링과 격자 기반 클러스터링 기법이 통합된 형태로 볼 수 있습니다.
CLIQUE 클러스터링의 핵심 아이디어
CLIQUE 클러스터링 알고리즘의 기본 개념은 다음과 같습니다.
다차원 데이터 포인트로 구성된 대규모 데이터셋에서 데이터 영역은 일반적으로 데이터 포인트에 의해 균일하게 채워지지 않습니다. CLIQUE의 클러스터링은 공간(또는 단위) 안의 희소한 영역과 '혼잡한(crowded)' 영역을 식별함으로써 데이터셋의 전체적인 분포 패턴을 파악합니다.
어떤 단위(unit)에 포함된 전체 데이터 포인트의 비율이 입력 모델 매개변수로 설정된 임계값을 초과하면, 그 단위는 밀집된 것으로 간주됩니다. CLIQUE에서 하나의 클러스터는 서로 연결된 밀집 단위들이 이루는 최대 그룹으로 표현됩니다.
CLIQUE의 2단계 클러스터링 과정
CLIQUE는 두 단계에 걸쳐 다차원 클러스터링을 수행합니다.
1단계: 부분 공간 분할과 밀집 단위 식별
첫 번째 단계에서 CLIQUE는 d차원 데이터 영역을 서로 겹치지 않는 직사각형 단위로 분할한 뒤, 그중에서 밀집 단위를 식별합니다. 이 작업은 각 차원에 대해 1차원 단위로 먼저 수행됩니다.
탐색 대상이 될 후보 검색 공간의 식별은 연관 규칙 마이닝(association rule mining)에서 사용되는 Apriori 속성에 기반합니다. 일반적으로 이 속성은 탐색 영역 내 항목에 대한 사전 지식을 활용하여 불필요한 영역을 가지치기(pruning)할 수 있게 해줍니다.
CLIQUE에 적용되는 Apriori 속성은 다음과 같습니다. 어떤 k차원 단위가 밀집되어 있다면, 그 단위를 (k-1)차원 공간으로 투영(projection)한 결과 역시 밀집되어 있습니다. 다시 말해, k차원 후보 밀집 단위가 주어졌을 때 그 (k-1)차원 투영 단위들을 검사하여 밀집되지 않은 단위가 하나라도 발견되면, 해당 k차원 단위 역시 밀집될 수 없다고 판단할 수 있습니다.
이러한 원리를 통해 (k-1)차원 공간에서 발견된 밀집 단위들만으로 k차원 공간의 잠재적(후보) 밀집 단위를 생성할 수 있습니다. 그 결과 실제로 탐색해야 하는 영역은 원래 전체 영역보다 훨씬 작아지며, 탐색된 밀집 단위들을 검토하여 최종 클러스터를 결정하게 됩니다.
2단계: 클러스터의 최소 설명 생성
두 번째 단계에서 CLIQUE는 각 클러스터에 대한 최소 설명(minimal description)을 생성합니다. 각 클러스터에 대해 연결된 밀집 단위들의 집합을 덮는 최대 영역을 결정하고, 이를 바탕으로 각 클러스터의 최소 커버(minimal cover), 즉 논리적 설명을 도출합니다.
CLIQUE의 특징과 장점
CLIQUE는 고밀도 클러스터가 존재하는 가장 높은 차원의 부분 공간을 반드시 찾아냅니다. 또한 입력 객체의 순서에 민감하지 않으며, 특정한 정규(canonical) 데이터 분포를 가정하지 않습니다. 입력 데이터의 크기에 대해 선형적으로 확장되며, 데이터의 차원 수가 늘어나는 경우에도 우수한 확장성(scalability)을 보여준다는 점이 큰 강점입니다.