Constructing optimal binary decision trees is NP-complete

DOI10.1016/0020-0190(76)90095-8zbMath0333.68029OpenAlexW1970074386WikidataQ56340228 ScholiaQ56340228MaRDI QIDQ1228355

Laurent Hyafil, Ronald L. Rivest

Publication date: 1976

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(76)90095-8

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

On the difficulty of designing good classifiers ⋮ Learning optimal decision trees using constraint programming ⋮ Sequential testing of complex systems: a review ⋮ On Tackling Explanation Redundancy in Decision Trees ⋮ Performance bounds for binary testing with arbitrary weights ⋮ Mathematical optimization in classification and regression trees ⋮ Efficient sequential decision-making algorithms for container inspection operations ⋮ Learning multicriteria classification models from examples: decision rules in continuous space ⋮ On the hardness of the minimum height decision tree problem ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Point probe decision trees for geometric concept classes ⋮ Reconstructing strings from substrings (Extended abstract) ⋮ bsnsing: A Decision Tree Induction Method Based on Recursive Optimal Boolean Rule Composition ⋮ Totally optimal decision trees for Boolean functions ⋮ A multi-tree committee to assist port-of-entry inspection decisions ⋮ Discrete decision theory: manipulations ⋮ An improved test selection optimization model based on fault ambiguity group isolation and chaotic discrete PSO ⋮ An experimental evaluation of simplicity in rule learning ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ HHCART: an oblique decision tree ⋮ Inferring decision trees using the minimum description length principle ⋮ Searching in random partially ordered sets ⋮ Shattering inequalities for learning optimal decision trees ⋮ Optimization and analysis of decision trees and rules: dynamic programming approach ⋮ Profit driven decision trees for churn prediction ⋮ Wrappers for feature subset selection ⋮ Recognizing polygonal parts width measurements ⋮ Optimal randomized classification trees ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ On sparse optimal regression trees ⋮ Data science applications to string theory ⋮ SAT-based optimal classification trees for non-binary data ⋮ A branch \& bound algorithm to determine optimal cross-splits for decision tree induction ⋮ Margin optimal classification trees ⋮ Sequential model-based diagnosis by systematic search ⋮ Optimal decision trees for the algorithm selection problem: integer programming based approaches ⋮ Supervised classification of curves via a combined use of functional data analysis and tree-based methods ⋮ On the Impact and Proper Use of Heuristics in Test-Driven Ontology Debugging ⋮ Theoretical analysis of git bisect ⋮ On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods ⋮ End-to-end learning of decision trees and forests ⋮ Conversational recommendation: theoretical model and complexity analysis ⋮ Multi-stage optimization of decision and inhibitory trees for decision tables with many-valued decisions ⋮ Inductive learning models with missing values ⋮ Balanced \(k\)-means clustering on an adiabatic quantum computer ⋮ A framework for inherently interpretable optimization models ⋮ Approximating optimal binary decision trees ⋮ Classification via two-way comparisons (extended abstract) ⋮ Decision-theoretic troubleshooting: hardness of approximation ⋮ Unnamed Item ⋮ \textsc{Treant}: training evasion-aware decision trees ⋮ Logical analysis of data: classification with justification ⋮ Unnamed Item ⋮ A study of search algorithms' optimization speed ⋮ Adaptive Submodular Ranking and Routing ⋮ Decision trees unearth return sign predictability in the S&P 500 ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Queries revisited. ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Hardness and inapproximability of minimizing adaptive distinguishing sequences ⋮ Discriminating Traces with Time ⋮ A Global Search Approach for Inducing Oblique Decision Trees Using Differential Evolution ⋮ Unnamed Item ⋮ Minimization of decision trees is hard to approximate ⋮ Bi-criteria optimization of decision trees with applications to data analysis ⋮ The binary identification problem for weighted trees ⋮ Learning decision trees with flexible constraints and objectives using integer optimization ⋮ Modular learning models in forecasting natural phenomena. ⋮ Learning local transductions is hard ⋮ Computer science and decision theory ⋮ Optimal classification trees ⋮ Regularizing axis-aligned ensembles via data rotations that favor simpler learners ⋮ Optimization problems for machine learning: a survey ⋮ Decision tree approximations of Boolean functions ⋮ Optimal decision trees for feature based parameter tuning: integer programming model and VNS heuristic ⋮ Chosen-Ciphertext Security from Subset Sum ⋮ Column generation based heuristic for learning classification trees ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Decision trees based on 1-consequences ⋮ Optimal decision trees for categorical data via integer programming ⋮ Electronic circuit diagnostic expert systems - a survey ⋮ Sparsity in optimal randomized classification trees ⋮ Profinite Rigidity in the SnapPea Census ⋮ Adaptive estimation of multivariate piecewise polynomials and bounded variation functions by optimal decision trees ⋮ A note on the comparison of five heuristic optimization techniques of a certain class of decision trees ⋮ Supervised Deep Learning in High Energy Phenomenology: a Mini Review* ⋮ Reduction of the number of particles in the stochastic weighted particle method for the Boltzmann equation ⋮ Variation of critical point of aging transition in a networked oscillators system ⋮ Optimal mistake bound learning is hard ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ Interpretable machine learning: fundamental principles and 10 grand challenges ⋮ Stochastic dynamic programming with factored representations ⋮ FINDING SMALL EQUIVALENT DECISION TREES IS HARD ⋮ Solving feature subset selection problem by a parallel scatter search ⋮ Stochastic Tree Search for Estimating Optimal Dynamic Treatment Regimes ⋮ Approximations to clustering and subgraph problems on trees ⋮ Unnamed Item ⋮ Optimal survival trees ⋮ Decision Trees for Geometric Models

Cites Work

• On the computational power of pushdown automata
• Combining decision rules in a decision table
• Reducibility among Combinatorial Problems
• Conversion of limited-entry decision tables to computer programs
• Optimal Binary Identification Procedures
• The complexity of theorem-proving procedures

This page was built for publication: Constructing optimal binary decision trees is NP-complete