Decision trees

Think of the game Twenty Questions, or a doctor’s checklist: is there a fever? If yes, has it lasted more than three days? Each answer narrows the possibilities until one remains. A decision treeDecision treeA model that classifies (or predicts a number) by asking a sequence of simple questions about the input, following one branch per answer down to a leaf that gives the prediction.Open in glossary classifies the same way. It asks a question about the input, follows the branch for the answer, asks another question, and stops at a leaf that names a class.

Trees are popular for a reason you can see at a glance: a person can read one. You can follow exactly why it made a decision, which is rarely true of a neural network. In this lesson you will build a tree by hand, then watch an algorithm grow one, and find out why a tree that is perfect on its training data is usually a bad tree.

A famous small dataset

In 1986 the computer scientist J. Ross Quinlan published “Induction of decision trees” in the first volume of the journal Machine Learning. It described ID3, an algorithm that builds a tree from examples, and illustrated it with a small training set of fourteen weather records. Each is described by four attributes and belongs to one of two classes, P or N. Later textbooks reuse a version of this data as a question of whether to play tennis.

Nine records are P and five are N. Which question should come first? A good question splits the records into groups that are each as close to one class as possible.

Measuring how mixed a group is

To compare questions you need a number for how mixed a group is, called impurity. Two are common. If $p_k$ is the share of the group in class $k$:

• EntropyEntropyA measure of how uncertain a probability distribution is, in bits. Zero means one outcome is certain; k bits is as uncertain as a fair choice among 2 to the power k outcomes.Taught in Inside a real language modelOpen in glossary, in bits: $H = -\sum_k p_k \log_2 p_k$. A pure group has entropy 0; an even two-class mix has 1 bit.
• Gini impurityGini impurityA measure of how mixed the classes in a group are: the chance that two members drawn at random (with replacement) belong to different classes. 0 for a pure group, 0.5 for an even two-class mix.Open in glossary: $G = 1 - \sum_k p_k^2$, the chance that two members drawn at random (with replacement) belong to different classes. Pure is 0; an even two-class mix is 0.5.

A question splits a group into smaller groups. Its value is how much it lowers impurity, averaging the children by their size. With entropy this drop is called information gainInformation gainHow much a question lowers the entropy of the class labels, averaging the resulting groups by size. Decision tree algorithms such as ID3 ask the question with the largest gain.Open in glossary:

For the weather data, the fourteen labels have entropy $H(9, 5) = 0.940$ bits. Asking about outlook gives sunny (2 P, 3 N), overcast (4 P, 0 N), and rain (3 P, 2 N). The average entropy afterwards is $\tfrac{5}{14}(0.971) + \tfrac{4}{14}(0) + \tfrac{5}{14}(0.971) = 0.694$ bits, so the gain is about $0.247$ bits. Quinlan’s paper reports 0.246, because it subtracts values already rounded to three places.

import numpy as np

# Quinlan's 14 weather records: outlook, temperature, humidity, windy, class.
rows = """sunny hot high false N
sunny hot high true N
overcast hot high false P
rain mild high false P
rain cool normal false P
rain cool normal true N
overcast cool normal true P
sunny mild high false N
sunny cool normal false P
rain mild normal false P
sunny mild normal true P
overcast mild high true P
overcast hot normal false P
rain mild high true N"""
data = np.array([r.split() for r in rows.splitlines()])
labels = data[:, 4]

def entropy(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return -np.sum(p * np.log2(p))

def gain(column):
    # Entropy before the split minus the weighted entropy of each branch.
    after = sum(np.mean(column == v) * entropy(labels[column == v])
                for v in np.unique(column))
    return entropy(labels) - after

print(f"entropy of all 14: {entropy(labels):.3f} bits")
for i, name in enumerate(["outlook", "temperature", "humidity", "windy"]):
    print(f"gain({name}) = {gain(data[:, i]):.3f} bits")

entropy of all 14: 0.940 bits
gain(outlook) = 0.247 bits
gain(temperature) = 0.029 bits
gain(humidity) = 0.152 bits
gain(windy) = 0.048 bits

ID3 does exactly what you did: at every node that is still mixed, ask the question with the largest gain, and stop when a node is pure. On this data it finds outlook at the root, humidity under sunny, and windy under rain: three questions that sort all fourteen records. Starting with temperature, the question with the smallest gain, the best possible tree needs seven.

This strategy is greedy: each choice is the best one available right now, and it is never revisited. Searching all possible trees for the smallest one quickly becomes hopeless as data grows, and greedy choices are fast and usually good.

Questions about numbers

Real data often has numbers rather than categories. A tree handles a number by asking a threshold question, “is $x \le t$?”. To find the best threshold, sort the training values and try a cut halfway between each pair of neighbors, keeping the cut with the largest drop in impurity. The CART method of Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone (Classification and Regression Trees, 1984) grows trees this way, with two-way splits and Gini impurity.

Each threshold cuts the plane with a straight vertical or horizontal line, so a tree divides the plane into boxes. Below, a tree grows on points with two features, across and up.

import numpy as np

# Ten points on a plane (across, up) with labels 0 = class A, 1 = class B.
X = np.array([[0.1, 0.2], [0.3, 0.8], [0.2, 0.5], [0.4, 0.3], [0.35, 0.9],
              [0.7, 0.2], [0.8, 0.6], [0.6, 0.85], [0.9, 0.4], [0.55, 0.15]])
y = np.array([0, 1, 0, 0, 1, 1, 1, 1, 1, 0])

def gini(labels):
    p = np.mean(labels) if len(labels) else 0.0
    return 1 - p**2 - (1 - p)**2

def best_split(X, y):
    best = (0.0, None, None)
    for f in range(X.shape[1]):
        values = np.unique(X[:, f])
        for t in (values[:-1] + values[1:]) / 2:  # midpoints between values
            left, right = y[X[:, f] <= t], y[X[:, f] > t]
            after = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
            if gini(y) - after > best[0]:
                best = (gini(y) - after, f, t)
    return best

def grow(X, y, depth, level=0, answer=""):
    pad = "    " * level + answer
    gain, f, t = best_split(X, y)
    if depth == 0 or f is None:  # out of depth, or no split lowers impurity
        print(f"{pad}leaf: {np.sum(y == 0)} A, {np.sum(y == 1)} B")
        return
    print(f"{pad}is {['across', 'up'][f]} <= {t:.3f}? (gain {gain:.3f})")
    mask = X[:, f] <= t
    grow(X[mask], y[mask], depth - 1, level + 1, "yes -> ")
    grow(X[~mask], y[~mask], depth - 1, level + 1, "no  -> ")

grow(X, y, depth=2)

is across <= 0.575? (gain 0.213)
    yes -> is up <= 0.650? (gain 0.444)
        yes -> leaf: 4 A, 0 B
        no  -> leaf: 0 A, 2 B
    no  -> leaf: 0 A, 4 B

When to stop

A tree can keep splitting until every leaf is pure. Unless two identical points carry different labels, it will then get every training point right. That sounds ideal, and it is the same trap you met in Overfitting and generalization. On the Circle data with labels flipped at random 10% of the time, the fully grown tree gets 100% of its training points right but only 83.3% of the test points. Stopped at depth 4, it gets 86.7% of the test points right: its boxes follow the circle without chasing each flipped point.

Depth is a tree’s capacity. Shallow trees are too blocky to follow the real boundary (underfitting); deep trees fit the noise (overfittingOverfittingWhen a model fits the quirks and noise of its training data so closely that it does worse on new data. Training error keeps falling while test error rises.Taught in Overfitting and generalizationOpen in glossary). Common ways to stop include a maximum depth, a minimum number of points per leaf, or growing a large tree and then pruning back the branches that do not help on held-out data, as CART does.

That last point, that trees are unstable, matters. Small changes to the training data can change an early split, and every question below it changes with it. The next lesson turns this weakness into a strength by growing many trees and letting them vote.