Reordering adaptive directed acyclic graphs: an improved algorithm for multiclass support vector machines

摘要

The problem of extending binary support vector machines (SVMs) for multiclass classification is still an ongoing research issue. Ussivakul and Kijsirikul proposed the adaptive directed acyclic graph (ADAG) approach that provides accuracy comparable to that of the standard algorithm - Max Wins and requires low computation. However, different sequences of nodes in the ADAG may provide different accuracy. In this paper we present a new method for multiclass classification, reordering ADAG, which is the modification of the original ADAG method. We show examples to exemplify that the margin (or 2/|w| value) between two classes of each binary SVM classifier affects the accuracy of classification, and this margin indicates the magnitude of confusion between the two classes. In this paper, we propose an algorithm to choose an optimal sequence of nodes in the ADAG by considering the |w| values of all classifiers to be used in data classification. We apply minimum-weight perfect matching with the reordering algorithm in order to select the best sequence of nodes in polynomial time. We then compare the performance of our method with previous methods including the ADAG and the Max Wins algorithm. Experiments denote that our method gives the higher accuracy, and runs faster than Max Wins.