module 05

Decision Trees

free pdf

Induction of Decision Trees

J. Ross Quinlan

Builds a tree of yes/no questions from examples. At each step it picks the question that removes the most uncertainty about the answer, measured in bits (information gain). It also fixes a bias toward questions with many possible answers.

book

Classification and Regression Trees

Leo Breiman et al.

The book behind most decision-tree code today. Every question is a simple yes/no split, the same tree can predict classes or numbers, and the tree is grown large first and then cut back so it doesn't memorise the training data.

the idea

Ask a yes/no question about the data, split it in two, and keep asking on each half until the groups are pure enough. The result is a flowchart a person can read, which is the main reason trees are still everywhere.

Each question cuts the space with a straight horizontal or vertical line, so a tree carves the space into boxes:

a tree cuts the space into boxes

2 boxes · train 0.821 · test 0.806

● filled class · ○ hollow class · darker background = more confident it's the filled class

every question splits one box into two with a straight horizontal or vertical cut. depth 1 is a single cut. deeper trees make smaller boxes; with no limit, the tree carves a box around almost every point, and training accuracy hits 1.0.

choosing the question

A group is pure when it holds one class. Two common ways to measure how mixed a group is, using the share of each class p_k:

entropy=−∑kpklog⁡2pkgini=1−∑kpk2\text{entropy} = -\sum_k p_k \log_2 p_k \qquad \text{gini} = 1 - \sum_k p_k^2

The best question is the one that lowers the mixing the most, weighted by group size. With entropy, that drop is Quinlan's information gain: the number of bits you save by knowing the answer.

One catch: a question with many possible answers, like "what's the ID number?", splits every example into its own pure group. It scores perfectly and is useless. Quinlan's gain ratio divides by how much the question shatters the data, which fixes this.

two families: ID3 and CART

ID3 (Quinlan) CART (Breiman and colleagues)
inputs categories numbers and categories
questions one branch per possible answer always yes/no: x_j ≤ t
measure information gain, then gain ratio gini
predicts classes classes and numbers
controlling size stop early grow big, then cut back

cutting back: pruning

A tree grown until every box is pure memorises the training data (notice "depth unlimited" above: training accuracy 1.0). Stopping early is risky too: a split that looks useless can make great splits possible below it.

CART's answer: grow the full tree, then prune it. Score every smaller version of the tree by its error plus a price α per box:

score=error+α×number of boxes\text{score} = \text{error} + \alpha \times \text{number of boxes}

Repeatedly remove the branch that buys the least error per box (the weakest link). As α grows you get a sequence of smaller and smaller trees. Pick the best one with cross-validation.

trees for numbers

Same idea, but each box predicts the average value of its points, and "mixed" means "spread out". The result is a staircase. These small number-predicting trees are the building blocks of gradient boosting.

how the code works

idea in tree.py
yes/no splits with gini, entropy or squared error DecisionTree._best_split
try every threshold in one pass sort once, then running totals
where the threshold goes halfway between neighbouring values
pruning cost_complexity_path, prune(alpha)
Quinlan's original ID3, with gain and gain_ratio

The speed trick: after sorting a feature, moving the threshold one step moves one point from the right group to the left. Running totals then give the score of every threshold at once, instead of recounting each time.

what the demo checks

Run uv run python examples/05_tree.py.

  • Quinlan's own weather example reproduced. The information gains (outlook 0.247, humidity 0.152, windy 0.048, temperature 0.029) and the final tree match the paper.
  • An ID-number attribute gets a near-perfect gain of 0.940; gain ratio cuts it to 0.247.
  • Pruning a 41-box tree back to 13 boxes reaches 0.892 test accuracy, better than any depth limit (best 0.866).
  • A diagonal boundary needs 15 boxes. Rotate the data 45° and it needs 2.

when it goes wrong

  • No depth limit: tiny boxes around noisy points.
  • Diagonal boundaries: staircases, because every cut is horizontal or vertical.
  • Unstable: move a few points and the first question can change, reshaping the whole tree. Random forests fix exactly this.