Learning decision trees through Monte Carlo tree search: An empirical evaluation
- 24 February 2020
- journal article
- research article
- Published by Wiley in WIREs Data Mining and Knowledge Discovery
- Vol. 10 (3)
Abstract
Decision trees (DTs) are a widely used prediction tool, owing to their interpretability. Standard learning methods follow a locally optimal approach that trades off prediction performance for computational efficiency. Such methods can however be far from optimal, and it may pay off to spend more computational resources to increase performance. Monte Carlo tree search (MCTS) is an approach to approximate optimal choices in exponentially large search spaces. We propose a DT learning approach based on the Upper Confidence Bound applied to tree (UCT) algorithm, including procedures to expand and explore the space of DTs. To mitigate the computational cost of our method, we employ search pruning strategies that discard some branches of the search tree. The experiments show that proposed approach outperformed the C4.5 algorithm in 20 out of 31 datasets, with statistically significant improvements in the trade‐off between prediction performance and DT complexity. The approach improved locally optimal search for datasets with more than 1,000 instances, or for smaller datasets likely arising from complex distributions.This article is categorized under: Algorithmic Development > Hierarchies and Trees Application Areas > Data Mining Software Tools Fundamental Concepts of Data and Knowledge > Data ConceptsKeywords
Funding Information
- European Union Horizon 2020 Research and Innovation Programme (Grant agreement 642676 (Cardiofunxion))
- Maria de Maeztu Units of Excellence Programme (MDM-2015-0502)
- Spanish Ministry of Economy and Competitiveness (Grant TIN2014-52923-R)
This publication has 23 references indexed in Scilit:
- KEEL: a software tool to assess evolutionary algorithms for data mining problemsSoft Computing, 2008
- A working guide to boosted regression treesJournal of Animal Ecology, 2008
- Top-Down Induction of Decision Trees Classifiers—A SurveyIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2005
- Greedy function approximation: A gradient boosting machine.The Annals of Statistics, 2001
- Bagging predictorsMachine Learning, 1996
- Induction of decision treesMachine Learning, 1986
- An Exploratory Technique for Investigating Large Quantities of Categorical DataJournal of the Royal Statistical Society Series C: Applied Statistics, 1980
- Constructing optimal binary decision trees is NP-completeInformation Processing Letters, 1976
- Individual Comparisons by Ranking MethodsBiometrics Bulletin, 1945
- The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of VarianceJournal of the American Statistical Association, 1937