Decision Tree Construction Via Linear Programming

By Kristin P. Bennett. 1992

How researchers see this paper

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

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, background): “In Bennett (1992), the hyperplane that minimizes the average distance from the misclassified individuals to the hyperplane is modeled as an LP problem, while in Bennett and Blue (1996), for a fixed topology of the tree and fixed predictions at the leaf nodes, the problem of finding the optimal obliq”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “Solvers have been used from the 1990’s (Bennett, 1992; Bennett & Blue, 1996) to the present (Verwer & Zhang, 2019; Blanquero et al., 2018; Nijssen et al., 2020; Bertsi-mas & Dunn, 2017; Rudin & Ertekin, 2018; Menickelly et al., 2018; Vilas Boas et al., 2019), but these generic solvers tend to be…”
Optimal Decision Trees (1996, methodology): “Greedy multivariate decision tree algorithms such as those in [2, 10, 24] construct decisions one at a time using linear combinations of all the attributes.”
An Optimal Constrained Pruning Strategy for Decision Trees (2009, methodology): “In another optimization-related tree construction method, Bennett (1992) proposes a linear programming model for determining linear-combination splits at nodes for two-class decision trees. Also, Bennett (1994) has studied how splitting decisions should be made at each level of a given particular fi”
Multivariate decision trees using linear discriminants and tabu search (2003, methodology): “Linear-programmingbased multivariate tree algorithms were developed in [3] and [34], and a multivariate classification tree method involving the use of stepwise regression was proposed in [49].”
Born-Again Tree Ensembles (2020, methodology): “Bennett (1992) used linear programming to construct trees with linear combination splits and showed that this technique performs better than conventional univariate split algorithms.”
Global Tree Optimization: A Non-greedy Decision Tree Algorithm (2007, methodology): “This type of decision has been used in greedy algorithms [6, 1].”
Optimization Models for Machine Learning: A Survey (2019, methodology): “Since building optimal binary decision trees is known to be NP-hard [122], heuristic approaches based on mathematical programming paradigms, such as linear optimization [21], continuous optimization [22], dynamic programming [8, 10, 74, 175], have been proposed.”
Bilinear separation of two sets inn-space (1993, methodology): “The w1 = w2 case for the uncoupled problem was practically avoided by starting with a good initial solution found by using the rst two planes of the MultisurfaceMethod-Tree algorithm [4, 6].”
Recent advances in decision trees: an updated survey (2022, methodology): “Although approaches of this line of research can be traced back to the ‘90s (Bennett 1992; Bennett and Blue 1996), the idea has only gained steam with the technical advances of modern optimization solvers (Bertsimas and Dunn 2017).”
Optimal trees for prediction and prescription (2018, background): “Nevertheless, there have been many efforts previously to develop effective ways of constructing optimal univariate decision trees using a variety of heuristic methods for growing the tree in one step, including linear optimization [7], continuous optimization [8], dynamic programming [37, 99], genet”
Oblique Multicategory Decision Trees Using Nonlinear Programming (2005, methodology): “Section 5 concludes the paper and discusses future directions for this research.”