Convex Constrained Clustering with Graph-Laplacian Pca

In this paper, we propose a new algorithm for constrained clustering, in which a new regularizer elegantly incorporates a small amount of weakly supervisory information in the form of pair-wise constraints to regularize the similarity between the low-dimensional representations of a set of data samples. By exploring both the local and global structures of the data samples with the guidance of the supervisory information, the proposed algorithm is capable of learning the lowdimensional representations with strong separability. Technically, the proposed algorithm is formulated and relaxed as a convex optimization model, which is further efficiently solved with the global convergence guaranteed. Experimental results on multiple benchmark data sets show that our proposed model can produce higher clustering accuracy than state-ofthe-art algorithms.