Chameleon là một thuật toán phân cụm phân cấp sử dụng mô hình động để quyết định sự giống nhau giữa các cặp cụm. Nó đã được thay đổi dựa trên những điểm yếu được quan sát thấy của hai thuật toán phân cụm phân cấp như ROCK và CURE.
ROCK và các thiết kế liên quan nhấn mạnh tính liên kết giữa các cụm trong khi bỏ qua dữ liệu liên quan đến sự gần gũi của cụm. CURE và thiết kế liên quan xem xét sự gần gũi của cụm nhưng bỏ qua tính liên kết giữa các cụm. Trong Chameleon, độ giống nhau của cụm được đánh giá tùy thuộc vào cách các đối tượng được kết nối tốt bên trong một cụm và mức độ gần nhau của các cụm. Đặc biệt, hai cụm được kết hợp nếu tính liên kết của chúng cao và chúng ở gần nhau.
Nó không dựa trên mô hình tĩnh, do người dùng cung cấp và có thể tự động thích ứng với các tính năng bên trong của các cụm được kết hợp. Quá trình hợp nhất hỗ trợ việc phát hiện ra các cụm tự nhiên và đồng nhất và được sử dụng cho tất cả các loại dữ liệu xem xét một chức năng tương tự có thể được xác định.
Chameleon cần kỹ thuật đồ thị k-gần nhất-lân cận để tạo một biểu đồ thưa thớt, trong đó mỗi đỉnh của biểu đồ xác định một đối tượng dữ liệu và tồn tại một edgeamong hai đỉnh (đối tượng) nếu một đối tượng nằm giữa k-đối tượng giống nhất của cái khác. Các cạnh được cân bằng để phản ánh sự giống nhau giữa các đối tượng.
Chameleon sử dụng thuật toán phân vùng đồ thị để phân vùng k-gần nhất-lân cận thành một số lượng lớn các cụm con tương đối nhỏ. Nó có thể sử dụng thuật toán phân cụm kết hợp phân cụm liên tục hợp nhất các nhóm con dựa trên tính tương đồng của chúng. Nó có thể xác định các cặp của hầu hết các cụm con tương tự nhau, nó tính đến cả tính liên kết lẫn nhau cũng như sự gần gũi của các cụm.
Đồ thị k-gần nhất-láng giềng nắm bắt động cách tiếp cận của vùng lân cận:bán kính lân cận của một đối tượng được quyết định bởi mật độ của vùng mà đối tượng đó cư trú. Trong một khu vực đông đúc, khu vực lân cận được thể hiện trong phạm vi hẹp. Trong vùng asparse, nó được đại diện rộng rãi hơn.
Ảnh hưởng này dẫn đến nhiều cụm tự nhiên hơn, so với các phương thức dựa trên mật độ như DBSCAN thay vào đó sử dụng một vùng lân cận trên toàn thế giới. Hơn nữa, mật độ của vùng được ghi lại dưới dạng trọng lượng của các cạnh. Đặc biệt, các cạnh của vùng dày đặc có xu hướng nặng hơn vùng thưa.
Thuật toán phân vùng đồ thị phân vùng đồ thị k-gần nhất-lân cận sao cho nó làm cho đường cắt cạnh nhỏ hơn. Nghĩa là, cụm C được chia thành các cụm conC i và C j để giảm thiểu trọng lượng của các cạnh có thể bị cắt nên C được chia đôi thành C i và C j . Cắt cạnh được biểu thị EC (C i , C j ) và xác định tính liên kết tuyệt đối giữa cụm C i và C j .