Clustering Algorithm for Constructing Connected Graphs with Reverse Nearest Neighbors

Abstract

The development of big data era makes the application of clustering algorithms more and more widespread, but most current clustering algorithms are sensitive to noisy data and cannot identify datasets with complex structures such as non-convex shapes. To address this problem, a clustering algorithm for constructing connected graph with reverse nearest neighbor is proposed. Firstly, a density calculation is designed to obtain the density of data points, and a dynamic noise discriminator is constructed to denoise the data so as to weaken the effect of noise on the clustering process. Secondly, considering that reverse neighbors better reflect the connection between data points and surrounding points, a clustering method is designed to construct reverse nearest neighbor connectivity graphs for the denoised data to identify data structure information within clusters, and to merge clusters using a given number of clusters. Finally, when classifying the noise points into clusters, considering that only classifying them into the closest clusters may lead to inaccurate classification results, a noise classification method is designed to take the density information into account to obtain the final clustering results. To verify the effectiveness of the proposed method, the clustering results of proposed algorithm are compared with those of five other clustering algorithms, and the external evaluation metrics Acc (cluster accuracy) and NMI (normalized mutual information) are used to evaluate the clustering results. Experimental results show that the clustering results of the proposed algorithm are better than those of comparison algorithms on the noisy datasets with complex structures such as non-convex shapes.

Keywords

• denoising; reverse neighbors; reverse nearest neighbor connectivity graph; clustering