2010 FlexibleConstrainedSpectralClus

• (Wang et al., 2010) ⇒ Xiang Wang, and Ian Davidson. (2010). “Flexible Constrained Spectral Clustering.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835877

Subject Headings:

Notes

• slides http://bayou.cs.ucdavis.edu/papers/kdd10.slides.pdf

Cited By

• ~7 http://scholar.google.com/scholar?q=%22Flexible+constrained+spectral+clustering%22+2010
• http://portal.acm.org/citation.cfm?id=1835877&preflayout=flat#citedby

Quotes

Abstract

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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 FlexibleConstrainedSpectralClus	Ian Davidson Xiang Wang			Flexible Constrained Spectral Clustering		KDD-2010 Proceedings		10.1145/1835804.1835877		2010