Source-linked AI summary
Random Forests for Big Data
Robin Genuer, Jean-Michel Poggi, Christine Tuleau-Malot, Nathalie Villa-Vialaneix
TL;DR
Massive, online, and heterogeneous data create challenges for statistical methods, including random forests. The paper reviews and experiments parallel, subsampling, divide-and-conquer, and online adaptations for classification at Big Data scale. Across the tested variants, sampRF with a small sampling fraction and blbRF were fastest, whereas onRF was not computationally efficient; the authors also identify limitations involving parameter choices and subsample representativeness.
Problem
Big Data creates statistical challenges because datasets can be massive, online, heterogeneous, and too large to fit in a single computer’s memory.
Method
The paper selectively reviews and experimentally compares five random-forest variants using subsampling, parallel or divide-and-conquer strategies, and online learning.
Results
sampRF with a small sampling fraction and blbRF were fastest, while onRF was not computationally efficient even compared with standard seqRF.
Takeaways & Limitations
Random-forest variants differ in relative computational performance, and their design choices require care to obtain low prediction error.
Takeaways & Limitations
Subsampled methods can suffer drastic prediction deterioration when subsamples lack representativeness, while prediction-error estimates can be poor in many cases.
Abstract
from arXiv · showhide
Big Data is one of the major challenges of statistical science and has numerous consequences from algorithmic and theoretical viewpoints. Big Data always involve massive data but they also often include online data and data heterogeneity. Recently some statistical methods have been adapted to process Big Data, like linear regression models, clustering methods and bootstrapping schemes. Based on decision trees combined with aggregation and bootstrap ideas, random forests were introduced by Breiman in 2001. They are a powerful nonparametric statistical method allowing to consider in a single and versatile framework regression problems, as well as two-class and multi-class classification problems. Focusing on classification problems, this paper proposes a selective review of available proposals that deal with scaling random forests to Big Data problems. These proposals rely on parallel environments or on online adaptations of random forests. We also describe how related quantities -- such as out-of-bag error and variable importance -- are addressed in these methods. Then, we formulate various remarks for random forests in the Big Data context. Finally, we experiment five variants on two massive datasets (15 and 120 millions of observations), a simulated one as well as real world data. One variant relies on subsampling while three others are related to parallel implementations of random forests and involve either various adaptations of bootstrap to Big Data or to "divide-and-conquer" approaches. The fifth variant relates on online learning of random forests. These numerical experiments lead to highlight the relative performance of the different variants, as well as some of their limitations.
1. Introduction
Big Data challenges statistical science through scale, computational complexity, online data, and heterogeneity. The paper reviews and evaluates strategies for scaling random forests, including subsampling, divide-and-conquer, parallel processing, and online updates.
- 1.1. Statistics in the Big Data world: Big Data often combines massive volume with online data streams, heterogeneity, and poorly structured data that hinder simple queries.These characteristics are summarized by the three Vs: Volume, Velocity, and Variety.
- 1.1. Statistics in the Big Data world: Big Data can exceed a single computer’s memory, requiring distribution across multiple computers and specialized frameworks.The paper notes that data size is constrained by available resources and RAM.
- 1.1. Statistics in the Big Data world: Large datasets create runtime problems for statistical procedures, especially complex prediction and exploratory-analysis tasks.The paper also links scale to algorithmic and theoretical consequences.
- 1.1. Statistics in the Big Data world: Common scaling strategies include subsampling, divide-and-conquer, algorithm weakening, and online updates.Divide-and-conquer splits a problem into smaller problems and combines their results; online updates use sequential low-cost steps.
- 1.2. Random forests and Big Data: Random forests are widely used nonparametric methods, but adapting them to Big Data raises open questions about implementations, statistical accuracy, and computational efficiency.The paper focuses on prediction performance, out-of-bag error, and variable importance while reviewing parallel and online approaches.
- 1.2. Random forests and Big Data: The paper reviews scalable random-forest strategies and experiments five variants on massive, simulated, and real-world datasets.The variants include subsampling, parallel bootstrap or divide-and-conquer methods, and online learning.
2. Random Forests
Random forests combine randomized decision trees built from bootstrap samples and aggregate their predictions for classification or regression. Their construction also supports out-of-bag error estimation and variable-importance assessment.
- Statistical targets: Random forests provide estimators of the Bayes classifier and the regression function under a zero conditional-mean noise model.For regression, the model is Y = s(X) + ε with E[ε|X] = 0.
- Decision trees: A classification tree predicts a class by following node questions from the root to a leaf, producing a piecewise-constant classifier.Its splits are parallel to the axes defined by the original variables.
- Random forest construction: Random forests aggregate many binary decision trees built using bootstrap samples and randomized tree construction.Bootstrap samples select observations with replacement, while randomized trees differ from CART through random variable selection at each node and no pruning.
- Prediction: For classification, the forest predicts by majority vote; for regression, it averages individual tree predictions.The method covers classification and regression problems.
- Big Data context: Big Data adaptations often mimic Breiman’s original random forest, but alternatives resample data differently or modify tree construction.The paper focuses on prediction performance, out-of-bag error, and variable importance in this context.
- Assessment: The out-of-bag error uses each observation only in trees whose bootstrap samples excluded it, then compares its label with the most frequent prediction.Variable importance is assessed by permuting a predictor in out-of-bag samples and comparing tree errors before and after permutation.
3. Scaling random forests to Big Data
The paper reviews subsampling, parallelization, alternative bootstrap schemes, and divide-and-conquer strategies for scaling random forests to Big Data. These variants reduce computational demands but introduce representativeness, bootstrap, tree-depth, and methodological mismatches that affect performance and interpretation.
- Sub-sampling RF: Subsampling m ≪ n observations without replacement and applying the original sequential or parallel RF algorithm reduces memory usage and computational effort.The approach builds a final forest with Q trees from the subsample.
- Scaling strategies: Random forests can be scaled by subsampling observations, parallelizing forest construction, using alternative bootstrap schemes, or applying divide-and-conquer methods.The reviewed variants include sampRF, parRF, m-out-of-n RF, BLB RF, and dacRF.
- Parallel implementations: Parallel RF partitions tree learning across K processes, with each process building a smaller forest whose trees are aggregated into the final classifier.The expected computational-time reduction is approximately a factor of K.
- Mismatches with original RF: Standard RF can become impractical at very large n because bootstrap samples contain approximately 0.63n distinct observations and fully grown trees may be deep and computationally expensive.The paper also notes that the impact of controlling the maximum number of tree nodes had not been studied in the cited discussion.
- Alternative bootstrap schemes: m-out-of-n bootstrap and BLB reduce the number of distinct observations processed, while BLB retains bootstrap samples of size n from only m ≪ n observations.The m-out-of-n approach may require careful selection of m; BLB is designed to avoid its bias while remaining manageable for very large n.
- Comparisons and results: The reviewed methods differ in equivalence and theoretical support: parRF differs from standard sequential learning only in tree-learning order, while consistency results are reported for bootstrap estimation and partition-based approaches.The paper’s experiments compare relative performance and limitations across variants.
4. Experiments
Experiments compare five Big Data random-forest variants on simulated and real datasets, examining accuracy, computational cost, error estimation, subsampling, bias, and online learning. The results show that several variants approach sequential random forests, but error estimates and accuracy can depend strongly on sampling and data balance.
- Experimental design: 15-million-observation simulated and 120-million-observation real-world experiments compare five Big Data random-forest variants.The study includes subsampling, parallel implementations, divide-and-conquer approaches, and online random forests.
- Experimental design: The sequential RF baseline used 500 trees, required approximately 18 hours to train, and achieved an OOB error of 4.564e−3.The OOB error served as the baseline for the other experiments.
- Error estimation and bias: OOB error was consistently close to test error, whereas BDerrForest could be biased, overestimating error for small sampRF and moonRF fractions and underestimating it for dacRF in extreme imbalance.For p = 0.01, dacRF was most affected, while moonRF was comparatively robust and blbRF strongly overestimated prediction error.
- Accuracy and computation: Many variants achieved performance close to sequential RF, including sampRF and moonRF with subsamples containing at least 0.1% of the original observations.blbRF was also close to seqRF and stable across K and q, while dacRF produced an accurate predictor.
- Subsampling and data bias: When subforests used observations from different conditional distributions X|Y, the test misclassification rate increased by more than 50-fold and BDerrForest became a poor error estimate.This distributional mismatch strongly deteriorated forest performance.
- Subsampling and data bias: Using about 0.01% of the data produced almost no accuracy difference from using all data, making small subsamples the best time–accuracy compromise when BDerrForest remains reliable.Subsample representativity strongly affects the estimated model, and balanced data improved detection of late flights by favoring sensitivity over specificity.
5. Conclusion and discussion
The paper reviews and evaluates Big Data adaptations of random forests, finding satisfactory predictive performance but important computational and representativeness limitations. It also identifies re-weighting and data-stream methods as directions for extending these approaches.
- 5.2. Re-weighting schemes: Future directions include re-weighting forests to address sampling bias and adapting online random forests to unbounded data streams processed with limited memory.
- 5.1. Conclusions: The review covers parallel and online random forests, including approximations of out-of-bag errors, and evaluates five variants on datasets with up to 120 million observations.The experiments include simulated and real-world data, subsampling, adapted bootstrap schemes, divide-and-conquer methods, and online learning.
- 5.1. Conclusions: sampRF with a small sampling fraction and blbRF were fastest, whereas onRF was not computationally efficient even relative to sequential standard random forests.
- 5.1. Conclusions: Satisfactory predictive results were obtained across methods, but subsample sizes and chunk counts must be designed carefully to keep prediction error low.
- 5.1. Conclusions: The easily designed out-of-bag error was often a poor estimate of prediction error, so an independent smaller test subsample is advised when feasible.With massive datasets, computing such a test error can be straightforward.
- 5.1. Conclusions: Nonrepresentative subsamples can drastically degrade Big Data random-forest performance, especially for dacRF, while constructing representative subsamples is itself difficult.
Additional file 1 — R and python scripts used for the simulation
R scripts used in the simulation sections are available at the listed GitHub address.
- R scripts used in the simulation sections are available at the listed GitHub address.