Maximum margin clustering with multivariate loss function

This paper presents a simple but powerful extension of the maximum margin clustering (MMC) algorithm that optimizes multivariate performance measure specifically defined for clustering, including Normalized Mutual Information, Rand Index and F-measure. Different from previous MMC algorithms that always employ the error rate as the loss function, our formulation involves a multivariate loss function that is a non-linear combination of the individual clustering results. Computationally, we propose a cutting plane algorithm to approximately solve the resulting optimization problem with a guaranteed accuracy. Experimental evaluations show clear improvements in clustering performance of our method over previous maximum margin clustering algorithms. © 2009 IEEE