Advanced search
Start date

Multi-objective hyper-heuristics for automatic design of multi-test decision tree induction algorithms

Grant number: 16/02870-0
Support type:Regular Research Grants
Duration: June 01, 2016 - July 31, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Márcio Porto Basgalupp
Grantee:Márcio Porto Basgalupp
Home Institution: 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, Brazil
Assoc. researchers: Alex Alves Freitas ; André Carlos Ponce de Leon Ferreira de Carvalho ; Rodrigo Coelho Barros


Decision-tree induction is one of the most employed methods to extract knowledge from data, since the representation of knowledge is very intuitive and easily understandable by humans. There are several distinct strategies for inducing decision trees from data, each one presenting advantages and disadvantages according to its corresponding inductive bias. In previous work, we proposed the algorithm HEAD-DT, a Hyper-Heuristic Evolutionary Algorithm for Automatically Designing Decision-Tree Induction Algorithms. HEAD-DT works over several manually-designed decision-tree components which were developed in the last 40 years, and following a typical evolutionary algorithm search, it combines the most suitable components for the task at hand. Recently, it was proposed a multi-test approach to decision trees in which several univariate tests can be used to create a single splitting rule in every non-terminal node of the classification tree. In contrast with the traditional univariate decision trees, the MTDT induction algorithms have some particularity. The splitting criterion, for example, can be directed by the majority voting mechanism where all univariate test components have the same importance. However, many other strategies could be developed for this task. In this context, we propose extending the HEAD-DT algorithm in two main aspects: (i) automatically evolving multi-test decision tree induction algorithms, with some extensions; and (ii) incorporating three multi-objectives approaches to guide the evolutionary process. In a nut shell, the solution provided by the GP is a decision tree induction algorithm capable of solving any classification problem rather than a single decision tree tailored according to a specific dataset. With that in mind, this project is actually proposing the development of a meta-learning algorithm, since it is an algorithm that learns a learning algorithm. (AU)