Decision Trees and Ensemble Methods

Overview#

Decision trees are one of the most intuitive machine learning models — they make predictions through a series of simple yes/no questions, mirroring how humans often reason through decisions. On their own, single trees tend to overfit badly, but combining many trees into an ensemble — through bagging (Random Forests) or boosting (Gradient Boosting, XGBoost, AdaBoost) — produces some of the most powerful and widely used models in practical machine learning. This notebook covers how decision trees work internally, Random Forests, and the major boosting algorithms, along with when to reach for each.

1. Decision Trees: How They Work#

A decision tree splits the data repeatedly based on feature values, forming a tree of yes/no questions, ending in leaf nodes that hold a prediction.

Python
CopyAsk AI
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

tree = DecisionTreeClassifier(max_depth=3, random_state=42)
tree.fit(X_train, y_train)

print(f"Test accuracy: {tree.score(X_test, y_test):.3f}")

Python
CopyAsk AI
# Visualizing the resulting tree
plt.figure(figsize=(12, 8))
plot_tree(tree, feature_names=load_iris().feature_names, class_names=load_iris().target_names, filled=True)
plt.show()

How splits are chosen: impurity measures#

At each node, the tree tries every possible feature and threshold, choosing the split that most reduces impurity — how mixed the classes are within a node.

Python
CopyAsk AI
# Gini impurity: probability of misclassifying a randomly chosen element
# if it were labeled according to the distribution of labels in the node
# Gini = 1 - sum(p_i^2) for each class i

# Entropy (used in "information gain"):
# Entropy = -sum(p_i * log2(p_i)) for each class i

tree_gini = DecisionTreeClassifier(criterion="gini", max_depth=3)
tree_entropy = DecisionTreeClassifier(criterion="entropy", max_depth=3)

A pure node (all samples belong to one class) has zero impurity; a node with an even 50/50 split of two classes has maximum impurity. The tree greedily picks, at each step, the split that produces the largest reduction in impurity — this greedy, one-step-at-a-time approach is why trees are fast to build, but it doesn't guarantee finding the globally optimal tree structure.

Regression trees#

Python
CopyAsk AI
from sklearn.tree import DecisionTreeRegressor

reg_tree = DecisionTreeRegressor(max_depth=4, random_state=42)
# For regression, splits are chosen to minimize variance (or MSE) within
# each resulting node, instead of classification impurity

2. Why Single Trees Overfit#

Python
CopyAsk AI
# An unconstrained tree can grow until every leaf is pure —
# essentially memorizing the training data
overfit_tree = DecisionTreeClassifier(random_state=42)   # no max_depth limit
overfit_tree.fit(X_train, y_train)

print(f"Training accuracy: {overfit_tree.score(X_train, y_train):.3f}")   # often 1.000
print(f"Test accuracy: {overfit_tree.score(X_test, y_test):.3f}")           # noticeably lower

An unconstrained tree keeps splitting until every leaf is perfectly pure (or contains just one sample), which almost always means it has memorized noise specific to the training set — a textbook case of high variance, low bias.

Controlling tree complexity directly#

Python
CopyAsk AI
DecisionTreeClassifier(
    max_depth=5,             # limits how many splits deep the tree can go
    min_samples_split=20,     # a node needs at least 20 samples to be split further
    min_samples_leaf=10,        # each leaf must have at least 10 samples
    max_leaf_nodes=20,            # caps the total number of leaves
)

These hyperparameters directly control the bias-variance tradeoff for a single tree — shallower/more constrained trees have higher bias, lower variance; deeper/less constrained trees have lower bias, higher variance. Even with careful tuning, a single tree rarely matches the performance of a well-built ensemble.

3. Random Forests: Bagging Many Trees#

Bagging (Bootstrap Aggregating) trains many models independently on different random subsets of the data, then averages (or votes on) their predictions. A Random Forest applies bagging specifically to decision trees, with one additional twist: each split only considers a random subset of features, not all of them.

Python
CopyAsk AI
from sklearn.ensemble import RandomForestClassifier

forest = RandomForestClassifier(
    n_estimators=100,        # number of trees in the forest
    max_depth=None,            # individual trees can still grow deep
    max_features="sqrt",         # each split only considers sqrt(n_features) features
    random_state=42,
)
forest.fit(X_train, y_train)

print(f"Test accuracy: {forest.score(X_test, y_test):.3f}")

Why averaging many overfit trees works#

text
Ask AICopy
Individual deep trees: LOW bias, HIGH variance (each one overfits its
                        own random bootstap sample differently)

Averaging many such trees: the variance of the AVERAGE of many
                             independent, noisy estimators is much lower
                             than the variance of any single one —
                             while bias stays roughly the same.

Result: a Random Forest keeps the LOW bias of deep individual trees,
        while dramatically reducing the HIGH variance problem, through
        averaging.

This is the key intuition behind bagging: it doesn't reduce bias (each tree is still potentially overfit), but averaging many independently overfit trees, each making different mistakes, cancels out much of that noise — as long as the individual trees are sufficiently different from each other (which the random feature subsampling and bootstrap sampling both encourage).

Feature importance#

Python
CopyAsk AI
import numpy as np

importances = forest.feature_importances_
feature_names = load_iris().feature_names

for name, importance in sorted(zip(feature_names, importances), key=lambda x: -x[1]):
    print(f"{name}: {importance:.3f}")

text
Ask AICopy
petal width (cm): 0.452
petal length (cm): 0.421
sepal length (cm): 0.089
sepal width (cm): 0.038

Feature importance in a Random Forest reflects how much each feature contributed, on average, to reducing impurity across all trees in the forest — a useful (though imperfect) tool for understanding which features drive the model's predictions.

Out-of-bag (OOB) evaluation#

Python
CopyAsk AI
forest_oob = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
forest_oob.fit(X_train, y_train)
print(f"OOB score: {forest_oob.oob_score_:.3f}")   # estimated without a separate validation set!

Since each tree is trained on a bootstrap sample (a random sample with replacement), roughly a third of the training data is left "out-of-bag" for each individual tree. Each sample's prediction can be evaluated using only the trees that didn't see it during training — giving a built-in, free validation-like estimate without needing a separate held-out set.

4. Boosting: Building Trees Sequentially#

Unlike bagging (which trains trees independently, in parallel), boosting builds trees sequentially, where each new tree focuses specifically on correcting the mistakes of the trees built before it.

text
Ask AICopy
Bagging (Random Forest):
  Tree 1, Tree 2, Tree 3, ... all trained INDEPENDENTLY, then averaged
  → reduces VARIANCE

Boosting (Gradient Boosting, AdaBoost, XGBoost):
  Tree 1 → errors → Tree 2 focuses on those errors → errors → Tree 3
  focuses on THOSE errors → ... combined as a weighted sum
  → reduces BIAS (and can reduce variance too, with care)

AdaBoost#

AdaBoost (Adaptive Boosting) trains a sequence of weak learners (often shallow trees, sometimes just "stumps" — trees of depth 1), where each subsequent learner pays more attention to the examples the previous learners got wrong, by increasing those examples' sample weights.

Python
CopyAsk AI
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

ada = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),   # a "stump" — a very weak learner
    n_estimators=100,
    learning_rate=1.0,
    random_state=42,
)
ada.fit(X_train, y_train)
print(f"Test accuracy: {ada.score(X_test, y_test):.3f}")

Gradient Boosting#

Gradient Boosting generalizes the boosting idea: each new tree is trained to predict the residual errors (roughly, the gradient of the loss function) of the combined ensemble so far, gradually reducing the overall error with each addition.

Python
CopyAsk AI
from sklearn.ensemble import GradientBoostingClassifier

gb = GradientBoostingClassifier(
    n_estimators=100,
    learning_rate=0.1,     # shrinks each tree's contribution — smaller values need more trees
    max_depth=3,              # individual trees are usually kept SHALLOW in boosting
    random_state=42,
)
gb.fit(X_train, y_train)
print(f"Test accuracy: {gb.score(X_test, y_test):.3f}")

learning_rate and n_estimators interact directly: a smaller learning rate requires more trees to reach the same level of fit, but often generalizes better — this is one of the most important tuning relationships in boosting.

XGBoost: an optimized, widely used implementation#

bash
Ask AICopy
pip install xgboost --break-system-packages

Python
CopyAsk AI
import xgboost as xgb

xgb_model = xgb.XGBClassifier(
    n_estimators=100,
    learning_rate=0.1,
    max_depth=3,
    subsample=0.8,           # each tree trains on a random 80% subsample of rows
    colsample_bytree=0.8,      # each tree considers a random 80% of columns
    reg_alpha=0.1,                # L1 regularization on leaf weights
    reg_lambda=1.0,                 # L2 regularization on leaf weights
    random_state=42,
)
xgb_model.fit(X_train, y_train)
print(f"Test accuracy: {xgb_model.score(X_test, y_test):.3f}")

XGBoost ("Extreme Gradient Boosting") is a highly optimized implementation of gradient boosting, with built-in regularization, efficient handling of missing values, parallel tree construction, and strong default performance — it's one of the most consistently high-performing algorithms for structured/tabular data in practice, and a frequent choice in machine learning competitions.

Early stopping (critical for boosting)#

Python
CopyAsk AI
from sklearn.model_selection import train_test_split

X_train2, X_val, y_train2, y_val = train_test_split(X_train, y_train, test_size=0.2, random_state=42)

xgb_model = xgb.XGBClassifier(n_estimators=1000, learning_rate=0.05, max_depth=3, random_state=42)
xgb_model.fit(
    X_train2, y_train2,
    eval_set=[(X_val, y_val)],
    early_stopping_rounds=20,     # stop adding trees if validation score hasn't improved in 20 rounds
    verbose=False,
)
print(f"Best iteration: {xgb_model.best_iteration}")

Since boosting adds trees sequentially and can eventually start overfitting if allowed to run too long, early stopping — halting once validation performance stops improving — is an essential technique, not an optional nicety, for getting the best generalization from a boosted model.

5. Random Forest vs Gradient Boosting/XGBoost#

A common practical approach: start with a Random Forest as a strong, low-effort baseline, then try XGBoost (or LightGBM/CatBoost) with proper tuning if squeezing out additional performance matters enough to justify the extra tuning effort.

6. Hyperparameter Tuning for Ensembles#

Python
CopyAsk AI
from sklearn.model_selection import GridSearchCV

param_grid = {
    "n_estimators": [50, 100, 200],
    "max_depth": [3, 5, 7],
    "learning_rate": [0.01, 0.1, 0.3],
}

grid_search = GridSearchCV(
    GradientBoostingClassifier(random_state=42),
    param_grid,
    cv=5,
    scoring="accuracy",
    n_jobs=-1,   # use all available CPU cores in parallel
)
grid_search.fit(X_train, y_train)

print(f"Best params: {grid_search.best_params_}")
print(f"Best CV score: {grid_search.best_score_:.3f}")

(Grid search and other hyperparameter tuning strategies are covered in full depth in the Hyperparameter Tuning & Model Selection notebook.)

Notes#

• A single unconstrained decision tree almost always overfits — the real power in tree-based methods comes from combining many trees into an ensemble, not from any individual tree.
• Bagging (Random Forest) primarily addresses variance by averaging many independently trained, overfit trees; boosting primarily addresses bias by sequentially focusing on previous errors.
• Boosting is more prone to overfitting than bagging if left unchecked — always use early stopping (or careful n_estimators/learning_rate tuning) with boosting methods.
• Feature importance from tree ensembles is a useful diagnostic tool, but can be misleading with highly correlated features (similar to the Lasso feature-selection instability covered in the Regularization notebook).
• XGBoost's built-in regularization parameters (reg_alpha, reg_lambda) directly parallel the L1/L2 regularization concepts from the Regularization Techniques notebook, applied to tree leaf weights instead of linear coefficients.

Best Practices Checklist#

• Never rely on a single, unconstrained decision tree for a real model — use an ensemble method instead
• Use max_depth, min_samples_leaf, etc. to control individual tree complexity, even within an ensemble
• Start with a Random Forest as a strong, easy-to-tune baseline before investing effort in boosting
• Use a lower learning_rate with more n_estimators for boosting, rather than a high learning rate with few trees
• Always use early stopping with boosting methods to prevent overfitting from too many sequential trees
• Use out-of-bag scoring for a free, built-in validation estimate with Random Forests
• Interpret feature importances cautiously when features are correlated
• Tune boosting hyperparameters (learning rate, max depth, subsample ratios) via cross-validation, not arbitrary defaults, for production use