← module 05 · decision trees
book

Classification and Regression Trees

Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone

Wadsworth (book); reissued by Chapman & Hall/CRC

about this write-up

A book still in print, with no free copy. This write-up is from secondary sources and standard textbook treatments (ESL ch. 9.2), not from a reading of the book.

the original →

why it mattered

Programs that grew trees already existed. This book put them on solid ground: an honest way to estimate the error, a principled way to pick the tree's size, and one method that handles both classes and numbers. Most decision-tree code today follows it.

the main pieces

1. Only yes/no questions. Every split asks x_j ≤ t for a number, or "is x_j one of these?" for a category. Two-way splits break the data up more slowly than many-way ones.

2. Measure how mixed a group is. For classes, the gini index 1 − Σ p_k² is the default. For numbers, the squared error inside the group.

3. Grow big, then cut back. Score each smaller version of the tree by

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

For every α there's one best smaller tree, and as α grows those trees are nested inside each other. You can find them all by repeatedly cutting the weakest branch. That turns "how big should the tree be?" into choosing one number.

4. Choose α honestly. Use held-out data or cross-validation. The book's one standard error rule picks the smallest tree whose error is within one standard error of the best, trading a tiny bit of accuracy for a simpler tree.

5. Missing values. At each split, also keep backup questions on other features that send points the same way. A point missing the main feature uses a backup.

6. Costs. Unequal costs for different mistakes can be built into growing and pruning.

7. Feature importance. Credit each feature with how much it reduced mixing. Random forests later built on this.

in this repo

  • DecisionTree follows CART: yes/no splits with gini, entropy or squared error.
  • cost_complexity_path() cuts the weakest branch again and again; prune(alpha) picks a tree from that sequence.
  • Not included: backup questions for missing values, costs, and category-set splits.
  • In the tree demo, a 41-leaf tree pruned back to 13 leaves beats every depth-limited tree on test accuracy.