Decision-tree induction is one of the most employed methods to extract knowledge from data. There are several distinct strategies for inducing decision trees from data, each one presenting advantages and disadvantages according to its corresponding inductive bias. These strategies have been continuously improved by researchers over the last 40 years. This thesis, following recent breakthroughs in the automatic design of machine learning algorithms, proposes to automatically generate decision-tree induction algorithms. Our proposed approach, namely HEAD-DT, is based on the evolutionary algorithms paradigm, which improves solutions based on metaphors of biological processes. HEAD-DT works over several manually-designed decision-tree components and combines the most suitable components for the task at hand. It can operate according to two different frameworks: i) evolving algorithms tailored to one single data set (specific framework); and ii) evolving algorithms from multiple data sets (general framework). The specific framework aims at generating one decision-tree algorithm per data set, so the resulting algorithm does not need to generalise beyond its target data set. The general framework has a more ambitious goal, which is to generate a single decision-tree algorithm capable of being effectively applied to several data sets. The specific framework is tested over 20 UCI data sets, and results show that HEAD-DTs specific algorithms outperform algorithms like CART and C4.5 with statistical significance. The general framework, in turn, is executed under two different scenarios: i) designing a domain-specific algorithm; and ii) designing a robust domain-free algorithm. The first scenario is tested over 35 microarray gene expression data sets, and results show that HEAD-DTs algorithms consistently outperform C4.5 and CART in different experimental configurations. The second scenario is tested over 67 UCI data sets, and HEAD-DTs algorithms were shown to be competitive with C4.5 and CART. Nevertheless, we show that HEAD-DT is prone to a special case of overfitting when it is executed under the second scenario of the general framework, and we point to possible alternatives for solving this problem. Finally, we perform an extensive experiment for evaluating the best single-objective fitness function for HEAD-DT, combining 5 classification performance measures with three aggregation schemes. We evaluate the 15 fitness functions in 67 UCI data sets, and the best of them are employed to generate algorithms tailored to balanced and imbalanced data. Results show that the automatically-designed algorithms outperform CART and C4.5 with statistical significance, indicating that HEAD-DT is also capable of generating custom algorithms for data with a particular kind of statistical profile / Árvores de decisão são amplamente utilizadas como estratégia para extração de conhecimento de dados. Existem muitas estratégias diferentes para indução de árvores de decisão, cada qual com suas vantagens e desvantagens tendo em vista seu bias indutivo. Tais estratégias têm sido continuamente melhoradas por pesquisadores nos últimos 40 anos. Esta tese, em sintonia com recentes descobertas no campo de projeto automático de algoritmos de aprendizado de máquina, propõe a geração automática de algoritmos de indução de árvores de decisão. A abordagem proposta, chamada de HEAD-DT, é baseada no paradigma de algoritmos evolutivos. HEAD-DT evolui componentes de árvores de decisão que foram manualmente codificados e os combina da forma mais adequada ao problema em questão. HEAD-DT funciona conforme dois diferentes frameworks: i) evolução de algoritmos customizados para uma única base de dados (framework específico); e ii) evolução de algoritmos a partir de múltiplas bases (framework geral). O framework específico tem por objetivo gerar um algoritmo por base de dados, de forma que o algoritmo projetado não necessite de poder de generalização que vá além da base alvo. O framework geral tem um objetivo mais ambicioso: gerar um único algoritmo capaz de ser efetivamente executado em várias bases de dados. O framework específico é testado em 20 bases públicas da UCI, e os resultados mostram que os algoritmos específicos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor do que algoritmos como CART e C4.5. O framework geral é executado em dois cenários diferentes: i) projeto de algoritmo específico a um domínio de aplicação; e ii) projeto de um algoritmo livre-de-domínio, robusto a bases distintas. O primeiro cenário é testado em 35 bases de expressão gênica, e os resultados mostram que o algoritmo gerado por HEAD-DT consistentemente supera CART e C4.5 em diferentes configurações experimentais. O segundo cenário é testado em 67 bases de dados da UCI, e os resultados mostram que o algoritmo gerado por HEAD-DT é competitivo com CART e C4.5. No entanto, é mostrado que HEAD-DT é vulnerável a um caso particular de overfitting quando executado sobre o segundo cenário do framework geral, e indica-se assim possíveis soluções para tal problema. Por fim, é realizado uma análise detalhada para avaliação de diferentes funções de fitness de HEAD-DT, onde 5 medidas de desempenho são combinadas com três esquemas de agregação. As 15 versões são avaliadas em 67 bases da UCI e as melhores versões são utilizadas para geração de algoritmos customizados para bases balanceadas e desbalanceadas. Os resultados mostram que os algoritmos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor que CART e C4.5, em uma clara indicação que HEAD-DT também é capaz de gerar algoritmos customizados para certo perfil estatístico dos dados de classificação

Decision-tree induction is one of the most employed methods to extract knowledge from data. There are several distinct strategies for inducing decision trees from data, each one presenting advantages and disadvantages according to its corresponding inductive bias. These strategies have been continuously improved by researchers over the last 40 years. This thesis, following recent breakthroughs in the automatic design of machine learning algorithms, proposes to automatically generate decision-tree induction algorithms. Our proposed approach, namely HEAD-DT, is based on the evolutionary algorithms paradigm, which improves solutions based on metaphors of biological processes. HEAD-DT works over several manually-designed decision-tree components and combines the most suitable components for the task at hand. It can operate according to two different frameworks: i) evolving algorithms tailored to one single data set (specific framework); and ii) evolving algorithms from multiple data sets (general framework). The specific framework aims at generating one decision-tree algorithm per data set, so the resulting algorithm does not need to generalise beyond its target data set. The general framework has a more ambitious goal, which is to generate a single decision-tree algorithm capable of being effectively applied to several data sets. The specific framework is tested over 20 UCI data sets, and results show that HEAD-DTs specific algorithms outperform algorithms like CART and C4.5 with statistical significance. The general framework, in turn, is executed under two different scenarios: i) designing a domain-specific algorithm; and ii) designing a robust domain-free algorithm. The first scenario is tested over 35 microarray gene expression data sets, and results show that HEAD-DTs algorithms consistently outperform C4.5 and CART in different experimental configurations. The second scenario is tested over 67 UCI data sets, and HEAD-DTs algorithms were shown to be competitive with C4.5 and CART. Nevertheless, we show that HEAD-DT is prone to a special case of overfitting when it is executed under the second scenario of the general framework, and we point to possible alternatives for solving this problem. Finally, we perform an extensive experiment for evaluating the best single-objective fitness function for HEAD-DT, combining 5 classification performance measures with three aggregation schemes. We evaluate the 15 fitness functions in 67 UCI data sets, and the best of them are employed to generate algorithms tailored to balanced and imbalanced data. Results show that the automatically-designed algorithms outperform CART and C4.5 with statistical significance, indicating that HEAD-DT is also capable of generating custom algorithms for data with a particular kind of statistical profile / Árvores de decisão são amplamente utilizadas como estratégia para extração de conhecimento de dados. Existem muitas estratégias diferentes para indução de árvores de decisão, cada qual com suas vantagens e desvantagens tendo em vista seu bias indutivo. Tais estratégias têm sido continuamente melhoradas por pesquisadores nos últimos 40 anos. Esta tese, em sintonia com recentes descobertas no campo de projeto automático de algoritmos de aprendizado de máquina, propõe a geração automática de algoritmos de indução de árvores de decisão. A abordagem proposta, chamada de HEAD-DT, é baseada no paradigma de algoritmos evolutivos. HEAD-DT evolui componentes de árvores de decisão que foram manualmente codificados e os combina da forma mais adequada ao problema em questão. HEAD-DT funciona conforme dois diferentes frameworks: i) evolução de algoritmos customizados para uma única base de dados (framework específico); e ii) evolução de algoritmos a partir de múltiplas bases (framework geral). O framework específico tem por objetivo gerar um algoritmo por base de dados, de forma que o algoritmo projetado não necessite de poder de generalização que vá além da base alvo. O framework geral tem um objetivo mais ambicioso: gerar um único algoritmo capaz de ser efetivamente executado em várias bases de dados. O framework específico é testado em 20 bases públicas da UCI, e os resultados mostram que os algoritmos específicos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor do que algoritmos como CART e C4.5. O framework geral é executado em dois cenários diferentes: i) projeto de algoritmo específico a um domínio de aplicação; e ii) projeto de um algoritmo livre-de-domínio, robusto a bases distintas. O primeiro cenário é testado em 35 bases de expressão gênica, e os resultados mostram que o algoritmo gerado por HEAD-DT consistentemente supera CART e C4.5 em diferentes configurações experimentais. O segundo cenário é testado em 67 bases de dados da UCI, e os resultados mostram que o algoritmo gerado por HEAD-DT é competitivo com CART e C4.5. No entanto, é mostrado que HEAD-DT é vulnerável a um caso particular de overfitting quando executado sobre o segundo cenário do framework geral, e indica-se assim possíveis soluções para tal problema. Por fim, é realizado uma análise detalhada para avaliação de diferentes funções de fitness de HEAD-DT, onde 5 medidas de desempenho são combinadas com três esquemas de agregação. As 15 versões são avaliadas em 67 bases da UCI e as melhores versões são utilizadas para geração de algoritmos customizados para bases balanceadas e desbalanceadas. Os resultados mostram que os algoritmos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor que CART e C4.5, em uma clara indicação que HEAD-DT também é capaz de gerar algoritmos customizados para certo perfil estatístico dos dados de classificação

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.