Constrained spectral clustering using L1 regularization

Jaya Kawale, Daniel Boley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

Constrained spectral clustering is a semi-supervised learning problem that aims at incorporating user-defined constraints in spectral clustering. Typically, there are two kinds of constraints: (i) must-link, and (ii) cannot-link. These constraints represent prior knowledge indicating whether two data objects should be in the same cluster or not; thereby aiding in clustering. In this paper, we propose a novel approach that uses convex subproblems to incorporate constraints in spectral clustering and co-clustering. In comparison to the prior state-of-art approaches, our approach presents a more natural way to incorporate constraints in the spectral methods and allows us to make a trade off between the number of satisfied constraints and the quality of partitions on the original graph. We use an L1 regularizer analogous to LASSO, often used in literature to induce sparsity, in order to control the number of constraints satisfied. Our approach can handle both must-link and cannot-link constraints, unlike a large number of previous approaches that mainly work on the former. Further, our formulation is based on the reduction to a convex subproblem which is relatively easy to solve using existing solvers. We test our proposed approach on real world datasets and show its effectiveness for both spectral clustering and co-clustering over the prior state-of-art.

Original languageEnglish (US)
Title of host publicationProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
EditorsJoydeep Ghosh, Zoran Obradovic, Jennifer Dy, Zhi-Hua Zhou, Chandrika Kamath, Srinivasan Parthasarathy
PublisherSiam Society
Pages103-111
Number of pages9
ISBN (Electronic)9781611972627
ISBN (Print)9781611972627
DOIs
StatePublished - 2013
EventSIAM International Conference on Data Mining, SDM 2013 - Austin, United States
Duration: May 2 2013May 4 2013

Publication series

NameProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013

Other

OtherSIAM International Conference on Data Mining, SDM 2013
Country/TerritoryUnited States
CityAustin
Period5/2/135/4/13

Bibliographical note

Publisher Copyright:
Copyright © SIAM.

Fingerprint

Dive into the research topics of 'Constrained spectral clustering using L1 regularization'. Together they form a unique fingerprint.

Cite this