Paper deep dive
Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning
Daniel Nowak Assis, Jean Paul Barddal, Fabrício Enembreck
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/23/2026, 2:32:37 AM
Summary
This paper introduces Hoeffding Adaptive Splitting Trees (HASTs), two novel decision tree models designed for data stream classification with concept drift. The authors identify that while adaptive splitting trees like LAST offer better adaptability than periodic Hoeffding Trees, they fail to maintain sufficient diversity within ensemble base learners due to correlated predictions in early stream phases. HASTs address this by combining the periodic splitting strategy of Hoeffding Trees (to foster diversity) with adaptive splitting mechanisms using change detection algorithms (to handle performance decay). Experimental results show HASTs achieve state-of-the-art performance in ensemble setups.
Entities (10)
Relation Signals (8)
Hoeffding Adaptive Splitting Trees → combinesmechanisms → Periodic Splitting and Adaptive Splitting
confidence 95% · combine the periodic splitting strategy... with adaptive splitting mechanisms
Hoeffding Adaptive Splitting Trees → isusedin → Ensemble Learning
confidence 95% · Hoeffding Adaptive Splitting Trees enhance ensemble performance
Hoeffding Adaptive Splitting Trees → solvesproblem → Concept Drift
confidence 95% · Hoeffding adaptive splitting trees for data stream classification with concept drift
Local Adaptive Streaming Tree → haslimitation → Low Diversity in Ensembles
confidence 92% · change detectors often fail to promote sufficient diversity within ensembles.
Hoeffding Adaptive Splitting Trees → isimprovementof → Hoeffding Tree
confidence 90% · These models combine the periodic splitting strategy of Hoeffding Trees... with adaptive splitting mechanisms
Hoeffding Adaptive Splitting Trees → isimprovementof → Local Adaptive Streaming Tree
confidence 90% · we propose two novel decision tree models... To address this issue [limitations of LAST]... Hoeffding Adaptive Splitting Trees
Hoeffding Tree → usesmechanism → Periodic Splitting
confidence 90% · performing periodic split attempts according to the Hoeffding bound.
→ →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.16659v1
- Canonical: https://arxiv.org/abs/2608.16659v1
Trouble viewing inline? Open PDF directly →
Full Text
72,667 characters extracted from source content.
Expand or collapse full text
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. Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning Daniel Nowak Assis Email: daniel.nassis@ppgia.pucpr.br Affiliation: Programa de Pós-Graduação em Informática (PPGIa), Pontifícia Universidade Católica do Paraná (PUCPR), Rua Imaculada Conceição 1155, 80215-901, Curitiba, Brazil Affiliation: Sorbonne Université, CNRS, LIP6, Paris, France Jean Paul Barddal Email: jean.barddal@ppgia.pucpr.br Affiliation: Programa de Pós-Graduação em Informática (PPGIa), Pontifícia Universidade Católica do Paraná (PUCPR), Rua Imaculada Conceição 1155, 80215-901, Curitiba, Brazil Fabrício Enembreck Email: fabricio@ppgia.pucpr.br Affiliation: Programa de Pós-Graduação em Informática (PPGIa), Pontifícia Universidade Católica do Paraná (PUCPR), Rua Imaculada Conceição 1155, 80215-901, Curitiba, Brazil keywordsData Stream Classification, Ensemble, Decision Tree, Concept Drift 1 Introduction Learning systems designed for online scenarios are well-known and an established area in Machine Learning. Data stream mining contemplates knowledge discovery in high-speed arriving data. In practice, it requires online deployment due to the high amount of data generated in real time. For an efficient learning system to work on streaming data, the algorithms deployed must be aware of the hasty and potentially infinite nature of streaming data. As pointed out in 10, ideally, a system designed for mining streaming data must i) process an instance of data, analyze it one time, and discard it, i) use a limited amount of memory, i) process an instance as fast as possible, and iv) be able to make predictions at any time. Another challenge in streaming data is concept drift 36. A concept drift occurs when the probabilistic properties of the data change over time. In a classification problem, a concept drift occurs between the times t and t+Δt+ , if Pt(X,Y)≠Pt+Δ(X,Y)P_t(X,Y)≠ P_t+ (X,Y), where PtP_t refers to the joint distribution at time t given a set of examples X and their class labels Y. Concept drifts may decrease the accuracy of machine learning models, which must swiftly detect and adapt to those situations to avoid compromising the entire learning process. Ensemble-based methods are considered state-of-the-art algorithms for the data stream classification problem. In the construction and evaluation of ensembles in the literature, the first choice as a starting point was, in general, the Hoeffding tree 19. The Hoeffding Tree algorithm is an incremental method that gradually expands the tree by making periodic split attempts as the data streams evolve, relying on the principles outlined in the Hoeffding Theorem 30. It has long been considered a state-of-the-art approach for constructing decision trees in the context of mining streaming data. However, recent insights from 4 highlight a limitation: the periodic split attempts may not effectively adapt to the evolving nature of the data stream. Since these split attempts occur at regular intervals, they fail to capture the precise moments when changes in accuracy or data distribution occur within the leaves. Furthermore, the algorithm continues to search for the best split even during periods of stability, causing increased processing time without significant improvements to the tree structure. Local Adaptive Streaming Trees (LAST), introduced in 4, overcome this limitation by continuously monitoring tree performance or class-distribution purity and splitting whenever change detectors flag a change, thereby outperforming Hoeffding-based trees 11 1 An ablation of LAST as a single tree has also been performed in 39, where it depicts the behavior of LAST under different change detectors. . Despite these promising results, LAST lacks the strategies needed to serve as a base model for ensemble learners. In practice, it has been observed that i) change detectors operate per base model, so instances affect individual learners rather than the ensemble as a whole; i) the trees are learned without any diversity induction scheme; and i) updating change detectors repeatedly incurs high computational overhead. Overall, it has been observed that i) the high correlation among decision tree outputs in the initial moments of the stream affects change detection across base learners, inducing similar splitting times and low diversity; and i) splitting time can be affected by random sampling, and LAST’s soft split constraint can produce poor splits, unlike the monolithic version, which reacts to changes in the model’s true performance or distribution. To address these challenges, we propose two new decision trees, namely Hoeffding Adaptive Splitting Trees (HASTs). These models combine a periodic splitting mechanism, which induces diversity among the decision tree learners by producing different trees, with an adaptive splitting mechanism that tracks either leaf-node performance or class-distribution purity and can react to changes at the leaf-node level. The two approaches differ in their combination strategy, drawing, respectively, on Hoeffding Trees 19 and Extremely Fast Decision Trees 38. The contributions of this paper are summarized as follows: 1. Two novel decision tree architectures that demonstrate state-of-the-art results in ensemble setups. 2. Comprehensive experimental analysis with state-of-the-art ensembles and insights into their performance, computational cost, and how they react to concept drifts. 3. Indication of future directions for the proposal of new ensembles. The remainder of this paper is organized as follows. Section 2 details the fundamental concepts of data stream mining and concept drift. Section 3 discusses the algorithms used in this work, such as online decision trees and ensembles. Section 4 revisits the limitations of LAST as base learners of ensembles and introduces the proposed decision trees. Section 5 outlines the experimental protocol used in this work. Section 6 discusses the results obtained. In Section 7, we conclude the paper by presenting the main findings of this study and identifying future research directions. 2 Background and Definitions Data streams are continuous and sequential data flows that arrive over time, with no predefined stopping point, often treated as potentially infinite. In a structured data stream, each arriving datum is a feature vector xt∈ℝdx_t ^d. Classification (a prediction of a class yny_n given an input x→n x_n) in this framework fundamentally differs from batch classification because in streaming data, storing all data is unfeasible, and thus, efficient stream mining requires classifiers that can ideally process data instances as rapidly as they arrive. If processing lags, the only options are to ignore new data (rendering the classifier less current) or attempt to store it, risking memory exhaustion and system collapse. Another problem in data streams is concept drift, characterized by temporal variations in the data’s probability distribution. Specifically, drift occurs between time t and t+Δt+ if the joint distribution P(x→,y)P( x,y) changes (Pt(x→,y)≠Pt+Δ(x→,y)P_t( x,y)≠ P_t+ ( x,y)). Based on the relationship P(x→,y)=P(x→)P(y|x→)P( x,y)=P( x)P(y| x), three types of drift are distinguished 24: 1. Virtual drift: Changes solely in the marginal distribution of features, P(x→)P( x). 2. Real drift: Changes solely in the posterior probability distribution (the classification boundary), P(y|x→)P(y| x). 3. Changes affecting both P(x→)P( x) and P(y|x→)P(y| x) simultaneously 36. In addition to the categories above, concept drifts can be categorized according to the temporal patterns exhibited. An abrupt shift is a sudden change from concept C1C_1 to C2C_2. A gradual shift is a slower transition between concepts. An incremental shift occurs through a series of intermediate concepts. Finally, a recurring concept scenario allows a previously observed concept to reappear. For the interested reader in the concept drift problem, we recommend the following recent studies that broaden the topic 36; 3. 3 Online Decision Trees and Ensembles In this section, we introduce existing works on online decision trees and ensembles that use tree variants for data stream classification. 3.1 Hoeffding Trees Hoeffding trees 19 are incremental and online decision trees that adopt a representation similar to their batch counterparts, such as C4.5 43 and CART 12 algorithms. In contrast to standard decision tree learning, which performs a greedy evaluation of linear splits in a data batch, Hoeffding Trees continuously increment the statistics required to check whether a split should be performed, and this analysis is carried out periodically. Targeting efficiency, the two main components of Hoeffding Trees are the Hoeffding bound constraint to prevent overgrowth and the periodic evaluation of splits in leaf nodes. Figure 1 presents the incremental training and splitting mechanism of Hoeffding Trees, where the Grace Period (GPGP) is a user-given parameter that sets the frequency at which a leaf node will attempt to split. Denoting n as the number of samples seen at leaf l, if n mod GP=0GP=0, a split attempt will ensue. Then it must pass the Hoeffding Test to result in a split. Figure 1: Training process of Hoeffding Trees The Hoeffding bound 30 is a theorem that presents a probability inequality for the difference between the mean (X¯ X) and expected value ([X] E[X]) of a set of random variables. With a level of confidence δ, one can derive that X¯−[X]≥ϵ X- E[X]≥ε following Equation 1, where R is the range of the random variable, and n is the number of observations. ϵ=R2log(1δ)2nε= R^2 ( 1δ)2n (1) The Hoeffding Tree applies this bound for impurity measures to determine if XaX_a, the attribute with the highest impurity measure G (such as information gain 43 or the Gini index 12), is the ideal attribute to split on a split attempt. Given XbX_b, the attribute with the second-highest impurity measure, if G(Xa)−G(Xb)≥ϵG(X_a)-G(X_b)≥ε, a split will occur on XaX_a. Note that limn→+∞ϵ=0 _n→+∞ε=0, and if G(Xa)G(X_a) and G(Xb)G(X_b) have similar values in a node, a split will require many observations to occur. To relax the Hoeffding constraint in these situations, the Hoeffding Tree has a tie threshold. Given τ (user-given threshold), a split will ensue when τ>ϵτ>ε. Assuming d to be the number of attributes, v the maximum number of values per attribute, c the number of classes, and l the number of leaf nodes, the Hoeffding tree algorithm requires (ldvc)O(ldvc) memory to store the necessary counts. An aspect that established Hoeffding Trees as accurate decision trees was the addition of Naive Bayes at leaf nodes 22. It was observed that Naive Bayes could outperform decision trees in initial streaming scenarios where the decision tree has trained with little data. In 32, the authors propose the selection of Naive Bayes or majority class strategy prediction according to the method with the highest accuracy at the leaf. Another critical aspect of Hoeffding Trees is memory management since storing all instances from a data stream is unfeasible. Leaf nodes maintain statistics from data, such as histograms for nominal data, and rely on forgetting mechanisms. We refer the interested reader to 31 for more details. 3.2 Extremely Fast Decision Trees In 38, the authors propose EFDT (Extremely Fast Decision Trees), an extension of Hoeffding Trees. The first change to Hoeffding Trees refers to the Hoeffding Bound. Instead of comparing the split evaluation function of the two features that maximize this function, the comparison is made between the feature XaX_a that maximizes the split evaluation function and the case where no split happens (X∅X_ ). Equation 2 is used as a condition for performing a split in XaX_a. G(Xa)−G(X∅)>R2log(1δ)2nG(X_a)-G(X_ )> R^2 ( 1δ)2n (2) Another extension proposed in EFDT is a split reevaluation mechanism 38. As more instances arrive, the probability of a better split appearing is higher than that of a split that ensued earlier. The reevaluation mechanism is similar to the splitting mechanism. The Hoeffding bound is used to compare the value of the split evaluation function of XaX_a in case a new split replaces the tree branch by a new split and the current feature (XcurrentX_current) split evaluation function at the time the split occurred. A branch of the tree is replaced by a new split if Equation 3 holds. G(Xa)−G(Xcurrent)>R2log(1δ)2nG(X_a)-G(X_current)> R^2 ( 1δ)2n (3) Since EFDT must store data at intermediate nodes to re-evaluate splits, it requires (ndvc)O(ndvc) memory, where n is the number of nodes. The default value for periodic reevaluation was defined as 2000 by the authors. In 37, the authors compare EFDT and Hoeffding Trees as base learners for ensembles, a similar aim to this work 4. Therefore, we also perform experiments with EFDT as a base learner of ensembles since the results in 37 suggest that EFDT is superior to Hoeffding Trees at an ensemble level. We also improve the evaluation of base learners in this work compared to 37 and explain the improvements in Section 5. 3.3 Adaptive Splitting Trees Hoeffding-based Trees follow a fixed periodic splitting strategy, activated at intervals of GP instances and controlled by the Hoeffding test. This policy is invariant to stream dynamics and tree performance, leading to blind recurrent splitting attempts and greedy split searches when little change occurs in the leaf, which results in little change in the tree structure. In 4, the authors overcame this limitation by proposing the Local Adaptive Streaming Tree (LAST). The rationale behind LAST is that change detectors can provide adaptability to determine split points at leaf nodes. Figure 2 presents LAST’s incremental training and splitting mechanism. In a leaf node, change detectors can monitor either the impurity or error rate. If a change detector at the leaf triggers a change, then a split will ensue if G(Xa)>0G(X_a)>0. Figure 2: LAST’s training process Change detectors are constantly updated with arriving instances, meaning that these algorithms track how the stream evolves. Since LAST applies the softest split constraint (G(Xa)>0G(X_a)>0), the change detectors effectively control how the tree grows. LAST requires (ψldvc)O(ψ ldvc) memory, where ψ is the memory complexity of the change detection algorithm applied. In 39, the authors presented a more thorough evaluation of LAST as a single monolithic decision tree, comparing LAST with different change detectors from the literature and performing an ablation analysis. This differs from the present paper, whose scope is ensemble learning. 3.4 Online Ensembles Ensembles are state-of-the-art algorithms for data stream classification, often adapting a batch version counterpart. In 40, the authors proposed an online version of Bagging 13. For each incoming instance, a base learner trains with k copies of the instance, where k is a random variable that follows a Poisson(λ=1)(λ=1) distribution, simulating random sampling with replacement in online scenarios. This process induces diversity amongst its members, which have their votes cast and combined using simple majority voting. In the same work, the authors proposed an online version of AdaBoost.M1 20. For each classifier, correct and wrong classification weights are maintained. When a new incoming instance arrives, the λ parameter starts at one, and the classifier is trained with k=k= Poisson(λ) copies of the instance. If a learner makes a wrong classification, the value λ increases based on the learner’s wrong weights, and in case the classifier makes a correct prediction, the value of λ decreases for the training of the next classifier. In contrast to Online Bagging, Online Boosting assigns each ensemble member a weight, which is used during prediction in a weighted majority voting scheme. To deal with concept drifts, the authors in 9 propose ADWIN-Bagging and ADWIN-Boosting. For each ensemble classifier, an ADaptive WINdowing (ADWIN) 8 drift detector monitors the error rates of the classifier. If the detector coupled with a classifier detects a concept drift, the least accurate member of the ensemble (in terms of the estimated ADWIN error) is reset. Extending the ADWIN-Bagging algorithm, authors in 11 propose the Leveraging Bagging algorithm. Instead of sampling being conducted by Poisson(λ=1λ=1), sampling follows Poisson(λ=6λ=6), making classifiers more specialized. In 11, the authors also propose using error output codes, as in 18, where binary classifiers are created per class, and the final ensemble prediction is a sum of the results of classifiers per class. This approach increases computational cost because the number of base learners scales with the number of classes. However, it can sometimes outperform standard Leveraging Bagging, despite the latter achieving the best average ranking in the original study 11. Extending the Online Boosting classifier, the authors proposed in 6 the Boosting-like Online Learning Ensemble (BOLE) algorithm. Training starts with λ=1λ=1, and classifiers are sorted by correct prediction rate (regarding correct and wrong classification weights 40). The classifier with the worst correct prediction rate is trained first. If this classifier gets a correct classification, the best classifier not yet trained (in terms of correct prediction rate) receives an altered λ for training. Otherwise, the worst classifier not yet trained receives it. BOLE significantly increases λ when many base learners misclassify instances, since the worst base learners influence each other until a base learner makes the right prediction. The performance of the ensemble overall influences the values of λ. In 27, the authors propose the Adaptive Random Forest (ARF) algorithm, a version of the Random Forest algorithm 14, where, in each split attempt, a random subset of features is considered for selecting the split with the best quality. Sampling is conducted by Poisson(λ=6)(λ=6). To deal with drifting scenarios, each classifier has two drift detectors, one for warnings and one for concept drift detection. If the warning detector triggers a change, a new classifier is trained in the background. Moreover, if the concept drift detector triggers a change, the previously trained background classifier replaces the original one. In addition to that, the classifier’s votes are weighted by accuracy. In 28, the authors propose the Streaming Random Patches (SRP) algorithm, a version of the Random Patches 35, using the same mechanisms as in ARF, but instead of considering a random subset of features per node, all the split attempts are evaluated with a random subset of features defined at the creation of the base learner. In SRP, sampling is conducted by Poisson(λ=6)(λ=6). In (42), the authors propose an extension to the Adaptive Random Forest (ARF) algorithm, namely Adaptive Regularized Ensemble (ARE). The authors integrate an instance selection technique for the base learners of ARF, where base learners train mostly with instances that they incorrectly classify. To avoid bias due to noisy instances, the authors propose a rejection strategy to train with instances that the base learner correctly classified. The base classifier will train with an instance that it correctly classified after rejecting ζ (user-given) instances of the same class. The authors also integrate a classifier selection technique, in which only the classifiers that perform above the average accuracy of the ensemble vote are selected. Another recent approach is Adaptive Random Tree Ensemble (ARTE), proposed in (41). ARTE base learners have random feature selection per node level, like ARF; however, the percentage selected is not fixed among base learners. In particular, the percentage selected per base learner is drawn from a uniform distribution. ARTE base learners also select the best split with random cut points, as in 26. 4 Hoeffding Adaptive Splitting Trees Base Learners As highlighted in 34, one of the key components of state-of-the-art ensembles is diversity, often induced via the distribution of a different number of copies of an instance to its base learners via random sampling with replacement, e.g., Bagging 13, or instance weighting, e.g., Boosting 20. However, under adaptive splitting, ensemble members tend to generate highly correlated predictions in the early phases of the data stream, potentially undermining ensemble diversity 37. Incremental decision trees begin learning from a single root node; consequently, during the early stages of the data stream, their predictions are issued by either a majority-class classifier or a Naive Bayes model, whichever attains higher accuracy 32. Because every ensemble member behaves this way, the members produce nearly identical outputs, and the change detectors attached to them are therefore updated with highly similar inputs. Since instances are weighted through Poisson(λ) sampling with expected value λ, the detectors exhibit similar behavior, trigger splits at closely aligned times, and ultimately yield reduced ensemble diversity. When the only source of differentiation among detectors is the variance introduced by Poisson weighting, split decisions are governed more by random sampling effects than by genuine performance differences or the underlying class distribution. Under these conditions, the LAST soft split criterion (G(Xa)>0G(X_a)>0) becomes liable to trigger suboptimal splits. To overcome this limitation, we propose two decision trees that enhance the splitting mechanism to be simultaneously adaptive, reacting to changes in the model’s performance or distribution, and induce diversity among base learners of the ensemble. Hoeffding-based Trees, such as Hoeffding Tree and EFDT, are sensitive to the number of copies they receive for training regarding splitting moment, since splitting time depends on the number of observations present in the leaf node, and present a hard constraint based on the Hoeffding bound. Therefore, we propose a combination of the adaptive and periodic splitting mechanism, as illustrated in Figure 3. Figure 3: Training process of combining adaptive and periodic splitting mechanism Algorithm 1 presents the proposed methods. First, we propose the Hoeffding Local Adaptive Splitting Tree (HLAST). HLAST maintains change detectors at leaf nodes that monitor either the predictive performance or the class distribution purity, as LAST does, and periodically performs split attempts with the Hoeffding bound, as Hoeffding Trees do. If the change detector flags a change, and G(Xa)>0G(X_a)>0 (Algorithm 1, line 18), or G(Xa)−G(Xb)>R2log(1δ)2nG(X_a)-G(X_b)> R^2 ( 1δ)2n (Algorithm 1, line 14) in a periodic split attempt, the leaf is split on XaX_a. We also propose the Extremely Fast Local Adaptive Streaming Tree (EFLAST). EFLAST performs splits periodically, if G(Xa)>R2log(1δ)2nG(X_a)> R^2 ( 1δ)2n (Algorithm 1, line 16) or adaptively, if the change detector flags a change and G(Xa)>0G(X_a)>0. We also maintain the splitting reevaluation mechanism (Algorithm 1, line 16), where non-leaf nodes replace their branch by a new split if G(Xa)−G(Xcurrent)>R2log(1δ)2nG(X_a)-G(X_current)> R^2 ( 1δ)2n. Overall, the proposed trees still periodically search for the best splits and incur a computational overhead due to the use of change detectors; however, we show experimentally that such overhead is not prohibitive. Algorithm 1 HLAST and EFLAST: splitting strategy by combination of adaptive decision trees and HT or EFDT 1: S: a data stream, X : a feature, G(⋅)G(·) : a purity measure (such as Gini or Entropy), ψ : a Change Detection algorithm GPGP: Grace Period (sample frequency that a leaf node will attempt to split) DTDT: Decision Tree (The constructed decision tree) splitting_type : splitting mechanism selection between HT or EFDT (instantiating HLAST or EFLAST, respectively) 2: for (x→n,yn)∈S( x_n,y_n)∈ S do 3: if splitting_type = EFDT then 4: Traverse tree and ascertain that non-leaf nodes pass the reevaluation of split attempts 5: end if 6: Let l←DT(x→n)l← DT( x_n) ⊳ traverse tree until leaf node 7: nl←nl+1n_l← n_l+1 ⊳ increment number of samples in the leaf 8: if ¬ (l has samples from only one class) then 9: if nln_l mod GP=0GP=0 then 10: Compute G(Xi)G(X_i) for each Xi∈XlX_i∈ X_l stored in l 11: Let XaX_a be the feature with highest G 12: Let AbA_b be the feature with second highest G 13: Let ϵ←R2log(1δ)2nlε← R^2 ( 1δ)2n_l ⊳ Eq. (1) 14: if splitting_type = HT then 15: Let cond←G(Aa)−G(Ab)>ϵcond← G(A_a)-G(A_b)>ε ⊳ HLAST tree type 16: else 17: Let cond←G(Aa)>ϵcond← G(A_a)>ε ⊳ EFLAST tree type 18: end if 19: if ((cond∨τ>ϵ)∨(lψCLOSECLOSE((cond τ>ε) (l_ψ detected a change OPEN∧G(Aa)>0) G(A_a)>0) ) ∧Aa≠∅ ~A_a≠ then 20: Replace l by leaf nodes that split on XaX_a 21: for each leaf node lil_i from splitting on XaX_a do 22: nli←0n_l_i← 0 23: liψ←ψl_iψ←ψ ⊳ creates a new change detector at each leaf node 24: end for 25: end if 26: end if 27: end if 28: end for 5 Methodology This section assesses the impact of the proposed tree models when integrated into ensembles constructed with various algorithms. The algorithms evaluated in this work were implemented in Java by extending the Massive Online Analysis (MOA) software (10). All of our experiments are reproducible, and the source code and additional results (such as raw accuracy and F1-Score results) are publicly available on the paper’s support repository22 2 https://sites.google.com/view/last-ensemble. We performed all the experiments on an Intel(R) Core(TM) i7-12700H @ 2.30 GHz with 16 GB of RAM. We performed experiments with 13 real-world datasets made available in 44 and 24 synthetic datasets retrieved from 15. Their main idea is to test how methods react to concept drift 9. Table 1 describes the datasets used in this work. The datasets at the top are synthetic, while the ones at the bottom are datasets representing real-world data. Table 1: Description of the evaluated datasets. Dataset # Samples # Features # Classes Majority Class (%) Concept Drift AGR-f(7,8,9,10,9,8,7)ra 10610^6 9 2 52.83 Recurrent-Abrupt AGR-f(7,8,9,10,9,8,7)rg 10610^6 9 2 52.83 Recurrent-Gradual AGR-f(1,2,3,4,5,6,7,8,9,10)a 10610^6 9 2 52.83 Abrupt AGR-f(10,9,8,7,6,5,4,3,2,1)a 10610^6 9 2 52.83 Abrupt AGR-f(1,2,3,4,5,6,7,8,9,10)g 10610^6 9 2 52.83 Gradual AGR-f(10,9,8,7,6,5,4,3,2,1)g 10610^6 9 2 52.83 Gradual SEA-f(1,2,3,4,3,2,1)ra 10610^6 3 2 59.91 Recurrent-Abrupt SEA-f(1,2,3,4,3,2,1)rg 10610^6 3 2 59.91 Recurrent-Gradual SEA-f(1,2,3,4)a 10610^6 3 2 59.91 Abrupt SEA-f(1,2,3,4)g 10610^6 3 2 59.91 Gradual SEA-f(4,3,2,1)a 10610^6 3 2 59.91 Abrupt SEA-f(4,3,2,1)g 10610^6 3 2 59.91 Gradual LED-f(7,5,3,1,3,5,7)ra 10610^6 24 10 10.28 Recurrent-Abrupt LED-f(7,5,3,1,3,5,7)rg 10610^6 24 10 10.28 Recurrent-Gradual LED-f(1,3,5,7)a 10610^6 24 10 10.28 Abrupt LED-f(1,3,5,7)g 10610^6 24 10 10.28 Gradual LED-f(7,5,3,1)a 10610^6 24 10 10.28 Abrupt LED-f(7,5,3,1)g 10610^6 24 10 10.28 Gradual RBFs 10610^6 10 5 30.01 Incremental RBFm 10610^6 10 5 30.01 Incremental RBFf 10610^6 10 5 30.01 Incremental HYPERs 10610^6 10 2 50 Incremental HYPERm 10610^6 10 2 50 Incremental HYPERf 10610^6 10 2 50 Incremental Outdoor 4,000 21 40 4.11 Unknown Elec 45,312 8 2 57.41 Unknown Rialto 82,250 27 10 10 Unknown Airlines 539,383 7 2 55.47 Unknown CoverType 581,012 54 7 48.75 Unknown Nomao 34,465 119 2 71.44 Unknown Poker 829,201 10 10 47.78 Unknown NOAA 18,158 8 2 69.74 Unknown INSECTSa 52,848 33 6 16.07 Abrupt INSECTSi 57,018 33 6 11.56 Incremental INSECTSg 24,150 33 6 15.76 Gradual Asfault 8,066 62 5 55.59 Unknown LADPU 22,950 96 10 10 Unknown The synthetic dataset generators are described as follows. AGRAWAL 1 The AGRAWAL generator simulates a loan-approval scenario with nine features that represent applicant attributes: salary (numerical, 0–150K), commission (numerical, 0–75K), age (numerical, 20–80), eloan (boolean), car (nominal, 1–20), zipcode (nominal, 0–8), hvalue (numerical, 50K–600K), hyears (numerical, 1–30), and loan (numerical, 0–500K). Ten classification functions encode distinct loan-approval rules over these attributes, mapping feature combinations to a binary label (approved or denied). These functions are progressively more complex from f1f_1 to f10f_10: the earlier ones depend on a single attribute with simple cut points, while the later ones combine several attributes through compound conditions and derived quantities. For instance, f1f_1 assigns the label using only age, approving applicants younger than 40 or at least 60 years old and denying the remaining middle-age range. In contrast, f10f_10 is the most elaborate rule, computing a derived disposable income from salary, commission, and loan together with an equity term that depends on hvalue and hyears, and approving the loan only when this disposable income is positive. Concept drift is simulated by switching between these functions. Following the table, we use a recurrent variant cycling through f7,f8,f9,f10,f9,f8,f7\f_7,f_8,f_9,f_10,f_9,f_8,f_7\ (6 drifts) and monotone ascending f1,…,f10\f_1,…,f_10\ and descending f10,…,f1\f_10,…,f_1\ variants (9 drifts each). SEA 45 The SEA generator produces three numerical features f1,f2,f3f_1,f_2,f_3 uniformly sampled from [0,10)[0,10), where f3f_3 is entirely irrelevant to the class label, making this a three-feature problem with an embedded irrelevant dimension. The class label is binary and is determined by a threshold applied to the sum of the two relevant features. Four concepts are defined as c1:(f1+f2≤8)c_1 (f_1+f_2≤ 8), c2:(f1+f2≤9)c_2 (f_1+f_2≤ 9), c3:(f1+f2≤7)c_3 (f_1+f_2≤ 7), and c4:(f1+f2≤9.5)c_4 (f_1+f_2≤ 9.5): an instance receives class 1 if the condition for the active concept holds, and class 0 otherwise. The recurrent variant cycles through concepts in the order c1,c2,c3,c4,c3,c2,c1\c_1,c_2,c_3,c_4,c_3,c_2,c_1\ (6 drifts), while the monotone abrupt and gradual variants follow c1,c2,c3,c4\c_1,c_2,c_3,c_4\ or c4,c3,c2,c1\c_4,c_3,c_2,c_1\ (3 drifts each). Gradual transitions are controlled by a window in which instances are drawn from both the outgoing and incoming concept with a probability that changes linearly. LED 12 The LED generator simulates reading a seven-segment LED display showing digits 0–9, where each digit is encoded by 7 boolean features corresponding to the active segments. An additional 17 boolean features are appended and are entirely irrelevant to the classification task, making feature selection non-trivial. Furthermore, each boolean feature is independently flipped with a 10% probability, introducing label noise. Concept drift is simulated by progressively masking or unmasking the originally relevant features: as the number of relevant features decreases, fewer segments are correctly observed and the classification boundary becomes harder to learn. In our experimental setup the order of relevant feature counts across concepts is 7,5,3,1,3,5,7\7,5,3,1,3,5,7\ for the recurrent variant (LEDra and LEDrg, 6 drifts) and 1,3,5,7\1,3,5,7\ or 7,5,3,1\7,5,3,1\ for the monotone variants (LEDa and LEDg, 3 drifts each). Abrupt variants transition instantaneously between concepts, whereas gradual variants mix instances from adjacent concepts over a transition window. RBF 10 The Radial Basis Function (RBF) generator creates a Gaussian mixture model over 10 features and 5 classes, in which each of the 50 randomly initialised centroids is associated with a standard deviation, a weight, and a class label; instances are drawn by selecting a centroid with probability proportional to its weight and sampling from the corresponding Gaussian. Incremental concept drift is introduced by continuously moving the centroids through the feature space at a fixed speed, so that the decision boundaries shift gradually over time rather than switching abruptly. Three speed variants are evaluated: RBFs (slow, speed =10−5=10^-5), RBFm (moderate, speed =10−4=10^-4), and RBFf (fast, speed =10−3=10^-3). The increasing speed makes it progressively harder for learners to track the drifting class regions. HYPER 33 A hyperplane in ℝdR^d is a (d−1)(d-1)-dimensional affine subspace defined by ∑i=1dwixi=w0 _i=1^dw_ix_i=w_0, which partitions the space into two half-spaces and thus provides a natural binary decision boundary. Instances are generated uniformly at random in [0,1]d[0,1]^d, and their class is determined by which side of the hyperplane they fall on. Incremental concept drift is simulated by continuously rotating the hyperplane: at each step, a random weight wiw_i is perturbed by an amount proportional to the magnitude parameter σ, and all weights are subsequently re-normalised. Three speed variants are evaluated: HYPERs (slow, σ=10−4σ=10^-4), HYPERm (moderate, σ=10−3σ=10^-3), and HYPERf (fast, σ=10−2σ=10^-2). All variants were configured with d=10d=10 features. In contrast to the experiments conducted in 37, all ensembles were set with 100 base learners, as used in recent state-of-the-art ensembles 27; 28. All parameters from ensembles were set to default as implemented in the MOA framework. In addition to the ensembles evaluated in 37, we also experimented with SRP (28), ARE (42), and ARTE (41). We acknowledge SGBT (29), a method that adapts gradient boosting trees for streaming scenarios; however, many datasets ran for a week constantly demanding memory swap and presented a high computational cost, and were therefore excluded from the experiments. We also chose not to include in our experiments ensemble algorithms specifically designed for imbalanced contexts, such as ROSE 16, KUE 15, and others cited in 2, opting instead to focus on general-purpose ensemble methods. Only the best state-of-the-art methods are evaluated for visualization convenience, including Leveraging Bagging, ARF, SRP, ARE, and ARTE, based on the results reported in 27; 28; 41. As in (38), we assess the predictive performance obtained with a test-then-train validation strategy, where every instance is used first for testing and then for training, known as Prequential evaluation 23. All metrics are averaged over 20 evenly spaced points of the stream, as more points did not change results drastically. To statistically compare the results obtained by the ensembles of base learners, we performed a Friedman test with a significance level of 1% (p-value <0.01<0.01) and a pairwise one-sided Wilcoxon signed-rank post-hoc test with a Holm correction (25; 7). We visually represent the results of this test using a diagram as in (17). In this diagram, the methods are sorted according to their average ranking output by the statistical test. The methods connected by a line do not present statistically significant differences. Time processing and memory efficiency are key components of data stream mining algorithms, as cited earlier and in 10. Although not covered in the experimentation presented in 37, in this work we evaluate CPU-Time, memory usage (peak RAM, in MB, throughout time), and the mean tree size (number of nodes) in the ensemble. For these metrics, we provide violin plots sorted by median. LAST variants that incorporate data distribution monitoring at the leaf nodes are indicated by the suffix “D”, as in LASTD, HLASTD and EFLASTD. The detector used in all LAST versions was HDDMA 21, given the analysis done in 39. It is important to clarify the relationship between this work and 39, which evaluates LAST exclusively as a monolithic decision tree and reports no ensemble experiments. Two of its contributions are directly relevant here. First, 39 (39) conjecture that LASTD, which monitors class-distribution purity rather than error rate, may suit ensemble use better than LAST: because of the instance sampling process, leaf nodes are expected to undergo more frequent distributional changes, which could lead LASTD to induce greater diversity among base learners. We investigate this hypothesis in the present work. Second, among the change detectors evaluated, HDDMA, MDDMA, and ADWIN stand out: they produce trees as accurate as the DDM-type detectors (DDM, EDDM, RDDM) while remaining more computationally efficient, owing to stricter detection bounds and fewer false positives. We adopt HDDMA, which achieved the best overall ranking, though MDDMA and ADWIN performed comparably. 6 Results This section presents results for experimentation conducted to assess the proposed methods. First, Section 6.1 presents a benchmark for ensembles and base learners. Next, Section 6.2 presents a comparison of tree sizes, while Section 6.3 discusses the computational cost of the methods. Finally, Section 6.4 analyzes the F1-Score of methods in concept drifting scenarios. 6.1 Benchmark This section benchmarks the proposed trees against Hoeffding Trees (HT), EFDT, and the original adaptive trees LAST and LASTD as base learners of the five ensembles evaluated in this work, where we report F1-Score. We discuss the behaviour of each base tree per dataset, so that the properties of the data that favour the proposed trees become explicit. The raw F1-Score and accuracy values for every combination of ensemble and base learner are available in the paper’s repository. 6.1.1 Best-performing base tree Figure 4 summarizes how each base tree compares against a standard Hoeffding Tree across all ensembles. The horizontal axis reports the percentage of cases in which the base learner wins over HT, while the vertical axis reports the F1-Score difference to HT in percentage points, where the marker is the median difference across all datasets and ensembles and the vertical bars span the lower and upper quantiles of that difference. In real-world data, HLASTD and HLAST are among the best-performing trees, winning over HT in 75%75\% and 63%63\% of the cases, respectively, ahead of EFDT and EFLAST, and largely ahead of the original adaptive trees LAST and LASTD, which win in only 38%38\% and 42%42\% of the cases. Considering the quantiles, HLASTD and HLAST keep a median difference at or above zero, and their upper quantile reaches above two and one percentage points, respectively, meaning that on the favorable datasets the gains are substantial, while their lower quantile stays close to zero, meaning they rarely lose much when they do not win. The original adaptive trees show the opposite behaviour, with a median difference below zero, which confirms that LAST and LASTD are weak ensemble base learners, while combining the adaptive mechanism with the periodic Hoeffding split recovers and surpasses the performance of HT. Figure 5 details this difference per dataset, with each point colored by the ensemble that produced it. The gains of the proposed trees concentrate on datasets with a larger number of classes, such as Outdoor (40 classes), Rialto, Poker and LADPU (10 classes), CoverType (7 classes) and the INSECTS variants (6 classes), reaching up to 1616 percentage points in LADPU and around 1010 points in Outdoor and Rialto. The highest gains come from Leveraging Bagging and ARE, the ensembles that grow the largest trees (Table 2), so the adaptive splitting strategy has the most pronounced effect on them, but the remaining ensembles also present positive gains in general, and the proposed trees produce higher predictive quality across the board. On binary datasets such as Electricity, Airlines, NOAA and Nomao, the difference stays close to zero. This behaviour follows directly from the description of the proposed trees. With more classes, a leaf node takes longer to become pure and offers more opportunities to split, so letting the change detector decide when to split, on top of the periodic Hoeffding attempts, produces larger and more diverse trees (Table 2). On binary problems the concept is learned quickly and the additional adaptive splitting remains mostly idle, leaving little room for improvement. The datasets on which the proposed trees perform best are also the most challenging, according to the streaming benchmark in 44. That work characterizes real-world streams by their temporal dependence and shows that, due to autocorrelation, a naive No-Change baseline—one that simply predicts the label of the most recent instance—can already achieve strong performance, rendering several commonly used benchmark datasets deceptively easy. This is not the case for Rialto, LADPU, and Asfault, where the proposed trees achieve their highest gains: these datasets lack such autocorrelation and thus require the model to genuinely learn the underlying concept. Even on datasets with autocorrelation, such as Electricity and CoverType, the ensembles outperform the No-Change baseline by a wide margin. In terms of F1-Score, ARTE and HLASTD reach 91.33%91.33\% against 84.43%84.43\% on Electricity and 86.60%86.60\% against 76.41%76.41\% on CoverType, confirming that the reported gains reflect genuine concept learning rather than artifacts of easy data. Figure 5 further shows that the two proposed trees do not behave identically across ensembles. Under SRP, HLAST is the weakest of the three base learners, with a standard HT outperforming it in roughly 70%70\% of the cases. The reason lies in how SRP operates: it assigns each base learner a fixed random subset of features at creation, so some learners are inevitably built on weak or uninformative subsets. Because HLAST relies on a soft adaptive split driven by the error rate, these learners continue splitting even when their features are poor, and since SRP weights votes by accuracy, the resulting large but weakly featured trees bias the weighted voting and degrade the ensemble. HLASTD avoids this pitfall: by monitoring class-distribution purity rather than the error rate, its growth is not driven by fluctuations of the error detector. HLASTD is therefore the natural choice to pair with SRP, whereas HLAST is better suited to ensembles such as ARTE. 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/HLASTD and HT in real-world data for all ensembles evaluated Figure 6 shows that on synthetic data the proposed trees have little effect, with the F1-Score difference to HT staying close to zero for all ensembles. The synthetic generators used in the benchmark configure simple linear concepts, as in AGRAWAL, SEA and HYPER, or binary patterns, as in LED, and their main purpose is to test how methods react to concept drift. As further discussed in Section 6.4, the ensembles react to drift in a very similar way, and the simple concepts are learned fast by the trees, so growing them further with adaptive splitting does not change the results in a meaningful way. The impact of the proposed trees is therefore more evident on real-world data, where the concepts are more complex. Figure 6: F1-Score difference between HLAST/HLASTD and HT in synthetic data for all ensembles evaluated 6.1.2 Best-performing ensemble Figure 7 reports the raw F1-Score of HT, HLAST, and HLASTD for every ensemble, marking the best base learner within each ensemble and the overall best result per dataset. The proposed trees provide the overall best result on most real-world datasets, and almost all of these wins occur on the multi-class datasets, in line with the per-tree analysis. Specifically, ARTE with HLASTD delivers the best result on Rialto, the INSECTS variants, LADPU, and Asfault; ARTE with HLAST leads on Nomao; and SRP with HLAST or HLASTD leads on Outdoor, Airlines, CoverType, and Poker. Considering the results as a whole, the proposed trees achieve the strongest performance, and we recommend ARTE as the ensemble to pair with them. ARTE combines a per-learner random feature percentage with random cut points, which already induces high diversity; the proposed trees build on this by splitting at more informed moments rather than blindly at fixed intervals. The combination is particularly effective on real-world data, where ARTE with HLASTD outperforms ARTE with HT on almost every dataset and yields the strongest and most consistent results across the entire benchmark. Figure 8 shows that, on synthetic data, the differences between base learners are small and the best result alternates among ensembles and trees, with Leveraging Bagging leading on LED, SRP on HYPER, and ARTE on SEA. This reinforces the point that synthetic concepts do not clearly separate the methods, and that the advantage of the proposed trees (and of ARTE in particular) stems mainly from the more complex real-world data. Figure 7: Raw F1-Score for HT/HLAST/HLASTD in real-world data for all ensembles evaluated Figure 8: Raw F1-Score for HT/HLAST/HLASTD in synthetic data for all ensembles evaluated Figure 9: (Continued) Raw F1-Score for HT/HLAST/HLASTD in synthetic data for all ensembles evaluated The main points observed in this section were: 1. HLAST and HLASTD are among the best-performing base trees on real-world data, surpassing HT and EFDT, while the original adaptive trees LAST and LASTD are the weakest as ensemble base learners. 2. The proposed trees yield larger gains on datasets with more classes, where leaves stay impure longer and the adaptive splitting has more room to act, and have little effect on binary and synthetic data, where the simpler concepts are learned fast. 3. HLASTD is the most suitable tree for SRP, as HLAST lets learners built on weak feature subsets keep growing and biases SRP’s accuracy-weighted voting. 4. The proposed trees achieve the best performance overall, and ARTE with HLASTD is the recommended combination, providing the strongest and most consistent results on real-world data. 6.2 Tree Size Table 2 shows the mean tree size and standard deviation of ARF decision trees, which had similar behavior in other ensembles as well. As expected, LAST presented lower standard deviation compared to other base learners, showing that LAST presents low diversity as a base learner of the ensemble. EFDT presented lower tree size compared to Hoeffding-based Trees due to the reevaluation process. However, lower tree size does not imply lower memory cost, as EFDT needs to store data at non-leaf nodes. Table 2: Mean and standard deviation of tree size of ARF base learners HT EFDT LAST LASTD 683,91 ± 3836.14 344.20 ± 717.44 40.70 ± 22 10.27 ± 9.22 HLAST HLASTD EFLAST EFLASTD 1062.42 ± 8062.94 1106.77 ± 8109.61 347.15 ± 812.37 359.33 ± 782.68 Fig. 10 shows the distribution of average tree size in real-world and synthetic datasets. In real-world datasets, ARTE with HLASTD presented higher median and third quartile compared to ARTE with HT, but still presented lower third quartile, median and first quartile compared to SRP with HT. ARE and LevBag presented the largest tree sizes among all ensembles and their respective base learners. The high tree size of ARE could be explained by the input of the change detectors, which depend mostly on instances that were misclassified and used for training by the base learner. An update of the change detector with all the instances, independently of rejection, could mitigate this. In synthetic data, ARTE with HLASTD also presented a higher median and third quartile than ARTE with HT and lower third quartile, median and first quartile compared to SRP with HT. The main points observed in this section were: 1. LAST presents a low standard deviation in tree size, showing lower diversity of the base learner as a member of the ensemble. 2. ARE base learners’ change detectors receive mostly instances incorrectly classified by the base learner, and updating the change detector with all instances could help the change detector to track the performance of the base learner, independently of training or not with the instance. 3. ARTE with HLASTD presents a higher tree size compared to ARTE with HT, but still a lower tree size compared to SRP with HT. 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) 6.3 Computational Cost Fig. 11 shows the distribution of CPU-Time in real-world and synthetic datasets. In real-world datasets, ARTE with HLASTD and ARTE with HT presented similar quantiles, while also presenting lower quantiles compared to ARF with HT and SRP with HT. The random splitting mechanism of ARTE reduces the cost of checking all possible splits, and, by simply resetting the classifier in case of concept drift detection, also lowers the cost of maintaining a background classifier. ARE with HT and HLASTD presented the lowest quantiles, showing the efficiency of the instance selection approach. In synthetic datasets, the difference between ARTE with HT and HLASTD is even more evident, as the number of instances of the synthetic datasets was 10610^6. SRP with HT presented a greater first quartile compared to ARTE with HT and HLASTD third quartile. ARF with HT also presented higher first quartile compared to ARTE with HT and HLASTD median. 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) Fig. 12 shows the distribution of peak RAM (MB) in real-world and synthetic datasets. The same pattern as for CPU-Time follows for both real and synthetic data, where ARTE with HLASTD and ARTE with HT present lower quantiles compared to ARF with HT and SRP with HT. The main points outlined in this section were: 1. ARTE with HLASTD and ARTE with HT present lower quantiles compared to ARF with HT and SRP with HT for CPU-Time and RAM-Hours in real-world and synthetic data. 2. The random splitting mechanism of ARTE reduces the cost of checking all possible splits and, by simply resetting the classifier in case of concept drift detection, also lowers the cost of maintaining a background classifier. 3. ARE presented the lowest quantiles, showing the efficiency of the regularization approach. 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) 6.4 Concept Drift Across the synthetic streams the ensembles describe very similar F1-Score curves over time, and after each drift, marked by the vertical lines in Figures 13–16, the curves recover to a comparable level within a short window, which indicates that on these simple concepts the dominant factor is how each ensemble reacts to drift rather than which base tree it carries, in line with the small effect of the proposed trees on synthetic data reported in Section 6.1.1. What separates the ensembles is how well their voting mechanism matches the structure of the current concept, and a few consistent patterns follow from the characteristics of each generator. In AGRAWAL (Fig. 13–16) ARTE attains the lowest F1-Score, because the concepts of AGRAWAL are defined by sharp cut points on the numerical attributes and the random split-point mechanism of ARTE seldom places a split exactly on these boundaries, which is most visible in the monotone variants (Fig. 15 and 16) where the ARTE curves settle a few points below the rest. SRP behaves in the opposite way and reaches the highest F1-Score in this dataset, since the trees that were assigned the features active in the current concept fit the cut points well and, being weighted by accuracy, take over the vote. In SEA the ordering is reversed and SRP, together with Leveraging Bagging, produces the lowest F1-Score among the ensembles right after each drift (Fig. 13, 14 and 15), because the concept is defined by the sum of two relevant features and, when the drift changes which features are decisive, many trees built on the features that became irrelevant still carry a large vote weight inherited from their high accuracy under the previous concept, which delays the ensemble in tracking the new concept. In LED the curves almost overlap, with the exception of ARE, whose F1-Score stabilises a few points below the rest (the lower curve in Fig. 13), because the seventeen irrelevant features and the 10% label noise of LED penalise the larger trees that ARE grows, which end up splitting on noisy attributes without a matching gain in leaf purity. 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 On the streams with incremental drift the F1-Score curves spread more than on the abrupt ones, since the boundary moves continuously and the ensembles never settle on a fixed concept. In RBF (Fig. 17) all ensembles stay tightly grouped at a high F1-Score except Leveraging Bagging with a Hoeffding Tree base, whose curve falls further below the group as the drift speed grows, from a small gap in RBFs to a pronounced drop in RBFf, where it stabilises around twenty points under the rest, while the remaining ensembles, including the proposed HLASTD variants, track the moving centroids without a comparable loss. In HYPER (Fig. 18) the spread is wider and no single ensemble dominates, but ARE is consistently among the best, because the instances misclassified during the intermediate concepts between two drifts feed additional training to its trees and the larger trees that ARE grows follow the rotating hyperplane more smoothly, whereas several ARF and ARTE configurations lag as the speed increases. In the INSECTS streams (Fig. 19) the ensembles produce very close F1-Score curves and all of them climb steadily as more instances arrive, with ARTE slightly ahead. 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 The main findings outlined in this section were: 1. On the synthetic streams the ensembles describe very similar F1-Score curves that recover quickly after each drift, so the drift-reaction mechanism of the ensemble, rather than the base tree, drives the differences, and specific properties of each generator explain the gaps that do appear. 2. ARTE struggles on datasets with sharp decision boundaries such as AGRAWAL, SRP and Leveraging Bagging lose F1-Score on the feature-dependent concepts of SEA, ARE trails on the noisy LED streams, and on the incremental drifts ARE adapts best while Leveraging Bagging with a plain Hoeffding Tree degrades sharply as the speed of the RBF drift increases. 7 Conclusion This paper presented the Hoeffding Adaptive Splitting Trees (HLAST and EFLAST) to overcome the limitations that both Hoeffding-based trees and the adaptive LAST face as base learners of data stream ensembles. By combining the periodic split attempts of a Hoeffding Tree with an adaptive split driven by change detectors, the proposed trees keep growing at more informed moments, which promotes ensemble diversity while preserving responsiveness to concept drift. Reporting F1-Score over a benchmark of real-world and synthetic streams across five ensembles, the experiments showed that HLAST and HLASTD are among the best-performing base trees on real-world data, surpassing HT and EFDT, while the original adaptive trees LAST and LASTD are the weakest, which confirms that pairing the adaptive mechanism with the periodic Hoeffding split is what recovers and then exceeds the performance of HT. The gains concentrate on datasets with more classes, where leaves stay impure for longer and the adaptive split has more room to act, reaching up to sixteen percentage points over HT, and on the most challenging real-world streams without temporal autocorrelation, such as Rialto, LADPU and Asfault, which shows that the improvement reflects genuine concept learning rather than artifacts of easy data. On binary and synthetic streams, whose simpler concepts are learned quickly, the proposed trees leave the results essentially unchanged. Taken together, the proposed trees achieve the best F1-Score overall, and ARTE with HLASTD is the recommended combination, improving over ARTE with HT on almost every real-world dataset and yielding the strongest and most consistent results of the benchmark. The pairing between tree and ensemble, however, matters: HLASTD, which monitors the class distribution purity, is the tree to couple with SRP, since the error-driven HLAST lets learners built on weak random feature subsets keep growing and biases the accuracy-weighted voting of SRP. This predictive quality comes at a competitive cost, as the analysis of tree size, CPU time and memory showed that ARTE with HLASTD grows larger trees than ARTE with HT but stays smaller and cheaper than SRP with HT in both CPU time and peak RAM, since its random split points avoid evaluating every candidate cut and its reset-on-drift policy spares the cost of maintaining background learners, while ARE attains the lowest cost of all through its instance-selection mechanism. The study also provided insights into the behavior of different ensembles under various drift scenarios through their F1-Score curves over time, where the ensembles recover to comparable levels shortly after each drift and the differences that remain follow from how each approach deals with feature selection and sampling rather than from the base tree. ARTE loses F1-Score on datasets with sharp decision boundaries such as AGRAWAL, since its random split points seldom land on the well-defined cut points, while SRP and Leveraging Bagging struggle on the feature-dependent concepts of SEA, where trees built on features that became irrelevant retain a large vote weight inherited from a past concept. ARE, in turn, trails on the noisy LED streams because its larger trees split on irrelevant attributes, yet this same aggressive growth makes it the best at tracking the incremental drifts of HYPER, whereas Leveraging Bagging with a plain Hoeffding Tree degrades sharply as the speed of the RBF drift increases. The results obtained provided insights for future work. First, ARE has set a good direction for the proposal of new ensembles, aiming to obtain the best predictive quality with the lowest computational cost possible. The design of extremely efficient ensembles can be further extended to: 1. Instead of rejecting instances, apply lower sampling. For example, misclassified instances are trained with Poisson(λ=6)(λ=6) copies, while correctly classified instances are trained with Poisson(λ=1)(λ=1) copies. The choice of varying λ=6λ=6 and λ=1λ=1 comes from the proposal in 11, which observed that λ=6λ=6 provides deeper trees and higher classification accuracy, opposed to the traditional λ=1λ=1 proposed in 40. 2. Adapt ARTE with regularization techniques. 3. Apply pre-pruning techniques to the decision tree base learners 5. Future research directions also include adapting these methods to regression problems, tuning the hyperparameters of the base learners, and increasing ensemble diversity by selecting a different percentage of features at each node. 8 Acknowledgments This work was financed by the Pontifícia Universidade Católica do Paraná (PUCPR) through the PIBIC Master – Combined Degree program. Finally, we sincerely thank the reviewers for their constructive feedback, which helped refine our original manuscript and strengthen the assessment of our methods. References Agrawal et al. (1993) R. Agrawal, T. Imielinski, and A. Swami Database mining: a performance perspective. IEEE Trans. on Knowl. and Data Eng. 5 (6), p. 914–925. External Links: ISSN 1041-4347, Link, Document Cited by: §5. Aguiar et al. (2024) G. Aguiar, A. Cano, and B. Krawczyk A survey on learning from imbalanced data streams: taxonomy, challenges, empirical study, and reproducible experimental framework. Machine Learning 113, p. 4165–4243. Cited by: §5. Aguiar and Cano (2024) G. J. Aguiar and A. Cano A comprehensive analysis of concept drift locality in data streams. Knowledge-Based Systems 289, p. 111535. External Links: ISSN 0950-7051, Document, Link Cited by: §2. Assis et al. (2024) D. N. Assis, J. P. Barddal, and F. Enembreck Just change on change: adaptive splitting time for decision trees in data stream classification. In Proceedings of ACM SAC Conference (SAC’24), ACM SAC’ 24, New York, NY, USA. Cited by: §1, §1, §3.2, §3.3. Barddal and Enembreck (2019) J. P. Barddal and F. Enembreck Learning regularized hoeffding trees from data streams. SAC ’19, New York, NY, USA, p. 574–581. External Links: ISBN 9781450359337, Document Cited by: item 3.. Barros et al. (2016) R. S. M. d. Barros, S. Garrido T. de Carvalho Santos, and P. M. Gonçalves Júnior A boosting-like online learning ensemble. In 2016 International Joint Conference on Neural Networks (IJCNN), Vol. , p. 1871–1878. External Links: Document Cited by: §3.4. Benavoli et al. (2016) A. Benavoli, G. Corani, and F. Mangili Should we really use post-hoc tests based on mean-ranks?. Journal of Machine Learning Research 17 (5), p. 1–10. External Links: Link Cited by: §5. Bifet and Gavaldà (2007) A. Bifet and R. Gavaldà Learning from time-changing data with adaptive windowing. Vol. 7, p. . External Links: Document Cited by: §3.4. Bifet et al. (2009) A. Bifet, G. Holmes, B. Pfahringer, R. Kirkby, and R. Gavaldà New ensemble methods for evolving data streams. KDD ’09, New York, NY, USA, p. 139–148. External Links: ISBN 9781605584959, Document Cited by: §3.4, §5. Bifet et al. (2010a) A. Bifet, G. Holmes, B. Pfahringer, P. Kranen, H. Kremer, T. Jansen, and T. Seidl Moa: massive online analysis, a framework for stream classification and clustering. In Proceedings of the first workshop on applications of pattern analysis, p. 44–50. Cited by: §1, §5, §5, §5. Bifet et al. (2010b) A. Bifet, G. Holmes, and B. Pfahringer Leveraging bagging for evolving data streams. In Machine Learning and Knowledge Discovery in Databases, Berlin, Heidelberg, p. 135–150. External Links: ISBN 978-3-642-15880-3 Cited by: §3.4, item 1.. Breiman (1984) L. Breiman Classification and regression trees. Wadsworth, Belmont, CA,. Cited by: §3.1, §3.1, §5. Breiman (1996) L. Breiman Bagging predictors. In Machine Learning, Vol. 24, p. 123–140. Cited by: §3.4, §4. Breiman (2001) L. Breiman Random forests. Mach. Learn. 45 (1), p. 5–32. External Links: ISSN 0885-6125, Link, Document Cited by: §3.4. Cano and Krawczyk (2019) A. Cano and B. Krawczyk Kappa updated ensemble for drifting data stream mining. Machine Learning 109, p. 175–218. Cited by: §5, §5. Cano and Krawczyk (2022) A. Cano and B. Krawczyk ROSE: robust online self-adjusting ensemble for continual learning on imbalanced drifting data streams. Machine Learning 111, p. 2561–2599. Cited by: §5. Demšar (2006) J. Demšar Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research 7, p. 1–30. Cited by: §5. Dietterich and Bakiri (1995) T. G. Dietterich and G. Bakiri Solving multiclass learning problems via error-correcting output codes. J. Artif. Int. Res. 2 (1), p. 263–286. External Links: ISSN 1076-9757 Cited by: §3.4. Domingos and Hulten (2000) P. Domingos and G. Hulten Mining high-speed data streams. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’00, New York, NY, USA, p. 71–80. External Links: ISBN 1581132336, Document Cited by: §1, §1, §3.1. Freund and Schapire (1996) Y. Freund and R. E. Schapire Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on International Conference on Machine Learning, ICML’96, San Francisco, CA, USA, p. 148–156. External Links: ISBN 1558604197 Cited by: §3.4, §4. Frías-Blanco et al. (2015) I. Frías-Blanco, J. d. Campo-Ávila, G. Ramos-Jiménez, R. Morales-Bueno, A. Ortiz-Díaz, and Y. Caballero-Mota Online and non-parametric drift detection methods based on hoeffding’s bounds. IEEE Transactions on Knowledge and Data Engineering 27 (3), p. 810–823. External Links: Document Cited by: §5. Gama et al. (2003) J. Gama, R. Rocha, and P. Medas Accurate decision trees for mining high-speed data streams. KDD ’03, New York, NY, USA, p. 523–528. External Links: ISBN 1581137370, Document Cited by: §3.1. Gama et al. (2013) J. Gama, R. Sebastião, and P.P. Rodrigues On evaluating stream learning algorithms. Machine Learning 90, p. 317–346. Cited by: §5. Gama et al. (2014) J. Gama, I. Žliobaite, A. Bifet, M. Pechenizkiy, and A. Bouchachia A survey on concept drift adaptation. ACM Comput. Surv. 46 (4). External Links: ISSN 0360-0300, Link, Document Cited by: §2. García and Herrera (2008) S. García and F. Herrera An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. Journal of Machine Learning Research 9 (89), p. 2677–2694. External Links: Link Cited by: §5. Geurts et al. (2005) P. Geurts, D. Ernst, and L. Wehenkel Extremely randomized trees. Machine Learning 63, p. 3–42. Cited by: §3.4. Gomes et al. (2017) H. M. Gomes, A. Bifet, J. Read, J. P. Barddal, F. Enembreck, B. Pfharinger, G. Holmes, and T. Abdessalem Adaptive random forests for evolving data stream classification. Machine Learning 106, p. 1469–1495. Cited by: §3.4, §5. Gomes et al. (2019) H. M. Gomes, J. Read, and A. Bifet Streaming random patches for evolving data stream classification. In 2019 IEEE International Conference on Data Mining (ICDM), Vol. , p. 240–249. External Links: Document Cited by: §3.4, §5. Gunasekara et al. (2024) N. Gunasekara, B. Pfahringer, H. Gomes, and A. Bifet Gradient boosted trees for evolving data streams. Machine Learning 113, p. 3325–3352. Cited by: §5. Hoeffding (1963) W. Hoeffding Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, p. 409–426. Cited by: §1, §3.1. Holmes et al. (2005a) G. Holmes, R. Kirkby, and B. Pfahringer Stress-testing hoeffding trees. In Knowledge Discovery in Databases: PKDD 2005, A. M. Jorge, L. Torgo, P. Brazdil, R. Camacho, and J. Gama (Eds.), Berlin, Heidelberg, p. 495–502. External Links: ISBN 978-3-540-31665-7 Cited by: §3.1. Holmes et al. (2005b) G. Holmes, R. Kirkby, and B. Pfahringer Stress-testing hoeffding trees. In Knowledge Discovery in Databases: PKDD 2005, Berlin, Heidelberg, p. 495–502. Cited by: §3.1, §4. Hulten et al. (2001) G. Hulten, L. Spencer, and P. Domingos Mining time-changing data streams. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, New York, NY, USA, p. 97–106. Cited by: §5. Kuncheva and Whitaker (2003) L.I. Kuncheva and C. Whitaker Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy. In Machine Learning, Vol. 51, p. 181–207. Cited by: §4. Louppe and Geurts (2012) G. Louppe and P. Geurts Ensembles on random patches. In Machine Learning and Knowledge Discovery in Databases, P. A. Flach, T. De Bie, and N. Cristianini (Eds.), Berlin, Heidelberg, p. 346–361. External Links: ISBN 978-3-642-33460-3 Cited by: §3.4. Lu et al. (2019) J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, and G. Zhang Learning under concept drift: a review. IEEE Transactions on Knowledge and Data Engineering 31 (12), p. 2346–2363. External Links: Document Cited by: §1, item 3, §2. Manapragada et al. (2022) C. Manapragada, H.M. Gomes, M. Salehi, A. Bifet, and G. I. Webb An eager splitting strategy for online decision trees in ensembles. In Data Min Knowl Disc, Vol. 36, p. 566–619. Cited by: §3.2, §4, §5, §5. Manapragada et al. (2018) C. Manapragada, G. I. Webb, and M. Salehi Extremely fast decision tree. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’18, New York, NY, USA, p. 1953–1962. External Links: ISBN 9781450355520, Document Cited by: §1, §3.2, §3.2, §5. Nowak Assis et al. (2025) D. Nowak Assis, J. P. Barddal, and F. Enembreck Behavioral insights of adaptive splitting decision trees in evolving data stream classification. Knowl Inf Syst. Cited by: §3.3, §5, footnote 1. Oza and Russell (2001) N. C. Oza and S. J. Russell Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. R3, p. 229–236. Cited by: §3.4, §3.4, item 1.. Paim and Enembreck (2024a) A. M. Paim and F. Enembreck Adaptive random tree ensemble for evolving data stream classification. Knowledge-Based Systems 309, p. 112830. External Links: ISSN 0950-7051, Document, Link Cited by: §3.4, §5. Paim and Enembreck (2024b) A. M. Paim and F. Enembreck Adaptive regularized ensemble for evolving data stream classification. Pattern Recognition Letters 180, p. 55–61. External Links: ISSN 0167-8655, Document, Link Cited by: §3.4, §5. Quinlan (1992) J. Quinlan C4.5: programs for machine. 340 Pine Street, 6th Floor San Francisco, CA 94104 USA. Cited by: §3.1, §3.1. Souza et al. (2020) V. M. Souza, D. M. dos Reis, A. G. Maletzke, and G. E. Batista Challenges in benchmarking stream learning algorithms with real-world data. Data Mining and K1nowledge Discovery 34, p. 1805–1858. Cited by: §5, §6.1.1. Street and Kim (2001) W. N. Street and Y. Kim A streaming ensemble algorithm (sea) for large-scale classification. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, New York, NY, USA, p. 377–382. Cited by: §5.