Structured Doubly Stochastic Matrix for Graph Based Clustering: Structured Doubly Stochastic Matrix
Structured Doubly Stochastic Matrix for Graph Based Clustering: Structured Doubly Stochastic Matrix
复制标题
DOI：
10.1145/2939672.2939805
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Xiaoqian Wang;F. Nie;Heng Huang
中科院分区：
文献类型：
--
作者：
Xiaoqian Wang;F. Nie;Heng Huang
聚类作为最重要的机器学习课题之一，已被广泛应用于各个领域。它在科学研究和工业实践中的广泛应用在当今时代引起了高度重视。聚类方法有很多种，其中基于图的基于亲和矩阵的聚类方法得到了很大的重视。近年来的研究工作利用双随机矩阵对输入亲和矩阵进行归一化，增强了基于图的聚类模型。虽然双随机矩阵可以提高聚类性能，但双随机矩阵中的聚类结构并不像预期的那样清晰。因此，需要后处理步骤来提取最终的聚类结果，这可能不是最优的。为了解决这一问题，本文提出了一种新的凸模型，通过对图拉普拉斯矩阵施加低秩约束来学习结构化双随机矩阵。本文提出的结构化双随机矩阵可以明确地揭示聚类结构，并对成对数据点的连接概率进行编码，从而提高聚类结果。推导出一种有效的优化算法来求解我们的新目标。此外，我们还提供了理论讨论，当输入不同时，我们的方法分别与K-means和谱图切割模型具有有趣的联系。我们在合成和基准数据集上进行了实验，以验证我们提出的方法的性能。实证结果表明，我们的模型为更好地解决k -均值聚类问题提供了一种方法。通过使用我们的模型提供的聚类指标作为初始化，K-means收敛到更小的目标函数值，聚类性能更好。此外，我们还将该模型的聚类性能与谱聚类和相关的双随机模型进行了比较。在所有数据集上，我们的方法的性能与相关方法相同或更好。
As one of the most significant machine learning topics, clustering has been extensively employed in various kinds of area. Its prevalent application in scientific research as well as industrial practice has drawn high attention in this day and age. A multitude of clustering methods have been developed, among which the graph based clustering method using the affinity matrix has been laid great emphasis on. Recent research work used the doubly stochastic matrix to normalize the input affinity matrix and enhance the graph based clustering models. Although the doubly stochastic matrix can improve the clustering performance, the clustering structure in the doubly stochastic matrix is not clear as expected. Thus, post processing step is required to extract the final clustering results, which may not be optimal. To address this problem, in this paper, we propose a novel convex model to learn the structured doubly stochastic matrix by imposing low-rank constraint on the graph Laplacian matrix. Our new structured doubly stochastic matrix can explicitly uncover the clustering structure and encode the probabilities of pair-wise data points to be connected, such that the clustering results are enhanced. An efficient optimization algorithm is derived to solve our new objective. Also, we provide theoretical discussions that when the input differs, our method possesses interesting connections with K-means and spectral graph cut models respectively. We conduct experiments on both synthetic and benchmark datasets to validate the performance of our proposed method. The empirical results demonstrate that our model provides an approach to better solving the K-mean clustering problem. By using the cluster indicator provided by our model as initialization, K-means converges to a smaller objective function value with better clustering performance. Moreover, we compare the clustering performance of our model with spectral clustering and related double stochastic model. On all datasets, our method performs equally or better than the related methods.