Discriminative Nonnegative Spectral Clustering With Flexible Constrained

Abstract

We introduce an uncomplicated spectral approach to the well studied constrained clustering problem. This spectral approach captures constrained clustering as a generalized eigenvalue problem with graph Laplacians.And constrained clustered problem defined by three weighted graphs and these are the data graph, knowledge graph, disjoint graph. 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.