Abstract: A hierarchical clustering algorithm based on density-sensitive distance which combined with Affinity Propagation（AP） algorithm and spectral clustering algorithm is proposed. Some “possible exemplars” are selected in the datasets by considering density-sensitive distance as similarity measure and repeatedly using AP algorithm；Applying the spectral clustering algorithm in the “possible exemplars”, the “final exemplars” are obtained; Each data points are assigned through the labels of their corresponding representative exemplars. Experimental results demonstrate that the algorithm outperforms the original AP algorithm and spectral clustering algorithm in terms of speed, memory usage, and clustering error rate.

Key words: affinity propagation, spectral clustering, density-sensitive distance, hierarchical

摘要： 以密度敏感距离作为相似性测度，结合近邻传播聚类算法和谱聚类算法，提出了一种密度敏感的层次化聚类算法。算法以密度敏感距离为相似度，多次应用近邻传播算法在数据集中选取一些“可能的类代表点”；用谱聚类算法将“可能的类代表点”再聚类得到“最终的类代表点”；每个数据点根据其类代表点的类标签信息找到自己的类标签。实验结果表明，该算法在处理时间、内存占用率和聚类错误率上都优于传统的近邻传播算法和谱聚类算法。

关键词: 近邻传播, 谱聚类, 密度敏感距离, 层次化