Column generation based heuristic for learning classification trees
From MaRDI portal
Publication:2289946
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Computational aspects of data analysis and big data (68T09) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Integer programming (90C10)
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.
Recommendations
- A procedure for improving generalization in classification trees
- scientific article; zbMATH DE number 2032414
- A novel algorithm to optimize classification trees
- Optimization of classification trees: Strategy and algorithm improvement
- A heuristic multi-class hierarchical tree structure construction method of support vector machine
- Generating decision tree from lattice for classification
Cites work
- A branch-and-price algorithm for stable workforce assignments with hierarchical skills
- A column generation approach for an employee scheduling problem with multiple shifts and work locations
- A column generation approach to airline crew scheduling
- A Linear Programming Approach to the Cutting-Stock Problem
- A suggested computation for maximal multi-commodity network flows
- An Algorithm for Constructing Optimal Binary Decision Trees
- Auction optimization using regression trees and linear models as integer programs
- Constructing optimal binary decision trees is NP-complete
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- scientific article; zbMATH DE number 4166922 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Learning decision trees with flexible constraints and objectives using integer optimization
- Optimal classification trees
- Optimal decision trees for categorical data via integer programming
- Routing with time windows by column generation
- Selected Topics in Column Generation
Cited in
(13)- On sparse optimal regression trees
- On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods
- On optimal regression trees to detect critical intervals for multivariate functional data
- New optimization models for optimal classification trees
- An improved column-generation-based matheuristic for learning classification trees
- Optimal classification trees with leaf-branch and binary constraints
- The MIP workshop 2023 computational competition on reoptimization
- Progressively strengthening and tuning MIP solvers for reoptimization
- An integrated data envelopment analysis and regression tree method for new product price estimation
- Rule generation for classification: scalability, interpretability, and fairness
- Learning-based column generation approach for the vehicle routing problem with release dates and incompatible loading constraints
- Towards a trade-off of interpretability, accuracy and scalability: enhanced formulations in linear classification models
- Mathematical optimization in classification and regression trees
This page was built for publication: Column generation based heuristic for learning classification trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2289946)
