Decision Trees and Random Forests

This lesson on Decision Trees and Random Forests is hands-on and example-driven. You will learn the mechanics of ensemble learning using Random Forests to overcome the high variance and overfitting issues inherent in single Decision Trees. You will be able to build, evaluate, and tune a robust Random Forest model using intrinsic validation techniques like Out-of-Bag error estimation.

What You'll Be Able To Do

• Define the two sources of randomness required for Random Forest construction.
• Calculate the generalization error of an ensemble model using Out-of-Bag samples.
• Contrast the bias-variance trade-offs between single Decision Trees and aggregated Random Forests.
• Implement the process of bootstrap aggregating (bagging) for model training.
• Optimize Random Forest performance by tuning the feature subset size hyperparameter.

Detailed Concept Walkthrough

1. DT Limitations and RF Motivation

Single Decision Trees (DTs) are simple but suffer from high variance, meaning they are prone to overfitting the training data and perform poorly on unseen examples. Random Forests (RFs) use aggregation to stabilize predictions and drastically reduce this variance.

• Mechanism: DTs partition the feature space greedily, often resulting in complex, highly specific boundaries that fit the training noise perfectly, leading to poor generalization.
• Under the Hood: This high complexity translates directly to high variance; small changes in the training data cause large, unstable changes in the resulting tree structure.
• Best Practice: RFs maintain the low bias of DTs while significantly reducing variance by averaging the predictions of many independently trained, high-variance trees.

Key Takeaway: Random Forests are an ensemble method designed to reduce model variance without substantially increasing bias.

2. Bootstrap Aggregating (Bagging)

Bagging (Bootstrap Aggregating) is the foundational technique where multiple models are trained on different subsets of the original data. This ensures the individual trees are trained on slightly different views of the data.

• Mechanism: Bootstrapping involves resampling the original training data set of size N, with replacement, to create new datasets (bootstrap samples) also of size N.
• Execution Flow: Each tree in the forest is trained independently on one unique bootstrap sample, ensuring diversity in the training sets because each sample contains duplicates and omits roughly one-third of the original data points.
• Formal Terminology: The term 'Bagging' formally describes the combined technique of Bootstrapping the data and then Aggregating (using majority voting for classification or averaging for regression) the final predictions.

import numpy as np

# Assume 'data' is the original training set (N samples)
N = 100
data = np.arange(N)

# Create a bootstrap sample (resampling with replacement)
# The sample size is equal to the original size N
bootstrap_sample_indices = np.random.choice(N, size=N, replace=True)
bootstrap_sample = data[bootstrap_sample_indices]

# Note: bootstrap_sample will contain duplicates and miss some original entries.

Key Takeaway: Bootstrapping creates diverse training sets for individual trees by sampling with replacement.

3. Feature Randomness and Decorrelation

To ensure the trees are truly independent and maximize variance reduction, Random Forests introduce a second layer of randomness by restricting the features available at each split point.

• Mechanism: When a tree node needs to find the best split, it only considers a random subset of the total available features (P) rather than all of them.
• Under the Hood: If trees were only bootstrapped but allowed to use all features, they would likely all split on the single strongest predictor, resulting in highly correlated trees and minimal variance reduction.
• Best Practice: This 'double randomness' (data sampling + feature subsetting) is crucial; the resulting decorrelated trees ensure that the errors of individual trees cancel each other out when aggregated.

from sklearn.ensemble import RandomForestClassifier

# P is the total number of features
P = 10

# Standard practice for classification: max_features = sqrt(P)
# This restricts the number of features considered at each split to 3
rf_classifier = RandomForestClassifier(n_estimators=100,
                                     max_features='sqrt',
                                     random_state=42)

Key Takeaway: Restricting feature selection at each split is essential to decorrelate the trees and maximize the variance reduction benefit of the ensemble.

4. Out-of-Bag Error Evaluation

Out-of-Bag (OOB) samples are the data points left out during the bootstrapping process for a specific tree. These samples provide an internal, unbiased estimate of the model's generalization error.

• Mechanism: For every data point, we aggregate the predictions only from the trees for which that point was OOB (i.e., trees that never saw that point during training).
• Execution Flow: The OOB error rate is calculated as the proportion of misclassified OOB samples, providing an estimate of the model's accuracy on unseen data.
• Best Practice: OOB error calculation eliminates the need for separate cross-validation or a dedicated validation set, saving computational time and maximizing the use of training data for model building.

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import make_classification

# Generate synthetic data
X, y = make_classification(n_samples=1000, random_state=42)

# Enable OOB score calculation during initialization
rf = RandomForestClassifier(n_estimators=100, 
                            oob_score=True, 
                            random_state=42)
rf.fit(X, y)

# Access the OOB score (accuracy estimate)
oob_accuracy = rf.oob_score_

Key Takeaway: OOB error provides an efficient, intrinsic measure of model accuracy without requiring external validation sets.

Topics Covered in Decision Trees and Random Forests

1. DT High Variance (00:00 - 01:04) — Decision Trees suffer from high variance and overfitting, necessitating the use of ensemble methods.
2. Bootstrap Aggregating Data (01:06 - 02:07) — Bootstrap samples are created by resampling the original training data with replacement to train individual trees.
3. Feature Subsetting (02:09 - 03:22) — Only a random subset of variables is considered at each split point to ensure the resulting trees are decorrelated.
4. RF Assembly and Voting (03:29 - 05:01) — The Random Forest aggregates predictions from all trees using majority voting to reach a final ensemble classification.
5. Defining Bagging (05:03 - 05:16) — Bagging is the formal term describing the combined technique of bootstrapping the data and aggregating the decisions.
6. OOB Error Validation (05:18 - 07:18) — Data samples not included in a tree's bootstrap sample are used as an internal validation set to estimate generalization error.
7. Hyperparameter Tuning (07:29 - 08:18) — The accuracy of the model is optimized by tuning the number of variables used at each split to minimize the OOB error.

ML Foundations Cheat Sheet

• Bagging — Ensemble method combining bootstrapping and aggregation

  from sklearn.ensemble import BaggingClassifier
  

• Bootstrapping — Resampling data with replacement to create diverse sets

  np.random.choice(N, size=N, replace=True)
  

• Feature Subsetting — Random subset of variables considered at each split

  max_features='sqrt'
  

• OOB Error — Estimates generalization error using unused training samples

  RandomForestClassifier(oob_score=True)
  

• Hyperparameter Tuning — Optimizing feature subset size to minimize OOB error

Comparison Table

Common Pitfalls

• Mistake: Training trees without feature randomness. Avoid: Always restrict the number of features considered at each split.
• Mistake: Assuming OOB error is perfect validation. Avoid: Use OOB as a strong estimate, but confirm with a final holdout test set.
• Mistake: Using Random Forests when interpretability is paramount. Avoid: Choose simpler models like single DTs for high transparency needs.
• Mistake: Setting the number of features too high. Avoid: Start tuning with $\sqrt{P}$ for classification to ensure tree decorrelation.

FAQs

• Why do we need two types of randomness? Bootstrapping diversifies the data, while feature subsetting ensures the resulting trees are decorrelated, which is necessary for variance reduction.
• What happens if I don't use feature subsetting? The trees will be highly correlated because they will all split on the strongest predictor, negating the variance reduction benefits of the ensemble.
• How do Random Forests make a final prediction? For classification, they use majority voting across all individual tree predictions; for regression, they average the numerical outputs.
• How should I choose the optimal feature subset size? Start with the standard $\sqrt{P}$ (classification) or $P/3$ (regression) and tune around that value to minimize the OOB error rate.