ETD

• classification
• decision tree induction
• evolutionary algorithms
• generative models
• variational autoencoder

Decision trees are among the most popular classification algorithms due to their knowledge representation that resembles human reasoning and is easy to understand. Commonly used decision tree induction methods, such as the CART algorithm, are based on a greedy top-down strategy. Although this approach is known to be an efficient heuristic, the resulting trees are only locally optimal and tend to have overly complex structures. An alternative way to search the parameter space of trees is to use global optimization methods such as evolutionary algorithms. In this thesis, I propose the GEN-Tree hybrid algorithm for the induction of decision trees. The first stage of the method consists of training a VAE model using various decision tree classifiers decoded in the form of linear chromosomes. Next, a genetic algorithm is used to explore the latent space of the trained VAE, with the aim of finding a decision tree with good predictive performance and a small size. I compared GEN-Tree with greedy and ensemble techniques using nine publicly available datasets. The results show that GEN-Tree is able to induce accurate decision trees with very low complexity, making them very interpretable.