Random Forest and Bagging

Bagging: the general idea

Bagging is short for bootstrap aggregating, and it is exactly those two steps:

1. Bootstrap. Draw a random sample of the training data, with replacement, the same size as the original. Roughly 63% of the rows appear at least once; the rest are left out.
2. Aggregate. Train one model per sample, then combine them — majority vote for classification, mean for regression.

Each tree sees a slightly different world, so each makes slightly different mistakes. Where they agree, the signal was real. Where they disagree, one of them was chasing noise, and the vote overrules it.

What makes a forest more than bagging

Bagged trees have a weakness: if one feature is strongly predictive, nearly every tree splits on it first, and the trees end up highly correlated. Averaging correlated models buys much less than averaging independent ones.

Random Forest adds a second source of randomness. At every split, the tree may only consider a random subset of the features — typically the square root of the total for classification. A tree that is denied the dominant feature is forced to find a different, still-useful split, and the forest becomes genuinely diverse rather than forty copies of the same idea.

That is the entire difference between bagged trees and a random forest: one extra random choice, made at every node.

Two sources of randomness, one purpose

A single decision tree grown to full depth is an unstable model: change a few rows and the tree changes shape completely. A random forest turns that instability into an advantage by growing hundreds of trees and averaging their votes — but only if the trees make different mistakes. Two identical trees average to one tree.

So the forest injects randomness twice.

Bagging (bootstrap aggregating). Each tree is trained on a random sample of the rows, drawn with replacement and the same size as the original dataset. Because of the replacement, each sample contains about 63% of the unique rows, some of them several times, and leaves about 37% out.

Random feature subsets. At every split, the tree may only consider a random subset of the features — typically the square root of the total for classification. This is the step that separates a random forest from plain bagging, and it matters more than it sounds. Without it, if one feature is highly predictive, every tree splits on it first and the trees end up nearly identical. Forcing most trees to look elsewhere produces genuinely diverse trees.

The errors of diverse trees are partly independent, and independent errors cancel when averaged. That is the entire mechanism.

Out-of-bag scoring: free validation

The 37% of rows left out of each tree's bootstrap sample have a use. For any given row, roughly a third of the trees never saw it, so those trees can predict it as if it were test data.

Aggregate that across all rows and you get an out-of-bag score — an honest estimate of generalisation performance, computed during training, with no separate validation set and no extra fitting.

from sklearn.ensemble import RandomForestClassifier

forest = RandomForestClassifier(
    n_estimators=500,        # more trees never hurts accuracy, only time
    max_features="sqrt",     # the diversity knob
    min_samples_leaf=1,      # raise it on noisy data
    oob_score=True,          # free validation estimate
    n_jobs=-1,               # trees are independent: use every core
    random_state=0,
)
forest.fit(X_train, y_train)
print(forest.oob_score_)

It is not a full replacement for cross-validation — it is specific to bagged models and slightly pessimistic, since each prediction uses only a third of the forest — but for a quick, honest number during development it is hard to beat.

Why more trees never overfits

This surprises people who have internalised "more complexity means overfitting", so it is worth stating precisely.

Adding trees to a random forest does not increase the risk of overfitting. Each tree is trained independently on its own bootstrap sample, and averaging more independent estimates reduces variance and then flattens out. Going from 100 to 1,000 trees costs ten times the compute and changes accuracy by a fraction of a percent, but it does not make the model worse.

What can overfit is each individual tree, which is why min_samples_leaf and max_depth still matter on noisy data. And boosting behaves in the opposite way entirely: there, more trees absolutely can overfit, because each new tree is fitted to the previous ones' errors.

The practical implication: pick n_estimators from your compute budget, not from a validation curve. 100 for iteration, 500 or more for a final model.

Where the improvement actually comes from

A forest beats one tree by averaging away variance, not bias. This measures both halves so you can see which one it fixed.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, BaggingClassifier
from sklearn.model_selection import train_test_split, cross_val_score

X, y = make_classification(n_samples=2500, n_features=20, n_informative=6,
                           flip_y=0.12, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)

print("one tree, refit on six different bootstrap resamples of the same data:")
rng = np.random.default_rng(0)
preds = []
for i in range(6):
    idx = rng.integers(0, len(Xtr), len(Xtr))
    t = DecisionTreeClassifier(random_state=0).fit(Xtr[idx], ytr[idx])
    preds.append(t.predict(Xte))
    print("   resample %d: accuracy %.4f" % (i, (preds[-1] == yte).mean()))
preds = np.array(preds)
disagree = (preds != preds[0]).any(axis=0).sum()
print("  the six trees disagree with each other on %d of %d test rows."
      % (disagree, len(yte)))
print("  that instability IS the variance a forest removes.")
print()

for name, model in (
    ("one tree",                DecisionTreeClassifier(random_state=0)),
    ("bagging, 200 trees",      BaggingClassifier(DecisionTreeClassifier(),
                                                  n_estimators=200, random_state=0)),
    ("random forest, 200",      RandomForestClassifier(n_estimators=200, random_state=0)),
):
    s = cross_val_score(model, X, y, cv=5)
    print("%-24s cv %.4f  (folds sd %.4f)" % (name, s.mean(), s.std()))
print()
print("bagging alone gets most of it. the extra step a forest adds is picking")
print("a random subset of features at each split, which makes the trees less")
print("similar to each other -- and averaging helps more the less they agree.")
print()

print("max_features is that knob:")
for mf in (1, 2, 4, 8, 20):
    s = cross_val_score(RandomForestClassifier(n_estimators=200, max_features=mf,
                                               random_state=0), X, y, cv=5)
    print("  max_features=%2d  cv %.4f" % (mf, s.mean()))
print("  max_features=20 is every feature, which is plain bagging.")
print()

print("more trees never hurts, it just stops helping:")
for k in (5, 25, 100, 400):
    s = cross_val_score(RandomForestClassifier(n_estimators=k, random_state=0),
                        X, y, cv=5)
    print("  %3d trees  cv %.4f" % (k, s.mean()))
print()
print("that is the useful property: n_estimators is not a thing you tune for")
print("overfitting. you raise it until the score flattens, then stop paying.")

Experiments to try

1. Start with the problem. Set the Number of Trees slider to 1. The boundary is a jagged staircase with isolated islands carved around individual mislabelled points. Train accuracy is near perfect and test accuracy is not — and pressing Regrow Forest four or five times swings test accuracy by several points. Watch Accuracy Spread: that swing is the variance bagging exists to remove.
2. Add trees and watch it settle. Set the Number of Trees slider to 40. The islands dissolve, test accuracy climbs, and Accuracy Spread collapses to a point or two — without any single tree having improved.
3. Confirm nothing was tuned away. Compare Forest Test Accuracy against Avg Single Tree. The individual trees are no better than before; the gain comes entirely from voting.
4. Take away one source of diversity. Untick Feature Subsampling and watch Gain from Voting shrink and Trees Disagreeing fall. Every tree may now consider both features at every split, so they reach for the same ones and their mistakes start to coincide. The gain does not vanish entirely, because bootstrapping still hands each tree a different sample — that is the difference between bagged trees and a random forest, measured.
5. Cripple the trees instead. Set the Max Depth slider to 1. Each tree is now a single split — a stump — and no amount of voting fixes it. Bagging reduces variance, not bias.
6. Turn up the noise. Set the Label Noise slider to 0.3, then compare one tree against forty. The gap between them widens: the more noise there is to memorise, the more averaging is worth.

Why it does not overfit with more trees

This surprises people: adding trees to a random forest does not cause overfitting. More trees means a more precise estimate of the same average, and the curve flattens rather than turning back up. Past a few hundred trees you are spending compute for no gain, but you are not doing damage.

What does overfit is depth, along with allowing tiny leaves. Those control how much each individual tree can memorise, and they are the knobs worth tuning.

Out-of-bag error, free of charge

Each tree leaves out about 37% of the rows during bootstrapping. Those rows are unseen by that tree, so you can evaluate the tree on them — and averaging that over the forest gives an honest estimate of generalisation error with no separate validation split at all. It is one of the few genuinely free lunches in machine learning, and it is why random forests are so convenient on small datasets.

Where this goes wrong

• Trusting the default feature importances. Impurity-based importance is biased toward high-cardinality and continuous features, which can look important simply because they offer more places to split. Prefer permutation importance.
• Expecting extrapolation. A forest predicts by averaging training labels in a region. Outside the range of the training data it returns the nearest thing it saw and flatlines — it cannot continue a trend the way a linear model can.
• Assuming it beats boosting. On structured tabular data, gradient boosting usually edges it out. Forests win on robustness: they need almost no tuning and are very hard to break.
• Ignoring class imbalance. Majority voting inherits whatever imbalance is in the data. Use class weights or balanced bootstrapping — see training on imbalanced data.

Worth remembering

A random forest trains many deep, deliberately different trees and lets them vote, which cancels the variance that makes any single deep tree unreliable. The diversity comes from two places — a bootstrap sample of the rows and a random subset of the features at every split — and without that diversity extra trees buy nothing. Adding trees never overfits, so depth and leaf size are the parameters that actually need care. It is the sensible default when you want a strong model with almost no tuning, and the out-of-bag rows give you an honest error estimate for free.

Feature importance, and why to distrust the default

Random forests hand you an importance score per feature, and it is one of the most-used and most-misread outputs in machine learning.

The default — mean decrease in impurity — adds up how much each feature reduced impurity across all splits. It is computed for free during training, and it has two well-documented biases: it inflates high-cardinality features (a column with many distinct values gets more opportunities to look useful) and it splits credit arbitrarily between correlated features (two near-duplicate columns each get about half the importance, making both look unimportant).

Permutation importance is the more trustworthy measure. Shuffle one column in the validation set, re-score, and see how much performance drops. If it drops a lot, that column mattered. It costs one extra scoring pass per feature and is computed on held-out data, which is exactly what you want.

from sklearn.inspection import permutation_importance

r = permutation_importance(forest, X_val, y_val, n_repeats=10, random_state=0)
for i in r.importances_mean.argsort()[::-1][:10]:
    print(f"{feature_names[i]:<25} {r.importances_mean[i]:.4f}")

For per-prediction explanations rather than global ones, SHAP values are the standard tool, and they handle correlated features more sensibly than either method above.

Forest or boosting?

The pragmatic reading: reach for a random forest when you want a strong result with almost no tuning, when your labels are noisy, or when you need to train quickly across many cores. Reach for boosting when you are chasing the last few points of accuracy and can afford to tune.

Questions people ask

How many trees do I need? Start at 100, use 500 for anything final. Watch the out-of-bag score flatten — past that point you are only spending time.

Does it need feature scaling? No. Trees compare against thresholds; units are irrelevant.

Can it handle missing values? Scikit-learn's implementation cannot — impute first. Some other implementations handle them natively.

Does it work for regression? Yes. Each leaf predicts the mean of its rows, and the forest averages the trees. Note that it cannot predict outside the range of the training targets.

Why is my forest slow to predict? Five hundred deep trees is a lot of memory traversal. Reduce n_estimators, cap max_depth, or raise min_samples_leaf — all three shrink the model with modest accuracy cost.

Is it interpretable? Individually no, structurally yes. You lose the readable rule path of a single tree but gain reliable importance rankings and, with SHAP, per-prediction explanations.

Recap in one screen

• Many deep trees, each on a bootstrap sample, each choosing splits from a random feature subset.
• Diversity is the point: independent errors cancel when averaged.
• More trees is safe — it reduces variance and then plateaus.
• Out-of-bag scoring gives a free, honest performance estimate.
• Prefer permutation importance to the built-in impurity importance.
• Excellent defaults, minimal tuning, and hard to break.