Robust Stream Classification using Time Neutralising Decision Trees
Organizations: Utrecht University, 8 Hiedelberglaan, Utrecht, 3584 CS, NL
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.
Figures & tables
| Name | Description | Value |
| Controls the time filtering sensitivity. | 0.20 | |
| Minimum number of samples needed to make a spit decision. | 20 | |
| Stopping threshold for when time splits are not informative. | 0.05 | |
| Threshold used to merge time leaf nodes using Mann-Whitney U Test. | 0.05 | |
| thresholds max | Number of split candidates generated per feature. | 15 |
| leaf model | Predictor that replaces non-pure leaf nodes. | LR |
| Method | Kappa without TNT | Kappa with TNT |
| TNT | 0.72. | - |
| DT | 0.38 | 0.73 |
| RF | 0.39 | 0.76 |
| GB | 0.38 | 0.75 |
| MLP | 0.39 | 0.74 |
| DNN | 0.39 | 0.75 |
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| Name | Features | Classes | Instances |
| Asfault (AF) [ 50 ] | 64 | 5 | 8,565 |
| Cancer (CA) [ 49 ] | 2,352 | 7 | 9,256 |
| Chess (CH) [ 58 ] | 8 | 3 | 503 |
| Electricity (EL) [ 24 ] | 8 | 2 | 45,312 |
| Forest Cover Type (FC) [ 5 ] | 54 | 7 | 581,012 |
| Gas Sensor Array (GS) [ 53 ] | 128 | 6 | 13,910 |
| Name | Range Explored | Final Value |
| [0.01, 0.5] | 0.20 | |
| [10, 50] | 20 | |
| [0.01, 0.1] | 0.05 | |
| [0.0001, 0.1] | 0.05 | |
| thresholds max | [5, 25] | 15 |
| leaf model | {MC, LR, NB} | LR |
| Name | Range Explored | Total (N) |
| Hyperplane [ 28 ] | mag_change = 0.2 | 5000 |
| RandomRBFDrift [ 40 ] | change_speed = 1.0 | 1000 |
| sample_per_phase = 100 | ||
| RotatingMoons ( A.4 ) | rotation_angle = 90 | 1600 |
| cycles = 4 | ||
| SEA [ 51 ] | sample_per_variant = 200 | 800 |
| MC | LR | NB | |
| Hyperplane | 0.61 | 0.61 | 0.61 |
| RandomRBFDrift | 0.40 | 0.44 | 0.44 |
| RotatingMoons | 0.78 | 0.81 | 0.82 |
| SEA | 0.78 | 0.81 | 0.80 |
| STAGGER | 0.44 | 0.57 | 0.53 |
| Average | 0.60 | 0.65 | 0.64 |
| EL | FC | OD | |
| DDM | 0.61 | 0.42 | 0.63 |
| DDM (Batched) | 0.45 | 0.07 | 0.19 |
Classification
Classification maps observations to discrete labels, including familiar, unknown, hierarchical, or multiple categories.
See all 449 papers