Enhancing directed binary trees for multi-class classification

One approach to multi-class classification consists in decomposing the original problem into a collection of binary classification tasks. The outputs of these binary classifiers are combined to produce a single prediction. Winner-takes-all, max-wins and tree voting schemes are the most popular methods for this purpose. However, tree schemes can deliver faster predictions because they need to evaluate less binary models. Despite previous conclusions reported in the literature, this paper shows that their performance depends on the organization of the tree scheme, i.e. the positions where each pairwise classifier is placed on the graph. Different metrics are studied for this purpose, proposing a new one that considers the precision and the complexity of each pairwise model, what makes the method to be classifier-dependent. The study is performed using Support Vector Machines (SVMs) as base classifiers, but it could be extended to other kind of binary classifiers. The proposed method, tested on benchmark data sets and on one real-world application, is able to improve the accuracy of other decomposition multi-class classifiers, producing even faster predictions.