Using complexity measures to determine the structure of directed acyclic graphs in multiclass classification

Author(s)

Quiterio, Thaise M. ^[1] ; Lorena, Ana C. ^[1]

Affiliation

^[1] Univ Fed Sao Paulo, UNIFESP, Inst Ciencia & Tecnol, Machine Learning Res Grp, Av Cesare Mansueto Giulio Lattes 1201, Sao Jose Dos Campos, SP - Brazila

• Document type: Journal article
• Source: APPLIED SOFT COMPUTING; v. 65, p. 428-442, APR 2018.
• Web of Science Citations: 1

Abstract

There are various strategies for decomposing a multiclass classification problem into multiple binary sub-problems. One of the most employed strategies is one-versus-one (OVO), in which there is one binary classifier for each pair of the classes of the original problem. Directed acyclic graphs (DAGs) can be used to combine the outputs of the OVO classifiers in a multiclass prediction. Although the use of these graphs presents some advantages, like reducing the number of classifiers consulted at each prediction, the number of possible graph structures for a given problem is factorial on its number of classes. This paper presents some data-driven strategies designed to find DAG structures suited for each multiclass classification problem. They are guided by the values of some data complexity measures, which evaluate the difficulty of the binary sub-problems. The idea is to place simpler binary sub-problems at the top of the DAG hierarchies. Experimentally, a small variation between the predictive results of distinct DAG structures was found, even for problems with a large number of classes. For this reason, simple greedy algorithms are in several cases able to obtain suitable DAG structures when compared to a more sophisticated genetic algorithm search strategy. (C) 2018 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 12/22608-8 - Use of data complexity measures in the support of supervised machine learning
• Grantee: Ana Carolina Lorena
• Support Opportunities: Research Grants - Young Investigators Grants
• FAPESP's process: 15/17291-3 - Determining the structure of directed acyclic graphs in multiclass classification using complexity measures of supervised problems
• Grantee: Thaise Marques Quiterio
• Support Opportunities: Scholarships in Brazil - Master