Files

ida2024_efficient_lookehead_decision_trees.pdf
  • Open Access
  • Adobe PDF
  • 476.76 KB
Download

Details

Authors
Abstract
Conventionally, decision trees are learned using a greedy ap- proach, beginning at the root and moving toward the leaves. At each in- ternal node, the feature that yields the best data split is chosen based on a metric like information gain. This process can be regarded as evaluating the quality of the best depth-one subtree. To address the shortsightedness of this method, one can generalize it to greater depths. Lookahead trees have demonstrated strong performance in situations with high feature in- teraction or low signal-to-noise ratios. They constitute a good trade-off between optimal decision trees and purely greedy decision trees. Cur- rently, there are no readily available tools for constructing these looka- head trees, and their computational cost can be significantly higher than that of purely greedy ones. In this study, we introduce an efficient imple- mentation of lookahead decision trees, specifically LGDT, by adapting a recently introduced algorithmic concept from the MurTree approach to find optimal decision trees of depth two. Additionally, we utilize an effi- cient reversible sparse bitset data structure to store the filtered examples while expanding the tree nodes in a depth-first-search manner. Experi- ments on state-of-the-art datasets demonstrate that our implementation offers remarkable computation-time performance.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Kiossou, H., Schaus, P., Nijssen, S., & Aglin, F. (2024). Efficient Lookahead Decision Trees. Lecture Notes in Computer Science : Advances in Intelligent Data Analysis XXII, p. 133-144. https://doi.org/10.1007/978-3-031-58553-1_11