Unified Spectral Regularization For Pairwise Constrained Clustering

Spectral Clustering are playing a more and more important role in the task of Clustering Analysis and its related Data Mining and Machine Learning field for its simpleness and effectiveness.Meanwhile,the proper encoding of some prior data pairwise constrains can effectively enhance the accuracy of spectral clustering.However,current constrained clustering methods are not able to effectively encode both the Must-Link and Cannot-Link constrains into the spectral process.In this paper,we present a unified regularized spectral formulation for constrained data clustering,and build a spectral clustering algorithm framework based on the Unified Spectral Regularization(USR).Unlike previous methods that rely on semi-definite programming(SDP),our formulation leads to a more efficient regularized spectral relaxation,which has similar capabilities of incorporating both must-link and cannot-link constraints and being directly applicable to multi-class problems.Specifically,in this algorithm framework,by solving a regularized eigen-decomposition problem,we efficiently find the global optimum labeling in the relaxed domain,based on which the near-optimum feasible clustering is finally obtained by minimizing the subspace distortion error to the optimal relaxed labeling using weighted K-means.The main contributions of this paper are reflected as follows: 1)a unified spectral regularization form for different pairwise constrains,which can better utilize the positive guidance of both Must-Link and Cannot-Link on the clustering results;2)an algorithm framework with high scalability which can take various similarity matrices as input;3)a prominent improvement in the clustering performance like accuracy and computation time against the state-of-art constrained clustering methods.We apply our method to natural scene clustering and UCI data clustering.Extensive experiments have validated the effectiveness and efficiency of the proposed method.