Em problemas convencionais de classificação, cada exemplo de um conjunto de dados é associado a apenas uma dentre duas ou mais classes. No entanto, existem problemas de classificação mais complexos, nos quais as classes envolvidas no problema são estruturadas hierarquicamente, possuindo subclasses e superclasses. Nesses problemas, exemplos podem ser atribuídos simultaneamente a classes pertencentes a dois ou mais caminhos de uma hierarquia, ou seja, exemplos podem ser classificados em várias classes localizadas em um mesmo nível hierárquico. Tal hierarquia pode ser estruturada como uma árvore ou como um grafo acíclico direcionado. Esses problemas são chamados de problemas de classificação hierárquica multirrótulo, sendo mais difíceis devido à alta complexidade, diversidade de soluções, difícil modelagem e desbalanceamento dos dados. Duas abordagens são utilizadas para tratar esses problemas, chamadas global e local. Na abordagem global, um único classificador é induzido para lidar com todas as classes do problema simultaneamente, e a classificação de novos exemplos é realizada em apenas um passo. Já na abordagem local, um conjunto de classificadores é induzido, sendo cada classificador responsável pela predição de uma classe ou de um conjunto de classes, e a classificação de novos exemplos é realizada em vários passos, considerando as predições dos vários classificadores. Nesta Tese de Doutorado, são propostos e investigados dois métodos para classificação hierárquica multirrótulo. O primeiro deles é baseado na abordagem local, e associa uma rede neural Multi-Layer Perceptron (MLP) a cada nível da hierarquia, sendo cada MLP responsável pelas predições no seu nível associado. O método é chamado Hierarchical Multi- Label Classification with Local Multi-Layer Perceptrons (HMC-LMLP). O segundo método é baseado na abordagem global, e induz regras de classificação hierárquicas multirrótulo utilizando um Algoritmo Genético. O método é chamado Hierarchical Multi-Label Classification with a Genetic Algorithm (HMC-GA). Experimentos utilizando hierarquias estruturadas como árvores mostraram que o método HMC-LMLP obteve desempenhos de classificação superiores ao método estado-da-arte na literatura, e desempenhos superiores ou competitivos quando utilizando hierarquias estruturadas como grafos. O método HMC-GA obteve resultados competitivos com outros métodos da literatura em hierarquias estruturadas como árvores e grafos, sendo capaz de induzir, em muitos casos, regras menores e em menor quantidade / conventional classification problems, each example of a dataset is associated with just one among two or more classes. However, there are more complex classification problems where the classes are hierarchically structured, having subclasses and superclasses. In these problems, examples can be simultaneously assigned to classes belonging to two or more paths of a hierarchy, i.e., examples can be classified in many classes located in the same hierarchical level. Such a hierarchy can be structured as a tree or a directed acyclic graph. These problems are known as hierarchical multi-label classification problems, being more difficult due to the high complexity, diversity of solutions, modeling difficulty and data imbalance. Two main approaches are used to deal with these problems, called global and local. In the global approach, only one classifier is induced to deal with all classes simultaneously, and the classification of new examples is done in just one step. In the local approach, a set of classifiers is induced, where each classifier is responsible for the predictions of one class or a set of classes, and the classification of new examples is done in many steps, considering the predictions of all classifiers. In this Thesis, two methods for hierarchical multi-label classification are proposed and investigated. The first one is based on the local approach, and associates a Multi-Layer Perceptron (MLP) to each hierarchical level, being each MLP responsible for the predictions in its associated level. The method is called Hierarchical Multi-Label Classification with Local Multi-Layer Perceptrons (HMC-LMLP). The second method is based on the global approach, and induces hierarchical multi-label classification rules using a Genetic Algorithm. The method is called Hierarchical Multi-Label Classification with a Genetic Algorithm (HMC-GA). Experiments using hierarchies structured as trees showed that HMC-LMLP obtained classification performances superior to the state-of-the-art method in the literature, and superior or competitive performances when using graph-structured hierarchies. The HMC-GA method obtained competitive results with other methods of the literature in both tree and graph-structured hierarchies, being able of inducing, in many cases, smaller and in less quantity rules
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-24032014-163900 |
| Date | 05 December 2013 |
| Creators | Ricardo Cerri |
| Contributors | André Carlos Ponce de Leon Ferreira de Carvalho, Luiz Henrique de Campos Merschmann, Roseli Aparecida Francelin Romero, Bianca Zadrozny, Fernando José von Zuben |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds