Column generation based math-heuristic for classification trees
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationMathMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
An improved column-generation-based matheuristic for learning classification trees
Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal trees in terms of accur…
ClassificationColumn generation for the discrete Unit Commitment problem with min-stop ramping constraints
The discrete unit commitment problem with min-stop ramping constraints optimizes the daily production of thermal power plants (coal, gas, fuel units). For this problem, compact Integer Linear Programming (ILP) formulatio…
Scalable Optimal Multiway-Split Decision Trees with Constraints
There has been a surge of interest in learning optimal decision trees using mixed-integer programs (MIP) in recent years, as heuristic-based methods do not guarantee optimality and find it challenging to incorporate cons…
ARCA Column Generation based Heuristic for the Tail Assignment Problem
This article proposes an efficient heuristic in accelerating the column generation by parallel resolution of pricing problems for aircrafts in the tail assignment problem (TAP). The approach is able to achieve considerab…
Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring
Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a sub-problem with a subset of columns (i.e., variables) and gradually includes new columns that can impro…
BIG-bench Machine Learning