Abstract: Based on existing distance metrics and the traditional spectral clustering algorithm, this paper proposes a new spectral clustering based on effective distance (SCED). Specifically, the proposed SCED algorithm uses effective distance to replace conventional Euclidean distance, by considering global properties of data that are reflected by sparse reconstruction coefficients. In effective distance, the similarity of a sample pair is evaluated by using not only the distance between these two samples, but also distances between one specific sample and other related samples. Sparse reconstruction coefficients are employed to reflect such global relationship among samples. The experimental results on ten UCI benchmark datasets demonstrate the efficiency of the proposed SCED algorithm.

Key words: spectral clustering, effective distance, distance metric

摘要： 在现有多种距离度量和传统谱聚类算法的基础上，提出了一种新的基于有效距离的谱聚类算法（spectral clustering based on effective distance，SCED）。SCED算法通过稀疏重构系数来构建样本与样本之间的有效距离，从而代替传统谱聚类算法中的欧氏距离，进行样本之间的相似度评估。与传统距离度量相比，有效距离不仅利用了样本对之间的距离信息，同时考虑了目标样本与其他所有相关样本之间的距离信息，因而该距离度量具有全局特性。在UCI标准数据集上的实验结果表明，SCED算法能有效提高聚类效果。

关键词: 谱聚类, 有效距离, 距离度量