CONSTRAINED 1-SPECTAL CLUSTERING
by Syama Sundar Rangapuram and Matthias Hein
An important form of prior information in clustering comes in the form of must-link and cannot-link constraints. In the paper [1], we presented a generalization of the popular spectral clustering technique to integrate such constraints. Motivated by the recently proposed 1-spectral clustering [2], our method is based on a tight relaxation of the constrained normalized cut problem into a continuous optimization problem. In contrast to the existing constrained spectral clustering methods, we can always guarantee to satisfy all constraints. Moreover, our soft formulation also allows to optimize a trade-off between normalized cut and the number of violated constraints. Our efficient implementation, that scales to large datasets, shows that our method consistently outperforms all the other proposed methods.
![]() |
![]() |
![]() |
![]() |
DOWNLOAD AND LICENSE
Constrained 1-Spectral Clustering has been developed by Syama Sundar Rangapuram, Max Planck Institute for Computer Science and Matthias Hein, Department of Computer Science, Saarland University, Germany. The Matlab code for Constrained 1-Spectral Clustering is published as free software under the terms of the GNU GPL v3.0. Please include a reference to the paper Constrained 1-Spectral Clustering and include the original documentation and copyright notice.
Download Constrained 1-SpectralClustering Code (Version: 1.1, Matlab/C Code)
Unzip the file cosc_v1_1.zip and see README.txt to setup and run the program. If there is any problem using this code, contact Syama Sundar Rangapuram: srangapu@mpi-inf.mpg.de
REFERENCES
[1] S. Rangapuram and M. Hein,
Constrained 1-Spectral Clustering,
In International conference on Artificial Intelligence and Statistics (AISTATS), 2012. PDF (Long version: PDF
)
[2] M. Hein and T. Bühler,
An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA,
In Advances in Neural Information Processing Systems 23 (NIPS 2010), accepted. PDF (Supplementary material: PDF
)