Constrained Spectral Clustering via Exhaustive and Efficient Constraint Propagation
Constrained Spectral Clustering via Exhaustive and Efficient Constraint Propagation
复制标题
DOI：
10.1007/978-3-642-15567-3_1
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Zhiwu Lu;H. Ip
中科院分区：
文献类型：
--
作者：
Zhiwu Lu;H. Ip
本文提出了一种详尽的和有效的约束传播方法，利用成对约束的谱聚类。由于传统的标签传播技术不能很容易地推广到传播成对的约束，我们解决的约束传播问题逆分解成一组独立的标签传播子问题，进一步解决在二次时间使用半监督学习基于k-最近邻图。由于这种时间复杂度与所有可能的成对约束的数量成正比，因此我们的方法提供了一种计算效率高的解决方案，用于在整个数据集内穷举传播成对约束。传播成对约束的穷举集，然后使用调整的权重（或相似性）矩阵的谱聚类。值得注意的是，本文首先清楚地显示了成对约束是如何独立传播的，然后积累成一个和解的封闭形式的解决方案。在真实数据集上的实验结果表明，我们的方法约束谱聚类优于国家的最先进的技术。
This paper presents an exhaustive and efficient constraint propagation approach to exploiting pairwise constraints for spectral clustering. Since traditional label propagation techniques cannot be readily generalized to propagate pairwise constraints, we tackle the constraint propagation problem inversely by decomposing it to a set of independent label propagation subproblems which are further solved in quadratic time using semi-supervised learning based onk-nearest neighbors graphs. Since this time complexity is proportional to the number of all possible pairwise constraints, our approach gives a computationally efficient solution for exhaustively propagating pairwise constraint throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are then used to adjust the weight (or similarity) matrix for spectral clustering. It is worth noting that this paper first clearly shows how pairwise constraints are propagated independently and then accumulated into a conciliatory closed-form solution. Experimental results on real-life datasets demonstrate that our approach to constrained spectral clustering outperforms the state-of-the-art techniques.