Section 5.6

Decision Trees

Q: Why do decision trees overfit so easily?

Because an unrestricted tree keeps splitting until every training point is in its own tiny, pure region. At that point it has memorized the data, including the noise. Each extra level of depth lets the tree draw more, smaller rectangles, so it can always push training accuracy toward 100%. But those last splits fit chance patterns in this sample, so performance on new data peaks at a moderate depth and then declines. The fixes are to limit growth (maximum depth, a minimum number of samples per leaf) or to grow a large tree and prune it back using cross-validation.

Q: Can a decision tree predict a number instead of a class?

Yes, with one change to the algorithm. A regression tree chooses each split to reduce the sum of squared deviations around the node means rather than Gini impurity, and a leaf predicts the mean of the training cases that fall in it. Depth still controls overfitting, and cost-complexity pruning still cuts the tree back. Know two consequences before you use one. Its predictions are a step function, so a tree with eight leaves can output only eight distinct numbers and a smooth relationship comes out as a staircase. And it cannot extrapolate. A case beyond the range of the training data falls into an edge leaf and gets that leaf's mean. So a tree fitted on ages 18 to 65 predicts the same value for an 80-year-old as for a 65-year-old. In software it is method = "anova" in rpart and DecisionTreeRegressor in scikit-learn.

Q: Why did my tree change completely when I added a little data?

Single trees are unstable by nature, so this is expected. The tree is built greedily: the first split is the one that looks best at that moment, and everything below it depends on that choice. If a small change in the data lets a different feature win the top split by a tiny margin, the whole structure below it can be rebuilt. The new tree can look unrelated to the old one, even though its predictions may be similar. Ensembles such as random forests were developed for this high variance. They average many trees grown on resampled data, so the instability of the individual trees largely cancels out and the predictions are far more stable.

Most models give you coefficients or scores. A decision tree gives you a flowchart you can read aloud: "Is the applicant's income above €40k? If yes, is their debt below 30%? Then approve." That transparency is its main strength. Its main weakness is that a tree can keep growing until it memorizes the noise in its training data. The widget below shows both.

Twenty questions, but for data

A decision tree classifies by asking a sequence of yes/no questions, each about a single feature: is x₁ < 5?, then is x₂ > 12?, and so on. Each question splits the data into two groups; the tree then asks a fresh question inside each group, and repeats. This is recursive splitting: the same "find the best split" step applied again and again to smaller and smaller subsets. The result divides the feature space into axis-aligned rectangles, and each rectangle is labeled with a class.

Which split? The one that purifies

At every step the tree tries all possible split points and keeps the one that makes the two resulting groups as pure as possible: ideally one group nearly all class A, the other nearly all class B. Purity is measured by Gini impurity: for a group, it's the chance you'd mislabel a random member if you guessed labels in proportion to the group's mix. A group that's 50/50 is maximally impure (Gini = 0.5); a group that's all one class is perfectly pure (Gini = 0). The tree greedily chooses whichever split lowers the (size-weighted) impurity the most. "Greedily" means it takes the best split available right now and never reconsiders it. That makes trees fast, but it can miss a better tree that starts with a split that looks worse at first.

Gini is not the only measure. The other standard choice is entropy, from information theory: describing a 50/50 group takes one full bit, and a pure group takes none. The drop in entropy from a split is called information gain, and it is what the older tree algorithms (ID3, C4.5) optimize. In R's rpart and in scikit-learn you switch between the two with one argument. Take a parent of 100 cases split evenly between the classes, so Gini = 0.5 and entropy = 1 bit. A split sending 60 cases one way (45 of them class A) and 40 the other (5 of them class A) leaves a weighted Gini of 0.3125 and a weighted entropy of 0.704. That is an impurity drop of 0.1875, or an information gain of 0.296 bits. The units differ, but both say the split helps, and the two measures usually prefer the same split. In 4,000 simulated datasets, with every possible threshold checked, the best Gini split and the best information-gain split were the same threshold 85% of the time. So the choice of measure matters little. How far you let the tree grow matters much more.

Tree depth and overfitting

Each level of depth lets the tree ask one more round of questions and draw smaller rectangles. A shallow tree captures the broad pattern, and a very deep tree can put every training point in its own box. Grow the tree below one level at a time and watch the two accuracy lines. Training accuracy climbs toward 100%, but accuracy on a held-out test set rises, peaks, and then falls as the deep splits start fitting noise. That rise and fall is overfitting.

🌳 Grow a tree, split by split

Two classes (indigo and orange) scattered with a curved true boundary plus some label noise. Each Grow adds one level of depth; the shaded regions are the tree's current decision boundary. Below, training and test accuracy at every depth so far. Grow past the peak and the tree starts memorizing the noise.

depth = 0

Training acc.

—

Test acc.

—

Training accuracy cannot warn you, because it keeps improving until the tree has memorized the data. Only the held-out line shows the best depth. So a single tree is usually kept shallow (for readability), or grown large and then pruned back to the depth that cross-validation picks.

Pruning: a penalty for every leaf

The usual advice is to grow a big tree and prune it, but how far back should you prune? The standard method is cost-complexity pruning. Score a tree by its error plus a charge for every leaf it keeps: R(T) + α × (number of leaves). At α = 0 the largest tree always wins. As α rises, branches that barely reduce the error are collapsed, which produces a nested sequence of smaller and smaller trees.

For example, a four-leaf subtree misclassifies 6 of 200 training cases, and collapsing it into a single leaf misclassifies 14. The subtree is kept only while α < (0.07 − 0.03) ÷ 3 = 0.0133. Above that value, the three extra leaves cost more than the four percentage points of training error they save. You pick α the way you pick depth, with cross-validation rather than by eye. R's rpart calls this parameter cp (scaled relative to the root node's error) and prints a table of tree sizes against cross-validated error, and scikit-learn calls it ccp_alpha.

The strengths — and the catch

Interpretability. You can print the tree and follow any prediction as a path of plain-language rules. No other model in this course is as easy to explain to someone who needs to know why.
No fuss. Trees don't need feature scaling, handle mixed variable types, and cope with nonlinear boundaries and interactions automatically.
Instability (the catch). Because splitting is greedy and top-down, a tiny change in the data can change the first split and rebuild the whole tree below it into something completely different. A single tree is a high-variance model.

That instability is the reason for the next lesson. If one tree is unstable, grow many of them on resampled data and average their votes. The individual trees' errors partly cancel out, and the average is a far more stable predictor. That is the idea behind random forests.

Why it matters: decision trees give you a model you can explain, and a clear picture of overfitting. More depth helps up to a point and then hurts, and only held-out accuracy tells you where that point is. Tune depth (or minimum leaf size) with cross-validation, never with training accuracy. A single tree is easy to read but unstable, and ensembles are designed to fix the instability.

Common questions

Why do decision trees overfit so easily?

Because an unrestricted tree keeps splitting until every training point is in its own tiny, pure region. At that point it has memorized the data, including the noise. Each extra level of depth lets the tree draw more, smaller rectangles, so it can always push training accuracy toward 100%. But those last splits fit chance patterns in this sample, so performance on new data peaks at a moderate depth and then declines. The fixes are to limit growth (maximum depth, a minimum number of samples per leaf) or to grow a large tree and prune it back using cross-validation.

Can a decision tree predict a number instead of a class?

Yes, with one change to the algorithm. A regression tree chooses each split to reduce the sum of squared deviations around the node means rather than Gini impurity, and a leaf predicts the mean of the training cases that fall in it. Depth still controls overfitting, and cost-complexity pruning still cuts the tree back. Know two consequences before you use one. Its predictions are a step function, so a tree with eight leaves can output only eight distinct numbers and a smooth relationship comes out as a staircase. And it cannot extrapolate. A case beyond the range of the training data falls into an edge leaf and gets that leaf's mean. So a tree fitted on ages 18 to 65 predicts the same value for an 80-year-old as for a 65-year-old. In software it is method = "anova" in rpart and DecisionTreeRegressor in scikit-learn.

Why did my tree change completely when I added a little data?

Single trees are unstable by nature, so this is expected. The tree is built greedily: the first split is the one that looks best at that moment, and everything below it depends on that choice. If a small change in the data lets a different feature win the top split by a tiny margin, the whole structure below it can be rebuilt. The new tree can look unrelated to the old one, even though its predictions may be similar. Ensembles such as random forests were developed for this high variance. They average many trees grown on resampled data, so the instability of the individual trees largely cancels out and the predictions are far more stable.