Chameleon: Hierarchical Clustering Using Dynamic Modeling

Presentation on theme: "Chameleon: Hierarchical Clustering Using Dynamic Modeling"— Presentation transcript:

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

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

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

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

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

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

7 相对近似性(RC) 相对近似性函数： :连接簇Ci和Cj的边的平均权重。
k-最近邻居图中，边的权重很好的表示了簇间接口层中数据项的相似度。 对孤立点和噪声不敏感。 优先合并簇间近似度与簇内近似度相近的簇。

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

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

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

11 对比试验（续） 变色龙算法的聚类结果（ k＝10，α＝2）

12 对比试验（续） CURE算法的聚类结果 25个簇 个簇 25个簇 个簇

13 对比试验（续） DBScan算法的聚类结果

14 总结 变色龙算法将互连性和近似性都大的簇合并。 可以发现高质量的任意形状的簇 问题
k-最近邻居图中k值的选取。 最小二等分的选取。 用户指定方式中阈值的选取。 在最坏情况下，高维数据的处理代价可能需要O(n2)的时间。

15 谢谢！