Optimal decision trees for categorical data via integer programming
From MaRDI portal
Publication:2046341
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.
Recommendations
Cites work
- A Bayesian framework for learning rule sets for interpretable classification
- Classification and Regression via Integer Optimization
- Constructing optimal binary decision trees is NP-complete
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- Optimal classification trees
- Random forests
Cited in
(26)- Learning certifiably optimal rule lists for categorical data
- Learning decision trees with flexible constraints and objectives using integer optimization
- Interpretable machine learning: fundamental principles and 10 grand challenges
- Shattering inequalities for learning optimal decision trees
- Column generation based heuristic for learning classification trees
- Sparsity in optimal randomized classification trees
- Optimal randomized classification trees
- On sparse optimal regression trees
- Robust optimal classification trees under noisy labels
- Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded
- Optimization of tree ensembles
- Building more accurate decision trees with the additive tree
- Decision trees with optimal joint partitioning
- Optimal classification trees
- SAT-based optimal classification trees for non-binary data
- Margin optimal classification trees
- On optimal regression trees to detect critical intervals for multivariate functional data
- Optimal multivariate decision trees
- An improved column-generation-based matheuristic for learning classification trees
- Supervised feature compression based on counterfactual analysis
- Loss-optimal classification trees: a generalized framework and the logistic case
- Integrated estimate-and-optimize decision trees learning for two-stage linear decision-making problems
- Rule generation for classification: scalability, interpretability, and fairness
- Optimal shapelets tree for time series interpretable classification
- Towards a trade-off of interpretability, accuracy and scalability: enhanced formulations in linear classification models
- Mathematical optimization in classification and regression trees
This page was built for publication: Optimal decision trees for categorical data via integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046341)
