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
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