Incorporating multi-test decision trees into the HEAD-DT algorithm

• Grant number: 15/13245-7
• Support Opportunities: Scholarships abroad - Research
• Start date: January 04, 2016
• End date: March 03, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Márcio Porto Basgalupp
• Grantee: Márcio Porto Basgalupp
• Host Investigator: Alex Alves Freitas
• Host 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
• Institution abroad: University of Kent, England
• Associated research grant: 10/20255-5 - Genetic programming for evolving decision tree induction algorithms, AP.JP

Abstract

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 an extension of the HEAD-DT algorithm to automatically evolve multi-test decision tree induction algorithms. 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.