Flexible constrained spectral clustering
Flexible constrained spectral clustering
复制标题
DOI：
10.1145/1835804.1835877
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Xiang Wang;I. Davidson
中科院分区：
文献类型：
--
作者：
Xiang Wang;I. Davidson
约束聚类已经在K-means和层次凝聚聚类等算法中得到了很好的研究。然而，如何将约束编码到谱聚类中仍然是一个发展中的领域。在本文中，我们提出了一个灵活的和广义的框架约束谱聚类。与以前的一些努力，隐式编码必须链接和不能链接的约束，通过修改图形拉普拉斯算子或由此产生的特征空间，我们提出了一个更自然和原则的制定，它保留了原来的图形拉普拉斯算子和明确编码的约束。我们的方法提供了几个实际的优点：它可以编码的程度的信念（重量）的Must-Link和Cannot-Link的约束;它保证下限如何以及给定的约束满足使用用户指定的阈值;它可以通过广义特征分解在多项式时间内确定性地解决。此外，通过继承谱聚类的目标函数和显式编码的约束，现有的谱聚类技术的分析仍然是有效的。因此，我们的工作可以作为一个自然的扩展，无约束的谱聚类，并被解释为寻找规范化的最小割的标记图。我们验证了我们的方法的有效性，在现实世界的数据集上的实证结果，与应用程序的约束图像分割和聚类基准数据集与二进制和置信度的约束。
Constrained clustering has been well-studied for algorithms like K-means and hierarchical agglomerative clustering. However, how to encode constraints into spectral clustering remains a developing area. In this paper, we propose a flexible and generalized framework for constrained spectral clustering. In contrast to some previous efforts that implicitly encode Must-Link and Cannot-Link constraints by modifying the graph Laplacian or the resultant eigenspace, we present a more natural and principled formulation, which preserves the original graph Laplacian and explicitly encodes the constraints. Our method offers several practical advantages: it can encode the degree of belief (weight) in Must-Link and Cannot-Link constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; and it can be solved deterministically in polynomial time through generalized eigendecomposition. Furthermore, by inheriting the objective function from spectral clustering and explicitly encoding the constraints, much of the existing analysis of spectral clustering techniques is still valid. Consequently our work can be posed as a natural extension to unconstrained spectral clustering and be interpreted as finding the normalized min-cut of a labeled graph. We validate the effectiveness of our approach by empirical results on real-world data sets, with applications to constrained image segmentation and clustering benchmark data sets with both binary and degree-of-belief constraints.