Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
Abstract
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.
Cite
Text
Brita et al. "Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I11.33210Markdown
[Brita et al. "Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/brita2025aaai-optimal/) doi:10.1609/AAAI.V39I11.33210BibTeX
@inproceedings{brita2025aaai-optimal,
title = {{Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound}},
author = {Brita, Catalin E. and van der Linden, Jacobus G. M. and Demirovic, Emir},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
pages = {11131-11139},
doi = {10.1609/AAAI.V39I11.33210},
url = {https://mlanthology.org/aaai/2025/brita2025aaai-optimal/}
}