title: A divide-and-combine method for large scale nonparallel support vector machines.
abstract: Nonparallel Support Vector Machine (NPSVM) which is more flexible and has better generalization than typical SVM is widely used for classification. Although some methods and toolboxes like SMO and libsvm for NPSVM are used, NPSVM is hard to scale up when facing millions of samples. In this paper, we propose a divide-and-combine method for large scale nonparallel support vector machine (DCNPSVM). In the division step, DCNPSVM divide samples into smaller sub-samples aiming at solving smaller subproblems independently. We theoretically and experimentally prove that the objective function value, solutions, and support vectors solved by DCNPSVM are close to the objective function value, solutions, and support vectors of the whole NPSVM problem. In the combination step, the sub-solutions combined as initial iteration points are used to solve the whole problem by global coordinate descent which converges quickly. In order to balance the accuracy and efficiency, we adopt a multi-level structure which outperforms state-of-the-art methods. Moreover, our DCNPSVM can tackle unbalance problems efficiently by tuning the parameters. Experimental results on lots of large data sets show the effectiveness of our method in memory usage, classification accuracy and time consuming.
authors.affiliation: Research Center on Fictitious Economy and Data Science, Chinese Academy of Sciences, Beijing 100190, China; Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China. Electronic address: tyj@ucas.ac.cn.
authors.forename: Yingjie
authors.initials: Y
authors.lastname: Tian
authors.affiliation: Research Center on Fictitious Economy and Data Science, Chinese Academy of Sciences, Beijing 100190, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 101408, China; Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China. Electronic address: juxuchan@126.com.
authors.forename: Xuchan
authors.initials: X
authors.lastname: Ju
authors.affiliation: Research Center on Fictitious Economy and Data Science, Chinese Academy of Sciences, Beijing 100190, China; Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China; College of Information Science and Technology, University of Nebraska at Omaha, Omaha, NE 68182, USA. Electronic address: yshi@ucas.ac.cn.
authors.forename: Yong
authors.initials: Y
authors.lastname: Shi
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D006801:Humans; D060388:Support Vector Machine
keywords: Clustering; Combine; Divide; Large scale; Nonparallel support vector machine; Support vector machine