Abstract: 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 WSnnG. 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.

Key words: Weighted Shared nearest neighbors Graph (WSnnG), minimum half, network module evaluation function, structural equivalence similarity degree, cohesion measure

摘要： 针对Chameleon算法中采用距离函数度量数据点间的相似度,导致距离相近的两个点可能仅拥有很少的共同特征,最小二分实际操作困难,合并时需要人工指定阈值以及一旦合并完成后不能撤销的问题,对Chameleon算法进行改进,提出一种引入共享近邻加权图（WSnnG）的Chameleon算法。该算法以数据对象间的共享近邻数来衡量相似度,进一步构造WSnnG,再利用网络模块性评价函数指导最小二分,然后以结构等价相似度作为合并的依据,最后通过引入内聚度度量函数解决合并后不能撤销的问题。在UCI数据集及4个二维人造数据集上的实验结果表明,该算法在聚类精度和运行时间方面具有更好的效果。

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