Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach
Global optimization of decision trees is a long-standing challenge in combinatorial optimization, yet such models play an important role in interpretable machine learning. Although the problem has been investigated for several decades, only recent advances in discrete optimization have enabled practical algorithms for solving optimal classification tree problems on real-world datasets. Mixed-integer programming (MIP) offers a high degree of modeling flexibility, and we therefore propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics, such as the F1-score, that explicitly addresses class imbalance. To improve scalability, we develop problem-specific acceleration techniques, including a tailored branch-and-cut algorithm, an instance-reduction scheme, and warm-start strategies. We evaluate the proposed approach on 50 benchmark datasets. The computational results show that the framework can efficiently optimize nonlinear metrics while achieving strong predictive performance and reduced solution times compared with existing methods.
Code (0)
등록된 구현이 없습니다.
Tasks
Interpretable Machine LearningSimilar Papers 제목 키워드 기반
Optimal Generalized Decision Trees via Integer Programming
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.…
Mixed integer linear optimization formulations for learning optimal binary classification trees
Decision trees are powerful tools for classification and regression that attract many researchers working in the burgeoning area of machine learning. One advantage of decision trees over other methods is their interpreta…
Binary ClassificationClassificationLearning Optimal Classification Trees Robust to Distribution Shifts
We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health a…
ClassificationRobust classificationOptimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees
Multivariate decision trees are powerful machine learning tools for classification and regression that attract many researchers and industry professionals. An optimal binary tree has two types of vertices, (i) branching …
Binary ClassificationODTlearn: A Package for Learning Optimal Decision Trees for Prediction and Prescription
ODTLearn is an open-source Python package that provides methods for learning optimal decision trees for high-stakes predictive and prescriptive tasks based on the mixed-integer optimization (MIO) framework proposed in Ag…
Classification