Xiang Wang
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.
Supplemental Material
- A. Asuncion and D. Newman. UCI machine learning repository, 2007.Google Scholar
- S. Basu, I. Davidson, and K. Wagstaff, editors. Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman & Hall/CRC, 2008. Google ScholarDigital Library
- T. Coleman, J. Saunderson, and A. Wirth. Spectral clustering with inconsistent advice. In ICML, pages 152--159, 2008. Google ScholarDigital Library
- I. Davidson and S. S. Ravi. Intractability and clustering with constraints. In ICML, pages 201--208, 2007. Google ScholarDigital Library
- T. De Bie, J. A. K. Suykens, and B. De Moor. Learning from general label constraints. In SSPR/SPR, pages 671--679, 2004.Google ScholarCross Ref
- P. Drineas, A. M. Frieze, R. Kannan, S. Vempala, and V. Vinay. Clustering large graphs via the singular value decomposition. Machine Learning, 56(1--3):9--33, 2004. Google ScholarDigital Library
- X. Ji and W. Xu. Document clustering with prior knowledge. In SIGIR, pages 405--412, 2006. Google ScholarDigital Library
- S. D. Kamvar, D. Klein, and C. D. Manning. Spectral learning. In IJCAI, pages 561--566, 2003. Google ScholarDigital Library
- H. Kuhn and A. Tucker. Nonlinear programming. ACM SIGMAP Bulletin, pages 6--18, 1982. Google ScholarDigital Library
- Z. Li, J. Liu, and X. Tang. Constrained clustering via spectral regularization. In CVPR, pages 421--428, 2009.Google ScholarCross Ref
- Z. Lu and M. A. Carreira-Perpinan. Constrained spectral clustering through affinity propagation. In CVPR, 2008.Google Scholar
- D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proc. 8th Int'l Conf. Computer Vision, volume 2, pages 416--423, July 2001.Google ScholarCross Ref
- A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849--856, 2001.Google ScholarDigital Library
- J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888--905, 2000. Google ScholarDigital Library
- U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395--416, 2007. Google ScholarDigital Library
- K. Wagstaff and C. Cardie. Clustering with instance-level constraints. In ICML, pages 1103--1110, 2000. Google ScholarDigital Library
- F. Wang, C. H. Q. Ding, and T. Li. Integrated KL (K-means - Laplacian) clustering: A new clustering approach by combining attribute data and pairwise relations. In SDM, pages 38--48, 2009.Google ScholarCross Ref
- S. White and P. Smyth. A spectral clustering approach to finding communities in graph. In SDM, 2005.Google ScholarCross Ref
- Q. Xu, M. desJardins, and K. Wagstaff. Constrained spectral clustering under a local proximity structure assumption. In FLAIRS Conference, pages 866--867, 2005.Google Scholar
- S. X. Yu and J. Shi. Grouping with bias. In NIPS, pages 1327--1334, 2001.Google Scholar
- S. X. Yu and J. Shi. Segmentation given partial grouping constraints. IEEE Trans. Pattern Anal. Mach. Intell., 26(2):173--183, 2004. Google ScholarDigital Library
Index Terms
- Flexible constrained spectral clustering
Recommendations
On constrained spectral clustering and its applications
Constrained clustering has been well-studied for algorithms such as K-means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alternative to encode many constraints ...
Constrained spectral clustering via multi–layer graph embeddings on a grassmann manifold
Exploring Complex and Big Data (special section, pp. 7-91), Johann Gamper, Robert Wrembel (Eds.)AbstractWe present two algorithms in which constrained spectral clustering is implemented as unconstrained spectral clustering on a multi-layer graph where constraints are represented as graph layers. By using the Nystrom approximation in one of the ...
Auto-weighted multi-view constrained spectral clustering
AbstractConstrained clustering is a new fashion of semi-supervised learning which focused on enhancing the quality of the partition by utilizing pairwise constraints. Though many constrained clustering methods have an excellent performance in ...
Comments