module 05
Decision Trees
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.
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
● filled class · ○ hollow class · darker background = more confident it's the filled class
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:
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:
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.