Maximum Margin Clustering Made Practical

Maximum Margin Clustering Made Practical
Kai Zhang - Hong Kong University of Science and Technology, Hong Kong Ivor W. Tsang - Hong Kong University of Science and Technology, Hong Kong James T. Kwok - Hong Kong University of Science and Technology, Hong Kong
Maximum margin clustering (MMC) is a recent large margin unsupervised learning approach that has often outperformed conventional clustering methods. Computationally, it involves non-convex optimization and has to be relaxed to different semidefinite programs (SDP). However, SDP solvers are computationally very expensive and only small data sets can be handled by MMC so far. To make MMC more practical, we avoid SDP relaxations and propose in this paper an effcient approach that performs alternating optimization directly on the original non-convex problem. A key step to avoid premature convergence is on the use of SVR with the Laplacian loss, instead of SVM with the hinge loss, in the inner optimization subproblem. Experiments on a number of synthetic and realworld data sets demonstrate that the proposed approach is often more accurate, much faster and can handle much larger data sets.

Kai Zhang - Hong Kong University of Science and Technology, Hong Kong
Ivor W. Tsang - Hong Kong University of Science and Technology, Hong Kong
James T. Kwok - Hong Kong University of Science and Technology, Hong Kong

Maximum margin clustering (MMC) is a recent large margin unsupervised learning approach that has often outperformed conventional clustering methods. Computationally, it involves non-convex optimization and has to be relaxed to different semidefinite programs (SDP). However, SDP solvers are computationally very expensive and only small data sets can be handled by MMC so far. To make MMC more practical, we avoid SDP relaxations and propose in this paper an effcient approach that performs alternating optimization directly on the original non-convex problem. A key step to avoid premature convergence is on the use of SVR with the Laplacian loss, instead of SVM with the hinge loss, in the inner optimization subproblem. Experiments on a number of synthetic and realworld data sets demonstrate that the proposed approach is often more accurate, much faster and can handle much larger data sets.