RANDOM FORESTS
📜 Abstract
Random forests are a combination of tree predictors such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest. The generalization error for forests converges a.s. to a limit as the number of trees in the forest becomes large. The generalization error of a forest of tree classifiers depends on the strength of the individual trees in the forest and the correlation between them. Using a random selection of features to split each node yields error rates that compare favorably to Adaboost (Freund and Schapire[1996]), but are more robust with respect to noise. Internal estimates monitor error, strength, and correlation and these are used to show the response to increasing the number of features used in the splitting. Internal estimates are also used to measure variable importance. These ideas are also applicable to regression.
✨ Summary
Summary
Breiman defines a random forest as an ensemble of tree predictors whose construction is governed by independently and identically distributed random vectors. The paper establishes that, as the number of trees increases, the forest converges almost surely to a limiting predictor and therefore does not overfit merely because additional trees are added. Its central theoretical analysis relates generalization error to two quantities: the strength of the individual trees and their correlation. The resulting bound motivates injecting randomness that lowers inter-tree correlation without substantially reducing predictive strength.
The empirical method combines bootstrap sampling with random selection of input variables, or with randomly generated linear combinations of inputs. The paper introduces out-of-bag estimates for monitoring ensemble error, tree strength, and correlation without requiring a separate test set. It also presents permutation-based variable-importance estimates. Experiments on classification and regression data indicate competitive accuracy relative to AdaBoost and bagging, improved robustness to label noise, useful performance when many predictors are individually weak, and straightforward parallelization. The paper further develops random forests for regression, where ensemble error is related to the correlation among tree residuals.
The work directly influenced subsequent research and practice. A 2003 study applied the method to compound classification and quantitative structure–activity relationship modeling, using its prediction aggregation, built-in performance assessment, descriptor importance, and compound-similarity capabilities in cheminformatics. (pubmed.ncbi.nlm.nih.gov) Later methodological work extended the random-forest framework to censored survival outcomes and genomic or clinical analysis. (academic.oup.com) Research applications also adopted the method for ecological and fisheries classification and used the associated R implementation. (academic.oup.com) The journal version is recorded as published in Machine Learning 45(1), pages 5–32, in October 2001, while the supplied manuscript is dated January 2001. (stat.berkeley.edu)