2015/05/24 by Syama Sundar Rangapuram, Matthias Hein, Rangapuram, Syama Sundar +1 · 1 citation
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Advanced Data Compression Techniques #Face and Expression Recognition #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1505.06485
Long version of paper accepted at AISTATS 2012
arxiv created 2015/05/24 · arxiv updated 2015/05/26
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.