Constrained 1-Spectral Clustering

Syama Sundar Rangapuram, Matthias Hein
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1143-1151, 2012.

Abstract

An important form of prior information in clustering comes in the form of cannot-link and must-link constraints of instances. 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 normalized cut 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-sundar12, title = {Constrained 1-Spectral Clustering}, author = {Rangapuram, Syama Sundar and Hein, Matthias}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1143--1151}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/sundar12/sundar12.pdf}, url = {https://proceedings.mlr.press/v22/sundar12.html}, abstract = {An important form of prior information in clustering comes in the form of cannot-link and must-link constraints of instances. 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 normalized cut 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.} }
Endnote
%0 Conference Paper %T Constrained 1-Spectral Clustering %A Syama Sundar Rangapuram %A Matthias Hein %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-sundar12 %I PMLR %P 1143--1151 %U https://proceedings.mlr.press/v22/sundar12.html %V 22 %X An important form of prior information in clustering comes in the form of cannot-link and must-link constraints of instances. 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 normalized cut 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.
RIS
TY - CPAPER TI - Constrained 1-Spectral Clustering AU - Syama Sundar Rangapuram AU - Matthias Hein BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-sundar12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1143 EP - 1151 L1 - http://proceedings.mlr.press/v22/sundar12/sundar12.pdf UR - https://proceedings.mlr.press/v22/sundar12.html AB - An important form of prior information in clustering comes in the form of cannot-link and must-link constraints of instances. 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 normalized cut 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. ER -
APA
Rangapuram, S.S. & Hein, M.. (2012). Constrained 1-Spectral Clustering. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1143-1151 Available from https://proceedings.mlr.press/v22/sundar12.html.

Related Material