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

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