Constructing classification trees using column generation
By Murat Firat, Guillaume Crognier, Adriana Felicia Gabor, Yingqian Zhang, Cor A. J. Hurkens. 2018
7 citations recorded by the source corpus.
This paper explores the use of Column Generation (CG) techniques in constructing univariate binary decision trees for classification tasks. We propose a novel Integer Linear Programming (ILP) formulation, based on paths in decision trees. We show that the associated pricing problem is NP-hard and propose a random procedure for column selection. In addition, to speed up column generation, we use a restricted parameter set via a sampling procedure using the well-known CART algorithm. Extensive numerical experiments show that our approach outperforms the state-of-the-art ILP-based algorithms in the recent literature both in computation time and solution quality. We also find better solutions that have higher training and testing accuracy than an optimized version of CART. Furthermore, our approach is capable of handling big data sets with tens of thousands of data rows, unlike other ILP-based algorithms. In addition, our approach has the advantage of being able to easily incorporate different objectives.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Emilio Carrizosa
- Rafael Blanquero
- Sicco Verwer
- Dolores Romero Morales
- Cristina Molero-Río
- Yingqian Zhang
- Vinícius G. Costa
- Cynthia Rudin
Citations in the corpus
- Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “…various Mathematical Optimization methods to build better quality decision trees, e.g., (Bennett and Blue 1996; Bessiere, Hebrard, and OSullivan 2009; Verwer and Zhang 2017; Bertsimas and Dunn 2017; Silva 2017; Dash, G ¨ unl ¨ uk, and Wei 2018; Blanquero et al. 2018a; 2018b; Firat et al. 2018).”
- Sparsity in Optimal Randomized Classification Trees (2020, background): “As stated in the introduction of the paper, CARTs, as many other approaches that implement orthogonal cuts [4, 14, 18], are leaders in terms of local sparsity.”