ML Anthology

Algorithms for Optimal Dyadic Decision Trees

Don R. Hush, Reid B. Porter
MLJ 2010 pp. 85-107
doi:10.1007/S10994-010-5167-X /mlj/2010/hush2010mlj-algorithms/

Abstract

A dynamic programming algorithm for constructing optimal dyadic decision trees was recently introduced, analyzed, and shown to be very effective for low dimensional data sets. This paper enhances and extends this algorithm by: introducing an adaptive grid search for the regularization parameter that guarantees optimal solutions for all relevant trees sizes, replacing the dynamic programming algorithm with a memoized recursive algorithm whose run time is substantially smaller for most regularization parameter values on the grid, and incorporating new data structures and data pre-processing steps that provide significant run time enhancement in practice.

PDF MLJ Semantic Scholar

Cite

Text

Hush and Porter. "Algorithms for Optimal Dyadic Decision Trees." Machine Learning, 2010. doi:10.1007/S10994-010-5167-X

Markdown

[Hush and Porter. "Algorithms for Optimal Dyadic Decision Trees." Machine Learning, 2010.](https://mlanthology.org/mlj/2010/hush2010mlj-algorithms/) doi:10.1007/S10994-010-5167-X

BibTeX

@article{hush2010mlj-algorithms,
  title     = {{Algorithms for Optimal Dyadic Decision Trees}},
  author    = {Hush, Don R. and Porter, Reid B.},
  journal   = {Machine Learning},
  year      = {2010},
  pages     = {85-107},
  doi       = {10.1007/S10994-010-5167-X},
  volume    = {80},
  url       = {https://mlanthology.org/mlj/2010/hush2010mlj-algorithms/}
}