Optimized Density Peak Clustering Algorithm by Natural Reverse Nearest Neighbor

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.

Keywords

• natural neighbor
• reverse nearest neighbor
• representative points
• local density
• clustering