Abstract: For the problem that traditional Euclidean distance similarity measure cannot fully reflect the distribution characteristics of the complicated data structure,a clustering algorithm based on relative density and k-nearest neighbors over manifolds was proposed.The manifold distance which describes the global consistency and the k-nearest neighbors concept that shows local similarity and affinity were introduced.Based on above descriptions,firstly,the similarity between two objects is measured through the k-nearest neighbors similarity over manifolds.Secondly,the cluster under different densities is found by adapting the relative uniformity of the k-nearest neighbors.Lastly,the k-nearest neighbor pair constraint rule is designed to search the nearest neighbor chain which is composed of the k-nearest data points,in order to classify data objects and identify outliers.Experimental results show that compared with traditional k-means clustering algorithm and the improved k-means clustering algorithm by manifold distance, the algorithm can effectively deal with the clustering problem for complicated data structure and achieve better clustering effect on artificial data sets and UCI public data sets.

Key words: Manifold distance,k-nearest neighbors over manifolds,k-nearest neighbors similarity,Relative density