Skip to content

_7_random_forests.md

Latest commit

 

History

History
810 lines (613 loc) · 21 KB

_7_random_forests.md

File metadata and controls

810 lines (613 loc) · 21 KB
Raw

Random Forests from Scratch: A Comprehensive Guide

Welcome to the world of Random Forests! 🌲🌲🌲 In this comprehensive guide, we'll explore one of the most powerful and popular machine learning algorithms. Think of it as a "committee of experts" where many decision trees vote together!

Table of Contents

  1. What are Random Forests?
  2. How Random Forests Work
  3. The Mathematical Foundation
  4. Implementation Details
  5. Step-by-Step Example
  6. Real-World Applications
  7. Understanding the Code
  8. Model Evaluation

What are Random Forests?

Random Forests are ensemble learning methods that combine multiple decision trees to create a more robust and accurate model. Instead of relying on a single decision tree, a random forest uses the "wisdom of the crowd" by combining predictions from many trees.

Real-world analogy: Imagine you're trying to predict tomorrow's weather. Instead of asking one meteorologist, you ask 100 different meteorologists and take a majority vote. Even if some are wrong, the collective wisdom is usually more accurate. That's exactly how a Random Forest works!

Key Characteristics

Aspect Details
Algorithm Type Ensemble, Tree-based
Learning Style Supervised, Parallel training
Tasks Classification and Regression
Output Multiple decision trees voting together
Key Advantage Reduces overfitting compared to single trees

The Core Ideas

1. "Many trees are better than one" - Ensemble learning
2. "Bootstrap sampling" - Each tree trained on random data subset
3. "Majority voting" - Classification combines predictions by voting
4. "Averaging" - Regression combines predictions by averaging

A Random Forest:

  1. Creates many decision trees (typically 50-500)
  2. Trains each tree on a random subset of training data (with replacement)
  3. Makes each tree vote on the final prediction
  4. Combines all votes to make the final prediction

How Random Forests Work

The Algorithm in 5 Steps

Step 1: Randomly sample training data (with replacement) for each tree
         ↓
Step 2: Build a decision tree on each random sample
         ↓
Step 3: Repeat Steps 1-2 for n_estimators trees
         ↓
Step 4: For new data, each tree makes a prediction
         ↓
Step 5: Final prediction = majority vote (classification) or average (regression)

Bootstrap Sampling (Bagging)

What is bootstrap sampling? Random sampling with replacement - meaning the same data point can be selected multiple times.

Visual Example:

Original Data: [A, B, C, D, E, F, G, H]  (8 samples)

Bootstrap Sample 1: [A, A, C, D, F, F, G, H]  # A and F appear twice
Bootstrap Sample 2: [B, C, D, E, E, G, H, H]  # E and H appear twice
Bootstrap Sample 3: [A, B, C, C, D, E, F, G]  # C appears twice

Each tree sees different data = more diversity!

Why it works:

  • Each tree learns from slightly different data
  • Reduces overfitting - no single tree memorizes all training data
  • Creates diversity among trees
  • Averages out individual tree errors

Visual Example: Forest Prediction

Training Data (Loan Approval):
Features: [Age, Income, Credit_Score]
Classes: Approve / Reject

Building Random Forest with 5 trees:

Tree 1: Random 10 samples → Builds tree → Predicts: Approve
Tree 2: Random 10 samples → Builds tree → Predicts: Approve
Tree 3: Random 10 samples → Builds tree → Predicts: Reject
Tree 4: Random 10 samples → Builds tree → Predicts: Approve
Tree 5: Random 10 samples → Builds tree → Predicts: Approve

Final Prediction: Majority Vote = Approve (4 out of 5 trees)
Confidence: 80% (4/5 trees agreed)

The Mathematical Foundation

Bootstrap Sampling Theory

Each bootstrap sample:

  • Has the same size as the original dataset
  • Contains about 63.2% unique samples (on average)
  • The remaining 36.8% are duplicates

Probability calculation:

For a dataset of n samples:
P(sample selected at least once) = 1 - (1 - 1/n)^n ≈ 1 - 1/e ≈ 0.632

Ensemble Combination

Classification - Majority Voting:

Final Prediction = mode(predictions from all trees)

Example with 5 trees:
Tree predictions: [1, 1, 0, 1, 1]
Counts: Class 0 = 1, Class 1 = 4
Final: Class 1 (majority)

Regression - Averaging:

Final Prediction = mean(predictions from all trees)

Example with 5 trees:
Tree predictions: [250k, 270k, 240k, 265k, 255k]
Final: (250 + 270 + 240 + 265 + 255) / 5 = 256k

Bias-Variance Tradeoff

Single Decision Tree:

  • Low bias (can fit complex patterns)
  • High variance (sensitive to data changes)
  • Prone to overfitting

Random Forest:

  • Slightly higher bias (due to averaging)
  • Much lower variance (due to ensemble)
  • Better generalization!
Variance Reduction:
If trees are independent with variance σ²:
Variance of ensemble = σ² / n_estimators

In practice:
- 1 tree: High variance
- 10 trees: ~10x lower variance
- 100 trees: ~100x lower variance (diminishing returns)

Implementation Details

Our implementation includes the following key components:

Class Structure

class RandomForest:
    def __init__(self, n_estimators=100, max_depth=None, ...):
        # Initialize forest parameters
        
    def _bootstrap_sample(self, X, y):
        # Create random subset of training data
        
    def fit(self, X, y):
        # Build all trees in the forest
        
    def predict(self, X):
        # Combine predictions from all trees
        
    def predict_proba(self, X):
        # Get class probabilities (classification)
        
    def score(self, X, y):
        # Calculate model performance

Core Methods

  1. __init__(n_estimators, max_depth, ...) - Initialize forest

    • n_estimators: Number of trees (default: 100)
    • max_depth: Depth of each tree (default: None = unlimited)
    • bootstrap: Use bootstrap sampling (default: True)
    • random_state: Random seed for reproducibility

  2. _bootstrap_sample(X, y) - Private helper method

    • Creates random sample with replacement
    • Returns subset for one tree
    • Size = original dataset size

  3. fit(X, y) - Train the forest

    • Creates n_estimators bootstrap samples
    • Builds a decision tree on each sample
    • Stores all trees in the forest

  4. predict(X) - Make predictions

    • Gets prediction from each tree
    • Classification: Returns majority vote
    • Regression: Returns average

  5. predict_proba(X) - Get probabilities

    • Only for classification
    • Returns proportion of trees predicting each class
    • Example: 70 trees predict Class 1 → probability = 0.70

  6. score(X, y) - Evaluate performance

    • Classification: Returns accuracy
    • Regression: Returns R² score

Step-by-Step Example

Let's walk through a complete example predicting loan approval based on customer features:

The Data

import numpy as np

# Features: [Age, Income ($k), Credit Score]
X_train = np.array([
    [25, 45, 650],   # Young, moderate income, fair credit
    [35, 75, 720],   # Middle-aged, good income, good credit
    [45, 95, 780],   # Older, high income, excellent credit
    [30, 50, 600],   # Young, moderate income, poor credit
    [40, 80, 750],   # Middle-aged, good income, good credit
    [50, 120, 800],  # Older, high income, excellent credit
    [28, 40, 580],   # Young, low income, poor credit
    [42, 85, 740],   # Middle-aged, good income, good credit
])

# Labels: 0=Reject, 1=Approve
y_train = np.array([0, 1, 1, 0, 1, 1, 0, 1])

Training the Model

model = RandomForest(n_estimators=5, max_depth=3, task='classification', random_state=42)
model.fit(X_train, y_train)

What happens internally:

Step 1: Create 5 bootstrap samples

Bootstrap Sample 1: Rows [0, 2, 2, 4, 5, 5, 6, 7]
  → Build Tree 1

Bootstrap Sample 2: Rows [1, 1, 2, 3, 4, 6, 7, 7]
  → Build Tree 2

Bootstrap Sample 3: Rows [0, 1, 3, 3, 4, 5, 6, 6]
  → Build Tree 3

Bootstrap Sample 4: Rows [0, 1, 2, 4, 4, 5, 6, 7]
  → Build Tree 4

Bootstrap Sample 5: Rows [1, 2, 3, 3, 5, 5, 6, 7]
  → Build Tree 5

Step 2: Each tree learns different patterns due to different data!

Making Predictions

# New customer application
X_test = np.array([[38, 70, 700]])  # Middle-aged, good income, decent credit

# Get prediction
prediction = model.predict(X_test)
probabilities = model.predict_proba(X_test)

print(f"Prediction: {'Approved' if prediction[0] == 1 else 'Rejected'}")
print(f"Confidence: {probabilities[0][1]:.2f}")

Internal Prediction Process

# Step 1: Each tree makes its prediction
Tree 1: Input [38, 70, 700] → Predicts 1 (Approve)
Tree 2: Input [38, 70, 700] → Predicts 1 (Approve)
Tree 3: Input [38, 70, 700] → Predicts 0 (Reject)
Tree 4: Input [38, 70, 700] → Predicts 1 (Approve)
Tree 5: Input [38, 70, 700] → Predicts 1 (Approve)

# Step 2: Count votes
Approve (1): 4 votes
Reject (0): 1 vote

# Step 3: Final prediction
Final: Approve (majority)
Confidence: 4/5 = 0.80 (80%)

Complete Example

# Multiple test applicants
X_test = np.array([
    [38, 70, 700],   # Good candidate
    [26, 35, 550],   # Risky candidate
    [48, 110, 790],  # Excellent candidate
])

predictions = model.predict(X_test)
probabilities = model.predict_proba(X_test)

for i in range(len(predictions)):
    status = "Approved" if predictions[i] == 1 else "Rejected"
    confidence = probabilities[i][1] if predictions[i] == 1 else probabilities[i][0]
    print(f"Applicant {i+1}: {status} (confidence: {confidence:.2f})")

# Output:
# Applicant 1: Approved (confidence: 0.80)
# Applicant 2: Rejected (confidence: 0.60)
# Applicant 3: Approved (confidence: 1.00)

Real-World Applications

1. Credit Risk Assessment

Predicting loan defaults:

  • Input: Income, credit score, debt ratios
  • Output: Risk level
  • Benefit: Banks reduce losses from bad loans

2. Medical Diagnosis

Disease prediction and classification:

  • Input: Symptoms, test results, medical history
  • Output: Disease probability
  • Example: Cancer detection, diabetes prediction

3. Fraud Detection

Identifying fraudulent transactions:

  • Input: Transaction amount, location, time, patterns
  • Output: Fraud probability
  • Example: Credit card fraud prevention

4. Customer Churn Prediction

Predicting which customers will leave:

  • Input: Usage patterns, demographics, complaints
  • Output: Churn probability
  • Benefit: Targeted retention campaigns

5. Stock Market Prediction

Forecasting price movements:

  • Input: Historical prices, volume, indicators
  • Output: Price direction
  • Example: Algorithmic trading systems

6. Recommendation Systems

Product and content recommendations:

  • Input: User behavior, preferences, history
  • Output: Recommendation scores
  • Example: Netflix, Amazon recommendations

7. Image Classification

Object recognition in images:

  • Input: Pixel values, image features
  • Output: Object categories
  • Example: Medical image analysis, quality control

Understanding the Code

Let's break down the key parts of our implementation:

1. Bootstrap Sampling

def _bootstrap_sample(self, X, y):
    n_samples = len(X)
    
    if self.bootstrap:
        # Sample with replacement
        indices = np.random.choice(n_samples, size=n_samples, replace=True)
    else:
        # Use all samples
        indices = np.arange(n_samples)
    
    return X[indices], y[indices]

How it works:

# Example with 5 samples
indices = np.random.choice(5, size=5, replace=True)
# Could return: [0, 2, 2, 4, 1]
# Sample 2 appears twice, samples 3 is not included

2. Forest Building

def fit(self, X, y):
    self.trees = []
    for i in range(self.n_estimators):
        # Create bootstrap sample
        X_sample, y_sample = self._bootstrap_sample(X, y)
        
        # Build tree
        tree = DecisionTree(max_depth=self.max_depth, ...)
        tree.fit(X_sample, y_sample)
        
        # Store tree
        self.trees.append(tree)

Key points:

  • Each tree is independent
  • Trees can be trained in parallel (not implemented here)
  • Each tree sees different data

3. Ensemble Prediction (Classification)

def predict(self, X):
    # Get all tree predictions
    tree_predictions = []
    for tree in self.trees:
        tree_pred = tree.predict(X)
        tree_predictions.append(tree_pred)
    
    tree_predictions = np.array(tree_predictions)
    
    # Majority voting
    predictions = []
    for i in range(len(X)):
        sample_preds = tree_predictions[:, i]
        unique_preds, counts = np.unique(sample_preds, return_counts=True)
        majority_vote = unique_preds[np.argmax(counts)]
        predictions.append(majority_vote)
    
    return np.array(predictions)

Example:

# 3 trees, 2 samples
tree_predictions = [
    [1, 0],  # Tree 1
    [1, 0],  # Tree 2
    [0, 0],  # Tree 3
]

# For sample 0: votes are [1, 1, 0] → majority is 1
# For sample 1: votes are [0, 0, 0] → majority is 0
# Result: [1, 0]

4. Probability Estimation

def predict_proba(self, X):
    probabilities = []
    for i in range(len(X)):
        sample_preds = tree_predictions[:, i]
        
        class_probs = []
        for class_idx in range(self.n_classes_):
            # Proportion of trees predicting this class
            prob = np.mean(sample_preds == class_idx)
            class_probs.append(prob)
        
        probabilities.append(class_probs)
    
    return np.array(probabilities)

Example:

# 5 trees predict: [1, 1, 0, 1, 1]
# Class 0: 1/5 = 0.20
# Class 1: 4/5 = 0.80
# Probabilities: [0.20, 0.80]

Model Evaluation

For Classification

1. Accuracy

Accuracy = (Correct Predictions) / (Total Predictions)

Example:

y_true = [0, 1, 1, 0, 1]
y_pred = [0, 1, 0, 0, 1]

correct = 4
total = 5
accuracy = 4/5 = 0.80 (80%)

2. Confusion Matrix

                Predicted
              0       1
Actual   0   [TN]    [FP]
         1   [FN]    [TP]

3. Precision and Recall

Precision = TP / (TP + FP)  # Of predicted positives, how many correct?
Recall = TP / (TP + FN)     # Of actual positives, how many found?

For Regression

R² Score

R² = 1 - (SS_res / SS_tot)

where:
SS_res = Σ(y_true - y_pred)²  # Residual sum of squares
SS_tot = Σ(y_true - y_mean)²  # Total sum of squares

Interpretation:

  • R² = 1.0: Perfect predictions
  • R² = 0.8: 80% of variance explained
  • R² = 0.0: No better than predicting mean
  • R² < 0.0: Worse than predicting mean

Advantages and Limitations

Advantages ✅

  1. High Accuracy

    • Often outperforms single decision trees
    • Competitive with other top algorithms
    • Good default choice for many problems

  2. Handles Overfitting Well

    • Bootstrap sampling reduces variance
    • Ensemble averaging smooths predictions
    • Naturally regularized

  3. Works with Many Features

    • Handles high-dimensional data
    • No need for feature scaling
    • Robust to irrelevant features

  4. Handles Missing Values

    • Can work with incomplete data
    • Maintains accuracy with missing values

  5. No Data Preprocessing Needed

    • Works with raw features
    • No need to scale or normalize
    • Handles categorical features (with encoding)

  6. Provides Feature Importance

    • Shows which features matter most
    • Helps with feature selection
    • Aids in model interpretation

  7. Versatile

    • Works for classification and regression
    • Handles multi-class problems
    • Works with various data types

Limitations ❌

  1. Slower Prediction

    • Must query every tree
    • Not ideal for real-time applications
    • Tradeoff: accuracy vs speed

  2. Memory Intensive

    • Stores many trees
    • Each tree can be large
    • Not suitable for very limited memory

  3. Less Interpretable

    • Hard to visualize 100 trees
    • Cannot easily trace decisions
    • "Black box" nature

  4. Longer Training Time

    • Must train many trees
    • Slower than single tree
    • But parallelizable!

  5. Diminishing Returns

    • More trees = more training time
    • Limited accuracy improvement after ~100 trees
    • Need to balance trees vs time

When to Use Random Forest

Good Use Cases:

  • ✅ Medium to large datasets
  • ✅ Many features (high dimensions)
  • ✅ Need high accuracy
  • ✅ Have time for training
  • ✅ Want robust model with minimal tuning
  • ✅ Mixed data types

Bad Use Cases:

  • ❌ Very small datasets (< 100 samples)
  • ❌ Need real-time predictions (milliseconds)
  • ❌ Require full interpretability
  • ❌ Very limited memory
  • ❌ Linear relationships (use regression instead)

Choosing Hyperparameters

Number of Trees (n_estimators)

Small (10-50):
  Pros: Faster training and prediction
  Cons: May underfit, higher variance
  
Medium (50-200):
  Pros: Good balance
  Cons: None - usually optimal
  
Large (200+):
  Pros: Maximum accuracy, lowest variance
  Cons: Slower, diminishing returns

Rule of thumb: Start with 100, increase if needed

Tree Depth (max_depth)

Shallow (3-5):
  Pros: Fast, less overfitting
  Cons: May underfit
  
Medium (10-15):
  Pros: Good balance
  Cons: None - usually good default
  
Deep (None/unlimited):
  Pros: Maximum flexibility
  Cons: Slower, can overfit

Rule of thumb: Start with 10-15, adjust based on performance

Bootstrap Sampling

bootstrap=True (default):
  - Standard random forest
  - Each tree sees ~63% unique samples
  - Recommended for most cases

bootstrap=False:
  - All trees see all data
  - Less diversity
  - Not recommended (similar to bagging without replacement)

Complete Usage Example

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, confusion_matrix

# Load dataset
data = load_breast_cancer()
X, y = data.data, data.target

# Split data
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

print(f"Training samples: {len(X_train)}")
print(f"Test samples: {len(X_test)}")
print(f"Features: {X.shape[1]}")
print(f"Classes: {data.target_names}")

# Create and train Random Forest
model = RandomForest(
    n_estimators=100,
    max_depth=10,
    task='classification',
    random_state=42
)
model.fit(X_train, y_train)

# Make predictions
y_pred = model.predict(X_test)
y_proba = model.predict_proba(X_test)

# Evaluate
accuracy = model.score(X_test, y_test)
print(f"\nAccuracy: {accuracy:.4f}")

# Detailed metrics
print("\nClassification Report:")
print(classification_report(y_test, y_pred, target_names=data.target_names))

# Show some predictions
print("\nSample Predictions:")
for i in range(5):
    true_label = data.target_names[y_test[i]]
    pred_label = data.target_names[y_pred[i]]
    confidence = y_proba[i][y_pred[i]]
    print(f"  True: {true_label}, Predicted: {pred_label}, Confidence: {confidence:.2f}")

Key Concepts to Remember

1. Ensemble Learning

Random Forest uses the power of many models (trees) to make better predictions than any single model.

2. Bootstrap Sampling

Each tree trains on a random subset of data, creating diversity and reducing overfitting.

3. Majority Voting

Classification combines predictions democratically - each tree gets one vote.

4. Bias-Variance Tradeoff

Random Forest reduces variance (overfitting) while maintaining low bias (good fit).

5. Hyperparameter Tuning

  • More trees = better (up to a point)
  • Tree depth controls complexity
  • Bootstrap adds diversity

6. Computational Complexity

  • Training: O(n_estimators × tree_cost)
  • Prediction: O(n_estimators × tree_depth)
  • Memory: O(n_estimators × tree_size)

Conclusion

Random Forests are one of the most powerful and practical machine learning algorithms! By understanding:

  • How bootstrap sampling creates diverse trees
  • How ensemble voting combines predictions
  • How hyperparameters control performance
  • When to use (and not use) random forests

You've gained a versatile tool that works well across many different problems! 🌲🌲🌲

When to Use Random Forest:

  • ✅ Need high accuracy with minimal tuning
  • ✅ Have sufficient training data
  • ✅ Can afford slightly longer training time
  • ✅ Want robust predictions
  • ✅ Don't need real-time predictions

When to Use Something Else:

  • ❌ Need instant predictions → Use simpler models
  • ❌ Need full interpretability → Use single decision tree
  • ❌ Very small dataset → Use simpler models
  • ❌ Linear relationships → Use linear regression

Next Steps:

  • Try Random Forest on your own datasets
  • Experiment with different n_estimators and max_depth
  • Compare with single Decision Trees
  • Learn about feature importance
  • Explore Gradient Boosting as an alternative
  • Study ensemble methods in depth

Happy coding! 🌲🤖