Online Random Forest
- Introduced by
- Saffari, A. et al.
- Year
- 2009
- Type
- Incremental ensemble (streaming decision trees)
- Family
- Machine learning
What does it do?
Online Random Forest (ORF) extends the classic Random Forest to streaming settings, updating each tree incrementally as new observations arrive without storing or replaying the full training set.
Algorithms such as Adaptive Random Forests (ARF) add drift detection so the ensemble adapts when the data distribution changes over time.
The intuition behind the method
Classic Random Forest requires the entire dataset upfront to grow its trees. Online Random Forest replaces batch bootstrap sampling with a Poisson-weighted online bagging trick: each incoming observation is passed to every tree, which decides — by drawing a Poisson count — how many times to treat that example as a new training point. Trees grow incrementally using online split-finding criteria (e.g., Hoeffding bounds), and a drift-detection module watches for concept drift, replacing stale trees with fresh ones. The result is a forest that learns continuously from a stream while still combining multiple diverse trees for variance reduction.
History
Online bagging was formalised by Oza & Russell (2001) as a Poisson-weighted approximation to bootstrap aggregation. Saffari et al. (2009) introduced On-line Random Forests combining online bagging with randomised feature selection and Hoeffding-based split criteria for computer-vision streams. Gomes et al. (2017) introduced Adaptive Random Forests (ARF), adding per-tree drift detection via ADWIN, and demonstrated state-of-the-art accuracy on benchmark data-stream classification tasks. ARF became a standard baseline in the MOA (Massive Online Analysis) framework.
When to use it
Use Online Random Forest when data arrives continuously or in large batches that cannot be held in memory, when concept drift is plausible (e.g., financial streams, sensor networks, user behaviour logs), or when low-latency predictions are required before the full dataset is available. It is also a natural fit for applications where labelled data trickles in over time. Avoid it when the full dataset fits comfortably in memory and retraining is affordable — in that case a standard Random Forest trained offline will typically be more accurate and simpler to validate. Avoid it also when you need stable, reproducible feature-importance rankings, as online forests produce less stable importance estimates than their batch counterparts.
Limitations and considerations
- Split decisions made early with sparse data can be sub-optimal and hard to revise.
- Feature-importance estimates are less stable than in batch Random Forest.
- Hyperparameter tuning (number of trees, drift-detection thresholds) is more complex in a streaming context.
- Evaluation requires dedicated stream-based protocols (prequential/test-then-train) that differ from standard cross-validation.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Learns from streaming data with constant memory per tree, independent of stream length.
- Adapts to concept drift when paired with drift-detection mechanisms such as ADWIN.
- Inherits the variance-reduction benefits of ensemble aggregation even in an online setting.
- Provides usable predictions from the first few observations, improving over time.
- No need to store or replay the full historical dataset.
Applications
- Real-time fraud and intrusion detection on network or transaction streams.
- Predictive maintenance from sensor streams where distributions shift with equipment ageing.
- Click-through rate prediction in advertising where user behaviour evolves daily.
- Medical monitoring where patient state changes continuously over time.
- Environmental and climate sensing with non-stationary seasonal patterns.
How it works
How it works
A set of T trees (or Hoeffding trees) is initialised. Each tree maintains per-leaf sufficient statistics — class counts or sum-of-squares for regression — instead of storing raw observations, making the model memory-constant per tree.
For each arriving observation, each tree independently draws k from a Poisson(1) distribution and treats the observation as k virtual replications of itself. When k = 0 the tree skips the point (acting as its out-of-bag sample). This approximates bootstrap sampling without requiring the full dataset.
Formula
k \sim \text{Poisson}(\lambda),\; \lambda=1Each tree updates the sufficient statistics at its active leaf. A split is triggered when a statistically sound criterion (such as the Hoeffding bound) indicates that the best split is unlikely to change with more data, after which the leaf is expanded into an internal node and new leaves are initialised.
An optional drift-detection module (e.g., ADWIN) monitors each tree's prediction error on the out-of-bag stream. When a statistically significant degradation is detected, the affected tree is reset or replaced with a freshly seeded tree, keeping the ensemble current with evolving distributions.
At any point, all active trees vote: majority vote for classification or mean prediction for regression. Trees that have processed very few examples may be down-weighted or excluded until they accumulate enough data to give reliable votes.
Formula
\hat{y} = \text{mode/mean of active trees}Common pitfalls
- Evaluating with standard k-fold cross-validation, which assumes i.i.d. data and ignores temporal order.
- Ignoring concept drift: failing to include a drift-detection component when the data distribution changes over time.
- Comparing online forest accuracy directly to a batch Random Forest trained on the full historical dataset — the latter has an inherent information advantage.
- Using too few trees early in the stream before each tree has seen enough data to make reliable splits.
- Forgetting that Poisson-weighted bagging approximates bootstrap — it does not exactly reproduce the statistical properties of batch bootstrap.
Frequently asked questions
How does Online Random Forest differ from standard Random Forest?
Standard Random Forest trains all trees at once on the full dataset using bootstrap sampling. Online Random Forest replaces batch bootstrap with Poisson-weighted online bagging, updates tree splits incrementally as each observation arrives, and optionally detects and adapts to concept drift — all without storing past data.
What is the Poisson weighting trick?
Each incoming example is shown to each tree k times, where k is drawn from Poisson(1). Because the expected value of k is 1, and k = 0 with probability ~37%, this statistically approximates the bootstrap process (sampling with replacement) without needing the full dataset in memory.
How should I evaluate an online random forest?
Use the prequential (test-then-train) protocol: for each incoming observation, first predict with the current model, record the error, then update the model. This gives an unbiased, temporally ordered estimate of predictive performance without data leakage.
When should I add drift detection?
Whenever the data-generating process is likely to change over time — for example, user preferences, financial markets, or mechanical systems that wear. Without drift detection, stale trees accumulate and drag down ensemble accuracy. ADWIN is a common, well-tested choice.
Is Adaptive Random Forest the same thing?
ARF is the most widely adopted variant of Online Random Forest. It combines online bagging, random feature selection, and per-tree ADWIN drift detection, and is available in the MOA and scikit-multiflow/River libraries. The term 'Online Random Forest' often refers generically to the family; ARF is a specific, highly recommended implementation.
Related methods
Sources
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.
Open publication referenceCopied.Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.
Open DOI referenceCopied.