Constructing Optimal Binary Decision Trees is NP-Complete.
Laurent HyafilRonald L. RivestPublished in: Inf. Process. Lett. (1976)
Keyphrases
- np complete
- decision trees
- computational complexity
- satisfiability problem
- dynamic programming
- worst case
- finding optimal
- np hard
- random forest
- machine learning
- decision tree learning
- predictive accuracy
- classification rules
- data sets
- phase transition
- non binary
- decision tree induction
- training data
- bounded treewidth
- polynomial time complexity