Decision Trees & Random Forests

A decision tree is built from nodes. Each internal node asks one question about a single feature (like "is temperature > 23?"). The answer sends each row down a branch. When a group is "good enough" — mostly one class — the tree stops and that group becomes a leaf, which holds the prediction.

To choose a question, the tree needs to measure how mixed a group is. A group of all "yes" rows is pure and needs no further questions; a 50/50 mix of "yes" and "no" is the most impure. The two standard ways to measure this are Gini impurity and entropy.

Gini impurity is the chance you'd label a random row wrong if you guessed based only on the group's class mix. The formula is 1 − Σ pᵢ², where pᵢ is the fraction of each class. It is 0.0 for a pure group and 0.5 for a 50/50 two-class mix. To score a split, you take the impurity of each side and weight it by how many rows land there — the side with more rows counts for more.

Run this worked example and watch the numbers. Lower weighted Gini means a better split.

# How a tree scores a split: Gini impurity (no libraries needed)
# Gini = 1 - sum(p_i ** 2)   where p_i is the fraction of each class
#   0.0  = pure group (all one class)  -> a perfect leaf
#   0.5  = worst case for 2 classes (50/50 mix)

def gini(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1     # tally each class
    impurity = 1.0
    for c in counts.values():
        p = c / n         
...

Entropy measures the same idea as Gini — how mixed a group is — but with logarithms: −Σ pᵢ·log₂(pᵢ). It is 0 for a pure group and 1.0 for a perfect 50/50 two-class split. Information gain is simply how much the entropy drops after a split: the entropy before, minus the weighted entropy of the groups after. The tree picks the feature with the highest information gain.

Gini and entropy almost always agree on which split is best. Gini is a touch faster (no logs), which is why it's scikit-learn's default; entropy/information gain is the classic textbook framing.

import math

# Entropy is another impurity measure. Information Gain = how much
# entropy DROPS after a split. The tree picks the split with the most gain.

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum((c / n) * math.log2(c / n) for c in counts.values())

# 10 rows: should we play tennis? (label = "play")
data = [
    {"outlook": "sunny",    "play": "no"},
    {
...

Left unchecked, a tree keeps splitting until every leaf holds a single training row. That tree scores nearly 100% on the data it learned from — but it has memorised the training set, including its random noise, instead of learning the real pattern. This is overfitting, and it shows up as a big gap between training accuracy and test accuracy.

You keep a tree general by limiting its complexity — this is pruning:

• max_depth — cap how many questions can be chained (e.g. 3–6).
• min_samples_leaf — refuse leaves smaller than, say, 5 rows.
• min_samples_split — don't split a node that's already tiny.
• cost-complexity pruning (ccp_alpha) — grow fully, then snip back weak branches.

Because a tree explicitly chooses which feature to split on, it can tell you which inputs mattered most. Each feature's importance is the total impurity it removed across all the splits that used it, scaled so the scores add up to 1.0. A feature that's never used scores 0.0.

This is one of the biggest reasons people love trees: they're interpretable. A doctor, a loan officer, or a regulator can read the importances and the split thresholds and understand exactly why the model said what it said — something a neural network struggles to offer.

One deep tree overfits easily. A random forest fixes that by training many trees and letting them vote. Two tricks make the trees different from each other:

• Bootstrap sampling (bagging): each tree trains on a random sample of the rows, drawn with replacement, so every tree sees a slightly different dataset.
• Feature randomness: at each split a tree may only choose from a random subset of features, so no single strong feature dominates every tree.

Each tree makes different mistakes. When you take the majority vote (for classification) or the average (for regression), the random errors cancel out and the shared signal remains. The forest is almost always more accurate and far more stable than any single tree — which is why random forests are a go-to baseline for tabular data.

These are the traps that bite almost everyone working with trees. Watch for them.

# ❌ No limits — this tree will overfit
clf = DecisionTreeClassifier()        # grows until every leaf is pure

# ✅ Shallow tree generalises better
clf = DecisionTreeClassifier(max_depth=4, min_samples_leaf=5)

print(clf.score(X_train, y_train))   # 1.00 — looks perfect, but meaningless

print(clf.score(X_train, y_train))   # 0.92
print(clf.score(X_test,  y_test))    # 0.88  <- the number that matters

# ❌ Unnecessary for trees — splits are threshold-based
X_scaled = StandardScaler().fit_transform(X)
DecisionTreeClassifier().fit(X_scaled, y)

DecisionTreeClassifier().fit(X, y)   # raw features are fine

# ❌ "approved" basically IS the label "loan_repaid" — leakage!
X = df[["income", "age", "approved"]]
y = df["loan_repaid"]

X = df[["income", "age"]]            # only legitimate, available features
X_train, X_test = train_test_split(X)  # split FIRST, fit on train only