Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning
Authors: Daniel Nowak Assis, Jean Paul Barddal, Fabrício Enembreck
Organizations: Programa de P´os-Gradua¸c˜ao em Inform´atica (PPGIa), Pontif´ıcia Universidade Cat´olica do Paran´a (PUCPR), Rua Imaculada Concei¸c˜ao 1155, 80215-901, Curitiba, Brazil · Sorbonne Universit´e, CNRS, LIP6, Paris, France
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.
Figures & tables
Figure 1: Training process of Hoeffding Trees
Figure 2: LAST’s training process
Figure 3: Training process of combining adaptive and periodic splitting mechanism
Dataset
# Samples
# Features
# Classes
Majority Class (%)
Concept Drift
AGR-f(7,8,9,10,9,8,7) ra
106
9
2
52.83
Recurrent-Abrupt
AGR-f(7,8,9,10,9,8,7) rg
106
9
2
52.83
Recurrent-Gradual
AGR-f(1,2,3,4,5,6,7,8,9,10) a
106
9
2
52.83
Abrupt
AGR-f(10,9,8,7,6,5,4,3,2,1) a
106
9
2
52.83
Abrupt
AGR-f(1,2,3,4,5,6,7,8,9,10) g
106
9
2
52.83
Gradual
AGR-f(10,9,8,7,6,5,4,3,2,1) g
106
9
2
52.83
Gradual
Table 1: Description of the evaluated datasets.
Figure 4: F1-Score of each base learner against HT, reported as the percentage of cases in which the base learner wins over HT (win rate) and the F1-Score difference quantiles in percentage points, for synthetic (left) and real-world (right) data
Figure 5: F1-Score difference between HLAST/HLAST D and HT in real-world data for all ensembles evaluated
Figure 6: F1-Score difference between HLAST/HLAST D and HT in synthetic data for all ensembles evaluated
Figure 7: Raw F1-Score for HT/HLAST/HLAST D in real-world data for all ensembles evaluated
Figure 8: Raw F1-Score for HT/HLAST/HLAST D in synthetic data for all ensembles evaluated
Figure 9: (Continued) Raw F1-Score for HT/HLAST/HLAST D in synthetic data for all ensembles evaluated
HT
EFDT
LAST
LAST D
683,91 ± 3836.14
344.20 ± 717.44
40.70 ± 22
10.27 ± 9.22
HLAST
HLAST D
EFLAST
EFLAST D
1062.42 ± 8062.94
1106.77 ± 8109.61
347.15 ± 812.37
359.33 ± 782.68
Table 2: Mean and standard deviation of tree size of ARF base learners
Figure 10: Distribution of average tree size of the ensembles with HT, EFDT and best-ranking reported proposed method per ensemble as base learners for real-world (top) and synthetic data (down)
Figure 11: Distribution of CPU-Time (in seconds) of the ensembles with HT, EFDT and best-ranking reported proposed method per ensemble as base learners for real-world (top) and synthetic data (down)
Figure 12: Distribution of Peak RAM (MB) usage throughout time of the ensembles with HT, EFDT and best-ranking reported proposed method per ensemble as base learners for real-world (top) and synthetic data (down)
Figure 13: F1-Score (in %) of ensembles in datasets that simulate recurrent and abrupt changes
Figure 14: F1-Score (in %) of ensembles in datasets that simulate recurrent and gradual changes
Figure 15: F1-Score (in %) of ensembles in datasets that simulate abrupt changes
Figure 16: F1-Score (in %) of ensembles in datasets that simulate gradual changes
Figure 17: F1-Score (in %) of ensembles in the RBF dataset, which simulates incremental changes
Figure 18: F1-Score (in %) of ensembles in the HYPER dataset, which simulates incremental changes
Figure 19: F1-Score (in %) of ensembles in the INSECTS datasets
Bagging-based ensembles, most notably Adaptive Random Forests, are among the strongest performers for learning from data streams. A common denominator across these methods is their reliance on Hoeffding Trees as base learners, which grow decision trees incrementally by testing whether a candidate split is significantly better than its alternatives using concentration inequalities. Despite their empirical success, existing variants lack valid statistical guarantees. Current analyses rely on fixed-sample concentration bounds, while split decisions are made using data-dependent stopping rules, which invalidates their guarantees and can drive the probabilty of incorrect splits to one. We introduce a principled alternative based on anytime-valid inference. Our method provides: (i) anytime-valid control of false splits under arbitrary data streams, including non-stationary settings; (ii) finite commitment time under a predictive advantage; and (iii) under stationary i.i.d. data, risk is monotone decreasing and strictly improves at every split. Empirically, we evaluate both standalone trees and their use within Adaptive Random Forests on non-stationary streams. Our method improves performance while producing substantially smaller trees.
Detecting concept drift in high-speed data streams remains challenging, particularly when models must operate on unlabeled data and avoid false alarms caused by benign shifts. While disagreement-based uncertainty has shown promise in neural networks, its adaptation to ensembles of incremental decision trees (IDTs) remains largely unexplored. We investigate this approach by constructing batch-specific disagreement measures via label flipping in ensemble members and evaluating their effectiveness for drift detection in tabular data streams. Our experiments show that, although this method performs well in ensembles of multi-layer perceptrons (MLPs), it consistently underperforms loss-based detectors when applied to IDTs. We attribute this behavior to the intrinsic rigidity of IDTs: learning primarily through structural expansion, with limited parameter adaptation, restricts model plasticity and prevents disagreement from reliably reflecting learning potential. Recent work on restructuring IDTs using their intrinsic decomposition into non-overlapping rules offers a promising direction for improving adaptability.
Lara Sá Neves, Afonso Lourenço, Lizy K. John +1
GECAD, ISEP, Polytechnic of Porto, Portugal · The University of Texas at Austin, USA
Many real-world applications generate continuous data streams for regression. Hoeffding trees and their variants have a long-standing tradition due to their effectiveness, either alone or as base models in broader ensembles. Recent batch-learning work shows that kernel density estimation (KDE) improves smoothed predictions in imbalanced regression [Yang et al., 2021], while hierarchical shrinkage (HS) provides post-hoc regularization for decision trees without modifying their structure [Agarwal et al., 2022]. We extend KDE to streaming settings via a telescoping formulation and integrate HS into incremental decision trees. Empirical evaluation on standard online regression benchmarks shows that KDE consistently improves early-stream performance, whereas HS provides limited gains. Our implementation is publicly available at: https://github.com/marinaAlchirch/DSFA_2026.