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

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

cs.LGAug 17, 2026

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

Abstract

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 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	$10^{6}$	9	2	52.83	Recurrent-Abrupt
AGR-f(7,8,9,10,9,8,7) rg	$10^{6}$	9	2	52.83	Recurrent-Gradual
AGR-f(1,2,3,4,5,6,7,8,9,10) a	$10^{6}$	9	2	52.83	Abrupt
AGR-f(10,9,8,7,6,5,4,3,2,1) a	$10^{6}$	9	2	52.83	Abrupt
AGR-f(1,2,3,4,5,6,7,8,9,10) g	$10^{6}$	9	2	52.83	Gradual
AGR-f(10,9,8,7,6,5,4,3,2,1) g	$10^{6}$	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 $\pm$ 3836.14	344.20 $\pm$ 717.44	40.70 $\pm$ 22	10.27 $\pm$ 9.22
HLAST	HLAST D	EFLAST	EFLAST D
1062.42 $\pm$ 8062.94	1106.77 $\pm$ 8109.61	347.15 $\pm$ 812.37	359.33 $\pm$ 782.68

Table 2: Mean and standard deviation of tree size of ARF base learners

Panel of Figure 10 — 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)

Panel of Figure 11 — 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)

Panel of Figure 12 — 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)

Panel of Figure 13 — Figure 13: F1-Score (in %) of ensembles in datasets that simulate recurrent and abrupt changes

Panel of Figure 14 — Figure 14: F1-Score (in %) of ensembles in datasets that simulate recurrent and gradual changes

Panel of Figure 15 — Figure 15: F1-Score (in %) of ensembles in datasets that simulate abrupt changes

Panel of Figure 16 — Figure 16: F1-Score (in %) of ensembles in datasets that simulate gradual changes

Panel of Figure 17 — Figure 17: F1-Score (in %) of ensembles in the RBF dataset, which simulates incremental changes

Panel of Figure 18 — Figure 18: F1-Score (in %) of ensembles in the HYPER dataset, which simulates incremental changes

Panel of Figure 19 — Figure 19: F1-Score (in %) of ensembles in the INSECTS datasets

Decision Tree Learning

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

See all 69 papers

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference
May 29, 2026Salim I. Amoukou, Saumitra Mishra, Manuela VelosoAnytime-Valid Inference Decision Tree Learning
J.P. Morgan AI Research.
Pitfalls of Unlabeled Disagreement-Based Drift Detection in Streaming Tree Ensembles
May 12, 2026Lara Sá Neves, Afonso Lourenço, Lizy K. John +1Concept Drift Ensemble Learning
GECAD, ISEP, Polytechnic of Porto, Portugal · The University of Texas at Austin, USA
On Imbalanced Regression with Hoeffding Trees
Feb 25, 2026Pantia-Marina Alchirch, Dimitrios I. DiochnosDecision Tree Learning Kernel Density Estimation
University of Oklahoma

May 29, 2026J/K move · Enter open · S save

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Salim I. Amoukou, Saumitra Mishra, Manuela Veloso

J.P. Morgan AI Research.

Anytime-Valid Inference Decision Tree Learning Random Forest Sequential Hypothesis Testing

Open paper AskPDF arXiv

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.

Abstract

Decision Tree Learning

Explore similar work

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Pitfalls of Unlabeled Disagreement-Based Drift Detection in Streaming Tree Ensembles

On Imbalanced Regression with Hoeffding Trees