2009 · 113 citations · 16 references
ComputingComputer ScienceData MiningMachine LearningOptimizationConvex AnalysisConvex OptimizationGlobal OptimizationOptimization For Machine LearningSemi-supervised LearningSupervised LearningClusteringConvex FunctionsConvex RelaxationsSemi-supervised ClusteringSemi-supervised ModelsSemidefinite ProgrammingSemidefinite Programming RelaxationSemidefinite Relaxation
Maximum margin principle has been suc-cessfully applied to many supervised and semi-supervised problems in machine learn-ing. Recently, this principle was extended for clustering, referred to as Maximum Mar-gin Clustering (MMC) and achieved promis-ing performance in recent studies. To avoid the problem of local minima, MMC can be solved globally via convex semi-definite programming (SDP) relaxation. Although many efficient approaches have been pro-posed to alleviate the computational bur-den of SDP, convex MMCs are still not scal-able for medium data sets. In this pa-per, we propose a novel convex optimiza-tion method, LG-MMC, which maximizes the margin of opposite clusters via “Label Gen-eration”. It can be shown that LG-MMC is much more scalable than existing convex ap-proaches. Moreover, we show that our con-vex relaxation is tighter than state-of-art con-vex MMCs. Experiments on seventeen UCI datasets and MNIST dataset show significant improvement over existing MMC algorithms. 1
16
Algorithms for Clustering Data
Warren S. Sarle, Anil K. Jain, Richard C. Dubes · Technometrics · 1990 · 7.8K citations
Training linear SVMs in linear time
Thorsten Joachims · 2006 · 2K citations
Multiple kernel learning, conic duality, and the SMO algorithm
Francis Bach, Gert Lanckriet, Michael I. Jordan · 2004 · 1.4K citations