Random Forest: Bootstrap Aggregating and Feature Randomness

1. Introduction

A Random Forest is an ensemble method that constructs a multitude of decision trees during training and outputs the class that is the mode of the classes (classification) or mean prediction (regression) of the individual trees. It combines bootstrap aggregating (bagging) with feature randomization to produce trees with low correlation and high predictive power.

The key insight: by introducing controlled randomness into tree construction, we reduce variance without substantially increasing bias.

2. Bootstrap Aggregating (Bagging)

2.1 The Bootstrap Procedure

Bagging (Breiman, 1996) draws B bootstrap samples from the original dataset of size n. Each bootstrap sample is drawn with replacement, meaning approximately 63.2% of unique original samples appear in any given bootstrap sample. The remaining ~36.8% are called out-of-bag (OOB) observations.

2.2 Bootstrap Sampling Visualization

Each bootstrap sample draws n=8 observations with replacement → duplicates appear, some originals missing

2.3 Mathematical Foundation

For a dataset $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n}$, each bootstrap sample $\mathcal{D}^*_b$ is drawn by uniformly sampling $n$ observations with replacement. The bagging predictor is:

where $\hat{f}^{*b}$ is the model trained on bootstrap sample $b$.

For regression, bagging reduces variance:

where $\rho$ is the pairwise correlation between trees. Without bagging (single tree), variance = $\sigma^2$. Bagging reduces the second term by factor $1/B$, but the irreducible $\rho \sigma^2$ term limits gains.

3. Random Forest Algorithm

3.1 Two Sources of Randomness

Random Forest (Breiman, 2001) adds a second randomization step: at each node, only a random subset of $m$ features (out of $p$ total) is considered for splitting. This decorrelates trees, reducing $\rho$ and thus overall variance.

3.2 The Algorithm

Algorithm: Random Forest (classification variant)
─────────────────────────────────────────────────
Input:  Training set D = {(x₁,y₁), ..., (xₙ,yₙ)}
        Number of trees B
        Features to consider at each split m
Output: Ensemble classifier |RF|

1:  for b = 1 to B do
2:      Draw bootstrap sample D*_b from D (sample n with replacement)
3:      Grow tree t_b on D*_b:
4:          at each node:
5:              randomly select m features from p total
6:              find best split among these m features
7:              split node into two child nodes
8:          stop when minimum node size or max depth reached
9:  end for
10: Output: |RF(x) = mode{ t_b(x) }_{b=1}^{B}

3.3 Theoretical Justification

Randomness reduces correlation. Consider the variance of the ensemble prediction. For $B$ identically distributed trees with pairwise correlation $\rho$ and individual variance $\sigma^2$:

• As $B \to \infty$, the second term vanishes: $\text{Var} \to \rho \sigma^2$
• Feature randomization reduces $\rho$ (trees become less correlated)
• The reduction in $\rho$ is the primary mechanism by which Random Forest outperforms bagged trees

Bias consideration: Random Forests do not reduce bias compared to individual trees (which are typically grown deep with low bias). The variance reduction comes at a slight cost in bias, but this is negligible for large trees.

4. Out-of-Bag (OOB) Evaluation

4.1 Concept

Each training observation $(x_i, y_i)$ is OOB for approximately 36.8% of the $B$ trees. We can use these trees to make predictions for that observation without a separate validation set.

4.2 OOB Error Formula

For classification, the OOB error is:

where $\hat{y}_i^{\text{OOB}}$ is the prediction from trees for which observation $i$ was OOB.

4.3 OOB vs Cross-Validation

5. Feature Importance

5.1 Mean Decrease Impurity (MDI)

For each feature $j$, sum the total decrease in Gini impurity (or variance for regression) contributed by splits on that feature across all trees, then normalize:

where $\Delta I(t)$ is the impurity decrease at node $t$:

5.2 Permutation Importance (Mean Decrease in Accuracy)

A more reliable measure. For each feature $j$:

1. Compute baseline OOB accuracy
2. Randomly permute the values of feature $j$ across all OOB observations
3. Compute OOB accuracy again
4. Importance = decrease in accuracy

where $\text{Acc}_b^{(\pi_j)}$ is the OOB accuracy of tree $b$ when feature $j$ is permuted.

5.3 Permutation Importance Procedure

For each tree t_b (b = 1, ..., B):
    1. Identify OOB observations O_b ⊂ {1, ..., n}
    2. Compute accuracy: Acc_b = (1/|O_b|) Σ_{i∈O_b} 𝟙[t_b(xᵢ) = yᵢ]
    3. For each feature j:
        a. Create permuted data: x̃ᵢⱼ = x_{π(i),j} for i ∈ O_b
           (permute column j only)
        b. Compute: Acc_b^(π_j) = (1/|O_b|) Σ_{i∈O_b} 𝟙[t_b(x̃ᵢ) = yᵢ]
        c. Contribution_b^(j) = Acc_b − Acc_b^(π_j)
    4. Importance_j = (1/B) Σ_b Contribution_b^(j)

6. Hyperparameter Tuning

6.1 Key Hyperparameters

6.2 The m (max_features) Trade-off

• $m = p$: All features considered → equivalent to bagging → $\rho$ is high
• $m = 1$: Random feature at each split → maximum decorrelation → high bias
• $m \approx \sqrt{p}$: Sweet spot for classification (Breiman's recommendation)

6.3 Tuning Strategy

from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import RandomizedSearchCV

param_distributions = {
    'n_estimators':      [100, 200, 500, 1000],
    'max_features':      ['sqrt', 'log2', 0.3, 0.5, 0.7],
    'max_depth':         [None, 10, 20, 30, 50],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf':  [1, 2, 4],
    'bootstrap':         [True, False],
}

rf = RandomForestClassifier(random_state=42, n_jobs=-1)
search = RandomizedSearchCV(
    rf, param_distributions,
    n_iter=100,
    cv=5,
    scoring='accuracy',
    n_jobs=-1,
    random_state=42
)
search.fit(X_train, y_train)
print(f"Best params: {search.best_params_}")
print(f"Best CV accuracy: {search.best_score_:.4f}")

7. Implementation in Python

7.1 Full Working Example

import numpy as np
import pandas as pd
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import (
    classification_report,
    confusion_matrix,
    roc_auc_score,
    RocCurveDisplay
)
import matplotlib.pyplot as plt

# --- Generate synthetic data ---
X, y = make_classification(
    n_samples=1000,
    n_features=20,
    n_informative=12,
    n_redundant=4,
    n_classes=2,
    random_state=42
)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# --- Fit Random Forest ---
rf = RandomForestClassifier(
    n_estimators=500,
    max_features='sqrt',
    max_depth=None,
    min_samples_leaf=2,
    oob_score=True,
    random_state=42,
    n_jobs=-1
)
rf.fit(X_train, y_train)

# --- Evaluate ---
print(f"OOB Score: {rf.oob_score_:.4f}")
print(f"Test Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Test ROC-AUC: {roc_auc_score(y_test, rf.predict_proba(X_test)[:, 1]):.4f}")
print("\nClassification Report:")
print(classification_report(y_test, rf.predict(X_test)))

7.2 Feature Importance Analysis

# --- Permutation Importance (more reliable) ---
from sklearn.inspection import permutation_importance

result = permutation_importance(
    rf, X_test, y_test,
    n_repeats=30,
    random_state=42,
    n_jobs=-1
)

feature_names = [f"Feature {i}" for i in range(X.shape[1])]
importances = pd.DataFrame({
    'feature': feature_names,
    'mdi_importance': rf.feature_importances_,
    'perm_importance': result.importances_mean,
    'perm_std': result.importances_std
}).sort_values('perm_importance', ascending=False)

print(importances.head(10))

7.3 OOB Error Convergence

# --- OOB error vs number of trees ---
errors = []
for n_trees in range(1, 501, 10):
    rf_temp = RandomForestClassifier(
        n_estimators=n_trees,
        oob_score=True,
        random_state=42
    )
    rf_temp.fit(X_train, y_train)
    errors.append({
        'n_trees': n_trees,
        'oob_error': 1 - rf_temp.oob_score_
    })

errors_df = pd.DataFrame(errors)

plt.figure(figsize=(8, 4))
plt.plot(errors_df['n_trees'], errors_df['oob_error'], color='#3b82f6', linewidth=2)
plt.xlabel('Number of Trees (B)')
plt.ylabel('OOB Error')
plt.title('OOB Error Convergence')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('oob_convergence.png', dpi=150)
plt.show()

7.4 Partial Dependence Plots

from sklearn.inspection import PartialDependenceDisplay

fig, axes = plt.subplots(1, 3, figsize=(15, 4))
PartialDependenceDisplay.from_estimator(
    rf, X_train,
    features=[0, 1, 2],
    feature_names=feature_names,
    ax=axes,
    kind='both',          # individual + average
    subsample=50,
    random_state=42
)
plt.tight_layout()
plt.savefig('partial_dependence.png', dpi=150)
plt.show()

8. Random Forest vs. Single Decision Tree

8.1 Comparison

8.2 When to Use Random Forest

Good choice:

• Tabular data with mixed feature types
• When interpretability is secondary to accuracy
• When you need robust estimates with minimal tuning
• As a strong baseline before trying more complex models

Less suitable:

• Very high-dimensional sparse data (consider linear models or gradient boosting)
• When prediction speed is critical (consider distillation or pruned trees)
• When interpretability is paramount (consider single trees or linear models)

9. Extensions and Variants

9.1 Extra-Trees (Extremely Randomized Trees)

Similar to Random Forest but with additional randomization: split thresholds are chosen randomly rather than optimizing over the feature values.

• Further reduces variance at cost of slightly higher bias
• Faster training (no sorting/split optimization per feature)

9.2 Balanced Random Forest

For imbalanced classification, each bootstrap sample is drawn to balance class frequencies:

9.3 Quantile Regression Forests

Extends Random Forest to estimate conditional quantiles $\hat{q}_\alpha(x)$ by keeping all training response values at each leaf and computing weighted quantiles.

10. Summary

Random Forests achieve excellent predictive performance through two simple ideas:

1. Bootstrap aggregating: Train each tree on a different random sample → decorrelates models → reduces variance
2. Feature randomization: At each split, consider only a random subset of features → further decorrelates trees → amplifies variance reduction

Key takeaways:

• OOB evaluation provides a free, unbiased estimate of generalization error
• Feature importance measures identify predictive variables
• Random Forests are robust to overfitting with minimal hyperparameter tuning
• They serve as a strong baseline for tabular data tasks

References

• Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140.
• Breiman, L. (2001). Random Forests. Machine Learning, 45(1), 5–32.
• Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. Chapter 15.
• Scikit-learn documentation: Random Forest