关键词: [K]-近邻图, 测地距离, 局部密度, 相似度, 谱聚类

Abstract: The traditional geodesic distance calculation method based on [K]-nearest neighbor graph can find the data relationships on manifold. However, if there are adhesive points between different clusters, the similarity based on traditional geodesic distance can not effectively reflect the true relationships between points, which make it difficult to cluster the datasets effectively. Since the similarity based on traditional geodesic distance can not deal with adhesive datasets effectively, spectral clustering based on local density and geodesic distance is proposed. Firstly, the local density of each point is calculated to find the nearest high density point, and choose marginal points and non-marginal points. Then, the edge between the marginal point and its nearest high density point is created, and edges between the [K]-nearest neighbor points and non-marginal points are created as well. Finally, the geodesic distance and similarity can be calculated to perform clustering. Experiments on artificial and UCI datasets show that the proposed algorithm can improve the clustering accuracy when dealing with the adhesive datasets.

Key words: [K]-nearest neighbor graph, geodesic distance, local density, similarity, spectral clustering