Abstract:

Density Peak Clustering(DPC) is widely used in many fields because of its simplicity and high efficiency.However,it has two disadvantages:① It is difficult to identify the real clustering center in the decision graph provided by DPC for data sets with an uneven cluster density and imbalance;② There exists a "chain effect" where a misallocation of the points with the highest density in a region will result in all points within the region pointing to the same false cluster.In view of these two deficiencies,a new concept of Natural Neighbor(NaN) is introduced,and a density peak clustering algorithm based on the natural neighbor(DPC-NaN) is proposed which uses the new natural neighborhood density to identify the noise points,selects the initial preclustering center point,and allocates the non-noise points according to the density peak method to get the preclustering.By determining the boundary points and merging radius of the preclustering,the results of the preclustering can be adaptively merged into the final clustering.The proposed algorithm eliminates the need for manual parameter presetting and alleviates the problem of "chain effect".Experimental results show that compared with the correlation clustering algorithm,the proposed algorithm can obtain better clustering results on typical data sets and perform well in image segmentation.

Key words: clustering, density peak clustering, natural neighbor, image segmentation