DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers

MD Saifur Rahman Mazumder; Feng Yu

cs.LGAug 20, 2026

DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers

Authors: MD Saifur Rahman Mazumder, Feng Yu

Organizations: Department of Mathematical Sciences University of Texas at El Paso

Abstract

Decision tree-based models are widely used in machine learning due to their interpretability and strong empirical performance. However, training decision trees can be computationally expensive, particularly for large and high-dimensional datasets, largely due to the exhaustive search over candidate splits at each node. To improve computational efficiency, we propose Data-Informed Centroid Splitting (DICS), a clustering-based framework that constructs a compact and informative set of candidate splits using data-driven priors. By incorporating class-aware structure, DICS significantly reduces the split search space for classification tasks while preserving predictive performance. We further provide theoretical analysis showing that under the stated assumptions, DICS does not degrade the performance of classification trees compared to exhaustive split search. DICS can be incorporated into classification trees, random forests, and gradient-boosting models. Extensive experiments demonstrate that DICS achieves comparable accuracy while substantially reducing training time across synthetic and benchmark datasets, highlighting the benefit of integrating data-informed priors into split selection for scalable classification tree learning.

Figures & tables

Panel of Figure 1 — Figure 1: Illustrative example: (left) classification vs. clustering boundaries; (right) midpoint vs. variance-adjusted boundaries.

$(N,P)$	Class	Time (sec) $\downarrow$			Speedup $\uparrow$	Test Acc $\uparrow$
$(N,P)$	Class	DT	BDTKS	CGCT	$t_{\mathrm{DT}}/t_{\mathrm{CGCT}}$	DT	BDTKS	CGCT
10000,1000	3	2.47 (0.03)	30.16	0.19 (0.02)	13.00	0.62 (0.00)	0.54	0.60 (0.00)
	5	2.53 (0.01)	34.36	0.25 (0.02)	10.12	0.54 (0.00)	0.39	0.52 (0.00)
	10	2.52 (0.00)	35.68	0.29 (0.02)	8.69	0.43 (0.00)	0.32	0.41 (0.00)
5000,7000	3	8.36 (0.10)	29.85	0.58 (0.05)	14.41	0.61 (0.01)	0.57	0.59 (0.01)
	5	8.14 (0.03)	29.44	0.91 (0.04)	8.94	0.47 (0.01)	0.38	0.45 (0.00)

Table 1: Accuracy and training time (in seconds) for DT, BDTKS, and CGCT in synthetic data. The ratio

t_{\mathrm{DT}}/t_{\mathrm{CGCT}}

quantifies the training time improvement of CGCT relative to DT.

$(N,P)$	Class	Time (sec) $\downarrow$		Speedup $\uparrow$	Test Acc $\uparrow$
$(N,P)$	Class	RF	CGRF	$t_{\mathrm{RF}}/t_{\mathrm{CGRF}}$	RF	CGRF
10000,1000	3	4.05 (0.13)	0.36 (0.04)	11.25	0.64 (0.00)	0.64 (0.00)
	5	4.32 (0.02)	0.41 (0.03)	10.54	0.56 (0.01)	0.56 (0.00)
	10	4.25 (0.04)	0.53 (0.02)	8.02	0.45 (0.01)	0.45 (0.01)
5000,7000	3	13.27 (0.45)	0.93 (0.10)	14.27	0.64 (0.00)	0.64 (0.01)
	5	13.18 (0.05)	1.14 (0.05)	11.56	0.53 (0.00)	0.52 (0.00)

Table 2: Accuracy and training time (in seconds) for RF and CGRF in synthetic data. The ratio

t_{\mathrm{RF}}/t_{\mathrm{CGRF}}

quantifies the training time improvement of CGRF relative to RF.

$(N,P)$	Class	Time (sec) $\downarrow$			Speedup $\uparrow$		Test Acc $\uparrow$
$(N,P)$	Class	XGBoost	LightGBM	FastC-GBM	$\rho_{1}$	$\rho_{2}$	XGBoost	LightGBM	FastC-GBM
10000,1000	3	1.62 (0.03)	1.16 (0.06)	0.32 (0.00)	5.06	3.62	0.68 (0.00)	0.68 (0.0)	0.65 (0.01)
	5	2.66 (0.07)	1.81 (0.07)	0.35 (0.00)	7.60	5.17	0.59 (0.01)	0.60 (0.01)	0.59 (0.01)
	10	5.03 (0.02)	3.31 (0.0)	0.51 (0.01)	9.86	6.49	0.47 (0.01)	0.46 (0.01)	0.45 (0.01)
5000,7000	3	6.62 (0.06)	3.09 (0.03)	0.24 (0.00)	27.58	12.87	0.63 (0.00)	0.63 (0.02)	0.61 (0.02)
	5	11.25 (0.09)	4.96 (0.07)	0.28 (0.00)	40.18	17.71	0.51 (0.02)	0.50 (0.02)	0.50 (0.02)

Table 3: Accuracy and training time (in seconds) for XGBoost, LightGBM and FastC-GBM in synthetic data. The ratios

\rho_{1}=t_{\mathrm{XGBoost}}/t_{\mathrm{FastC-GBM}}

and

\rho_{2}=t_{\mathrm{LightGBM}}/t_{\mathrm{FastC-GBM}}

quantify the training time improvement of FastC-GBM relative to XGBoost and LightGBM, respectively.

	Train time (s) $\downarrow$			Speedup $\uparrow$	Test Acc $\uparrow$
Dataset	DT	CGCT	BDTKS	$t_{DT}/t_{CGCT}$	DT	CGCT	BDTKS
Helena	1.30	0.12	470.25	10.83	0.28	0.26	0.16
Spambase	0.02	0.01	5.42	2.00	0.95	0.93	0.79
Santander	17.99	0.83	714.26	21.67	0.91	0.90	0.85
CIFAR-10	42.63	3.33	533.91	12.80	0.34	0.31	0.29
MNIST	3.27	0.99	124.42	3.30	0.83	0.79	0.91

Table 4: Accuracy and training time (in seconds) for DT, BDTKS, and CGCT in real datasets. The ratio

t_{\mathrm{DT}}/t_{\mathrm{CGCT}}

quantifies the training time improvement of CGCT relative to DT.

	Train time (s) $\downarrow$		Speedup $\uparrow$	Test Acc $\uparrow$
Dataset	RF	CGRF	$t_{\mathrm{RF}}/t_{\mathrm{CGRF}}$	RF	CGRF
Helena	1.43 (0.12)	0.22 (0.02)	6.50	0.29 (0.00)	0.28 (0.00)
Spambase	0.09 (0.00)	0.03 (0.01)	3.00	0.95 (0.00)	0.94 (0.00)
Santander	22.04 (0.46)	3.12 (0.04)	7.06	0.90 (0.00)	0.90 (0.00)
CIFAR-10	55.96 (2.47)	4.37 (0.12)	12.80	0.40 (0.01)	0.38 (0.01)
MNIST	5.24 (0.25)	2.28 (0.02)	2.30	0.93 (0.00)	0.92 (0.00)

Table 5: Accuracy and training time (in seconds) for RF and CGRF in real datasets. The ratio

t_{\mathrm{RF}}/t_{\mathrm{CGRF}}

quantifies the training time improvement of CGRF relative to RF.

	Train time (s) $\downarrow$			Speedup $\uparrow$		Test Acc $\uparrow$
Dataset	XGBoost	LightGBM	FastC-GBM	$\rho_{1}$	$\rho_{2}$	XGBoost	LightGBM	FastC-GBM
Helena	13.01 (0.14)	13.38 (0.15)	5.48 (0.26)	2.37	2.44	0.35 (0.00)	0.23 (0.00)	0.32 (0.00)
Spambase	0.20 (0.00)	0.16 (0.01)	0.06 (0.00)	3.34	2.67	0.95 (0.00)	0.95 (0.00)	0.94 (0.00)
Santander	0.91 (0.03)	1.09 (0.02)	1.12 (0.01)	0.81	0.97	0.90 (0.00)	0.90 (0.00)	0.90 (0.00)
CIFAR-10	52.50 (0.86)	26.57 (0.29)	2.80 (0.04)	18.75	9.49	0.45 (0.00)	0.48 (0.00)	0.46 (0.00)
MNIST	29.42 (0.07)	4.33 (0.01)	2.55 (0.04)	11.54	1.70	0.94 (0.00)	0.95 (0.00)	0.95 (0.00)

Table 6: Accuracy and training time (in seconds) for XGBoost, LightGBM and FastC-GBM in real datasets. The ratios

\rho_{1}=t_{\mathrm{XGBoost}}/t_{\mathrm{FastC-GBM}}

and

\rho_{2}=t_{\mathrm{LightGBM}}/t_{\mathrm{FastC-GBM}}

quantify the training time improvement of FastC-GBM relative to XGBoost and LightGBM, respectively.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Parameter sensitivity of CGCT on CIFAR-10 with respect to (a) the maximum number of cluster pairs ( $m$ ), (b) the maximum number of feature-threshold pairs ( $k$ ), (c) the maximum tree depth ( $D$ ), and (d) the mini-batch size ( $b$ ). Each point represents the mean test accuracy over 50 runs, and error bars denote $\pm 3$ standard deviations.

	Mean Local Gain $\bar{g}_{d}$		Weighted Gain $G_{d}^{(w)}$		Cumulative Gain $C_{d}$		$R_{d}$ (%)
Depth	DT	CGCT	DT	CGCT	DT	CGCT
1	0.019	0.019	0.019	0.019	0.019	0.019	100.00
2	0.013	0.012	0.012	0.012	0.031	0.031	99.46
3	0.015	0.014	0.013	0.013	0.044	0.043	98.04
4	0.015	0.015	0.013	0.013	0.057	0.057	99.37
5	0.018	0.017	0.013	0.013	0.070	0.070	99.40

Appendix

Table 7: Depth-wise impurity reduction of independently grown exhaustive DT and CGCT on CIFAR-10 with maximum depth

D=8

, where Depth 1 denotes the root level. For depth

d

\bar{g}_{d}=|\mathcal{I}_{d}|^{-1}\sum_{j\in\mathcal{I}_{d}}g_{j}

is the mean local Gini gain,

G_{d}^{(w)}=\sum_{j\in\mathcal{I}_{d}}(n_{j}/N)g_{j}

is the sample-weighted impurity reduction,

C_{d}=\sum_{r=1}^{d}G_{r}^{(w)}

is the cumulative weighted gain, and

R_{d}=C_{d}^{\mathrm{CGCT}}/C_{d}^{\mathrm{DT}}

is the cumulative gain retained by CGCT relative to exhaustive DT.

$N$	Gain Gap $\Delta_{G}$	$\sqrt{N}\,\Delta_{G}$
1,000	0.0039	0.1227
2,000	0.0025	0.1100
5,000	0.0017	0.1183
10,000	0.0012	0.1242
20,000	0.0011	0.1492

Appendix

Table 8: Split-level gain gap between DICS and exhaustive DT across increasing sample sizes. Results are averaged over 40 independent runs.

$(N,P)$	Class	Time (sec) $\downarrow$			Speedup $\uparrow$	ACC $\uparrow$
$(N,P)$	Class	DT	BDTKS	CGCT	$t_{\mathrm{DT}}/t_{\mathrm{CGCT}}$	DT	BDTKS	CGCT
10000,1000	3	2.59 (0.02)	31.84	0.18 (0.02)	14.39	0.67 (0.00)	0.53	0.65 (0.00)
	5	2.49 (0.00)	35.54	0.27 (0.02)	9.22	0.50 (0.00)	0.31	0.49 (0.00)
	10	2.64 (0.00)	38.21	0.30 (0.02)	8.80	0.46 (0.00)	0.30	0.44 (0.01)
5000,7000	3	8.15 (0.09)	29.65	0.63 (0.03)	12.94	0.69 (0.00)	0.62	0.68 (0.01)
	5	8.56 (0.04)	29.83	0.92 (0.05)	9.30	0.39 (0.00)	0.30	0.37 (0.01)

Appendix

Table 9: Accuracy and training time (in seconds) for DT, BDTKS, and CGCT in real datasets. The ratio

t_{\mathrm{DT}}/t_{\mathrm{CGCT}}

quantifies the training time improvement of CGCT relative to DT. Here

\rho=0

$(N,P)$	Class	Time (sec) $\downarrow$		Speedup $\uparrow$	ACC $\uparrow$
$(N,P)$	Class	RF	CGRF	$t_{\mathrm{RF}}/t_{\mathrm{CGRF}}$	RF	CGRF
10000,1000	3	4.16 (0.04)	0.34 (0.02)	12.23	0.70 (0.00)	0.70 (0.00)
	5	4.13 (0.05)	0.39 (0.00)	10.59	0.54 (0.00)	0.54 (0.01)
	10	4.54 (0.00)	0.50 (0.02)	9.08	0.47 (0.00)	0.47 (0.00)
5000,7000	3	13.67 (0.46)	0.86 (0.07)	15.89	0.73 (0.00)	0.73 (0.01)
	5	14.13 (0.15)	1.22 (0.03)	11.58	0.44 (0.01)	0.44 (0.00)

Appendix

Table 10: Accuracy and training time (in seconds) for RF and CGRF in synthetic data. The ratio

t_{\mathrm{RF}}/t_{\mathrm{CGRF}}

quantifies the training time improvement of CGRF relative to RF. Here

\rho=0

$(N,P)$	Class	Time (sec) $\downarrow$			Speedup $\uparrow$		ACC $\uparrow$
$(N,P)$	Class	XGBoost	LightGBM	CGXGB	$\rho_{1}$	$\rho_{1}$	XGBoost	LightGBM	CGXGB
10000,1000	3	1.43 (0.01)	0.97 (0.00)	0.30 (0.01)	4.77	3.23	0.71 (0.01)	0.71 (0.01)	0.70 (0.01)
	5	2.36 (0.00)	1.59 (0.00)	0.37 (0.00)	6.38	4.30	0.54 (0.00)	0.55 (0.01)	0.55 (0.01)
	10	4.50 (0.01)	2.93 (0.01)	0.44 (0.01)	10.23	6.66	0.48 (0.01)	0.47 (0.02)	0.45 (0.01)
5000,7000	3	6.73 (0.05)	3.13 (0.06)	0.24 (0.01)	28.04	13.04	0.75 (0.02)	0.75 (0.02)	0.74 (0.01)
	5	10.81 (0.23)	4.80 (0.15)	0.29 (0.00)	37.28	16.55	0.41 (0.02)	0.41 (0.02)	0.38 (0.01)

Appendix

Table 11: Accuracy and training time (in seconds) for XGBoost, LightGBM and FastC-GBM in synthetic data. The ratios

\rho_{1}=t_{\mathrm{XGBoost}}/t_{\mathrm{FastC-GBM}}

and

\rho_{2}=t_{\mathrm{LightGBM}}/t_{\mathrm{FastC-GBM}}

quantify the training time improvement of FastC-GBM relative to XGBoost and LightGBM, respectively. Here

\rho=0

Dataset	$\mathbf{N}$	$\mathbf{P}$	$\mathbf{K}$
Helena	65,196	27	100
Spambase	4,601	57	2
Santander	200,000	200	2
CIFAR-10	60,000	3,072	10
MNIST	70,000	784	10
Fashion-MNIST	70,000	784	10

Appendix

Table 12: Summary of datasets used in the experiments, including sample size (

N

), number of features (

P

), and number of classes (

K

Decision Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

Search Strategies for Optimal Classification and Regression Trees
Jul 30, 2026Jacobus G. M. van der Linden, Mim van den Bos, Emir DemirovićDecision Tree Learning Classification
Delft University of Technology
Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
Sep 5, 2026Jiancheng Tu, Wenqi FanDecision Tree Learning Dynamic Programming
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Adaptive MSD-Splitting: Enhancing C4.5 and Random Forests for Skewed Continuous Attributes
Apr 21, 2026Jake LeeDecision Tree Learning Random Forest
Independent Researcher · Austin, TX, USA

Jul 30, 2026J/K move · Enter open · S save

Search Strategies for Optimal Classification and Regression Trees

Jacobus G. M. van der Linden, Mim van den Bos, Emir Demirović

Delft University of Technology

Decision Tree Learning Classification

Open paper AskPDF arXiv

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.

Abstract

Decision Tree Learning

Explore similar work

Search Strategies for Optimal Classification and Regression Trees

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

Adaptive MSD-Splitting: Enhancing C4.5 and Random Forests for Skewed Continuous Attributes