Column generation based heuristic for learning classification trees
By Murat Firat, Guillaume Crognier, Adriana Felicia Gabor, Cor A. J. Hurkens, Yingqian Zhang. 2020
28 citations recorded by the source corpus.
Abstract 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 root-to-leaf paths in decision trees. The model is solved via a Column Generation based heuristic. To speed up the heuristic, we use a restricted instance data by considering a subset of decision splits, sampled from the solutions of the well-known CART algorithm. Extensive numerical experiments show that our approach is competitive with the state-of-the-art ILP-based algorithms. In particular, the proposed approach is capable of handling big data sets with tens of thousands of data rows. Moreover, for large data sets, it finds solutions competitive to CART.
Subfields: Artificial Intelligence, Information Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Birol Yüceoglu
- S. Ilker Birbil
- Carlos Eduardo Pedreira
- Vinícius G. Costa
- Mert Edali
- Stefan Szeider
- André Schidler
- James W. Taylor
In Information Systems
Citations in the corpus
- Recent advances in decision trees: an updated survey (2022, background): “…several discrete choices, the formulations themselves are usually classified as either MIO ( Verwer and Zhang 2017; Bertsimas and Dunn 2017; Rhuggenaath et al. 2018; Aghaei et al. 2019; Firat et al. 2020; Günlük et al. 2021) or purely binary integer programming (BIP; Verwer and Zhang 2019).”
- Rule Covering for Interpretation and Boosting (2020, background): “[6] propose a column generation based heuristic for learning decision tree.”