基于相对密度和流形上k近邻的聚类算法

Clustering Algorithm Based on Relative Density and k-nearest Neighbors over Manifolds

针对传统的基于欧氏距离的相似性度量不能完全反映复杂结构的数据分布特性的问题,提出了一种基于相对密度和流形上k近邻的聚类算法。基于能描述全局一致性信息的流形距离,及可体现局部相似性和紧密度的k近邻概念,通过流形上k近邻相似度度量数据对象间的相似性,采用k近邻的相对紧密度发现不同密度下的类簇,设计近邻点对约束规则搜寻k近邻点对构成的近邻链,归类数据对象及识别离群点。与标准k-means算法、流形距离改进的k-means算法进行了性能比较,在人工数据集和UCI数据集上的仿真实验结果均表明,该算法能有效地处理复杂结构的数据聚类问题,且聚类效果更好。

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.