Optimal Generalized Decision Trees via Integer Programming

Abstract

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.

References in corpus (3)

• Scikit-learn: Machine Learning in Python
• Efficient non-greedy optimization of decision trees
• Learning Optimized Or's of And's

Cited by in corpus (12)

• Sparsity in Optimal Randomized Classification Trees
• Decision Trees for Decision-Making under the Predict-then-Optimize Framework
• Born-Again Tree Ensembles
• Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information
• Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information
• Learning Optimal Classification Trees: Strong Max-Flow Formulations
• Optimal Sparse Decision Trees
• Interpretable and Fair Boolean Rule Sets via Column Generation
• Rule Covering for Interpretation and Boosting
• IPBoost -- Non-Convex Boosting via Integer Programming
• Fair Decision Rules for Binary Classification
• Dive into Decision Trees and Forests: A Theoretical Demonstration