Scalable Constrained Clustering: A Generalized Spectral Method
arXiv:1504.00653
Abstract
We present a principled spectral approach to the well-studied constrained clustering problem. It reduces clustering to a generalized eigenvalue problem on Laplacians. The method works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches. We support this claim with experiments on various data sets: our approach recovers correct clusters in examples where previous methods fail, and handles data sets with millions of data points - two orders of magnitude larger than before.
this paper is superseded by the article "Scalable Constrained Clustering: A Generalized Spectral Method" authored by M. Cucuring, I. Koutis, S. Chawla, G. Miller and R. Peng