Maximum Margin Clustering with Pairwise Constraints

Maximum margin clustering (MMC), which extends the theory of support vector machine to unsupervised learning, has been attracting considerable attention recently. The existing approaches mainly focus on reducing the computational complexity of MMC. The accuracy of these methods, however, has not always been guaranteed. In this paper, we propose to incorporate additional side-information, which is in the form of pairwise constraints, into MMC to further improve its performance. A set of pairwise loss functions are introduced into the clustering objective function which effectively penalize the violation of the given constraints. We show that the resulting optimization problem can be easily solved via constrained concave-convex procedure (CCCP). Moreover, for constrained multi-class MMC, we present an efficient cutting-plane algorithm to solve the sub-problem in each iteration of CCCP. The experiments demonstrate that the pairwise constrained MMC algorithms considerably outperform the unconstrained MMC algorithms and two other clustering algorithms that exploit the same type of side-information.