Chapter 20 of 37 · intermediate

Decision trees

What this chapter covers

In week 1 we drew one line on one feature and called it a classifier. This chapter is what happens when one line isn't enough: you draw another, and another, each one splitting a piece of the space you already carved. Stack enough of them and you get a decision tree — the model that reads like a flowchart, bends around curved and multi-class boundaries a single stump can't touch, and doesn't care what units your features are in.

We build the whole thing from scratch in NumPy — Gini impurity, the best-split search, the recursive grow, prediction by walking the tree — then hand the same job to scikit-learn and check the numbers line up. The centerpiece is an animation: you watch the tree grow one split at a time and see the 2-D plane get chopped into boxes, each box painted with the class it predicts. By the end the boxes hug the data almost perfectly, which is exactly where the trouble starts. A tree that fits the training data perfectly has usually memorized it, and we'll watch that happen too.

Hold onto one idea from week 1: a tree of depth one is a decision stump, the threshold classifier we already built. Everything here is that same split, applied again and again.

A bit of history

The recursive-splitting idea is older than the phrase "machine learning." In 1963 James Morgan and John Sonquist, two social scientists at Michigan, built AID — Automatic Interaction Detection — to find structure in survey data by repeatedly splitting respondents into subgroups that best explained the outcome. It ran on a mainframe and it was, in spirit, a regression tree.

Two lines carried the idea into modern machine learning. In statistics, Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone published Classification and Regression Trees in 1984 — the CART book — which pinned down the version we still use: binary splits, Gini impurity, and pruning to fight overfitting. In parallel, on the AI side, Ross Quinlan built ID3 (1986) and then C4.5 (1993), which used information gain and entropy instead of Gini and handled things like missing values. The two traditions converged on nearly the same algorithm. What we build here is CART: Gini, binary splits, greedy growth. It's the tree under the hood of every random forest and gradient boosting library you'll use later, so it's worth building once by hand.

The intuition

Forget diabetes for a second and look at flowers. The iris dataset is 150 flowers from three species, and if you plot two measurements — petal length and petal width — the species almost separate on their own.

Look at the setosa cluster in the bottom left. It's completely detached — one horizontal cut at a petal width of about 0.8 fences it off from everything else, no mistakes. That's a stump, and it gets you a third of the way home for free. The other two species overlap in the top right, and no single line separates them. But a line through just that region would, and then maybe one more line to clean up the stragglers.

That's the whole idea of a tree. Ask one yes/no question about one feature, split the data on the answer, then ask a fresh question inside each half. Every question is a stump. The tree is what you get when you keep asking, letting each region of the space earn its own sequence of cuts. Where a single stump has to commit to one line for the entire dataset, a tree spends its splits where they're needed.

The math

A split is only worth making if it leaves the data purer than it found it, so we need to measure purity. CART uses Gini impurity. For a set of labels where class $k$ makes up a fraction $p_k$ of the rows, the impurity is

G = 1 - \sum_{k} p_k^{2}

Read it as the chance you'd be wrong if you guessed a random label by drawing one at random from the set. A pure node — every row the same class — has one $p_k = 1$ and the rest zero, so $G = 0$ . A perfectly even two-class node has $p_0 = p_1 = 0.5$ , giving $G = 1 - 0.25 - 0.25 = 0.5$ . The three-class iris root, 50 of each species, sits at $G = 1 - 3(1/3)^2 = 0.667$ , the worst it can be for three classes.

A split at threshold $t$ on feature $j$ sends the rows into a left set $L$ (feature $\le t$ ) and a right set $R$ . Its quality is the impurity we started with minus the size-weighted impurity of the two children — the impurity decrease:

\Delta(j, t) = G(\text{parent}) - \frac{|L|}{N}\,G(L) - \frac{|R|}{N}\,G(R)

The weights $|L|/N$ and $|R|/N$ matter: a split that makes a tiny corner perfectly pure while leaving the bulk untouched shouldn't score as high as one that cleans up the whole set. Training a node is picking the feature and threshold that maximize this decrease:

(j^{*}, t^{*}) = \arg\max_{j,\,t}\; \Delta(j, t)

That argmax is exactly the week-1 search — try every candidate line, keep the best — except now it runs over every feature at once, and it runs again inside each child. The impurity decrease at the iris root is $0.667 - 0.333 = 0.333$ : splitting off setosa cuts the impurity in half in one cut.

What it's good at, what it isn't

Trees are the most human-readable model in machine learning. The output is a flowchart you can print and hand to a domain expert who's never heard of gradients, and they can argue with it split by split. They don't care about feature scale — Gini doesn't change if you measure petal width in centimeters or inches — so there's no normalizing, no standardizing, none of the preprocessing that trips people up. They handle numeric and categorical features together, they find interactions on their own by nesting splits, and they draw nonlinear, multi-class boundaries that a single line never could.

The catch is variance. A tree grown to full depth will carve the training data into boxes so tight that each one holds a single point, hitting 100% training accuracy by memorizing noise. Move one point and the whole tree above it can reshuffle. That instability is the tree's defining weakness, and it's the reason nobody ships a single deep tree in production. The fix isn't to abandon trees — it's to grow many of them and average the noise out, which is bagging and random forests, or to grow them in sequence correcting each other's mistakes, which is boosting. Both are the next chapters. A single tree is the atom; the useful models are built from piles of them.

The data

Two datasets do two jobs here. The concept animation uses iris in two dimensions — petal length and petal width, all three species, 150 flowers — small and clean enough that you can watch every split land on points you can see.

For the honest accuracy numbers we go back to the Pima Indians Diabetes set from week 1: 768 patients, eight measurements each, a binary diabetes label. It's noisy and overlapping in a way iris isn't, which makes it the right place to watch a tree overfit. Same data, same 70/30 split as week 1 — 537 patients to train on, 231 held out to test — so the numbers are comparable across chapters.

Build it, one function at a time

Four ideas, in the order you'd write them. Purity first, because everything else is a search to improve it.

Gini impurity of a label set — one line of NumPy once you count the classes:

def gini(y):
    """Gini impurity of a set of labels: 1 - sum_k p_k^2.

    0 when every label is the same (a pure node), and it climbs toward
    1 - 1/K as the K classes even out. This is the number a split tries to
    drive down.
    """
    if len(y) == 0:
        return 0.0
    counts = np.bincount(y)
    p = counts / counts.sum()
    return float(1.0 - np.sum(p * p))

np.bincount counts how many rows fall in each class; square the fractions, sum, subtract from one. A leaf has to guess a single label, and it guesses the most common one in the node:

def majority(y):
    """The label a leaf predicts: the most common class in the node.

    Ties break toward the lower class index (np.argmax keeps the first max),
    which is what makes a wrong dataset fail the checkpoints identically.
    """
    return int(np.argmax(np.bincount(y)))

Now the heart of it: the best-split search. This is the week-1 argmax grown up — loop over every feature, over every candidate threshold (the midpoints between sorted unique values), score each split by its impurity decrease, and keep the winner.

def best_split(X, y):
    """Search every feature and every candidate threshold for the split that
    most reduces Gini impurity.

    For each feature we take the midpoints between consecutive sorted unique
    values as candidate thresholds. A split sends rows with feature <= t left
    and the rest right; its quality is the parent impurity minus the
    size-weighted impurity of the two children (the impurity decrease). We
    return the (feature, threshold, gain) with the largest decrease, or None
    if no split helps.
    """
    n, d = X.shape
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in range(d):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0
        for t in thresholds:
            left = X[:, f] <= t
            n_left = int(left.sum())
            if n_left == 0 or n_left == n:
                continue
            child = (n_left / n) * gini(y[left]) + \
                    ((n - n_left) / n) * gini(y[~left])
            gain = parent - child
            if gain > best_gain:
                best_gain, best_f, best_t = gain, f, float(t)
    if best_f < 0:
        return None
    return best_f, best_t, best_gain

Notice the shape of it: a threshold split is that same feature <= t comparison from the stump, and the inner logic is scoring one cut. The only new thing is the outer loop over features — the tree gets to choose which measurement to split on, not just where. If no split reduces impurity, it returns None, and that's the signal to stop.

With a way to find one split, the tree is that split applied recursively. Build a node, and if it isn't pure and we haven't hit the depth limit, split it and build a child on each half:

def build_tree(X, y, max_depth, depth=0):
    """Recursively grow a CART tree to a maximum depth.

    A node is a dict. A leaf carries its predicted class; an internal node
    carries the feature index and threshold to split on plus its two
    children. Recursion stops when the node is pure, the depth cap is hit, or
    no split reduces impurity — at which point the node becomes a leaf.
    """
    node = {"n": int(len(y)), "gini": gini(y), "prediction": majority(y)}
    if depth >= max_depth or node["gini"] == 0.0:
        node["leaf"] = True
        return node
    split = best_split(X, y)
    if split is None:
        node["leaf"] = True
        return node
    f, t, gain = split
    left = X[:, f] <= t
    node.update({
        "leaf": False, "feature": int(f), "threshold": t, "gain": gain,
        "left": build_tree(X[left], y[left], max_depth, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, depth + 1),
    })
    return node

Each node is a plain dict — a leaf carries its prediction, an internal node carries the feature and threshold to test plus its two children. The recursion bottoms out three ways: the node is already pure, we've hit max_depth, or no split helps. Set max_depth=1 and this builds a single split — a stump, week 1 exactly.

Prediction is the easy half. Drop a sample at the root and let each node's question route it left or right until it lands in a leaf:

def predict_one(node, x):
    """Walk one sample from the root to a leaf, following each split."""
    while not node["leaf"]:
        node = node["left"] if x[node["feature"]] <= node["threshold"] \
            else node["right"]
    return node["prediction"]


def predict(tree, X):
    """Predict every row of X by walking the tree from the root."""
    return np.array([predict_one(tree, x) for x in X])

No arithmetic, no dot products — just a walk down a chain of comparisons. That's why trees predict fast and read clearly.

Watch it work

Here's the payoff. This is the real best_split running on the 2-D iris data, one split per frame, grown best-first — at each step it applies the single split, anywhere in the tree so far, that buys the largest drop in total impurity. Watch the plane get carved into boxes. Each box is shaded by the class it would predict, the newest split line glows orange, and the points sit on top so you can see a box go pure. The caption names the split and the running training accuracy.

Press play. The first cut is the free one — a horizontal line at petal width 0.8 fences off setosa (cyan) into its own box, and accuracy jumps from 0.33 (guessing one class for everyone) to 0.67. From there the splits go to work on the versicolor/virginica overlap in the upper right, each one slicing a smaller rectangle to clean up a handful of misclassified points. By the seventh split the boxes hug the classes and training accuracy is 0.993. Reset and run it again.

Look at how the later splits behave. They carve thin slivers to capture one or two stubborn points near the boundary. On iris that's mostly fine. On messier data it's the beginning of overfitting — the tree contorting itself around individual training points that won't generalize. To see that clearly you need noisier data and a held-out test set, so here it is on Pima. This plots training accuracy and test accuracy as we let the tree grow deeper:

This is the picture to sit with. Training accuracy (cyan) climbs the whole way — from 0.754 at depth 1 to 0.998 by depth 12, an almost perfect fit. Test accuracy (purple) does something else entirely: it peaks at 0.736 at depth 4, then turns and falls, all the way down to 0.662 by depth 12. That widening gap between the two lines is overfitting, drawn in real data. Every split past depth 4 makes the tree look better on data it's already seen and worse on data it hasn't. The tree isn't learning anymore; it's memorizing. Depth 4 is where this tree should stop, and picking that stopping point — by pruning, by a depth cap, by cross-validation — is half of using trees well.

The full implementation

The whole thing, no library, top to bottom. Four core functions and a couple of helpers — this is the file the animation ran:

"""A classification decision tree (CART), built from scratch.

Grow a tree by repeatedly asking "which single yes/no question about one
feature splits this data into the two purest groups?", then recurse on each
group until the labels run out or a depth limit stops you. Prediction is a
walk from the root to a leaf, one comparison per node. Pure NumPy — no ML
library anywhere in this file (pandas only loads the CSV).

A depth-1 tree is exactly the decision stump from week 1: one feature, one
threshold, one split. Everything here is that idea, applied over and over.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: gini
def gini(y):
    """Gini impurity of a set of labels: 1 - sum_k p_k^2.

    0 when every label is the same (a pure node), and it climbs toward
    1 - 1/K as the K classes even out. This is the number a split tries to
    drive down.
    """
    if len(y) == 0:
        return 0.0
    counts = np.bincount(y)
    p = counts / counts.sum()
    return float(1.0 - np.sum(p * p))
# endregion


# region: majority
def majority(y):
    """The label a leaf predicts: the most common class in the node.

    Ties break toward the lower class index (np.argmax keeps the first max),
    which is what makes a wrong dataset fail the checkpoints identically.
    """
    return int(np.argmax(np.bincount(y)))
# endregion


# region: best_split
def best_split(X, y):
    """Search every feature and every candidate threshold for the split that
    most reduces Gini impurity.

    For each feature we take the midpoints between consecutive sorted unique
    values as candidate thresholds. A split sends rows with feature <= t left
    and the rest right; its quality is the parent impurity minus the
    size-weighted impurity of the two children (the impurity decrease). We
    return the (feature, threshold, gain) with the largest decrease, or None
    if no split helps.
    """
    n, d = X.shape
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in range(d):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0
        for t in thresholds:
            left = X[:, f] <= t
            n_left = int(left.sum())
            if n_left == 0 or n_left == n:
                continue
            child = (n_left / n) * gini(y[left]) + \
                    ((n - n_left) / n) * gini(y[~left])
            gain = parent - child
            if gain > best_gain:
                best_gain, best_f, best_t = gain, f, float(t)
    if best_f < 0:
        return None
    return best_f, best_t, best_gain
# endregion


# region: build_tree
def build_tree(X, y, max_depth, depth=0):
    """Recursively grow a CART tree to a maximum depth.

    A node is a dict. A leaf carries its predicted class; an internal node
    carries the feature index and threshold to split on plus its two
    children. Recursion stops when the node is pure, the depth cap is hit, or
    no split reduces impurity — at which point the node becomes a leaf.
    """
    node = {"n": int(len(y)), "gini": gini(y), "prediction": majority(y)}
    if depth >= max_depth or node["gini"] == 0.0:
        node["leaf"] = True
        return node
    split = best_split(X, y)
    if split is None:
        node["leaf"] = True
        return node
    f, t, gain = split
    left = X[:, f] <= t
    node.update({
        "leaf": False, "feature": int(f), "threshold": t, "gain": gain,
        "left": build_tree(X[left], y[left], max_depth, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, depth + 1),
    })
    return node
# endregion


# region: predict
def predict_one(node, x):
    """Walk one sample from the root to a leaf, following each split."""
    while not node["leaf"]:
        node = node["left"] if x[node["feature"]] <= node["threshold"] \
            else node["right"]
    return node["prediction"]


def predict(tree, X):
    """Predict every row of X by walking the tree from the root."""
    return np.array([predict_one(tree, x) for x in X])
# endregion


def accuracy(tree, X, y):
    """Fraction of rows the tree classifies correctly."""
    return float((predict(tree, X) == y).mean())


def count_leaves(node):
    """Number of leaves in the tree — its effective complexity."""
    if node["leaf"]:
        return 1
    return count_leaves(node["left"]) + count_leaves(node["right"])


def load_iris_2d(path="../data/iris.csv"):
    """Iris with just two features (petal length, petal width) and the 3-class
    target. Two dimensions so the axis-aligned splits are visible as boxes."""
    df = pd.read_csv(path)
    X = df[["petal_length", "petal_width"]].to_numpy(float)
    y = df["target"].to_numpy(int)
    return X, y, df


def load_diabetes(path="../data/diabetes.csv"):
    """Pima Indians Diabetes: 768 patients, 8 features, binary Outcome."""
    df = pd.read_csv(path)
    features = [c for c in df.columns if c != "Outcome"]
    X = df[features].to_numpy(float)
    y = df["Outcome"].to_numpy(int)
    return X, y, features

The library version

Nobody hand-rolls a tree in production, and you shouldn't either once you've built one. scikit-learn's DecisionTreeClassifier is the same algorithm — Gini, greedy best split, recursive growth to a depth cap — written in C and ready for pruning:

def sk_tree(X_train, y_train, X_test, y_test, max_depth):
    """Fit a CART tree at a given depth and return (train_acc, test_acc).

    criterion="gini" and the greedy best-split search are sklearn's defaults,
    so this is the library twin of build_tree — same objective, same
    axis-aligned splits, same depth stop.
    """
    clf = DecisionTreeClassifier(
        criterion="gini", max_depth=max_depth, random_state=0,
    )
    clf.fit(X_train, y_train)
    train_acc = float(clf.score(X_train, y_train))
    test_acc = float(clf.score(X_test, y_test))
    return train_acc, test_acc, clf

criterion="gini" and the greedy search are the defaults, so this really is the twin of our build_tree. It searches the same candidate thresholds we do and splits on feature <= threshold the same way, which is why the two agree so closely. The differences are the ones that matter in practice, not in the math: sklearn's version is orders of magnitude faster, it exposes real pruning (ccp_alpha, min_samples_leaf) that our version lacks, and at the root of a random forest it'll add feature subsampling. Same tree, more knobs.

Scratch versus library

Fit both at max_depth=4 on the 537-patient training half of Pima, score on the 231 held out. Here's the face-off:

The bars are identical: 0.736 test accuracy, both trees, both with 16 leaves and 0.823 training accuracy. That's the result you want — our hand-written recursion and sklearn's C implementation grew the same tree, because on this data with this depth there's only one greedy Gini tree to grow. The exact figures live in results.json, regenerated whenever the code changes, so the prose and the chart can't drift from what the code produced.

Two honest notes. First, 0.736 isn't a triumph — the week-1 stump scored 0.732 on this same split, so three extra levels of tree bought four thousandths of a point. Pima is a hard, noisy dataset where a shallow tree barely beats one line, which is its own kind of lesson: depth isn't free accuracy. Second, that's the test number. On the training data the depth-4 tree scores 0.823 and a deep one scores 0.998, and if you quoted those you'd be lying to yourself. The gap is the whole point of the overfitting curve above.

Takeaways

A decision tree is a stump you didn't stop building. That's the through-line from week 1: one split is a threshold classifier, and a tree is the same greedy search run recursively inside each region it carves. Everything you learned about the stump — that it's interpretable, that it needs no scaling, that it draws axis-aligned boundaries — is still true, except now the boundaries can bend around the data because you get as many cuts as you want.

That freedom is the whole trade. Reach for a tree when you want a model a human can read, when your features are a mix of types and units you don't want to normalize, or when the boundary is nonlinear in a way one line can't follow. Don't trust a single deep one: it will memorize your training set and fall apart on new data, exactly as the Pima curve showed past depth 4. Cap the depth, prune it, and treat one tree as a diagnostic rather than a final model.

The reason trees matter so much isn't the single tree — it's what you build from it. Grow hundreds on bootstrapped samples and average them and the variance that makes one tree fragile washes out: that's a random forest, the next chapter. Grow them in sequence, each one fixing the last one's errors, and you get gradient boosting, a couple of chapters after. Both of the strongest classical models on tabular data are just trees, piled up and coordinated. Build the atom well and the rest of the course is stacking it.