Chameleon: Hierarchical Clustering Using Dynamic Modeling ——变色龙:一个利用动态模型的层次聚类算法 梁敏 2003.5.26
内容简介 与以往算法的比较 变色龙算法 聚类步骤 稀疏图 相对互连性 相对近似性 聚类 对比试验 总结 2003.5.26
与以往算法的比较 以往算法的不足 变色龙算法同时考虑了互连性和近似性 只处理符合某静态模型的簇 忽略了不同簇间的信息 忽略互连性 互连性:簇间距离 较近数据对的多少。 忽略近似性 近似性:簇间数据对 的相似度(最近距离)。 变色龙算法同时考虑了互连性和近似性 2003.5.26
变色龙算法的聚类步骤 步骤 2003.5.26
稀疏图 节点表示数据项 边表示数据项的相似度 图的表示基于k-最近邻居图的方法 边表示边的一个节点v在另一个节点u的k个最相似点中。 好处: 距离很远的数据项完全不相连 边的权重代表了潜在的空间密度信息 在密集和稀疏区域的数据项都同样能建模 表示的稀疏便于使用有效的算法 2003.5.26
相对互连性(RI) 相对互连性函数: EC( Ci, Cj):连接簇Ci和Cj的所有边的权重和。 EC( Ci):把簇Ci划分为两个大致相等部分的最小等分线切断的所有边的权重和。 相对互连性能处理簇间形状不同和互连程度不同的问题。 2003.5.26
相对近似性(RC) 相对近似性函数: :连接簇Ci和Cj的边的平均权重。 k-最近邻居图中,边的权重很好的表示了簇间接口层中数据项的相似度。 对孤立点和噪声不敏感。 优先合并簇间近似度与簇内近似度相近的簇。 2003.5.26
聚类 第一阶段:得到子簇 原因:准确计算簇内的互连性和近似性要求簇足够数据项 用hMetis算法 hMetis算法根据最小化截断的边的权重和来分割k-最近邻居图 2003.5.26
聚类(续) 第二阶段:合并子簇 用户指定阈值(TRI和TRC) 函数定义 访问每个簇,计算它与临近簇的RI和RC。 合并RI和RC分别超过TRI和TRC的簇对。若满足条件的临近簇多于一个,合并具有最高绝对互连性的簇。 重复上两步,直到没有可合并的簇。 函数定义 度量函数:RI( Ci, Cj)× RC( Ci, Cj)α α>1,更重视相对近似性 α<1,更重视相对互连性 选择使该函数值最大的簇对合并。 2003.5.26
对比试验 变色龙算法与CURE和DBScan算法比较 2003.5.26
对比试验(续) 变色龙算法的聚类结果( k=10,α=2) 2003.5.26
对比试验(续) CURE算法的聚类结果 25个簇 11个簇 25个簇 8个簇 2003.5.26
对比试验(续) DBScan算法的聚类结果 2003.5.26
总结 变色龙算法将互连性和近似性都大的簇合并。 可以发现高质量的任意形状的簇 问题 k-最近邻居图中k值的选取。 最小二等分的选取。 用户指定方式中阈值的选取。 在最坏情况下,高维数据的处理代价可能需要O(n2)的时间。 2003.5.26
谢谢! 2003.5.26