Constrained 1-Spectral Clustering
By Syama Sundar Rangapuram, Matthias Hein. 2012
89 citations recorded by the source corpus.
An important form of prior information in clustering comes in form of cannot-link and must-link constraints. We present a generalization of the popular spectral clustering technique which integrates such constraints. Motivated by the recently proposed $1$-spectral clustering for the unconstrained problem, our method is based on a tight relaxation of the constrained normalized cut into a continuous optimization problem. Opposite to all other methods which have been suggested for constrained spectral clustering, we can always guarantee to satisfy all constraints. Moreover, our soft formulation allows to optimize a trade-off between normalized cut and the number of violated constraints. An efficient implementation is provided which scales to large datasets. We outperform consistently all other proposed methods in the experiments.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Bernt Schiele
- Zsolt Kira
- Andrew Zisserman
- Kai Han
- Zhaoyang Lv
- Matthias Hein
- Andrea Vedaldi
- Yen-Chang Hsu
In Computer Vision and Pattern Recognition
- Bernt Schiele
- Luc Van Gool
- Andrew Zisserman
- Andrea Vedaldi
- Ming-Hsuan Yang
- Dacheng Tao
- Trevor Darrell
- Jitendra Malik
Citations in the corpus
- Learning to cluster in order to Transfer across domains and tasks (2017, background): “For example, CSP (Wang et al., 2014) and COSC (Rangapuram & Hein, 2012).”
- Spectral Graph Reduction for Efficient Image and Streaming Video Segmentation (2014, methodology): “The first approach is drawn from [21] and reduces the original graph such that the normalized cut (NCut) is preserved.”
- Learning Must-Link Constraints for Video Segmentation Based on Spectral Clustering (2014, methodology): “Further, we discuss the integration of learned must-link constraints via graph reduction techniques [38, 16] and learning and inference strategies.”
- Multi-class Classification without Multi-class Labels (2019, methodology): “CSP (Wang et al., 2014) and COSC (Rangapuram & Hein, 2012) use this strategy.”