Margin optimal classification trees
From MaRDI portal
Abstract: In recent years there has been growing attention to interpretable machine learning models which can give explanatory insights on their behavior. Thanks to their interpretability, decision trees have been intensively studied for classification tasks, and due to the remarkable advances in mixed-integer programming (MIP), various approaches have been proposed to formulate the problem of training an Optimal Classification Tree (OCT) as a MIP model. We present a novel mixed-integer quadratic formulation for the OCT problem, which exploits the generalization capabilities of Support Vector Machines for binary classification. Our model, denoted as Margin Optimal Classification Tree (MARGOT), encompasses the use of maximum margin multivariate hyperplanes nested in a binary tree structure. To enhance the interpretability of our approach, we analyse two alternative versions of MARGOT, which include feature selection constraints inducing local sparsity of the hyperplanes. First, MARGOT has been tested on non-linearly separable synthetic datasets in 2-dimensional feature space to provide a graphical representation of the maximum margin approach. Finally, the proposed models have been tested on benchmark datasets from the UCI repository. The MARGOT formulation turns out to be easier to solve than other OCT approaches, and the generated tree better generalizes on new observations. The two interpretable versions are effective in selecting the most relevant features and maintaining good prediction quality.
Cites work
- A brief history of linear and mixed-integer programming computation
- A mixed integer linear programming support vector machine for cost-effective group feature selection: branch-cut-and-price approach
- A novel embedded min-max approach for feature selection in nonlinear support vector machine classification
- Constructing optimal binary decision trees is NP-complete
- Feature selection for support vector machines via mixed integer linear programming
- Greedy function approximation: A gradient boosting machine.
- HHCART: an oblique decision tree
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- scientific article; zbMATH DE number 5430994 (Why is no real title available?)
- scientific article; zbMATH DE number 1304261 (Why is no real title available?)
- scientific article; zbMATH DE number 1149432 (Why is no real title available?)
- Interpretable machine learning: fundamental principles and 10 grand challenges
- Learning decision trees with flexible constraints and objectives using integer optimization
- LIBLINEAR: a library for large linear classification
- Massive data discrimination via linear support vector machines
- Mathematical optimization in classification and regression trees
- Mixed integer linear programming for feature selection in support vector machine
- Multivariate classification trees based on minimum features discrete support vector machines
- Multivariate decision trees
- Nonlinear optimization and support vector machines
- On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods
- Optimal classification trees
- Optimal decision trees for categorical data via integer programming
- Optimal randomized classification trees
- Optimization problems for machine learning: a survey
- Random forests
- Robust optimal classification trees under noisy labels
- Shattering inequalities for learning optimal decision trees
- Sparsity in optimal randomized classification trees
- Support vector machines: theory and applications.
- Support-vector networks
- The doubly regularized support vector machine
Cited in
(5)- New optimization models for optimal classification trees
- An improved column-generation-based matheuristic for learning classification trees
- Loss-optimal classification trees: a generalized framework and the logistic case
- Feature and functional form selection in additive models via mixed-integer optimization
- 50 years of mixed-integer nonlinear and disjunctive programming
This page was built for publication: Margin optimal classification trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065640)
