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

• Grant number: 16/02870-0
• Support Opportunities: Regular Research Grants
• Start date: June 01, 2016
• End date: July 31, 2018
• 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 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
• Associated researchers: Alex Alves Freitas ; André Carlos Ponce de Leon Ferreira de Carvalho ; Rodrigo Coelho Barros

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 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)

Scientific publications

(6)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

FRANCISQUINI, RODRIGO; NASCIMENTO, MARIA C. V.; BASGALUPP, MARCIO P.; IEEE. NGA-LP: A robust and improved genetic algorithm to detect communities in directed networks. 2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2018-01-01. (16/02870-0, 15/21660-4)

SOUSA, ARUA DE M.; LORENA, ANA C.; BASGALUPP, MARCIO P.; IEEE. GEEK: Grammatical Evolution for automatically Evolving Kernel functions. 2017 16TH IEEE INTERNATIONAL CONFERENCE ON TRUST, SECURITY AND PRIVACY IN COMPUTING AND COMMUNICATIONS / 11TH IEEE INTERNATIONAL CONFERENCE ON BIG DATA SCIENCE AND ENGINEERING / 14TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE AND SYSTEMS, v. N/A, p. 8-pg., 2017-01-01. (12/22608-8, 16/02870-0)

BASGALUPP, MARCIO; CERRI, RICARDO; SCHIETGAT, LEANDER; TRIGUERO, ISAAC; VENS, CELINE. Beyond global and local multi-target learning. INFORMATION SCIENCES, v. 579, p. 508-524, NOV 2021. (16/02870-0)

CARDOSO, KARLA R.; CINTRA, MARCOS E.; BASGALUPP, MARCIO; IEEE. Extracting Rules for Black Jack Using Machine Learning and Fuzzy Systems. 2018 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ-IEEE), v. N/A, p. 6-pg., 2018-01-01. (16/02870-0)

SANTOS, JEFERSON S.; SAVII, RICARDO M.; IDE, JAIME S.; LI, CHIANG-SHAN R.; QUILES, MARCOS G.; BASGALUPP, MARCIO P.; GERVASI, O; MURGANTE, B; MISRA, S; BORRUSO, G; et al. Classification of Cocaine Dependents from fMRI Data Using Cluster-Based Stratification and Deep Learning. COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2017, PT I, v. 10404, p. 16-pg., 2017-01-01. (16/16291-2, 16/02870-0)

MIQUILINI, PATRICIA; ROSSI, RAFAEL G.; QUILES, MARCOS G.; DE MELO, VINICIUS V.; BASGALUPP, MARCIO P.; IEEE. Automatically Design Distance Functions for Graph-based Semi-Supervised Learning. 2017 16TH IEEE INTERNATIONAL CONFERENCE ON TRUST, SECURITY AND PRIVACY IN COMPUTING AND COMMUNICATIONS / 11TH IEEE INTERNATIONAL CONFERENCE ON BIG DATA SCIENCE AND ENGINEERING / 14TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE AND SYSTEMS, v. N/A, p. 8-pg., 2017-01-01. (16/00868-9, 16/02870-0)