카멜레온(Chameleon)이란?
카멜레온(Chameleon)은 동적 모델링(dynamic modeling)을 활용하여 클러스터 쌍 간의 유사성을 판단하는 계층적 군집화(hierarchical clustering) 알고리즘입니다. 이 알고리즘은 ROCK과 CURE 같은 기존 계층적 군집화 기법들의 약점을 보완하기 위해 개발되었습니다.
ROCK과 CURE의 한계를 보완한 설계
ROCK 계열의 설계는 클러스터 간 상호 연결성(interconnectivity)을 강조하는 반면, 클러스터 간 근접성(proximity)에 관한 정보는 소홀히 다룹니다. 반면 CURE 계열은 근접성을 고려하지만 상호 연결성은 간과합니다.
카멜레온은 이 두 요소를 모두 반영합니다. 즉, 클러스터 내부 객체들이 얼마나 잘 연결되어 있는지와 클러스터 간 근접성을 함께 기준으로 유사성을 평가합니다. 특히 두 클러스터의 상호 연결성이 높고 서로 가까이 위치해 있을 때 병합이 이루어집니다.
정적 모델에 의존하지 않는 자동 적응
카멜레온은 사용자가 미리 제공하는 정적인(static) 모델에 의존하지 않으며, 병합되는 클러스터의 내부 특성에 자동으로 적응할 수 있습니다. 이러한 병합 과정은 자연스럽고 균질한(homogeneous) 클러스터의 발견을 지원하며, 유사도 함수(similarity function)를 정의할 수 있는 한 어떤 종류의 데이터에도 적용할 수 있습니다.
k-최근접 이웃 그래프 구축
카멜레온은 희소 그래프(sparse graph)를 생성하기 위해 k-최근접 이웃(k-nearest-neighbor) 그래프 기법을 사용합니다. 그래프의 각 정점(vertex)은 데이터 객체를 나타내며, 한 객체가 다른 객체의 k개 가장 유사한 객체 중 하나에 해당할 경우 두 정점 사이에 간선(edge)이 존재합니다. 각 간선에는 객체 간 유사도를 반영하는 가중치가 부여됩니다.
그래프 분할과 병합 과정
카멜레온은 그래프 분할(graph partitioning) 알고리즘을 사용하여 k-최근접 이웃 그래프를 수많은 비교적 작은 하위 클러스터(subcluster)로 나눕니다. 이후 응집형(agglomerative) 계층적 군집화 알고리즘을 적용하여 유사도를 기반으로 하위 클러스터를 반복적으로 병합합니다.
가장 유사한 하위 클러스터 쌍을 결정할 때, 카멜레온은 클러스터의 상호 연결성과 근접성을 모두 고려한다는 점이 핵심입니다.
동적 이웃 반경과 밀도 가중치
k-최근접 이웃 그래프는 이웃(neighborhood) 개념을 동적으로 포착합니다. 즉, 객체의 이웃 반경은 해당 객체가 속한 영역의 밀도에 따라 결정됩니다. 밀도가 높은 영역에서는 이웃 범위가 좁게 정의되고, 희소한 영역에서는 더 넓게 정의됩니다.
이러한 특성 덕분에 전역적(global) 이웃 개념을 사용하는 DBSCAN 같은 밀도 기반 방법보다 더 자연스러운 클러스터를 얻을 수 있습니다. 또한 영역의 밀도는 간선의 가중치로 기록되며, 특히 밀도가 높은 영역의 간선은 희소한 영역의 간선보다 큰 가중치를 갖는 경향이 있습니다.
엣지 컷 최소화 원리
그래프 분할 알고리즘은 k-최근접 이웃 그래프를 분할할 때 엣지 컷(edge cut)을 최소화하도록 작동합니다. 즉, 클러스터 C를 하위 클러스터 Ci와 Cj로 나눌 때, 분할로 인해 잘려야 하는 간선의 가중치 합을 최소화합니다.
엣지 컷은 EC(Ci, Cj)로 표시되며, 클러스터 Ci와 Cj 간의 절대적 상호 연결성(absolute interconnectivity)을 나타냅니다.