什么是变色龙算法？

变色龙是一种层次聚类算法，它使用动态建模来决定簇对之间的相似性。它是基于对ROCK和CURE等两种层次聚类算法观察到的缺点而改进的。

ROCK及其相关设计强调簇的互连性，而忽略了关于簇接近性的数据。CURE及其相关设计考虑簇的接近性，但忽略了簇的互连性。在变色龙算法中，簇的相似性是根据簇内对象的连接程度和簇的接近程度来评估的。特别是，如果两个簇的互连性高且彼此靠近，则将它们合并。

它不基于静态的、用户提供的模型，可以自动适应被合并簇的内部特征。合并过程支持发现自然且均匀的簇，并且考虑到可以定义相似性函数，它适用于所有类型的数据。

变色龙算法需要k近邻图技术来构建稀疏图，其中图的每个顶点定义一个数据对象，如果一个对象属于另一个对象的k个最相似对象之一，则这两个顶点（对象）之间存在一条边。边的权重反映对象之间的相似性。

变色龙算法使用图划分算法将k近邻图划分为大量相对较小的子簇。它可以使用凝聚层次聚类算法，该算法基于子簇的相似性重复合并子簇。它可以确定最相似子簇对，同时考虑簇的互连性和接近性。

k近邻图动态地捕捉邻域的概念：对象的邻域半径由对象所驻留区域的密度决定。在密集区域，邻域表示较窄；在稀疏区域，邻域表示较宽。

这种影响导致比基于密度的算法（如DBSCAN，它使用全局邻域）更自然的簇。此外，区域的密度被记录为边的权重。特别是，密集区域的边的权重往往高于稀疏区域的边的权重。

图划分算法划分k近邻图，以使边割最小化。也就是说，将簇C细分为子簇Ci和Cj以最小化如果将C一分为二为Ci和Cj，则可能被切割的边的权重。边割表示为EC(Ci, Cj)，并确定簇Ci和Cj之间的绝对互连性。

更新于：2021年11月24日

4K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告