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 = {Syama Sundar Rangapuram and Matthias Hein}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1143--1151}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 1143--1151 %U http://proceedings.mlr.press %V 22 %W PMLR %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 PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-sundar12 PB - PMLR SP - 1143 DP - PMLR EP - 1151 L1 - http://proceedings.mlr.press/v22/sundar12/sundar12.pdf UR - http://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 PMLR 22:1143-1151

Related Material