文档介绍：Chameleon: Hierarchical Clustering Using Dynamic Modeling
——变色龙:一个利用动态模型的层次聚类算法
梁敏

内容简介
与以往算法的比较
变色龙算法
聚类步骤
稀疏图
相对互连性
相对近似性
聚类
对比试验
总结

与以往算法的比较
以往算法的不足
只处理符合某静态模型的簇
忽略了不同簇间的信息
忽略互连性
互连性:簇间距离
较近数据对的多少。
忽略近似性
近似性:簇间数据对
的相似度(最近距离)。
变色龙算法同时考虑了互连性和近似性

变色龙算法的聚类步骤
步骤

稀疏图
节点表示数据项
边表示数据项的相似度
图的表示基于k-最近邻居图的方法
节点表示数据项
边表示边的一个节点v在另一个节点u的k个最相似点中。
好处:
距离很远的数据项完全不相连
边的权重代表了潜在的空间密度信息
在密集和稀疏区域的数据项都同样能建模
表示的稀疏便于使用有效的算法

相对互连性(RI)
相对互连性函数:
EC( Ci, Cj):连接簇Ci和Cj的所有边的权重和。
EC( Ci):把簇Ci划分为两个大致相等部分的最小等分线切断的所有边的权重和。
相对互连性能处理簇间形状不同和互连程度不同的问题。

相对近似性(RC)
相对近似性函数:
:连接簇Ci和Cj的边的平均权重。
:把簇Ci划分为两个大致相等部分的最小等分线切断的所有边的平均权重。
k-最近邻居图中,边的权重很好的表示了簇间接口层中数据项的相似度。
对孤立点和噪声不敏感。
优先合并簇间近似度与簇内近似度相近的簇。

聚类
第一阶段:得到子簇
原因:准确计算簇内的互连性和近似性要求簇足够数据项
用hMetis算法
hMetis算法根据最小化截断的边的权重和来分割k-最近邻居图

聚类(续)
第二阶段:合并子簇
用户指定阈值(TRI和TRC)
访问每个簇,计算它与临近簇的RI和RC。
合并RI和RC分别超过TRI和TRC的簇对。若满足条件的临近簇多于一个,合并具有最高绝对互连性的簇。
重复上两步,直到没有可合并的簇。
函数定义
度量函数:RI( Ci, Cj)× RC( Ci, Cj)α
α>1,更重视相对近似性
α<1,更重视相对互连性
选择使该函数值最大的簇对合并。

对比试验
变色龙算法与CURE和DBScan算法比较