Random Forests: Theory and Feature Importance

Module: Machine Learning | Difficulty: Advanced

Random Forest Algorithm

1. Bootstrap sample from
2. Train tree on , selecting features at each split

Generalization Error Bound

where is average correlation and is strength.

Out-of-Bag Estimate

Feature Importance

Gini Importance (MDI):

Permutation Importance:

import numpy as np
from sklearn.ensemble import RandomForestClassifier

def permutation_importance(model, X, y, n_repeats=10):
    baseline = model.score(X, y)
    importances = np.zeros(X.shape[1])
    for j in range(X.shape[1]):
        scores = []
        for _ in range(n_repeats):
            X_perm = X.copy()
            np.random.shuffle(X_perm[:, j])
            scores.append(model.score(X_perm, y))
        importances[j] = baseline - np.mean(scores)
    return importances

Research Insight: Gini importance is biased toward features with many categories. Permutation importance is more reliable but computationally expensive. The theoretical bound shows that reducing correlation between trees is more important than increasing tree strength.