Quasi-optimal decision trees: bridging greedy heuristics and global optimization
摘要
This paper introduces a quasi-optimal decision tree (QODT) framework for constructing interpretable decision trees. In classification settings, this framework is referred to as quasi-optimal classification trees (QOCTs). The proposed approach aims to bridge the gap between greedy decision tree induction and computationally expensive globally optimized tree construction. Instead of relying solely on one-step split heuristics, QODT constructs optimization-based subtrees of limited depth at each branching step. This allows the method to incorporate deeper structural information into local decisions while avoiding the full computational burden of end-to-end optimal tree construction. As a result, the framework provides a practical trade-off between computational cost, interpretability, and predictive performance. The proposed method does not guarantee global optimality, but it offers a structured approximation that is more informative than purely greedy approaches. By recursively solving smaller optimization problems of bounded depth, QODT enables the construction of deeper trees under computationally tractable settings. Experimental results on benchmark datasets indicate that QOCT achieves predictive performance generally comparable to CART and, in some cases, to optimal classification trees (OCTs), while preserving interpretability. Compared with full-depth optimal tree construction, the method reduces computational requirements in practice, making it a useful intermediate alternative between purely greedy methods and fully optimal decision tree approaches.