Determinando a estrutura de grafos direcionados acíclicos em classificação multiclasse por medidas de complexidade de problemas supervisionados

Resumo

Vários problemas práticos envolvem distinguir dados dentre múltiplas classes. Uma abordagem adotada para lidar com esses problemas de classificação multiclasse é decompô-los em vários subproblemas binários e combinar as suas soluções. A decomposição um-versus-um (one-versus-one), que gera um subproblema binário para cada par de classes, é uma das estratégias decomposicionais mais usadas. Técnicas de classificação binária padrão podem então ser usadas para induzir os classificadores para os pares de classes, enquanto a estrutura hierárquica de um grafo direcionado acíclico (DAG, do Inglês Directed Acyclic Graph) pode ser empregada para combinar suas saídas. Como os resultados preditivos do DAG na tarefa de classificação multiclasse são dependentes de como os classificadores binários encontram-se organizados na hierarquia, neste trabalho medidas de complexidade de problemas supervisionados serão empregadas para determinar a estrutura do DAG. Essas medidas estimam a complexidade da fronteira de classificação com base em índices extraídos dos dados disponíveis para aprendizado. O objetivo é posicionar subproblemas binários mais simples em níveis superiores do DAG, minimizando a propagação de erros pela estrutura hierárquica. (AU)