CONSTRAINED 1-SPECTAL CLUSTERING
An important form of prior information in clustering comes in the form of must-link and cannot-link constraints. In the paper , we presented a generalization of the popular spectral clustering technique to integrate such constraints. Motivated by the recently proposed 1-spectral clustering , 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)
 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 )