Optimal Generalized Decision Trees via Integer Programming

By Matt Menickelly, Oktay Günlük, Jayant R. Kalagnanam, Katya Scheinberg. 2016

33 citations recorded by the source corpus.

Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mixed integer programming formulation to construct optimal decision trees of a prespecified size. We take the special structure of categorical features into account and allow combinatorial decisions (based on subsets of values of features) at each node. Our approach can also handle numerical features via thresholding. We show that very good accuracy can be achieved with small trees using moderately-sized training sets. The optimization problems we solve are tractable with modern solvers.

Subfields: Artificial Intelligence, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mathematical Optimization

Citations in the corpus

Constructing classification trees using column generation (2018, methodology): “Finding optimal decision trees is known to be NP-hard (Hyafil and Rivest (1976)).”
Column generation based heuristic for learning classification trees (2020, methodology): “[18] propose an efficient MILP formulation for the problem of constructing classification trees for data with categorical features.”
Complete Search for Feature Selection in Decision Trees (2019, background): “Bertsimas and Dunn (2017) and Menickelly et al. (2016); Verwer and Zhang (2017) formulate tree induction as a mixed-integer optimization problem and as an integer programming problem respectively.”