Abstract:

The density peak clustering algorithm is a density based clustering algorithm. The shortcomings of the density peak clustering algorithm are sensitive to parameters and poor clustering results on complex manifold data sets. A novel density peak clustering algorithm is proposed in this paper, which is based on the natural reverse nearest neighbor structure. First of all, reverse nearest neighbor is introduced to calculate the local density of data objects. Then, the initial cluster centers are selected by combining the representative points and the density. Furthermore, the density adaptive distance is used to calculate the distance between the initial cluster centers, the decision graph is constructed on the initial cluster centers by using the local density calculated based on reverse nearest neighbor and the density adaptive distance, and the final cluster centers are selected according to the decision graph. Finally, the remaining data objects are assigned to the same cluster as their nearest initial cluster centers belong to. The experimental results show that the algorithm has better clustering effect and accuracy compared with the experimental comparison algorithms on the synthetic data sets and UCI real data sets, and it has greater advantages in dealing with complex manifold data sets.

Key words: natural neighbor, reverse nearest neighbor, representative points, local density, clustering

摘要：

密度峰值聚类算法是一种基于密度的聚类算法。针对密度峰值聚类算法存在的参数敏感和对复杂流形数据得到的聚类结果较差的缺陷，提出一种新的密度峰值聚类算法，该算法基于自然反向最近邻结构。首先，该算法引入反向最近邻计算数据对象的局部密度；其次，通过代表点和密度相结合的方式选取初始聚类中心；然后，应用密度自适应距离计算初始聚类中心之间的距离，利用基于反向最近邻计算出的局部密度和密度自适应距离在初始聚类中心上构建决策图，并通过决策图选择最终的聚类中心；最后，将剩余的数据对象分配到距离其最近的初始聚类中心所在的簇中。实验结果表明，该算法在合成数据集和UCI真实数据集上与实验对比算法相比较，具有较好的聚类效果和准确性，并且在处理复杂流形数据上的优越性较强。

关键词: 自然邻居, 反向最近邻, 代表点, 局部密度, 聚类