Instance selection for speeding up multi-class SVMs with neighborhoods

Although support vector machines (SVMs) are an excellent technology for classification, it is still a serious challenge for this method to be applied to massive datasets with large number of classes and instances. This paper presents an instance selection method, the Filtered Nearest Enemies (FINE) algorithm, to substantially reduce the scale of a multi-class dataset and speed up the training of SVM models. With the one versus rest style of training multi-class SVMs, for each instance, FINE selects k nearest neighbors from each of the other classes (named k-Nearest Enemies). After selecting k-nearest enemies of all instances, an effective filtering procedure is used to reduce redundant and noisy instances. Furthermore, a strategy is adopted to control the imbalance of training data. Experiments performed on a wide variety of datasets demonstrate the superiority of FINE over other competitive algorithms. On most datasets the proposed method can keep or even improve the classification accuracy while sharply reducing the training data and training time of SVMs.