Improving Decision Trees through the Lens of Parameterized Local Search
Preprint
Abstract
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The influence of dimensions on the complexity of computing decision treesArtificial Intelligence, 2025
- Multi-GPU approach to global induction of classification trees for large-scale data miningApplied Intelligence, 2021
- Evolutionary induction of a decision tree for large-scale data: a GPU-based approachSoft Computing, 2016
- Data Mining: Practical Machine Learning Tools and Techniques2011
- Lossless fitness inheritance in genetic algorithms for decision treesSoft Computing, 2009
- Parameterized Complexity of Vertex Cover VariantsTheory of Computing Systems, 2007
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- Constructing optimal binary decision trees is NP-completeInformation Processing Letters, 1976