Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)
Linli Xu, James Neufeld, Bryce Larson, Dale Schuurmans
We propose a new method for clustering based on finding maximum mar- gin hyperplanes through data. By reformulating the problem in terms of the implied equivalence relation matrix, we can pose the problem as a convex integer program. Although this still yields a difficult com- putational problem, the hard-clustering constraints can be relaxed to a soft-clustering formulation which can be feasibly solved with a semidef- inite program. Since our clustering technique only depends on the data through the kernel matrix, we can easily achieve nonlinear clusterings in the same manner as spectral clustering. Experimental results show that our maximum margin clustering technique often obtains more accurate results than conventional clustering methods. The real benefit of our ap- proach, however, is that it leads naturally to a semi-supervised training method for support vector machines. By maximizing the margin simul- taneously on labeled and unlabeled training data, we achieve state of the art performance by using a single, integrated learning principle.