Incorporando árvores de decisão com múltiplos testes no algoritmo HEAD-DT

• Processo: 15/13245-7
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Data de Início da vigência: 04 de janeiro de 2016
• Data de Término da vigência: 03 de março de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Márcio Porto Basgalupp
• Beneficiário: Márcio Porto Basgalupp
• Pesquisador Anfitrião: Alex Alves Freitas
• Instituição Sede: Instituto de Ciência e Tecnologia (ICT). Universidade Federal de São Paulo (UNIFESP). Campus São José dos Campos. São José dos Campos , SP, Brasil
• Instituição Anfitriã: University of Kent, Inglaterra
• Vinculado ao auxílio: 10/20255-5 - Programação genética para evolução de algoritmos de indução de árvores de decisão, AP.JP
• Assunto(s): Algoritmos evolutivos
• Palavra(s)-Chave do Pesquisador: Algoritmos Evolutivos | Árvores de Decisão | híper-heurísticas | Aprendizado de Máquina e Computação Evolutiva

Resumo

Árvores de Decisão constituem uma técnica poderosa e amplamente utilizada em tarefas de aprendizado de máquina e mineração de dados, principalmente em virtude da facilidade de interpretação do conhecimento adquirido. Existem diversas estratégias para indução de árvores de decisão, cada qual com suas vantagens e desvantagens de acordo com seus correspondentes vieses. Em contraste com os algoritmos tradicionais de indução de árvores de decisão - todos manualmente desenvolvidos por humanos - foi proposto o algoritmo HEAD-DT, uma abordagem de hiper-heurística evolutiva para construção automática de algoritmos de indução de árvores de decisão. HEAD-DT trabalha sobre diversos componentes manualmente desenvolvidos para indução de árvores de decisão, e é conduzido por um algoritmo típico de busca evolutiva, combinando os componentes mais adequados para o problema em questão. Recentemente, foi introduzido o conceito de árvores de decisão com múltiplos testes (MTDT, do inglês Multi-Test Decision Trees), uma nova forma de representação de árvores de decisão. Nas MTDT, cada nó da árvore pode ser composto por múltiplos testes univariados, o que pode ser visto como um caso intermediário (em termos de interpretabilidade) entre as árvores de decisão univariadas e as árvores de decisão multivariadas. Em relação aos algoritmos tradicionais de árvores de decisão univariadas, os algoritmos de indução das MTDT possuem certas particularidades. O critério de split é um exemplo claro, em que pode ser conduzido por um mecanismo de votação majoritária em que todos os testes univariados têm a mesma importância. No entanto, diversas outras estratégias podem ser desenvolvidas para realizar essa tarefa. Nesse contexto, o presente projeto propõe estender o algoritmo HEAD-DT - originalmente proposto para árvores de decisão univariadas - para construção automática de algoritmos de indução de árvores de decisão com múltiplos testes. Embora muitos trabalhos utilizem algoritmos evolutivos para indução de árvores de decisão, o que se propõe aqui é algo totalmente diferente, pois a ideia é evoluir algoritmos genéricos para indução de árvores de decisão de múltiplos testes, ou seja, o resultado final do método será um algoritmo de indução, e não apenas uma árvore de decisão. Isso caracteriza um algoritmo de meta-learning, pois o objetivo é aprender um algoritmo de aprendizagem.