Uma abordagem multiobjetiva para construção automática de algoritmos de indução de árvores de decisão

Abstract

Decision tree induction is one of the most employed methods to extract knowledge from data, as the representation of knowledge is very intuitive and easily understandable by humans. A successful strategy for inducing decision trees, the greedy top-down approach, has been continuously improved by researchers over the years. After recent breakthroughs in the automatic design of machine learning algorithms, was proposed a hyper-heuristic evolutionary algorithm for automatically generating decision-tree induction algorithms, named HEAD-DT. In this work, this approach was expanded, making the fitness function, which previously worked with only one goal in multiobjective function. In this context, it was used two techniques for optimizing multi-objective fitness: a weighted formula and the lexicographical technique. Experiments will be conducted in 20 public data sets to assess the performance of the new version of HEAD-DT, and we compare it to the traditional decision-tree algorithms C4.5, CART in addition to the original version of HEAD- DT algorithm. Results show that the multi-objective version of HEAD-DT is able to generate promising algorithms when compared to both previous version of HEAD-DT, C4.5 and CART regarding predictive accuracy, F-Measure and complexity (number of nodes). Therefore, this work presents the first efforts to transform the HEAD-DT in a multiobjective algorithm, that is, able to guide the process of evolution by two or more goals.

Indução de árvores de decisão é um dos métodos mais utilizados para extrair conhecimento a partir dos dados, uma vez que a representação do conhecimento é muito intuitivo e de fácil compreensão por seres humanos. Uma estratégia bem sucedida para a indução de árvores de decisão, a abordagem top-down, tem sido continuamente melhorada ao longo dos anos. Após avanços recentes na automatização de algoritmos de aprendizado de máquina, foi proposto um algoritmo evolutivo de hiper-heurística para a geração automática de algoritmos de indução de árvores de decisão: HEAD-DT. Neste trabalho, essa abordagem foi ampliada, tornando a função de fitness, que antes trabalhava com apenas um objetivo, em multiobjetiva. Neste contexto, será adotada duas técnicas para a otimizar o fitness multiobjetivo: a fórmula ponderada e a lexicográfica. Serão realizados experimentos em 20 conjuntos de dados públicos para avaliar o desempenho da nova versão do HEAD-DT, e compará-lo com os tradicionais algoritmos de árvore de decisão C4.5 e CART, além da versão original do algoritmo HEAD-DT. Os resultados mostram que a versão multiobjetiva do HEAD-DT é capaz de gerar algoritmos promissores quando comparados com C4.5, CART e a versão anterior do HEAD-DT, em relação à acurácia, f-measure e número de nós. Diante disso, este trabalho apresenta os primeiros esforços para transformar o HEAD-DT em um algoritmo multiobjetivo, isto é, capaz de guiar o processo de evolução por meio de dois ou mais objetivos.