Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning

Daniel Nowak Assis; Jean Paul Barddal; Fabrício Enembreck

Source-linked AI summary

Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning

Daniel Nowak Assis, Jean Paul Barddal, Fabrício Enembreck

arXiv:2608.16659v1Aug 17, 2026cs.LGcs.AI

TL;DR

Data-stream ensembles need tree learners that both adapt to concept drift and maintain diversity, but adaptive splitting alone can produce overly similar learners. The paper proposes Hoeffding Adaptive Splitting Trees, combining periodic and change-triggered splits; experiments show state-of-the-art ensemble performance, with gains up to sixteen F1-Score percentage points over Hoeffding Trees.

Problem
Adaptive tree base learners can lack diversity because similar early predictions drive change detectors to trigger closely aligned splits.
Method
Hoeffding Adaptive Splitting Trees combine periodic Hoeffding-style split attempts with change-detector-driven adaptive splitting at leaf nodes.
Results
The proposed trees achieve the best overall F1-Score, with gains reaching up to sixteen percentage points over Hoeffding Trees and strong results across ensembles.
Takeaways & Limitations
Pairing adaptive splitting with periodic Hoeffding splitting improves ensemble base learners, while the best tree–ensemble pairing depends on the ensemble.
Takeaways & Limitations
The proposed trees incur computational overhead from their change detectors, although experiments indicate that this overhead is not prohibitive.

Abstract

from arXiv · show

Ensembles of decision trees are well-established methods for data stream classification. In ensemble learning, Hoeffding Trees are widely adopted as base learners, performing periodic split attempts according to the Hoeffding bound. Recent studies, however, indicate that this standard splitting mechanism lacks adaptability, while adaptive trees that trigger splits in response to performance degradation have achieved superior results. In this paper, we identify limitations in the use of adaptive-splitting decision trees as ensemble base learners, showing that change detectors often fail to promote sufficient diversity within ensembles. To address this issue, we propose two novel decision tree models, termed Hoeffding Adaptive Splitting Trees. These models combine the periodic splitting strategy of Hoeffding Trees, which fosters ensemble diversity, with adaptive splitting mechanisms that employ change detection algorithms to identify performance decay and determine split points. Experimental results demonstrate that Hoeffding Adaptive Splitting Trees enhance ensemble performance and achieve state-of-the-art results across a comprehensive evaluation, including benchmark comparisons, computational cost analysis, and concept drift adaptation.

1 Introduction

Concept drift can reduce streaming-classification accuracy, while Hoeffding Trees’ periodic splitting supports ensemble learning but lacks adaptability. The paper proposes Hoeffding Adaptive Splitting Trees, combining periodic and change-triggered splitting to improve diversity and drift response in ensembles.

Motivation: Concept drift changes data distributions over time and can decrease model accuracy, requiring rapid detection and adaptation.For classification, drift occurs when the joint distribution P_t(X, Y) differs from P_t+∆(X, Y).
Existing methods: Hoeffding Trees incrementally expand through periodic split attempts as streams evolve and are widely used as ensemble base learners.Their splitting process relies on the Hoeffding Theorem.
Existing methods: LAST improves adaptability by splitting when change detectors flag performance or purity changes, but its per-model detectors can produce insufficient ensemble diversity.Correlated early tree outputs can induce similar splitting times across base learners.
Proposed approach: HASTs combine periodic splitting for ensemble diversity with adaptive splitting that tracks leaf performance or class-distribution purity and reacts to detected changes.The paper introduces two novel decision tree architectures for ensemble learning.
Contributions: The paper evaluates the proposed architectures through comprehensive experiments covering ensemble performance, computational cost, and concept-drift response.The stated contributions include state-of-the-art results in ensemble setups and directions for future ensemble development.

2 Background and Definitions

Data streams are continuous, potentially infinite sequences whose classification setting cannot feasibly store all data, requiring efficient stream-mining classifiers. Concept drift occurs when the joint distribution changes over time and can be characterized by distributional components and temporal patterns.

Data Streams: Data streams continuously deliver feature vectors over time without a predefined stopping point, often treated as potentially infinite.In structured streams, each datum is a feature vector x_t ∈ R^d.
Data Streams: Stream classification differs from batch classification because storing all arriving data is unfeasible, motivating efficient stream-mining classifiers.
Concept Drift: Concept drift occurs when the joint distribution P(x, y) changes between time t and t + Δ.The distribution decomposes as P(x, y) = P(x)P(y|x).
Concept Drift: Drift types include changes in P(x), changes in P(y|x), or simultaneous changes in both distributions, with temporal patterns ranging from abrupt to recurring.Abrupt, gradual, and incremental shifts describe transitions between concepts, while recurring scenarios allow previously observed concepts to reappear.

3 Online Decision Trees and Ensembles

Online decision-tree ensembles use incremental Hoeffding-based splitting, while adaptive trees use change detectors to respond to stream evolution. This section reviews their splitting criteria, resource requirements, and ensemble extensions for concept drift.

Hoeffding Trees: Hoeffding Trees periodically attempt leaf splits after every GP instances and accept a split when the Hoeffding criterion distinguishes the best attribute.The split test compares the highest- and second-highest-scoring attributes using G(Xa)−G(Xb) ≥ϵ.
Hoeffding Trees: The Hoeffding bound controls split decisions by bounding the difference between an observed mean and its expected value with confidence level δ.The bound uses R as the random variable’s range and n as the number of observations.
Adaptive Splitting: Hoeffding-based Trees are invariant to stream dynamics and performance, causing recurrent split attempts and limited structural change when leaf distributions change little.This fixed periodic policy can produce greedy split searches despite little change in the leaf.
Adaptive Splitting: LAST uses leaf-level change detectors monitoring impurity or error rate, triggering a split when change is detected and G(Xa) > 0.Because change detectors update continuously, they track stream evolution and control tree growth under the softest split constraint.
Ensemble Methods: Online Bagging induces ensemble diversity by training each learner on k copies drawn from Poisson(λ = 1), while ADWIN-based methods reset inaccurate members after detected drift.Leveraging Bagging instead samples from Poisson(λ = 6), making classifiers more specialized, and adds error output codes at increased computational cost.

4 Hoeffding Adaptive Splitting Trees Base Learners

HLAST and EFLAST combine adaptive change-detection-based splitting with periodic Hoeffding-bound split attempts to improve adaptability while preserving ensemble diversity. The proposed trees address correlated early predictions and add computational overhead that experiments show is not prohibitive.

Motivation: Adaptive splitting can produce highly correlated early predictions across ensemble members, undermining the diversity needed for strong ensemble performance.Incremental trees initially predict with either a majority-class classifier or Naive Bayes, causing members and their change detectors to receive highly similar inputs.
Design trade-off: The proposed trees retain periodic searches for the best splits while adding change-detector overhead.The paper reports experimentally that this computational overhead is not prohibitive.
HLAST: HLAST combines leaf-level change detectors with periodic Hoeffding-bound split attempts.Its detectors monitor predictive performance or class-distribution purity, and a flagged change triggers splitting when G(Xa) > 0 during a periodic attempt.
EFLAST: EFLAST combines periodic and adaptive splitting with split reevaluation at non-leaf nodes.It performs periodic splits when the Hoeffding condition is met or adaptive splits when change detection flags a change and G(Xa) > 0.

5 Methodology

The methodology evaluates the proposed tree models within diverse ensembles using reproducible MOA implementations, real-world and synthetic streams, and standardized prequential testing. It also assesses statistical significance and computational efficiency across the ensemble configurations.

Experimental setup: Experiments used Java implementations extending MOA, 13 real-world datasets, and 24 synthetic datasets on an Intel Core i7-12700H system with 16 GB RAM.Source code and additional results are publicly available in the paper’s support repository.
Ensemble configurations: All ensembles contained 100 base learners, used MOA default parameters, and included SRP, ARE, and ARTE alongside ensembles evaluated previously.The study also considered SGBT but reports that many datasets required a week of continuous processing.
Evaluation protocol: Predictive performance was measured with prequential test-then-train evaluation, averaging metrics over 20 evenly spaced points in each stream.Additional points did not materially change the results.
Statistical analysis: Ensemble results were compared using a Friedman test at 1% significance and one-sided Wilcoxon signed-rank post-hoc tests with Holm correction.The statistical rankings were visualized in diagrams, with connected methods indicating no statistically significant difference.
Efficiency analysis: Computational evaluation covered CPU time, peak RAM usage in MB over time, and mean ensemble tree size measured by node count.These metrics were presented as violin plots sorted by median.

6 Results

The proposed HLAST and HLASTD trees outperform standard and original adaptive trees mainly on challenging, multi-class real-world streams, while offering little advantage on synthetic data. HLASTD is especially effective with SRP and ARTE, with ARTE-HLASTD recommended for strongest and most consistent real-world performance.

Real-world results: The proposed trees achieve their largest gains on multi-class datasets, reaching up to 16 percentage points on LADPU and around 10 points on Outdoor and Rialto.The gains concentrate on datasets with more classes, including Outdoor, Rialto, Poker, LADPU, CoverType, and INSECTS variants.
Ensemble-specific behavior: HLASTD is best suited to SRP because it avoids continued growth on weak feature subsets that can bias accuracy-weighted voting, whereas HLAST is better suited to ensembles such as ARTE.HLAST is the weakest of the three base learners under SRP, with standard HT outperforming it in roughly 70% of cases.
Synthetic results: The proposed trees have little effect on synthetic data, where F1-Score differences to HT remain close to zero and the best result alternates among ensembles and trees.The benchmark’s synthetic generators use simple linear concepts or binary patterns that are learned quickly, and ensembles react similarly to drift.
Real-world results: HLAST and HLASTD are among the best-performing base trees on real-world data, while LAST and LASTD are the weakest ensemble base learners.The proposed trees surpass HT and EFDT, whereas the original adaptive trees show median performance below HT.
Overall comparison: ARTE with HLASTD is the recommended combination, achieving the strongest and most consistent results on real-world data.ARTE’s random feature percentages and cut points already induce diversity, while the proposed trees split at more informed moments than fixed intervals.
Computational cost: ARTE with HLASTD has higher tree-size quantiles than ARTE with HT but similar CPU-Time quantiles, while ARTE’s random splitting reduces split-checking and background-classifier maintenance costs.ARTE with HLASTD still has lower tree-size quartiles and median than SRP with HT on real-world datasets.

7 Conclusion

The paper introduces HLAST and EFLAST, combining periodic Hoeffding splitting with change-detector-driven adaptive splitting to improve ensemble diversity and concept-drift responsiveness. Experiments report strong F1-Score performance, while future work targets efficient ensembles and broader adaptation.

Contributions: HLAST and EFLAST combine periodic Hoeffding split attempts with change-detector-driven adaptive splits, promoting ensemble diversity while preserving responsiveness to concept drift.The trees grow at more informed moments by integrating both splitting mechanisms.
Experimental findings: HLAST and HLASTD are among the best-performing base trees on real-world streams, surpassing HT and EFDT, while LAST and LASTD are the weakest.The experiments report F1-Score across real-world and synthetic streams and five ensembles.
Experimental findings: The proposed trees achieve the best F1-Score overall, with ARTE and HLASTD recommended for their strongest and most consistent benchmark results.ARTE with HLASTD improves over ARTE with HT on almost every real-world dataset, while HLASTD is recommended with SRP.
Drift analysis: Ensembles recover to comparable F1-Score levels shortly after drift, while remaining differences reflect feature selection and sampling rather than the base tree.ARTE loses F1-Score on sharp-boundary datasets such as AGRAWAL because random split points seldom reach well-defined cut points.
Future work: Future work includes lower sampling, regularization for ARTE, pre-pruning, regression adaptation, base-learner hyperparameter tuning, and greater ensemble diversity through varied feature percentages.One proposed sampling scheme trains misclassified instances with Poisson(λ = 6) copies and correctly classified instances with Poisson(λ = 1) copies.