Novos métodos de programação linear inteira mista para o problema das árvores de classificação ótimas

Abstract

Classification trees are very useful techniques in the field of machine learning due to the ease of human interpretation of their predictions. Motivated by the improvement of algorithms and hardware capacity for solving integer programming problems, recent works address the creation of optimal classification trees through linear models, the most general model being entitled Optimal Classification Trees (OCT). We propose in this work a reformulation of the OCT, valid inequalities based on the precedence graph of the learning input and a branch-and-cut strategy on the restrictions that depend on the number n of points that is very large in several instances of the literature. In addition, we present techniques and strategies to mitigate the high computational cost linked to this high dimensionality of points through their reduction, by means of heuristics and exact models, aiming to establish a trade-off between assertiveness, representativeness and models execution time. The results demonstrate that the model reformulation reduces on average 57% the computational time of the OCT, and that the precedence inequalities decrease in 58% the number of nodes solved by the branch-and-bound strategies.