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

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: APPLIED SOFT COMPUTING; v. 65, p. 428-442, APR 2018.
• Citações Web of Science: 1

Resumo

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)

• Processo FAPESP: 12/22608-8 - Uso de medidas de complexidade de dados no suporte ao aprendizado de máquina supervisionado
• Beneficiário: Ana Carolina Lorena
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Processo FAPESP: 15/17291-3 - Determinando a estrutura de grafos direcionados acíclicos em classificação multiclasse por medidas de complexidade de problemas supervisionados
• Beneficiário: Thaise Marques Quiterio
• Modalidade de apoio: Bolsas no Brasil - Mestrado