Determinação Da Estrutura De Grafos Direcionados Aciclicos Em Classificação Multiclasse

Determinação Da Estrutura De Grafos Direcionados Aciclicos Em Classificação Multiclasse

Author Quiterio, Thaise Marques Autor UNIFESP Google Scholar
Advisor Lorena, Ana Carolina Autor UNIFESP Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Graduate program Ciência da computação
Abstract A large number of practical problems involves distinguishing data among multi-ple classes. One way to solve these multiclass classification problems is to decompose them into several two-class subproblems and to assign a binary predictor to each one of the generated subproblems. The label of a new example is obtained after combi-ning the individual outputs of the predictors. This work studies the One-versus-One decomposition (OVO) and the combination of the outputs is performed by Directed Acyclic Graphs (DAGs). DAGs are able to combine the outputs of the OVO classifiers more eficiently. However, there is a fatorial number of possible graph structures on the number of problem classes. Since the predictive results of a DAG in multiclass classification can be dependent on how the classifiers are organized within the hie-rarchy, some strategy is needed to determine the most appropriate solution for each problem. In this work, data complexity measures are used to design DAG structu-res. These measures estimate the complexity of the classification boundary based on indexes extracted from the data. By employing such measures in the evaluation of the pairwise subproblems, some algorithms are formulated to organize them in the DAGs. The intent is to place simpler binary subproblems at upper levels of the hi-erarchies, in order to reduce the incidence of cumulative errors. Experimentally, the results of distinct DAG types did not vary much: Decision DAGs (DDAGs), Adaptive DAGs (ADAGs) and Reordering ADAGs (RADAGs). Randomly sampled structures also presented results close to those obtained by the proposed methods. We present herewith strategies that were able to obtain structures of different DAG variants with accuracy performance close to the average of randomly generated DAGs.

Um grande número de problemas práticos envolve distinguir dados em diversas classes. Uma das maneiras de resolver esses problemas multiclasse é através da de-composição destes em vários subproblemas de duas classes e atribuir um preditor a cada subproblema extraído. O rótulo de um novo exemplo é estimado após a com-binação das saídas individuais dos preditores. Este trabalho estuda a decomposição um-versus-um (OVO, do Inglês One-Versus-One) e a combinação das saídas é reali-zada por grafos direcionados acíclicos (DAGs, do Inglês Directed Acyclic Graphs). O uso de DAGs pode tornar mais eficiente a combinação dos classificadores OVO. Po-rém, existe um número fatorial de possíveis grafos em função do número de classes dos problemas. Como os resultados preditivos do DAG na classificação multiclasse podem ser dependentes da forma como os classificadores são organizados dentro da hierarquia, é necessário adotar alguma estratégia para determinar as soluções mais adequadas para cada problema. Neste trabalho, medidas de complexidade de da-dos são utilizadas para projetar as estruturas de DAGs. Estas medidas estimam a complexidade da fronteira de classificação com base em índices extraídos dos dados. Empregando-as na avaliação dos subproblemas, são apresentados algoritmos para organizar os pares de classes nos DAGs. A estratégia adotada é a de posicionar os subproblemas mais simples em níveis superiores dos grafos, de maneira a reduzir propagações de erros no uso das estruturas hierárquicas. Experimentalmente, notou-se que não houve uma variação muito grande nos resultados da avaliação predi-tiva com diferentes DAGs: DAGs de Decisão (DDAGs), DAGs Adaptativos (ADAGs) e ADAGs Reordenados (RADAGs). Estruturas amostradas aleatoriamente também apresentaram resultados em geral próximos aos obtidos pelos métodos propostos. Assim, as estratégias formuladas neste trabalho foram capazes de obter estruturas de diferentes variantes de DAGs com desempenho próximo ao médio de DAGs geradas aleatoriamente.
Keywords Adags
Radags
Adags
Radags
Language Portuguese
Date 2017-02-20
Research area Otimização
Knowledge area Ciência Da Computação
Publisher Universidade Federal de São Paulo (UNIFESP)
Extent 121p.
Origin https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=4995890
Access rights Closed access
Type Dissertation
URI http://repositorio.unifesp.br/handle/11600/50890

Show full item record




File

File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account