Abstract: Spectral clustering algorithm can obtain a better graph cut criterion by introducing p-Laplacian operator. But the similarity matrix doesn't fully exploit the local information of the dataset in the algorithm. Simultaneously, the similarity measurement and data clustering are often conducted in two seperated steps, the learned data similarity may not be optimal one for data clustering and lead to the suboptimal results. Therefore, this paper proposes p-spectral clustering algorithm with the optimization of local similarity. The algorithm learns the data similarity matrix by assigning the adaptive and optimal neighbors for each data point based on the local distances. Meanwhile, the new rank constraint is imposed to the Laplacian matrix of the data similarity matrix, such that the connected components in the resulted similarity matrix are exactly equal to the cluster number. The experiments show that p-spectral clustering algorithm based on local similarity optimization can produce better clustering results.

Key words: p-Laplacian operator, local similarity, adaptive and optimal neighbors, rank constraint

摘要： 通过引入p-Laplacian算子，谱聚类算法得以获得较好的图切判据。但算法中的相似矩阵未能充分挖掘数据样本的局部结构信息，同时相似性的计算与数据样本的聚类是在两个不同的步骤中实现的，故得到的相似矩阵并不一定是最适合此聚类方法的，从而得不到最优的聚类结果。因此，提出了基于局部相似性优化的p-谱聚类算法。该算法通过数据样本的自适应和最优近邻之间的局部距离来优化相似性测度的方法，同时通过p-Laplacian矩阵的秩约束，可以得到对应无向图中连通分量的数目等于聚类数目。实验表明，基于局部相似性优化的p-谱聚类算法可以获得更好的聚类效果。

关键词: p-Laplacian算子, 局部相似性, 自适应和最优近邻, 秩约束