Simple and scalable constrained clustering: A generalized spectral method

Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, Richard Peng

Research output: Contribution to conferencePaperpeer-review

23 Scopus citations

Abstract

We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem in which both matrices are graph Laplacians. The algorithm 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 both in speed and quality.

Original languageEnglish (US)
Pages445-454
Number of pages10
StatePublished - Jan 1 2016
Event19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 - Cadiz, Spain
Duration: May 9 2016May 11 2016

Conference

Conference19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016
Country/TerritorySpain
CityCadiz
Period5/9/165/11/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Simple and scalable constrained clustering: A generalized spectral method'. Together they form a unique fingerprint.

Cite this