Decision Trees, Random Forests, and Gradient Boosting¶

A single decision tree is intuitive and interpretable, but it is fragile. Ask any practitioner which model they reach for first on a new tabular dataset — almost always it is Random Forest. Then, if they need that final edge for a competition or production system, it is XGBoost or LightGBM. This file explains why, and gives you the intuition to use all three confidently.

Learning Objectives¶

Explain how a decision tree selects splits using Gini impurity and entropy
Control tree depth to manage the overfitting/underfitting tradeoff
Describe how Random Forest uses bagging and feature subsampling to improve on a single tree
Tune the key hyperparameters of Random Forest
Explain how Gradient Boosting sequentially corrects residuals
Extract and interpret feature importances
Choose between Decision Tree, Random Forest, and Gradient Boosting for a given problem

Decision Trees — Learning Rules from Data¶

How Splits Work¶

A decision tree learns a series of if-then rules by recursively splitting the data. At each node, the algorithm searches every feature and every possible split value, picks the split that most reduces impurity in the resulting child nodes, and repeats until it reaches a stopping condition.

Two common impurity measures:

Gini impurity — the probability of misclassifying a randomly chosen sample:

$$\text{Gini} = 1 - \sum_{k} p_k^2$$

Entropy — information gain from the split:

$$\text{Entropy} = -\sum_{k} p_k \log_2(p_k)$$

In practice, Gini and entropy give very similar results. Gini is slightly faster to compute. Entropy is sometimes preferred when you want the tree to search more splits.

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.metrics import classification_report
import pandas as pd

cancer = load_breast_cancer(as_frame=True)
X_train, X_test, y_train, y_test = train_test_split(
    cancer.data, cancer.target,
    test_size=0.2, random_state=42, stratify=cancer.target
)

tree_model = DecisionTreeClassifier(
    max_depth=4,
    criterion="gini",
    min_samples_leaf=5,
    random_state=42
)
tree_model.fit(X_train, y_train)

# Print the tree structure as text — this is what makes trees interpretable
tree_rules = export_text(tree_model, feature_names=list(cancer.feature_names))
print(tree_rules[:600])  # First 600 characters of the rules
# Output:
# |--- worst radius <= 16.80
# |   |--- worst concave points <= 0.14
# |   |   |--- mean texture <= 16.11
# |   |   |   |--- class: 1
# |   |   |--- mean texture > 16.11
# |   |   |   |--- class: 1
# |   |--- worst concave points > 0.14
# |   |   |--- worst perimeter <= 114.10
# |   |   |   |--- class: 1
# |   |   |--- worst perimeter > 114.10
# |   |   |   |--- class: 0
# |--- worst radius > 16.80
# |   |--- worst concave points <= 0.17
# |   |   |--- class: 1
# ...

print(f"\nTest accuracy: {tree_model.score(X_test, y_test):.4f}")
# Output: Test accuracy: 0.9298

Overfitting — The Core Problem with Single Trees¶

An unconstrained decision tree will memorise every training example. It will create a leaf for every data point if allowed. This produces perfect training accuracy and terrible test accuracy.

from sklearn.metrics import accuracy_score

# Fully grown tree vs depth-limited tree
for max_d in [None, 1, 2, 4, 6, 10]:
    dt = DecisionTreeClassifier(max_depth=max_d, random_state=42)
    dt.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, dt.predict(X_train))
    test_acc = accuracy_score(y_test, dt.predict(X_test))
    depth = f"{max_d}" if max_d else "None (unlimited)"
    print(f"max_depth={depth:<15} Train: {train_acc:.4f}  Test: {test_acc:.4f}")

# Output:
# max_depth=None (unlimited) Train: 1.0000  Test: 0.9035
# max_depth=1               Train: 0.9407  Test: 0.9386
# max_depth=2               Train: 0.9560  Test: 0.9561
# max_depth=4               Train: 0.9802  Test: 0.9298
# max_depth=6               Train: 0.9956  Test: 0.9123
# max_depth=10              Train: 1.0000  Test: 0.9035

Warning

A tree with max_depth=None is almost always overfit. It perfectly memorises training data, including noise. In production, a decision tree with more than 6–8 levels is usually a red flag unless the dataset is enormous. Use cross-validation to find the right max_depth.

Key Decision Tree Hyperparameters¶

Parameter	What It Controls	Typical Starting Range
`max_depth`	Maximum tree depth	3–8
`min_samples_split`	Minimum samples to split a node	5–20
`min_samples_leaf`	Minimum samples in a leaf	3–10
`criterion`	Split quality measure	`"gini"` or `"entropy"`
`max_features`	Features to consider at each split	`"sqrt"`, `"log2"`, or an int

Random Forest — Why Aggregation Works¶

The Intuition¶

A single tree is high-variance. Small changes in training data cause big changes in the tree structure. The fix: build many trees on different subsets of the data, then aggregate their predictions.

Random Forest does two things that make this work:

Bagging (Bootstrap Aggregating): Each tree is trained on a random sample (with replacement) of the training data. Roughly 63% of the data is used for each tree; the rest ("out-of-bag" samples) can be used for validation.

Feature subsampling: At each split, only a random subset of features is considered. The default is sqrt(n_features) for classification. This forces trees to be different from each other — if all trees used all features, they would find the same best split and produce correlated trees that do not help each other.

The combined prediction (majority vote for classification, average for regression) is more stable than any single tree.

from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import classification_report

rf_model = RandomForestClassifier(
    n_estimators=200,        # number of trees
    max_features="sqrt",     # features to consider at each split
    max_depth=None,          # trees grow until pure (bagging handles variance)
    min_samples_leaf=3,      # minimum samples per leaf
    oob_score=True,          # use out-of-bag samples for validation
    n_jobs=-1,               # use all CPU cores
    random_state=42
)
rf_model.fit(X_train, y_train)

print(f"OOB accuracy: {rf_model.oob_score_:.4f}")
print(f"Test accuracy: {rf_model.score(X_test, y_test):.4f}")
print(classification_report(y_test, rf_model.predict(X_test), target_names=["malignant", "benign"]))
# Output:
# OOB accuracy: 0.9648
# Test accuracy: 0.9737
#               precision    recall  f1-score   support
#    malignant       0.98      0.93      0.95        43
#       benign       0.96      0.99      0.98        71
#     accuracy                           0.97       114

Info

The out-of-bag score is a form of cross-validation built into Random Forest for free. Each tree evaluates itself on the training samples it never saw. This gives a reliable estimate of generalisation performance without a separate validation set.

Feature Importance — What the Model Is Actually Using¶

One of the most valuable outputs of a Random Forest is feature importance. For each feature, sklearn reports the average reduction in impurity it contributes across all trees and all splits.

import pandas as pd
import matplotlib.pyplot as plt

feature_importance_df = pd.DataFrame({
    "feature": cancer.feature_names,
    "importance": rf_model.feature_importances_
}).sort_values("importance", ascending=False)

print(feature_importance_df.head(10).to_string(index=False))
# Output (approximate):
#                          feature  importance
#              worst concave points    0.1647
#                    worst perimeter    0.1493
#                      worst radius    0.1204
#                       mean concave points    0.0987
#                    worst area    0.0834
#                      mean perimeter    0.0721
#                          mean radius    0.0619
#                         worst concavity    0.0538
#                     mean concavity    0.0461
#                           mean area    0.0389

# Plot the top 10 features
top10 = feature_importance_df.head(10)
plt.figure(figsize=(10, 5))
plt.barh(top10["feature"][::-1], top10["importance"][::-1], color="teal")
plt.xlabel("Mean impurity decrease (feature importance)")
plt.title("Random Forest — Top 10 Feature Importances")
plt.tight_layout()
plt.savefig("rf_feature_importance.png", dpi=150)

Warning

Feature importance from Random Forest is biased toward high-cardinality numerical features and features with many unique values. A feature can appear important simply because it has many possible split points. For a less biased alternative, use permutation importance: from sklearn.inspection import permutation_importance.

Key Random Forest Hyperparameters¶

Parameter	What It Controls	When to Change It
`n_estimators`	Number of trees	More is better up to a point; 100–500 is typical
`max_features`	Features per split	`"sqrt"` for classification; try smaller values if overfitting
`max_depth`	Maximum tree depth	`None` by default; reduce if model is slow
`min_samples_leaf`	Minimum samples in leaf	Increase to smooth predictions on noisy data
`oob_score`	Enable OOB validation	Always set `True`
`n_jobs`	Parallel cores	Set to `-1` to use all available cores

Gradient Boosting — Sequential Error Correction¶

The Core Idea¶

Random Forest builds trees in parallel and averages them. Gradient Boosting builds trees sequentially: each new tree is trained to correct the errors (residuals) of the combined ensemble so far.

At each step: 1. Compute the residuals: what the current ensemble got wrong 2. Train a new shallow tree to predict those residuals 3. Add the new tree to the ensemble with a small learning rate (η)

The learning rate scales down each tree's contribution. Small learning rate + many trees = more careful, stable learning. This is the essence of regularised boosting.

from sklearn.ensemble import GradientBoostingClassifier
from sklearn.metrics import roc_auc_score

gb_model = GradientBoostingClassifier(
    n_estimators=200,      # number of boosting rounds (trees)
    learning_rate=0.05,    # step size (smaller = more conservative)
    max_depth=3,           # shallow trees work best for boosting
    subsample=0.8,         # use 80% of data per tree (stochastic boosting)
    random_state=42
)
gb_model.fit(X_train, y_train)

y_proba_gb = gb_model.predict_proba(X_test)[:, 1]
print(f"Gradient Boosting ROC-AUC: {roc_auc_score(y_test, y_proba_gb):.4f}")
print(f"Gradient Boosting Accuracy: {gb_model.score(X_test, y_test):.4f}")
# Output:
# Gradient Boosting ROC-AUC: 0.9970
# Gradient Boosting Accuracy: 0.9737

Tip

There is a well-known tradeoff in boosting: lower learning_rate requires more n_estimators to reach the same performance, but tends to produce a more regularised model. A common starting point is learning_rate=0.05 with n_estimators=300–500.

XGBoost and LightGBM — Industrial-Grade Boosting¶

The sklearn GradientBoostingClassifier is a clean reference implementation but slow on large datasets. In practice, teams use:

XGBoost — adds L1/L2 regularisation, handles missing values natively, and uses approximate tree algorithms for speed.

LightGBM — histogram-based splitting, leaf-wise tree growth (vs depth-wise in XGBoost), much faster on large datasets.

# XGBoost (install: pip install xgboost)
try:
    from xgboost import XGBClassifier

    xgb_model = XGBClassifier(
        n_estimators=300,
        learning_rate=0.05,
        max_depth=4,
        subsample=0.8,
        colsample_bytree=0.8,   # fraction of features per tree (like max_features in RF)
        use_label_encoder=False,
        eval_metric="logloss",
        random_state=42,
        verbosity=0
    )
    xgb_model.fit(X_train, y_train)
    xgb_auc = roc_auc_score(y_test, xgb_model.predict_proba(X_test)[:, 1])
    print(f"XGBoost ROC-AUC: {xgb_auc:.4f}")
    # Output: XGBoost ROC-AUC: 0.9982
except ImportError:
    print("Install xgboost: pip install xgboost")

# LightGBM (install: pip install lightgbm)
try:
    from lightgbm import LGBMClassifier

    lgbm_model = LGBMClassifier(
        n_estimators=300,
        learning_rate=0.05,
        max_depth=4,
        subsample=0.8,
        colsample_bytree=0.8,
        random_state=42,
        verbose=-1
    )
    lgbm_model.fit(X_train, y_train)
    lgbm_auc = roc_auc_score(y_test, lgbm_model.predict_proba(X_test)[:, 1])
    print(f"LightGBM ROC-AUC: {lgbm_auc:.4f}")
    # Output: LightGBM ROC-AUC: 0.9978
except ImportError:
    print("Install lightgbm: pip install lightgbm")

Full Model Comparison¶

from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.model_selection import cross_val_score
import pandas as pd

cancer = load_breast_cancer(as_frame=True)

models = {
    "Logistic Regression": Pipeline([
        ("scaler", StandardScaler()),
        ("model", LogisticRegression(max_iter=1000))
    ]),
    "Decision Tree (depth=4)": DecisionTreeClassifier(max_depth=4, random_state=42),
    "Random Forest (200 trees)": RandomForestClassifier(n_estimators=200, random_state=42),
    "Gradient Boosting": GradientBoostingClassifier(n_estimators=200, learning_rate=0.05, random_state=42),
}

comparison_results = []
for name, model in models.items():
    cv_auc = cross_val_score(model, cancer.data, cancer.target, cv=5, scoring="roc_auc")
    cv_acc = cross_val_score(model, cancer.data, cancer.target, cv=5, scoring="accuracy")
    comparison_results.append({
        "Model": name,
        "CV AUC (mean)": round(cv_auc.mean(), 4),
        "CV AUC (std)": round(cv_auc.std(), 4),
        "CV Accuracy (mean)": round(cv_acc.mean(), 4)
    })

results_df = pd.DataFrame(comparison_results).sort_values("CV AUC (mean)", ascending=False)
print(results_df.to_string(index=False))
# Output (approximate):
#                   Model  CV AUC (mean)  CV AUC (std)  CV Accuracy (mean)
#           Gradient Boosting         0.9960        0.0038              0.9649
#      Random Forest (200 trees)      0.9950        0.0037              0.9631
#          Logistic Regression         0.9958        0.0031              0.9736
#        Decision Tree (depth=4)      0.9316        0.0261              0.9262

When to Use Which Model¶

Scenario	Recommended Model	Reason
Need explainable rules for a stakeholder	Decision Tree (depth ≤ 5)	Human-readable if/then logic
Quick strong baseline on any tabular data	Random Forest	Robust, minimal tuning needed
Maximum performance on structured data	XGBoost or LightGBM	State of the art for tabular tasks
Small dataset, need speed	Decision Tree or LogReg	Low overhead
Very large dataset (millions of rows)	LightGBM	Fastest boosting implementation
Data with missing values	XGBoost	Handles missing natively

Success

In a real project, the typical sequence is: Logistic Regression baseline → Random Forest → XGBoost with tuning. This covers 95% of tabular classification problems. Reaching further (stacking, neural nets) gives diminishing returns unless the dataset is very large or the problem is highly complex.

Interview Questions¶

Q: How does Random Forest reduce overfitting compared to a single Decision Tree?

Show answer

Random Forest trains many trees on different bootstrap samples of the data (bagging) and uses a random subset of features at each split. This forces the trees to be diverse — they see different data and consider different features. When the predictions are aggregated (by majority vote), individual trees' errors cancel out. The variance of the ensemble is much lower than the variance of any single tree. A single tree can memorise noise; an ensemble of diverse trees cannot all memorise the same noise.

Q: What is the learning rate in Gradient Boosting and why does it matter?

Show answer

The learning rate (η) scales down the contribution of each new tree added to the ensemble. A small learning rate (e.g., 0.01–0.05) means each tree makes only a small correction, so the model improves gradually. This acts as regularisation — the model is less likely to overfit to noise in any single step. The tradeoff is that a smaller learning rate requires more trees (n_estimators) to converge to the same level of performance. A learning rate that is too large leads to overfitting; too small leads to underfitting or requires very long training.

Q: What does the Gini impurity measure?

Show answer

Gini impurity measures the probability that a randomly selected sample from a node would be incorrectly classified if it were given a random label based on the class distribution at that node. A node with a 50/50 class split has maximum Gini impurity (0.5 for binary classification). A pure node (all one class) has Gini impurity of 0. The algorithm searches for splits that minimise the weighted average of the child nodes' Gini impurity — i.e., splits that produce purer children.

Q: What is the difference between XGBoost and sklearn's GradientBoostingClassifier?

Show answer

Both implement gradient boosting, but XGBoost is significantly faster and more feature-rich. Key differences: XGBoost uses second-order (Newton's method) gradient approximations for faster convergence; it supports L1 and L2 regularisation on tree weights; it handles missing values natively by learning the best default direction for missing values at each split; and it uses parallelism and cache-aware algorithms to train on large datasets efficiently. Sklearn's implementation is simpler and correct, but does not scale well beyond a few hundred thousand rows.

What's Next¶

You've covered decision tree splitting with Gini impurity, the depth-overfitting tradeoff, Random Forest bagging and feature randomness, feature importance and its biases, Gradient Boosting's sequential error correction, XGBoost and LightGBM as industrial-grade implementations, and the model selection decision table for tabular classification. Next up: 05-classification-metrics — where you'll learn to interpret confusion matrices, precision, recall, F1-score, ROC-AUC, and how to choose the right metric given your business problem's cost structure for false positives versus false negatives.

Optional Deep Dive

Read "The Elements of Statistical Learning" (ESL) by Hastie, Tibshirani, and Friedman, Chapter 15 (Random Forests) — it provides the variance-reduction mathematics behind bagging and explains why the correlation between trees determines the ensemble's generalisation error, giving you the theoretical foundation behind the empirical results you observed here.

Previous: KNN and Naive Bayes | Next: Classification Metrics