Scalable Constrained Clustering: A Generalized Spectral Method
Preprint
Abstract
We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Constrained Spectral Clustering using L1 Regularization2013
- A fast solver for a class of linear systemsCommunications of the ACM, 2012
- On constrained spectral clustering and its applicationsData Mining and Knowledge Discovery, 2012
- Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processingComputer Vision and Image Understanding, 2011
- Comparing Community Structure to Characteristics in Online Collegiate Social NetworksSIAM Review, 2011
- Normalized Cuts Revisited: A Reformulation for Segmentation with Linear Grouping ConstraintsJournal of Mathematical Imaging and Vision, 2010
- Graph Partitioning by Spectral Rounding: Applications in Image Segmentation and Clustering2006
- Segmentation given partial grouping constraintsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient MethodSIAM Journal on Scientific Computing, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000