On Constrained Spectral Clustering and Its Applications

Details On Constrained Spectral Clustering and Its Applications On Constrained Spectral Clustering and Its Applications

2012-01-25

arxiv.org/abs/1201.5338v1

Computer Science

Learning

Scientific paper

Constrained clustering has been well-studied for algorithms such as K-means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alternative to encode many constraints is to use spectral clustering, which remains a developing area. In this paper, we propose a flexible and generalized framework for constrained spectral clustering. In contrast to some previous efforts that implicitly encode Must-Link and Cannot-Link constraints by modifying the graph Laplacian or the underlying eigenspace, we present a more natural and principled formulation, which explicitly encodes the constraints as part of a constrained optimization problem. Our method offers several practical advantages: it can encode the degree of belief in Must-Link and Cannot-Link constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; and it can be solved deterministically in polynomial time through generalized eigendecomposition. Furthermore, by inheriting the objective function from spectral clustering and encoding the constraints explicitly, much of the existing analysis of unconstrained spectral clustering techniques remains valid for our formulation. We validate the effectiveness of our approach by empirical results on real-world datasets. We also demonstrate an innovative use of encoding large number of constraints: transfer learning via constraints.

Affiliated with

Also associated with

No associations

Rating

On Constrained Spectral Clustering and Its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Constrained Spectral Clustering and Its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Constrained Spectral Clustering and Its Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-683731