The one-against-all partition based binary tree support vector machine algorithms for multi-class classification

The binary tree support vector machine (SVM) algorithm is one of the mainstream algorithms for multi-class classification in the fields of pattern recognition and machine learning. In order to reduce the training and testing time of one-against-all SVM (OAA-SVM) and reduced OAA-SVM (R-OAA-SVM), in this study, two OAA partition based binary tree SVM algorithms are proposed for multi-class classification. One is the single-space-mapped binary tree SVM (SBT-SVM) and the other is the multi-space-mapped binary tree SVM (MBT-SVM). In the proposed two algorithms, the best OAA partition is determined for each non-leaf node and the k-fold cross validation strategy is adopted to obtain the optimal classifiers. A set of experiments is conducted on nine UCI datasets and two face recognition datasets to demonstrate their performances. The results show that in term of testing accuracy, MBT-SVM is comparable with one-against-one SVM (OAO-SVM), R-OAA-SVM and OAA-SVM and superior to SBT-SVM. In term of testing time, MBT-SVM is superior to OAO-SVM, binary tree of SVM (BTS), R-OAA-SVM and OAA-SVM and slightly longer than SBT-SVM. In term of training time, MBT-SVM is superior to BTS, R-OAA-SVM and OAA-SVM and comparable with SBT-SVM. For the datasets with smaller class number and training sample number, the training time of MBT-SVM is comparable with that of OAO-SVM. For the datasets with larger class number or training sample number, in most cases, the training time of MBT-SVM is longer than that of OAO-SVM.

► We propose an OAA based single-space-mapped binary tree SVM algorithm (SBT-SVM).
► We propose an OAA based multi-space-mapped binary tree SVM algorithm (MBT-SVM).
► The testing accuracy of MBT-SVM is higher than that of SBT-SVM and comparable with that of OAO-SVM.
► The training time of MBT-SVM is shorter than those of BTS, OAA-SVM and R-OAA-SVM.
► The testing time of MBT-SVM is significantly shorter than that of OAO-SVM and BTS.