Ensemble Models Part 1: Decision Trees & Random Forest

Welcome to Part 1 of our Ensemble Models series!

In machine learning, we often face the challenge of building models that are complex enough to capture the real patterns in our data, yet simple enough to generalize well to new, unseen data. This challenge is governed by the Bias-Variance Trade-off.

Ensemble Learning solves this trade-off by combining multiple “weak” or “base” models (typically simple Decision Trees) to build a single, highly accurate “strong” model.

In this post, we will explore the foundational building block of ensembles—the Decision Tree—and study the parallel ensemble approach: Bagging and Random Forest.

🌳 1. The Building Block: Decision Trees

A Decision Tree splits the feature space recursively into disjoint regions. For a given input, it traverses the tree from root to leaf, executing simple conditional checks (e.g., feature_X > threshold) and outputs the prediction associated with the leaf node.

graph TD
    A["Root Node: Is Income > $50k?"]
    A -- Yes --> B["Is Credit Score > 700?"]
    A -- No --> C["Reject Loan (Leaf)"]
    B -- Yes --> D["Approve Loan (Leaf)"]
    B -- No --> E["Reject Loan (Leaf)"]

Metrics of Messiness: Gini Impurity vs. Entropy

To find the best splits, the tree algorithm evaluates potential split points based on how much they reduce impurity (disorder) in the resulting branches:

A. Gini Impurity

Gini Impurity measures the probability of a randomly chosen element being incorrectly labeled if it were randomly labeled according to the class distribution in the subset:

(where \(p_i\) is the probability of an item belonging to class \(i\))

• Pure Group (e.g., 10 Apples, 0 Oranges): Gini = \( 1 - (1.0)^2 = 0 \) (Perfect purity).
• Messy Group (e.g., 5 Apples, 5 Oranges): Gini = \( 1 - (0.5^2 + 0.5^2) = 0.5 \) (Maximum impurity for 2 classes).

B. Entropy

Entropy measures the level of disorder or uncertainty (the “surprise” factor) in a group:

• Pure Group (10 Apples): Entropy = \( 0 \) (No uncertainty/surprise).
• Messy Group (5 Apples, 5 Oranges): Entropy = \( 1.0 \) (Maximum uncertainty).

C. Gini Gain vs. Information Gain

To select the best feature and split point, the algorithm computes the difference in impurity before and after the split:

• Gini Gain: \( \text{Gini}(D_{\text{parent}}) - \sum \frac{|D_{\text{child}}|}{|D_{\text{parent}}|} \text{Gini}(D_{\text{child}}) \)
• Information Gain (for Entropy): \( \text{Entropy}(D_{\text{parent}}) - \sum \frac{|D_{\text{child}}|}{|D_{\text{parent}}|} \text{Entropy}(D_{\text{child}}) \)

The tree evaluates all possible split points across all features and selects the split that maximizes the gain (i.e., causes the largest drop in messiness).

Why is Gini the default? Gini Impurity does not require calculating logarithms, making it computationally faster to compute than Entropy. In practice, they yield nearly identical results.

Hyperparameter Tuning Blueprint: Decision Trees

Unconstrained trees will split until every leaf is pure, memorizing training noise and causing high variance (overfitting). We use the following hyperparameters to control their growth:

• max_depth: The maximum depth of the tree.
  • Effect: Deep trees capture complex patterns but overfit. Shallow trees underfit.
  • Tuning Tip: Start with 3 to 5 for baselines.
• min_samples_split: The minimum number of samples required to split an internal node.
  • Effect: Higher values prevent the tree from creating splits that only describe a tiny, potentially noisy subset of data.
• min_samples_leaf: The minimum number of samples required to be at a leaf node.
  • Effect: Higher values smooth the model, especially for regression. A split is only allowed if both child nodes contain at least this many samples.
• max_features: The number of features to consider when looking for the best split.
  • Effect: Restricting features adds randomness, which is useful when building ensembles.
• ccp_alpha (Cost Complexity Pruning):
  • Effect: A post-pruning technique. It balances tree complexity (number of leaves) against training performance. Higher values prune more of the tree.

🗳️ 2. The Parallel Approach: Bagging (Bootstrap Aggregating)

Remember: A single deep decision tree has low bias (it is very smart and fits training data well) but high variance (it is fragile and overfits).

Bagging (Bootstrap Aggregating) aims to reduce variance by training multiple independent base models in parallel and aggregating their predictions.

                  ┌───► Bootstrapped Sample 1 ──► Tree 1 (Deep) ──┐
                  │                                               │
Training Data ────┼───► Bootstrapped Sample 2 ──► Tree 2 (Deep) ──┼──► Average/Vote ──► Final Prediction
                  │                                               │
                  └───► Bootstrapped Sample B ──► Tree B (Deep) ──┘

The Math of Bootstrapping & Out-of-Bag (OOB) Data

Instead of training all trees on the exact same dataset, we create different versions of the dataset. For each tree, we draw a sample of size \(N\) from the training set with replacement. Because we sample with replacement, some rows are duplicated, and some rows are left out.

Mathematically, the probability of never selecting a specific row in \(N\) draws is:

As \(N\) grows large:

This means that for every tree, approximately 36.8% of the data is left out. This is called Out-of-Bag (OOB) data.

To evaluate the model’s performance without the computational cost of cross-validation:

1. For Row A, we find all trees that did not see Row A during training.
2. We ask only those trees to predict Row A and aggregate their vote.
3. Repeating this for all rows gives us the OOB Score.

🌲 3. Random Forest (The Extension)

If we just do standard Bagging, we run into a problem: Correlated Trees.

If one feature (e.g., Salary) is extremely predictive, every tree will split on it first. Your trees will look almost identical, and averaging identical trees doesn’t reduce variance effectively.

Random Forest fixes this by adding Feature Bagging:

• At each split, the tree is only allowed to choose from a random subset of features (typically \(\sqrt{\text{total features}}\)).
• This forces different trees to look at different features, decorrelating them and drastically lowering the forest’s overall variance.

Hyperparameter Tuning Blueprint: Random Forest

• n_estimators: The number of trees in the forest.
  • Effect: More trees make the model more stable and reduce variance. Unlike boosting, Random Forest cannot overfit by adding more trees; the error just plateaus.
  • Tuning Tip: Set as high as your computer can handle (e.g., 100 to 500).
• max_features: The size of the random subset of features to consider at each split.
  • Effect: Lowering this increases random variation, making trees more diverse (lower correlation) but makes individual trees weaker.
  • Tuning Tip: Default is 'sqrt' (square root of total features) for classification, and 1.0 (all features) or 0.33 for regression.
• bootstrap & oob_score:
  • Effect: If bootstrap=True, you can set oob_score=True to get the out-of-bag validation score.
• Tree-specific hyperparameters: You can also tune max_depth, min_samples_split, and min_samples_leaf for the individual trees. However, in Random Forest, we usually want these trees to be deep (high-variance), allowing the ensemble averaging to do the heavy lifting.

🎯 What’s Next?

In Part 2: Gradient Boosting & XGBoost, we will dive into the sequential boosting family—explaining how models learn from residuals and exploring the math that makes XGBoost the gold standard for tabular data.