基于消息传递的谱聚类算法

Spectral Clustering Algorithm Based on Message Passing

谱聚类将数据聚类问题转化成图划分问题,通过寻找最优的子图,对数据点进行聚类。谱聚类的关键是构造合适的相似矩阵,将数据集的内在结构真实地描述出来。针对传统的谱聚类算法采用高斯核函数来构造相似矩阵时对尺度参数的选择很敏感,而且在聚类阶段需要随机确定初始的聚类中心,聚类性能也不稳定等问题,本文提出了基于消息传递的谱聚类算法。该算法采用密度自适应的相似性度量方法,可以更好地描述数据点之间的关系,然后利用近邻传播(Affinity propagation,AP)聚类中“消息传递”机制获得高质量的聚类中心,提高了谱聚类算法的性能。实验表明,新算法可以有效地处理多尺度数据集的聚类问题,其聚类性能非常稳定,聚类质量也优于传统的谱聚类算法和k means算法。

Spectral clustering transforms data clustering problem into a graph partitioning problem and classifies data points by finding the optimal sub-graphs.The key to spectral clustering is constructing a suitable similarity matrix,which can truly describe the intrinsic structure of the dataset.However,traditional spectral clustering algorithms adopt Gaussian kernel function to construct the similarity matrix,which results in their sensitivity of selection for scale parameter.In addition,the initial cluster centers need randomly determing at the clustering stage and the clustering performance is not stable.The paper presents an algorithm based on message passing.The algorithm uses a density adaptive similarity measure,which can well describe the relations between data points,and it can obtain high-quality cluster centers through message passing mechanism in affinity propagation(AP)clustering.Moreover,the performance of clustering is optimized by the method.Experiments show that the proposed algorithm can effectively deal with the clustering problem of multi-scale datasets.Its clustering performance is very stable,and the clustering quality is better than traditional spectral clustering algorithm and k-means algorithm.