Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
Authors: Jiancheng Tu, Wenqi Fan
Organizations: Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.
Figures & tables
Figure 1: One Adaptive STreeD refinement cycle. Candidate restriction reduces p features to qt , and aggregation maps n projected records to ut weighted unique records before the inner solve.
Data set
Samples
Original features
Binary features
Classes
COMPAS
12,381
22
230
2
Diabetic
101,766
47
544
3
Give Me Some Credit
150,000
10
375
2
FICO
10,459
23
758
2
Transactions
786,363
113
653
2
Table 1: Data sets used in the computational experiments
Figure 2: Runtime distributions by maximum tree depth. Boxes show interquartile ranges and center lines show medians. The dashed line marks the 600-second time limit.
Figure 3: Training and test accuracy by data set and maximum tree depth. Points show five-split means and error bars show sample standard deviations.
Data set
Pairs
Mean comp.
Mean sp.
Max sp.
Faster
Same
Better
COMPAS
30
10.19
2.44
7.48
23/30
30/30
0
Diabetic
30
39.05
3.83
36.68
18/30
28/30
2
Give Me Some Credit
30
281.68
9.53
40.02
20/30
27/30
3
FICO
30
98.78
2.14
7.96
19/30
30/30
0
Transactions
30
538.46
23.05
121.41
20/30
23/30
7
All
150
193.63
8.20
121.41
100/150
138/150
12
Table 2: Weighted aggregation ablation on five binarized data sets
Figure 4: Effect of weighted unique-data aggregation under fixed candidate sets. The dashed line in panel (b) indicates equal recorded runtime between standard STreeD and Weighted STreeD.
Figure 5: Sensitivity to candidate-set capacity K . Runtime curves show depth-specific medians on a logarithmic scale, with shaded interquartile ranges. Accuracy curves report mean matched test-accuracy differences relative to K=20 in percentage points.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Max bins
Mean binary feat.
Median runtime (s)
D=4 runtime (s)
Limit share
Mean train acc.
Mean test acc.
Median comp.
5
100.8
1.50
7.74
6.7%
0.79291
0.78772
1.28
10
139.0
2.96
59.07
13.3%
0.79526
0.79065
1.07
20
201.6
7.30
444.87
13.3%
0.79616
0.79275
1.06
50
344.2
33.67
606.12
26.7%
0.79663
0.79273
1.02
100
512.0
119.71
609.26
33.3%
0.79670
0.79256
1.01
Appendix
Table 3: Sensitivity of Weighted STreeD to the maximum number of quantile bins
Figure 6: Sensitivity to the maximum number of quantile bins. Panel (a) reports the median recorded runtime over the five data sets at each depth; the dashed line marks the nominal 600-second limit. Panel (b) reports the mean test-accuracy difference relative to B=100 for each data set, averaged over depths 2–4. Positive values favor the indicated binning level. Time-limited runs contribute their best feasible incumbents.
Symbol
Meaning
Scope
I
Original training set
Fixed input data
F
Full feature index set {1,…,p}
Full post-binarization space
S
Candidate split-feature set
Fixed within one DP solve
q
Candidate-set size, q=∣S∣
Fixed within one DP solve
D
Maximum tree depth
Feasible tree class
M
Maximum number of internal split nodes
Feasible tree class
Appendix
Table 4: Notation used in the weighted unique-data dynamic program.
K
Successful
Runtime
Train acc.
Test acc.
Runtime/ K=20
Test diff. (pp)
10
150
7.95 [2.29–22.30]
0.7942±0.1420
0.7892±0.1449
0.788
-0.127
15
150
9.29 [2.72–24.74]
0.7953±0.1415
0.7896±0.1447
0.897
-0.088
20
150
10.48 [3.35–27.44]
0.7965±0.1408
0.7905±0.1443
1.000
0.000
25
150
17.99 [4.42–30.66]
0.7976±0.1408
0.7907±0.1448
1.110
0.027
30
150
20.89 [6.39–33.48]
0.7982±0.1404
0.7909±0.1447
1.241
0.039
35
149
27.45 [8.19–39.61]
0.7995±0.1403
0.7916±0.1448
1.563
0.064
Appendix
Table 5: Sensitivity of Adaptive STreeD to candidate-set capacity
We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal value and recovery of an optimal tree. The reduced model supports two solution methods: column generation and message passing. Column generation solves integral restricted LPs and uses bounds over the full feasible domain to certify optimality. Message passing recursively combines optimal subtree costs. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.
Jiancheng TU, WenqiFan
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Optimal decision trees (ODTs) are compact, interpretable machine learning models that globally optimize a given objective, but their scalability remains challenging. While recent work has proposed a variety of search strategies to improve scalability, the precise contribution of each strategy remains unclear. To address this gap, we introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones. This provides a common lens through which to understand and compare different strategies, which we use to empirically investigate the effect of 18 search strategies. Compared to the state of the art, the best strategy in our evaluation achieves significantly better anytime performance for classification, and improves runtime by more than an order of magnitude for regression.
Jacobus G. M. van der Linden, Mim van den Bos, Emir Demirović
Despite the importance for interpretability, decision trees face severe scalability challenges. Existing global optimal methods are often limited by binary feature selection and shallow tree depths, whereas traditional heuristic approaches frequently sacrifice predictive accuracy. To overcome these limitations, this paper proposes a moving-horizon approximate branch-and-reduce method to train near-optimal deep classification trees on large-scale datasets with continuous features. Built on a hierarchical root-subtree optimization framework, the method solves the root-level problem via branch-and-reduce while approximating the induced subtree problem using greedy heuristics. Although the underlying framework is capable of guaranteeing global optimality, the approximation, which functions as a lookahead rollout in a reinforcement learning context, significantly boosts efficiency for deeper structures. A low-cost moving-horizon strategy is then employed to iteratively refine model accuracy. Extensive numerical results demonstrate that our method exceeds the testing accuracy of existing heuristic baselines while offering significantly greater scalability, in terms of both dataset size and tree depth, than global optimal solvers.
Chenxuanyin Zou, Jiayang Ren, Qiangqiang Mao +3
Department of Chemical and Biological Engineering University of British Columbia · Department of Electrical and Computer Engineering University of British Columbia · Department of Computer Science University of British Columbia