基于局部密度和测地距离的谱聚类

Spectral clustering based on local density and geodesic distance

传统根据K-近邻图计算测地距离的方法,虽然能够发现流形分布数据间的相似关系,但是当不同类的点存在粘连关系时,依此计算相似度时不能体现样本间的真实关系,从而无法有效聚类。针对传统测地距离计算相似度的方法不能有效处理粘连数据集的问题,提出了基于局部密度和测地距离的谱聚类方法。计算样本的局部密度,寻找每个样本点的最近高密度点,并选择边缘点和非边缘点;在边缘点和其最近高密度点之间构造边、非边缘点之间的K个近邻点构造边,依此计算测地距离和相似度并进行聚类。在人工数据集和UCI数据集上的实验表明,该算法在处理粘连数据集时有效提高了聚类准确率。

The traditional geodesic distance calculation method based on K-nearest neighbor graph can find the data relationshipson manifold.However,if there are adhesive points between different clusters,the similarity based on traditionalgeodesic distance can not effectively reflect the true relationships between points,which make it difficult to cluster thedatasets 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 pointis calculated to find the nearest high density point,and choose marginal points and non-marginal points.Then,the edgebetween the marginal point and its nearest high density point is created,and edges between the K-nearest neighbor pointsand 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 accuracywhen dealing with the adhesive datasets.