Clustered Support Vector Machines
Quanquan Gu, Jiawei Han · 2013
In many problems of machine learning, the data are distributed nonlinearly. One way to address this kind of data is training a non-linear classifier such as kernel support vector machine (kernel SVM). However, the com-putational burden of kernel SVM limits its application to large scale datasets. In this paper, we propose a Clustered Support Vec-tor Machine (CSVM), which tackles the data in a divide and conquer manner. More specif-ically, CSVM groups the data into several clusters, followed which it trains a linear sup-port vector machine in each cluster to sepa-rate the data locally. Meanwhile, CSVM has an additional global regularization, which re-quires the weight vector of each local linear SVM aligning with a global weight vector. The global regularization leverages the in-formation from one cluster to another, and avoids over-fitting in each cluster. We derive a data-dependent generalization error bound for CSVM, which explains the advantage of CSVM over linear SVM. Experiments on sev-eral benchmark datasets show that the pro-posed method outperforms linear SVM and some other related locally linear classifiers. It is also comparable to a fine-tuned ker-nel SVM in terms of prediction performance, while it is more efficient than kernel SVM. 1