Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.07903 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909455826812928 |
|---|---|
| author | Brita, Catalin E. van der Linden, Jacobus G. M. Demirović, Emir |
| author_facet | Brita, Catalin E. van der Linden, Jacobus G. M. Demirović, Emir |
| contents | Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound Brita, Catalin E. van der Linden, Jacobus G. M. Demirović, Emir Machine Learning Artificial Intelligence Data Structures and Algorithms Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics. |
| title | Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound |
| topic | Machine Learning Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.07903 |