📊 statistics

DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers

The paper proposes Data-Informed Centroid Splitting (DICS), a clustering-based framework that significantly accelerates decision tree training by using data-driven priors to reduce the split search space while maintaining comparable predictive accuracy and offering theoretical performance guarantees.

Original authors: MD Saifur Rahman Mazumder, Feng Yu

Published 2026-08-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: MD Saifur Rahman Mazumder, Feng Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, there exists a family of tools known as decision trees. Imagine a flowchart that asks a series of simple yes-or-no questions about a piece of data—such as whether an email contains certain words or whether a patient's blood pressure exceeds a specific level—to arrive at a final conclusion. These models are beloved by data scientists because they are easy to understand and often very accurate. However, there is a significant cost to building them. To create the most effective flowchart, a computer must examine millions of possible questions at every single step, searching for the perfect split that separates one group of data from another. This exhaustive search is like trying to find a needle in a haystack by checking every single piece of straw one by one; it works, but it takes a tremendous amount of time and computing power, especially when the data is large and complex.

Researchers at the University of Texas at El Paso have proposed a new way to speed up this process without sacrificing accuracy. They call their method Data-Informed Centroid Splitting, or DICS. Instead of blindly checking every possible question, the new approach uses a preliminary step to understand the general shape of the data. It groups similar data points together and identifies the centers of these groups. By looking at the boundaries between these centers, the method generates a short, smart list of the most promising questions to ask. This allows the computer to skip the vast majority of useless options and focus only on the splits that are likely to matter. The result is a system that learns much faster while still making the same correct predictions as the slower, traditional methods.

The core idea behind this work relies on a simple observation: data points that belong to the same category tend to cluster together in the digital space. If you were to map out thousands of customer records or biological samples, the items of the same type would naturally form tight groups. The researchers reasoned that the lines separating these groups are likely to be the same lines that separate the different categories in a classification task. To test this, they first used a standard clustering technique to find the center of each group of similar data points. They then calculated the midpoints between these centers to create a set of candidate questions. To make this even more precise, they adjusted these midpoints based on how spread out the data was within each group, ensuring the dividing lines were fair even if one group was more scattered than another.

This approach stands in contrast to older methods that try to speed up tree building by simply rounding off data values or using random guesses. While those techniques can be fast, they often lose important details or require the computer to make many more guesses to find a good answer. The new method, however, is guided by the actual structure of the data. The researchers showed that by using this clustering guide, they could reduce the number of questions the computer needs to ask by a massive margin. In their tests, they found that the new method could train a decision tree up to twenty-two times faster than the standard approach on synthetic data, and up to twenty-one times faster on real-world datasets, with almost no drop in accuracy.

The team did not stop at single decision trees; they applied this same logic to more powerful systems that combine many trees together, such as random forests and gradient boosting machines. These ensemble methods are often the most accurate tools available for complex tasks, but they are also the most computationally expensive. By integrating the data-informed splitting strategy into these larger systems, the researchers achieved similar dramatic speedups. For instance, on a dataset involving over twenty thousand records, the new method trained a random forest in less than two seconds, whereas the standard method took over forty-four seconds. The accuracy remained nearly identical, proving that the speed came from efficiency, not from cutting corners on the quality of the model.

To ensure their findings were robust, the researchers tested their method on a wide variety of real-world challenges, including detecting spam emails, identifying fraudulent financial transactions, and classifying images of clothing and digits. In every case, the new approach maintained its lead in speed. On the Spambase dataset, for example, the traditional method took a fraction of a second, but the new method was twice as fast. On the larger Santander dataset, which contained two hundred thousand records, the new method was more than seven times faster. Even on complex image recognition tasks like CIFAR-10, where the data is notoriously difficult to process, the new method was nearly thirteen times faster than the standard decision tree while keeping the error rate low.

The researchers also provided a mathematical proof to support their observations. They demonstrated that as the amount of data grows, the difference between the splits chosen by their new method and the splits chosen by the exhaustive search becomes vanishingly small. Essentially, the method is guaranteed to find a split that is nearly as good as the absolute best possible one, provided the data follows certain natural patterns. This theoretical backing gives confidence that the speedup is not a lucky fluke but a reliable feature of the approach. The work suggests that by understanding the shape of the data before building the model, computers can make smarter decisions about where to look, saving vast amounts of time and energy.

While the current study focuses on classification tasks, where the goal is to sort data into distinct categories, the researchers acknowledge that the same principles could potentially be applied to regression problems, where the goal is to predict a specific number. They note that the method is currently limited to classification, but the success of the approach opens the door for future work to extend these efficiency gains to other types of machine learning. For now, the study offers a clear path forward for anyone working with large datasets who needs to build accurate models without waiting days for the computer to finish its calculations. By letting the data itself point the way, the researchers have shown that we can build smarter, faster trees without losing the strength of the forest.

Technical Summary: Data-Informed Centroid Splitting (DICS) for Decision Tree Classifiers

1. Problem Statement

Decision tree-based models, including their ensemble variants like Random Forests and Gradient Boosting Machines, are widely used for their interpretability and empirical performance. However, training these models faces a significant computational bottleneck: the exhaustive search for optimal splits at each node.

In standard decision tree induction, the algorithm evaluates every possible split point for every feature. For a dataset with $N$ samples and $P$ features, this involves sorting samples and evaluating up to $(N-1)P$ candidate splits per node. This process is computationally expensive, particularly for large-scale and high-dimensional datasets. While existing methods like histogram-based binning (e.g., in XGBoost and LightGBM) reduce this cost by discretizing features, they introduce quantization errors and require a trade-off between efficiency and accuracy. Furthermore, these methods lack prior guidance on which splits are likely to be informative, treating all candidate thresholds equally.

2. Methodology: Data-Informed Centroid Splitting (DICS)

The authors propose Data-Informed Centroid Splitting (DICS), a framework that leverages the structural information within the data to construct a compact, informative set of candidate splits, thereby reducing the search space without altering the underlying greedy tree objective.

Core Concept

The method is motivated by the observation that in classification tasks, samples of the same class tend to cluster together in the feature space. Consequently, the boundaries between these clusters often approximate the classification decision boundaries. DICS exploits this by using clustering to generate candidate split thresholds.

Algorithmic Steps

Clustering: The algorithm applies K-means clustering to the feature matrix $X$ to obtain $K$ centroids $\{\mu_c\}_{c=1}^K$ . These centroids represent dominant modes of the data distribution.
Boundary Generation: Instead of evaluating all possible thresholds, DICS generates candidate splits based on the boundaries between cluster centroids.
- For any pair of clusters $c_1$ and $c_2$ , a boundary is defined.
- Midpoint Boundary: The simplest boundary is the midpoint between centroids: $\zeta = \frac{1}{2}(\mu_{c_1} + \mu_{c_2})$ .
- Variance-Adjusted Boundary: To handle cases where clusters have different variances (dispersion), the authors propose a variance-adjusted boundary where the distance from the centroids to the split is proportional to their standard deviations ( $\hat{\sigma}$ ):
  $\zeta(\mu_{c_1}, \mu_{c_2}) = \frac{\hat{\sigma}_{c_1}\mu_{c_2} + \hat{\sigma}_{c_2}\mu_{c_1}}{\hat{\sigma}_{c_1} + \hat{\sigma}_{c_2}}$
Candidate Selection: There are $\binom{K}{2}$ possible centroid pairs. To avoid redundancy, the algorithm selects the top $m$ pairs with the largest inter-centroid distances. These pairs define the set of candidate thresholds for each feature.
Integration: The resulting set of candidate splits is used to grow the tree. This approach is integrated into:
- CGCT: Cluster-Guided Classification Tree (standard DT).
- CGRF: Cluster-Guided Random Forest.
- FastC-GBM: A gradient boosting machine that combines DICS with Gradient-based One-Side Sampling (GOSS) and feature subsampling.

Computational Complexity

Precomputation: DICS introduces a one-time overhead of $O(TKbP)$ using mini-batch K-means, where $T$ is iterations and $b$ is batch size. This is negligible compared to the split-finding stage.
Split Finding: The cost per node reduces from $O(NP)$ (exhaustive) or $O(H P)$ (histogram-based) to $O(mP)$ , where $m$ is the number of selected centroid pairs. Since $m$ is typically small (e.g., $m=10$ for $K=5$ ), this offers a significant reduction in complexity.

3. Theoretical Analysis

The paper provides a theoretical analysis (Theorem 1) to demonstrate that DICS does not degrade predictive performance asymptotically.

Assumptions: The analysis assumes a density regularity condition where the marginal density of features is bounded near the optimal split.
Result: The difference in the impurity gain between the optimal split found by exhaustive search (DT) and the optimal split found by DICS is bounded by $O(1/\sqrt{N})$ .
Implication: As the number of samples $N$ increases, the gap in performance between the two methods vanishes. The partitions induced by DICS differ from the optimal partitions on at most $O(\sqrt{N})$ samples, ensuring that the retained gain ratio remains high even at deeper tree levels.

4. Experimental Results

The authors evaluated DICS on both synthetic and real-world datasets, comparing it against standard Decision Trees (DT), Random Forests (RF), XGBoost, LightGBM, and the related method BDTKS.

Synthetic Data

Speedup: DICS-based models achieved substantial speedups.
- CGCT: 8–22x faster than standard DT.
- CGRF: 8–30x faster than standard RF.
- FastC-GBM: 5–50x faster than XGBoost and 3.6–27x faster than LightGBM.
Accuracy: The accuracy trade-off was marginal, typically within 0.02 of the baseline models.
Comparison: The related method BDTKS (which applies K-means recursively at every node) was found to be computationally expensive and did not offer advantages in speed or accuracy.

Real-World Datasets

Experiments were conducted on datasets including Helena, Spambase, Santander, CIFAR-10, MNIST, and Fashion-MNIST.

Efficiency: DICS consistently reduced training times. For example, CGCT was 2–21x faster than DT on real datasets. FastC-GBM was up to 18.75x faster than XGBoost.
Robustness: On the Helena dataset, LightGBM performed poorly, whereas FastC-GBM maintained stable performance, suggesting improved robustness.
Accuracy: While some datasets (e.g., CIFAR-10) showed a slight decrease in accuracy compared to synthetic settings, the drop remained small, and the method generally preserved predictive performance.

5. Significance and Claims

The paper claims that DICS offers a scalable solution for training tree-based classifiers by integrating data-informed priors into the split selection process.

Key Contribution: The primary contribution is the demonstration that clustering structure can serve as an effective prior to drastically reduce the split search space without compromising the greedy optimization objective of decision trees.
Modest Claims: The authors explicitly state that their theoretical results show DICS is asymptotically close to exhaustive search but do not claim it is superior in all cases. They acknowledge that the relationship between split gain and final classification accuracy is non-trivial.
Limitations and Future Work: The current framework is focused on classification. The authors identify extending this approach to regression tasks as a primary direction for future work. They also note that while the method is effective for classification, the performance on specific real-world datasets (like Santander) can be influenced by implementation-level memory management issues rather than the algorithm itself.

In summary, DICS provides a principled way to trade a negligible amount of search space for a massive reduction in computational cost, making it particularly valuable for large-scale, high-dimensional classification problems.