Undirected cyclic graph based multiclass pair-wise classifier: Classifier number reduction maintaining accuracy

• Published in: Neurocomputing (Amsterdam) 2016-01, Vol.171, p.1576-1590
• Main Authors: Mendialdua, I., Echegaray, G., Rodriguez, I., Lazkano, E., Sierra, B.
• Format: Article
• Language: English
• Subjects: Decomposition strategies; Machine learning; One-vs-One; Supervised classification
• ISSN: 0925-2312; 1872-8286
• DOI: 10.1016/j.neucom.2015.07.078

Supervised classification approaches try to classify correctly the new unlabelled examples based on a set of well-labelled samples. Nevertheless, some classification methods were formulated for binary classification problems and has difficulties for multi-class problems. Binarization strategies decompose the original multi-class dataset into multiple two-class subsets. For each new sub-problem a classifier is constructed. One-vs-One is a popular decomposition strategy that in each sub-problem discriminates the cases that belong to a pair of classes, ignoring the remaining ones. One of its drawbacks is that it creates a large number of classifiers, and some of them are irrelevant. In order to reduce the number of classifiers, in this paper we propose a new method called Decision Undirected Cyclic Graph. Instead of making the comparisons of all the pair of classes, each class is compared only with other two classes; evolutionary computation is used in the proposed approach in order to obtain suitable class pairing. In order to empirically show the performance of the proposed approach, a set of experiments over four popular Machine Learning algorithms are carried out, where our new method is compared with other well-known decomposition strategies of the literature obtaining promising results. •A new version of One-Vs-One is presented where the number of classifiers is reduced.•Each class is compared only with other two classes.•Evolutionary computation is used to obtain suitable class pairing.•The proposed approach is compared with other state of the art methods over 4 different machine learning algorithms obtaining comparable results.