Extreme Maximum Margin Clustering

Chen ZHANG  ShiXiong XIA  Bing LIU  Lei ZHANG  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.8   pp.1745-1753
Publication Date: 2013/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1745
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
maximum margin clustering,  unsupervised learning,  extreme learning machine (ELM),  random feature mapping,  

Full Text: PDF>>
Buy this Article

Maximum margin clustering (MMC) is a newly proposed clustering method that extends the large-margin computation of support vector machine (SVM) to unsupervised learning. Traditionally, MMC is formulated as a nonconvex integer programming problem which makes it difficult to solve. Several methods rely on reformulating and relaxing the nonconvex optimization problem as semidefinite programming (SDP) or second-order cone program (SOCP), which are computationally expensive and have difficulty handling large-scale data sets. In linear cases, by making use of the constrained concave-convex procedure (CCCP) and cutting plane algorithm, several MMC methods take linear time to converge to a local optimum, but in nonlinear cases, time complexity is still high. Since extreme learning machine (ELM) has achieved similar generalization performance at much faster learning speed than traditional SVM and LS-SVM, we propose an extreme maximum margin clustering (EMMC) algorithm based on ELM. It can perform well in nonlinear cases. Moreover, the kernel parameters of EMMC need not be tuned by means of random feature mappings. Experimental results on several real-world data sets show that EMMC performs better than traditional MMC methods, especially in handling large-scale data sets.