引入共享近邻加权图的Chameleon算法  

Improved Chameleon algorithm using weighted nearest neighbors graph

作　　者：薛文娟[1,2] 刘培玉[1,2] 刘栋[1,2] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014

出　　处：《计算机应用》2012年第10期2884-2887,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60873247);山东省高新自主创新专项工程项目(2008ZZ28);山东省自然科学基金资助项目(ZR2009GZ007)

摘　　要：针对Chameleon算法中采用距离函数度量数据点间的相似度,导致距离相近的两个点可能仅拥有很少的共同特征,最小二分实际操作困难,合并时需要人工指定阈值以及一旦合并完成后不能撤销的问题,对Chameleon算法进行改进,提出一种引入共享近邻加权图(WSnnG)的Chameleon算法。该算法以数据对象间的共享近邻数来衡量相似度,进一步构造WSnnG,再利用网络模块性评价函数指导最小二分,然后以结构等价相似度作为合并的依据,最后通过引入内聚度度量函数解决合并后不能撤销的问题。在UCI数据集及4个二维人造数据集上的实验结果表明,该算法在聚类精度和运行时间方面具有更好的效果。For the Chameleon algorithm using distance function to measure the similarity of data points, resulting in that the two proximate points may only have a few common characteristics, minimum half has practical difficulties, the merger needs artificial specified threshold value, and can not be revoked once the merger is completed. Therefore, the authors improved Chameleon algorithm and proposed a new Chameleon algorithm using Weighted Shared nearest neighbors Graph （WSnnG）. Firstly, it measured the similarity by using the number of shared nearest neighbors, further constructed the WSnuG. Secondly, it resolved minimum half through the introduction of the network module evaluation function, then according to the structural equivalence similarity degree as a basis for merger. Finally, a new cohesion measure was discussed to solve problems that can not be revoked after the merger. The experimental results on UCI data sets and four two-dimensional artificial data sets show that the improved Chameleon algorithm using WSnnG has greatly improved in clustering accuracy and running time.

关 键 词：共享近邻加权图 最小二分 网络模块性评价函数 结构等价相似度 内聚度度量函数 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP309[自动化与计算机技术—控制科学与工程]