Robust Stream Classification using Time Neutralising Decision Trees

AI summary

Overview

• Research area: Data stream learning / concept drift, with a focus on decision tree architectures and the batch-versus-incremental learning debate.
• Technical level: Intermediate. Readers need basic familiarity with decision trees, information gain, and the idea of a non-stationary data distribution; the information-theoretic argument is presented compactly and supported by appendix simulations.
• Scope: The paper introduces Time Neutralising Trees (TNT), a batch decision tree that uses instance arrival time as a training-time feature to filter out stale data, and evaluates it against incremental trees and sliding-window batch trees on 24 data streams.

What This Paper Is About

Stream learning has traditionally assumed each instance is seen once and cannot be stored, so deployed models rely on drift detectors to signal when to reset or retrain. Those detectors generally report only when drift happened, not where in the feature space it happened. The authors argue that once storing instances is allowed, a learner can instead work out for itself which historical samples are still relevant, and they build a decision tree that does exactly that.

Key Contributions

1. A refinement of the concept drift definition that conditions drift on sub-regions of the feature space rather than treating it as a global phenomenon, together with information-theoretic formalisms for when retraining or resetting is the appropriate action.
2. Time Neutralising Trees (TNT), a decision tree that treats time indices as a feature during training, detects when a temporal split is more informative than the best spatial split, and then filters ("neutralises") training instances whose labels are statistically inconsistent with the most recent context. Filtered instances can be re-admitted if the stream returns to a previous context.
3. An evaluation of TNT against incremental trees (HT, EFDT, PLASTIC, HAT, LAST), drift-detector-reset trees (HT with ADWIN, DDM, or D3), and sliding-window batch trees on 24 real and semi-real streams from the USP DS repository. The authors describe this as the most comprehensive evaluation of decision tree algorithms for data stream classification tasks.
4. A demonstration that TNT can serve as a preprocessing filter in front of other batch architectures (Random Forest, Gradient Boosting, MLP, DNN) on the Hyperplane stream, letting models with no native drift adaptation match streaming ensembles.

Main Findings

• Batch trees beat incremental trees: On the 24 streams, batch decision trees clearly separate from incremental decision trees in the critical difference diagram. The best-ranked methods are the TNT variants and the 500-instance sliding-window batch tree, while all incremental trees (including the drift-aware HAT and LAST) rank lower. The authors note that as few as 250 stored samples was enough on this benchmark.
• TNT ranks best among the trees evaluated: TNT₅₀₀ and TNT achieve mean ranks of 4.8 and 5.2 respectively, against 5.2 for DT₅₀₀ and 7 for DT∞. TNT's gains are described as particularly noticeable on the GasSensorArray (GS), StarLightCurves (SL), and Yoga (YG) streams.
• Passive forgetting still helps: TNT₅₀₀ (retrained every 50 instances on the last 500) ranked higher on average than TNT trained on the full history, and DT₅₀₀ ranked higher than DT∞. The authors suggest fewer but still sufficient samples reduce overfitting to historical data, and that windowing counteracts conservatively tuned filtering.
• Incremental trees win on a few streams: The incremental learners outperform batch trees on Electricity (EL), Forest Cover Type (FC), and Outdoor Objects (OD), which the authors associate with high label autocorrelation and/or heavy prior study in the literature. They also note these results are flattered by the incremental models updating immediately after each prediction while batch models must wait 50 predictions, and cite related work showing incremental performance drops under verification latency.
• Incremental trees fail on some streams: Streams with high feature counts or class imbalance, such as Cancer (CA), Heartbeats (HB), and Ozone (OZ), are cases where the incremental trees are unable to generalise at all.
• Filtering as preprocessing: On the Hyperplane stream (chosen because it simulates pure posterior drift), Kappa rises from 0.38 to 0.73 for DT, 0.39 to 0.76 for RF, 0.38 to 0.75 for GB, 0.39 to 0.74 for MLP, and 0.39 to 0.75 for DNN when TNT filtering is applied first. TNT alone scores 0.72, while the streaming ensembles AMF, ARF, and SRP score 0.52, 0.72, and 0.76.
• Hyperparameter sensitivity: Tuning over 100 Latin Hypercube configurations on five synthetic streams (Hyperplane, RandomRBFDrift, SEA, STAGGER, RotatingMoons) indicated that the minimum split sample count N_min and the number of split candidates per feature were generally the most important parameters. A low filter factor λ was most significant on Hyperplane, where old instances become outdated quickly, but λ was less pivotal than expected overall; too low a λ was detrimental on the other streams.
• Leaf model ablation: Replacing impure leaf nodes with Logistic Regression gave a slight improvement over a majority-class leaf, mitigating the effect of poorly chosen N_min and split-candidate settings; Naive Bayes was also tested.
• Stated caveat: The authors do not claim TNT ensembles are competitive out of the box — building an ensemble of TNT trees was found ineffective due to repeated computation across base models, and is left to future work.

Methodology in Plain English

The authors start from an observation about where drift occurs in feature space. Picture a one-dimensional stream with a single drift point: some regions are entirely new (learn from the new data), some are stable (do nothing), and some contain old instances that now actively conflict with current labels (forget them before learning). Only the third case needs active forgetting, and it is the case the method targets.

The theoretical argument is that the mutual information between features and labels over an entire non-stationary stream is a weighted mixture across all distinct concepts the stream has passed through, and this mixture is bounded above by the average mutual information of those individual concepts. As the number of distinct concepts grows, whole-stream mutual information tends to zero. So the goal becomes finding a time interval containing the most recent instance that maximises information about the labels. Drift detectors implicitly approximate this, but cannot recover what they forget.

TNT implements this with an ordinary decision tree procedure modified in one place. At every candidate split node it computes the best possible split on time indices as well as the best split on features. If the time split beats the feature split by more than a margin λ (λ in [0,1), where values near 0 make the tree react and filter aggressively), the tree stops looking for a spatial split and instead grows a temporary subtree that splits only on time. That subtree is grown until purity, a minimum sample count N_min, or a minimum information gain τ is reached. The rightmost leaf, representing the most recent context, is used as a reference; every other leaf's label distribution is compared to it with a Mann-Whitney U test at significance α_mwu. Leaves that fail to differ are merged with the reference (their instances are deemed still relevant); the rest are discarded. The surviving instances are handed back, the best spatial split is recomputed on them, and normal tree building resumes. Because relevant data can sit in disjoint stretches of time, the filtering splits repeatedly rather than cutting time once. Time indices are used only during training, never at inference, since splits on time become meaningless as new instances arrive.

Evaluation uses the test-then-train protocol on 24 streams spanning 2 to 3,600 features and 503 to 581,012 instances, spanning domains such as urban development, medicine, and epidemiology. Batch trees are retrained from scratch every 50 instances on windows of 50, 100, 250, 500, or all history; TNT uses the full-history schedule and TNT₅₀₀ the 500-instance schedule. Performance is tracked with Cohen's Kappa measured every 50 instances over the last 50, after a 50-instance warm start, with 10 replicates of stochastic methods, fractional ranking, Mann-Whitney U tests at p = 0.05 with Holm-Bonferroni correction, and a critical difference diagram.

Why This Matters

• Research impact: The paper adds a concrete, tunable mechanism to the argument that the "no storage" assumption in stream learning is an unnecessary constraint. It reframes drift adaptation as a feature-space-local question of which historical instances to keep, rather than a global binary reset triggered by a detector, and it provides the information-theoretic framing for that reframing.
• Real-world applications:
  • Energy and transport monitoring: The Electricity stream and the paper's own example of weekday-versus-weekend public transport usage illustrate recurring drift, where discarded information later becomes useful again — exactly the case TNT's re-inclusion mechanism targets.
  • Medical monitoring: The Heartbeats and Cancer streams represent settings where sensor or clinical data drift over time and where classifier reliability matters.
  • Environmental and industrial sensing: The Ozone and GasSensorArray streams stand for air-quality and chemical-sensor deployments where sensor drift and seasonal context changes are routine.
  • Urban and epidemiological analytics: The USP DS repository streams cover urban development and epidemiology, where population behaviour shifts over months or years.
• Industry relevance: The practical message is that when historical data can be retained, a retrained batch model with sensible filtering is often a better investment than a specialised incremental learner, and that TNT filtering can be bolted in front of existing Random Forest, Gradient Boosting, or neural network pipelines to give them drift robustness without redesigning them.

Future Directions

• Extending the time-filtering procedure to ensemble architectures such as Random Forests, so TNT-style filtering can be compared directly against Adaptive Random Forests, Aggregated Mondrian Forests, Streaming Random Patches, and Streaming Gradient Boosted Trees.
• Reducing TNT's sensitivity to the time-filtering threshold λ by making it context-sensitive, with the authors suggesting a Hoeffding-like bound analogous to those used in incremental decision trees.
• Addressing the repeated-computation problem that made naive TNT ensembles ineffective, which currently blocks an ensemble version of the method.
• The setting itself raises an open question the paper does not resolve in its main body: how to bound and manage the storage cost of keeping historical instances, since the full-history TNT variant is acknowledged as infeasible in some deployments, and only a 500-instance windowed variant is offered as a mitigation.

Target Audience

Researchers and practitioners working on concept drift and stream classification will get the most from this paper, particularly those already questioning the single-pass, no-storage assumption. It is also relevant to applied machine learning engineers who maintain production models on evolving data and want a lower-complexity alternative to drift detectors plus resets, and to readers interested in the information-theoretic treatment of non-stationarity. Readers without a background in mutual information or hypothesis testing will need to lean on the plain-language descriptions of the filtering procedure.

Authors’ abstract

Data Streams are characterised as a potentially infinite source of data subject to non-stationarity. This non-stationarity, also called Concept Drift, often results in deployed predictive models having to be perpetually retrained as the underlying data generating process of the stream changes over time. Drift Detectors are a class of methods used to identify these changes, triggering these retraining procedures. Historically, Stream Learning has operated under the assumption that instances are only seen once, and cannot be stored for later use. Contemporary work relaxes this assumption, yet drift detection and simple resetting procedures are still ubiquitous. Building on related work which has shown that traditional Batch Learning algorithms often outperform Stream Learning algorithms when instances can be stored, we introduce Time Neutralising Trees (TNT), a Decision Tree architecture that enables robust stream classification in settings with Concept Drift. During training, TNT will filter out ("neutralise") old training samples that are no longer relevant given the current context of the stream. If those instances become relevant again, TNT will then re-include them. We evaluate TNT, and related algorithms on 24 real and semi-real classification data streams from the USP DS repository. Results show strong evidence that TNT achieves best-in-class performance on a wide-range of data streams with varying concept drift types.