You built a working decision tree. On the data you trained it on, it scores almost perfectly — maybe flawlessly. That looks like success, so you point it at some new data and watch it stumble. What happened? The tree did not learn the underlying rule; it memorised the exact rows it saw. A decision tree is flexible enough to give every training point its own leaf, which means it can always push its training error to zero — even if half the labels are random noise. A flawless training score is not a sign you are finished. It is a warning. This lesson is about that warning: why a tree that fits perfectly usually predicts badly, how to measure the damage, and the simple stops that keep it honest.
flowchart TD D["a deeper tree"] --> T["train accuracy climbs toward 1.00"] D --> E["test accuracy peaks, then falls"] T --> G["the widening gap is overfitting"] E --> G style G fill:#b91c1c,color:#fff
Why depth turns into memorisation
A tree splits a node because doing so lowers its impurity, and it keeps splitting until a node is pure or it runs out of examples. The trap is that impurity can always reach zero if the leaves are allowed to be small enough. Hand the tree a leaf holding a single example and that leaf is, by definition, perfectly pure — there is no mixture left to measure. So an unbounded tree does not stop at the real structure. It keeps carving until every awkward, noisy, or mislabeled point sits alone in its own leaf, and the training accuracy reads one hundred percent. The model has not discovered a rule. It has built a lookup table that happens to cover exactly the rows it was shown.
def gini(labels):
n = len(labels)
if n == 0:
return 0.0
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return 1.0 - sum((c / n) ** 2 for c in counts.values())
def majority(labels):
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return max(counts, key=counts.get)
def best_threshold(xs, ys):
pairs = sorted(zip(xs, ys))
parent = gini([y for _, y in pairs])
n = len(pairs)
best = None
best_gain = 0.0
for i in range(n - 1):
if pairs[i][0] == pairs[i + 1][0]:
continue
thr = (pairs[i][0] + pairs[i + 1][0]) / 2
left = [pairs[j][1] for j in range(i + 1)]
right = [pairs[j][1] for j in range(i + 1, n)]
gain = parent - (len(left) * gini(left) + len(right) * gini(right)) / n
if gain > best_gain:
best_gain = gain
best = thr
return best
def build(xs, ys, depth=0, max_depth=10):
if len(set(ys)) <= 1 or len(ys) < 2 or depth >= max_depth:
return majority(ys)
thr = best_threshold(xs, ys)
if thr is None:
return majority(ys)
left = [i for i in range(len(xs)) if xs[i] <= thr]
right = [i for i in range(len(xs)) if xs[i] > thr]
return {'thr': thr,
'left': build([xs[i] for i in left], [ys[i] for i in left], depth + 1, max_depth),
'right': build([xs[i] for i in right], [ys[i] for i in right], depth + 1, max_depth)}
def count_leaves(tree):
if not isinstance(tree, dict):
return 1
return count_leaves(tree['left']) + count_leaves(tree['right'])
def predict(tree, x):
while isinstance(tree, dict):
tree = tree['left'] if x <= tree['thr'] else tree['right']
return tree
def accuracy(tree, xs, ys):
return sum(1 for x, y in zip(xs, ys) if predict(tree, x) == y) / len(ys)
# one feature, with two labels deliberately flipped as noise
train_x = [1, 2, 3, 4, 5, 6, 7, 8]
train_y = [0, 0, 0, 1, 0, 1, 1, 1]
deep = build(train_x, train_y, max_depth=10)
print('train accuracy:', round(accuracy(deep, train_x, train_y), 3))
print('number of leaves:', count_leaves(deep))
Run it and the story is stark. A tree trained on eight points grew four leaves to reach a perfect training score, two of them single-example leaves that exist only to absorb the two flipped labels. Nothing about those singleton leaves describes a genuine pattern — they are memorised entries. That is why training accuracy, taken on its own, is a number you cannot trust. It can always be inflated by growing the tree, and growing the tree is exactly what produces the memorisation. The honest question is not how well the tree did on the data it saw, but how well it does on data it did not.
Train versus test: the honest score
The way you see memorisation is to score the tree twice. Fit it on the training set and measure accuracy there, then score it on a held-out test set it has never seen. A healthy model does comparably on both. An overfit model shows a widening gap: training accuracy near perfect, test accuracy well below. That gap is the whole diagnosis. A tree that scores perfectly on training and badly on test has not solved the problem; it has learned the training rows by heart. So when you compare models, you read the test score — because training accuracy can only flatter you, and a deeper tree can always push it higher without making the model genuinely better.
def gini(labels):
n = len(labels)
if n == 0:
return 0.0
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return 1.0 - sum((c / n) ** 2 for c in counts.values())
def majority(labels):
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return max(counts, key=counts.get)
def best_threshold(xs, ys):
pairs = sorted(zip(xs, ys))
parent = gini([y for _, y in pairs])
n = len(pairs)
best = None
best_gain = 0.0
for i in range(n - 1):
if pairs[i][0] == pairs[i + 1][0]:
continue
thr = (pairs[i][0] + pairs[i + 1][0]) / 2
left = [pairs[j][1] for j in range(i + 1)]
right = [pairs[j][1] for j in range(i + 1, n)]
gain = parent - (len(left) * gini(left) + len(right) * gini(right)) / n
if gain > best_gain:
best_gain = gain
best = thr
return best
def build(xs, ys, depth=0, max_depth=10):
if len(set(ys)) <= 1 or len(ys) < 2 or depth >= max_depth:
return majority(ys)
thr = best_threshold(xs, ys)
if thr is None:
return majority(ys)
left = [i for i in range(len(xs)) if xs[i] <= thr]
right = [i for i in range(len(xs)) if xs[i] > thr]
return {'thr': thr,
'left': build([xs[i] for i in left], [ys[i] for i in left], depth + 1, max_depth),
'right': build([xs[i] for i in right], [ys[i] for i in right], depth + 1, max_depth)}
def predict(tree, x):
while isinstance(tree, dict):
tree = tree['left'] if x <= tree['thr'] else tree['right']
return tree
def accuracy(tree, xs, ys):
return sum(1 for x, y in zip(xs, ys) if predict(tree, x) == y) / len(ys)
train_x = [1, 2, 3, 4, 5, 6, 7, 8]
train_y = [0, 0, 0, 1, 0, 1, 1, 1]
test_x = [3, 4, 5, 6]
test_y = [0, 0, 1, 1]
for d in range(1, 6):
tree = build(train_x, train_y, max_depth=d)
tr = round(accuracy(tree, train_x, train_y), 3)
te = round(accuracy(tree, test_x, test_y), 3)
print('depth', d, '| train', tr, '| test', te)
Read that sweep from top to bottom. Training accuracy is a one-way story: it can only stay flat or climb as the tree grows deeper, because extra splits hand it more power to fit the rows in front of it. Test accuracy behaves differently. It rises while the new splits capture genuine structure, then turns and falls once the splits start chasing noise. The peak — the depth where test accuracy is highest — is the sweet spot, and every split beyond it buys training accuracy at the cost of generalisation. That turning point is what a depth limit tries to land on: deep enough to learn the signal, shallow enough to ignore the noise.
flowchart TD R["a split"] --> N["another split"] R --> L1["leaf: many mixed examples"] N --> L2["leaf: 1 example, pure by definition"] N --> L3["leaf: 1 example, pure by definition"] style L2 fill:#b45309,color:#fff style L3 fill:#b45309,color:#fff
The stops that keep a tree honest
Three levers rein in a runaway tree, and they all work by refusing to split. A depth limit caps how many splits deep the tree may grow, so it captures only the broadest structure and stops before it can isolate individual points. A minimum leaf size forbids any split that would leave a child with too few examples, blocking the tiny pure leaves that signal memorisation. Pruning goes the other way: it lets the tree grow, then cuts back branches whose splits do not hold up — splits that improve training impurity without adding real signal. All three trade a little training accuracy for a lot of generalisation, and you choose between them by watching the test score.
flowchart TD S["a node wants to split"] --> Q["check the stop rules"] Q -->|"depth limit reached"| STOP["stop and make a leaf"] Q -->|"too few examples to split"| STOP Q -->|"node already pure"| STOP Q -->|"a child would be too small"| STOP Q -->|"none of these"| GO["split again"] style STOP fill:#166534,color:#fff style GO fill:#3776ab,color:#fff
def gini(labels):
n = len(labels)
if n == 0:
return 0.0
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return 1.0 - sum((c / n) ** 2 for c in counts.values())
def majority(labels):
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return max(counts, key=counts.get)
def best_threshold(xs, ys):
pairs = sorted(zip(xs, ys))
parent = gini([y for _, y in pairs])
n = len(pairs)
best = None
best_gain = 0.0
for i in range(n - 1):
if pairs[i][0] == pairs[i + 1][0]:
continue
thr = (pairs[i][0] + pairs[i + 1][0]) / 2
left = [pairs[j][1] for j in range(i + 1)]
right = [pairs[j][1] for j in range(i + 1, n)]
gain = parent - (len(left) * gini(left) + len(right) * gini(right)) / n
if gain > best_gain:
best_gain = gain
best = thr
return best
def build(xs, ys, depth=0, max_depth=10, min_leaf=1):
if len(set(ys)) <= 1 or len(ys) < 2 or depth >= max_depth:
return majority(ys)
thr = best_threshold(xs, ys)
if thr is None:
return majority(ys)
left = [i for i in range(len(xs)) if xs[i] <= thr]
right = [i for i in range(len(xs)) if xs[i] > thr]
if len(left) < min_leaf or len(right) < min_leaf:
return majority(ys)
return {'thr': thr,
'left': build([xs[i] for i in left], [ys[i] for i in left], depth + 1, max_depth, min_leaf),
'right': build([xs[i] for i in right], [ys[i] for i in right], depth + 1, max_depth, min_leaf)}
def predict(tree, x):
while isinstance(tree, dict):
tree = tree['left'] if x <= tree['thr'] else tree['right']
return tree
def accuracy(tree, xs, ys):
return sum(1 for x, y in zip(xs, ys) if predict(tree, x) == y) / len(ys)
train_x = [1, 2, 3, 4, 5, 6, 7, 8]
train_y = [0, 0, 0, 1, 0, 1, 1, 1]
test_x = [3, 4, 5, 6]
test_y = [0, 0, 1, 1]
deep = build(train_x, train_y, max_depth=10, min_leaf=1)
safe = build(train_x, train_y, max_depth=10, min_leaf=2)
print('min_leaf=1 | train', round(accuracy(deep, train_x, train_y), 3),
'| test', round(accuracy(deep, test_x, test_y), 3))
print('min_leaf=2 | train', round(accuracy(safe, train_x, train_y), 3),
'| test', round(accuracy(safe, test_x, test_y), 3))
What does this print? Gini impurity is 1 minus the sum of each class's squared share.
def gini(labels):
n = len(labels)
counts = {}
for y in labels:
counts[y] = counts.get(y, 0) + 1
return 1.0 - sum((c / n) ** 2 for c in counts.values())
print(round(gini([0, 0, 1, 1]), 3))
Two of the four labels are class 0 and two are class 1, so each share is one half.
1 - (0.5 squared + 0.5 squared) = 1 - 0.5 = 0.5.
Write count_leaves(tree) that counts the leaves of a decision tree. A leaf is any value that is not a dict (a class label like 0); an internal node is a dict with 'left' and 'right' subtrees. Return the total number of leaves.
def count_leaves(tree):
# a leaf is anything that is not a dict
pass
If the value is not a dict, it is a single leaf, so return 1.
Otherwise recurse into both 'left' and 'right' and add the results.
def count_leaves(tree):
if not isinstance(tree, dict):
return 1
return count_leaves(tree['left']) + count_leaves(tree['right'])
This best_depth(records) picks the depth with the highest TRAINING accuracy. That always rewards the deepest, most overfit tree. It must pick by TEST accuracy — the score on data the tree never trained on. Fix the single field it reads.
def best_depth(records):
# records: list of {'depth', 'train', 'test'}
return max(records, key=lambda r: r['train'])['depth']
Training accuracy flatters the model — deeper always looks better on the data it saw.
Change the key so it compares the 'test' field instead of the 'train' field.
def best_depth(records):
# records: list of {'depth', 'train', 'test'}
return max(records, key=lambda r: r['test'])['depth']
Write most_overfit_depth(records) that returns the depth where the model is MOST overfit — the depth at which training accuracy most exceeds test accuracy. records is a list of {'depth', 'train', 'test'}. This is a different question from picking the best test score: you are finding the widest generalisation gap.
def most_overfit_depth(records):
# the depth with the largest (train - test) gap
pass
Overfitting means the model does far better on training than on test.
Use the difference r['train'] - r['test'] as the key, and take the max.
def most_overfit_depth(records):
return max(records, key=lambda r: r['train'] - r['test'])['depth']
A decision tree scores 100% on its training set but only 60% on held-out test data. What is the correct diagnosis?
A wide gap between near-perfect training accuracy and poor test accuracy is the signature of overfitting: the tree fit the training rows, noise included, too closely. Adding depth would make the memorisation worse, not better.
Recap
- An unbounded tree can drive its training error to zero by giving each point its own leaf — that is memorisation, not learning.
- Overfitting shows up as a gap: high training accuracy alongside lower test accuracy.
- Compare models with the test score, never the training score, which can only flatter.
- A depth limit, a minimum leaf size, and pruning each force the tree to stop splitting earlier and generalise better.
- Choose those settings on a separate validation set, and keep the test set untouched for a final, honest check.
Next you will turn one fragile tree into a whole forest — bagging and boosting combine many weak trees into a model that is far harder to overfit.