Random forest

Random forests were introduced by Leo Breiman (2001, Machine Learning 45(1)). They combine bagging (bootstrap aggregating, Breiman 1996), where each tree is trained on a bootstrap sample drawn with replacement, with random feature subsampling: at every split only a random subset of features is considered. The second source of randomness decorrelates the trees, and because the variance of an average falls with the correlation between its members, the ensemble has much lower variance than any single deep tree while keeping its low bias.

The key hyperparameters are the number of trees, where more is never worse for accuracy but costs time; max_features, the size of the random subset, with sqrt(p) a common default for classification and all features the scikit-learn default for regression; and tree depth or minimum leaf size. Breiman's original method lets each tree vote; scikit-learn instead averages the trees' predicted class probabilities.

Since each bootstrap sample leaves out about a third of the rows (1 - 1/e, roughly 36.8 percent), every tree has out-of-bag samples it never saw. Predicting each row with only the trees that did not train on it gives the out-of-bag error, a nearly free estimate of generalisation error. Forests also yield feature importances, either the mean decrease in impurity (fast but biased toward high-cardinality features) or permutation importance.

Random forests are robust, parallelise trivially and need little tuning, which makes them a strong baseline for tabular data. Well-tuned gradient boosting usually beats them on accuracy, and like all tree ensembles they cannot extrapolate beyond the target range seen in training. Extremely randomised trees (Geurts et al., 2006) push the idea further by also choosing split thresholds at random.