什么是变色龙？

Chameleon 是一种分层聚类算法，它使用动态建模来确定成对集群之间的相似性。它根据观察到的两种层次聚类算法（如 ROCK 和 CURE）的弱点进行了更改。

ROCK 和相关设计强调集群互连性，而忽略了有关集群邻近度的数据。CURE 和相关设计考虑了集群邻近性，而忽略了集群互连性。在 Chameleon 中，集群相似性的评估取决于集群内部对象的连接程度以及集群的接近程度。尤其是，如果两个集群的互连性高并且它们靠得很近，那么它们会被组合在一起。

它不基于静态的、用户提供的模型，可以自动适应正在组合的集群的内部特征。合并过程支持发现自然和同类簇，并用于所有类型的数据，因为可以定义相似性函数。

Chameleon需要k-nearest-neighbor graph技术来制作稀疏图，图中的每个顶点定义一个数据对象，如果一个对象在k个最相似的对象之间，则两个顶点（对象）之间存在一条边另一个。边缘被加权以反映对象之间的相似性。

Chameleon 使用图划分算法将 k-最近邻图划分为大量相对较小的子集群。它可以使用凝聚层次聚类算法，根据子聚类的相似性反复合并子聚类。它可以确定最相似的子集群对，它同时考虑了集群的互连性和紧密度。

k-nearest-neighbor graph 动态地捕捉邻域的趋近：对象的邻域半径由对象所在区域的密度决定。在密集区域中，邻域被狭窄地表示。在稀疏区域，它的代表更广泛。

与使用全球邻域的 DBSCAN 等基于密度的方法相比，这种影响会产生更自然的聚类。此外，该区域的密度被记录为边缘的权重。特别是，密集区域的边缘往往比稀疏区域的边缘权重。

图分区算法对 k-最近邻图进行分区，使得边缘切割更小。也就是说，簇 C 被细分为子簇 C _i和 C _{j ，}以最小化在 C 被二等分为 C _i和 C _{j 时}可以切割的边的权重。边缘切割表示为 EC (C _i , C _j )，并确定了集群 C _i和 C _j之间的绝对互连性。