Decision trees

A decision tree classifies by asking questions, one after another, like a game of twenty questions:

                outlook?
         /         |          \
     sunny      overcast      rain
       |           |            |
  humidity?       play        windy?
   /     \                   /     \
 high   normal             yes      no
 don't   play             don't    play

Each inner node asks about one feature, each branch is an answer, and each leaf gives a class. Trees are easy to read and explain, which matters when a person must understand why a loan was refused.

Choosing the questions

Training picks, at each node, the question that best separates the classes. "Best" needs a measure of how mixed a group is.

Entropy (from information theory) measures the mix of a group with class shares p₁, p₂, ...:

H = − Σ pᵢ × log₂ pᵢ

A pure group (all one class) has H = 0; a 50/50 split of two classes has H = 1, the most mixed possible.

The information gain of a question is how much it lowers the entropy:

gain = H(parent) − Σ (size of child / size of parent) × H(child)

Training computes the gain of every possible question, takes the best, and repeats inside each child, until the groups are pure or too small.

from math import log2

def entropy(yes, no):
    total = yes + no
    h = 0.0
    for count in (yes, no):
        if count:
            p = count / total
            h -= p * log2(p)
    return h

parent = entropy(9, 5)
groups = {"sunny": (2, 3), "overcast": (4, 0), "rain": (3, 2)}   # (play, no play)
children = sum((y + n) / 14 * entropy(y, n) for y, n in groups.values())

print(f"H(all 14 days) = {parent:.3f}")
for name, (y, n) in groups.items():
    print(f"  {name}: {y} play, {n} not, H = {entropy(y, n):.3f}")
print(f"after splitting on outlook: {children:.3f}")
print(f"information gain: {parent - children:.3f}")

This is the classic "play tennis" data: 9 days of play and 5 of none, so H = 0.940. Splitting on outlook makes the overcast group pure, and gains about 0.25 bits, more than any other feature, so outlook is the first question, at the root of the tree above.

The Gini index, 1 − Σ pᵢ², is another measure of mix, quicker to compute and used by many libraries. Both usually pick the same questions.

Numeric features

For a number like hours studied, the questions are thresholds: "hours ≥ 4?" Training tries a threshold between each pair of neighbouring values and keeps the one with the best gain:

from math import log2

hours = [1, 2, 3, 4, 5, 6, 7, 8]
passed = [0, 0, 1, 0, 1, 1, 1, 1]

def entropy(labels):
    if not labels:
        return 0.0
    p = sum(labels) / len(labels)
    return -sum(q * log2(q) for q in (p, 1 - p) if q > 0)

best = None
for i in range(len(hours) - 1):
    threshold = (hours[i] + hours[i + 1]) / 2          # between two neighbours
    left = [y for x, y in zip(hours, passed) if x < threshold]
    right = [y for x, y in zip(hours, passed) if x >= threshold]
    after = len(left) / len(hours) * entropy(left) + len(right) / len(hours) * entropy(right)
    gain = entropy(passed) - after
    if best is None or gain > best[1]:
        best = (threshold, gain)

print(f"best question: hours >= {best[0]}? (gain {best[1]:.3f})")

A tree with just one question is a decision stump.

Overfitting, and forests

A tree that keeps splitting until every leaf is pure can memorize the training data, noise included. Limit it: a maximum depth, a minimum number of examples per leaf, or pruning (grow the full tree, then cut back the branches that do not help on validation data).

A random forest trains many trees, each on a random sample of the examples and of the features, and lets them vote. The trees' mistakes partly cancel out, and forests are among the most reliable methods for table-shaped data.

Mark lesson complete