카멜레온은 동적 모델링을 사용하여 클러스터 쌍 간의 유사성을 결정하는 계층적 클러스터링 알고리즘입니다. ROCK 및 CURE와 같은 두 가지 계층적 클러스터링 알고리즘의 관찰된 약점을 기반으로 변경되었습니다.
ROCK 및 관련 디자인은 클러스터 근접성에 관한 데이터를 무시하면서 클러스터 상호 연결성을 강조합니다. CURE 및 관련 설계는 클러스터 근접성을 고려하지만 클러스터 상호 연결성은 무시합니다. 카멜레온에서 클러스터 유사성은 클러스터 내부의 객체가 얼마나 잘 연결되어 있는지와 클러스터의 근접성에 따라 평가됩니다. 특히, 두 클러스터는 상호 연결성이 높고 서로 가까울 경우 결합됩니다.
정적 사용자 제공 모델을 기반으로 하지 않으며 결합되는 클러스터의 내부 기능에 자동으로 적응할 수 있습니다. 병합 과정은 자연 군집과 동종 군집의 발견을 지원하며, 유사성 함수를 정의할 수 있다는 점을 고려하여 모든 유형의 데이터에 사용됩니다.
카멜레온은 희소 그래프를 만들기 위해 k-최근접이웃 그래프 기술이 필요합니다. 여기서 그래프의 각 꼭짓점은 데이터 개체를 정의하고 한 개체가 사이에 있으면 두 꼭짓점(객체) 사이에 간선이 존재합니다. 다른 것의 k-가장 유사한 객체. 가장자리는 개체 간의 유사성을 반영하도록 가중치가 부여됩니다.
카멜레온은 그래프 분할 알고리즘을 사용하여 k-최근접 이웃 그래프를 다수의 비교적 작은 하위 클러스터로 분할합니다. 유사성을 기반으로 하위 클러스터를 반복적으로 병합하는 응집 계층적 클러스터링 알고리즘을 사용할 수 있습니다. 가장 유사한 하위 클러스터의 쌍을 결정할 수 있으며 클러스터의 근접성과 상호 연결성을 모두 고려합니다.
k-최근접 이웃 그래프는 이웃의 접근 방식을 동적으로 캡처합니다. 물체의 이웃 반경은 물체가 있는 영역의 밀도에 의해 결정됩니다. 밀집된 지역에서 이웃은 좁게 표현됩니다. 희소 영역에서는 더 광범위하게 나타납니다.
이 영향은 대신 전 세계적인 이웃을 사용하는 DBSCAN과 같은 밀도 기반 방법과 비교할 때 보다 자연스러운 클러스터를 생성합니다. 또한 영역의 밀도는 가장자리의 가중치로 기록됩니다. 특히 조밀한 영역의 가장자리는 희소 영역의 가장자리보다 무게가 더 나가는 경향이 있습니다.
그래프 분할 알고리즘은 k-최근접 이웃 그래프를 분할하여 가장자리 절단을 더 작게 만듭니다. 즉, 클러스터 C는 하위 클러스터Ci로 세분화됩니다. 및 Cj C를 Ci 로 이등분해야 절단될 수 있는 모서리의 무게를 최소화하기 위해 및 Cj . 에지 컷은 EC(Ci , Cj ) 클러스터 Ci 간의 절대 상호 연결성을 결정합니다. 및 Cj .