Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
Cătălin E. Brița, Jacobus G. M. van der Linden, Emir Demirović
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.
BibTeX
@article{Brița_van der Linden_Demirović_2025, title={Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33210}, DOI={10.1609/aaai.v39i11.33210}, abstractNote={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.}, number={11}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Brița, Cătălin E. and van der Linden, Jacobus G. M. and Demirović, Emir}, year={2025}, month={Apr.}, pages={11131-11139} }