Decision Trees

You already know how to read one. Is the rent under £700? If yes, is it within 3.5 km of campus? If yes, predict it lets within a week. Follow the branches to a leaf and the leaf is your answer.

What makes it a model rather than a flowchart is that nobody chose those questions. Two things get decided from the data at every step: which feature to ask about, and where to cut it. Everything else follows.

This buys something the previous chapter could not. A k-Nearest Neighbours prediction justifies itself with a list of neighbours. A tree hands you a rule in words, and a landlord could argue with it. That is a real difference, and it is most of why trees survive in places where somebody has to explain a decision.

A good question separates the classes. Before any split, these fifty flats are a jumble. After splitting on rent at £697, one side is mostly flats that let quickly and the other is mostly flats that did not. The mess went down.

That mess has a number. Gini impurity asks: if you picked a flat from this group at random and guessed its outcome using nothing but the group's own proportions, how often would you be wrong? With two outcomes, an even 50/50 split scores 0.5, the worst possible. A group where every flat agrees scores 0. The formula is one minus the sum of each outcome's share squared, so a group that is 80/20 scores 1 − (0.8² + 0.2²) = 0.32.

To score a candidate split, measure the impurity of both sides, weight each by how many flats it holds, and subtract from the parent's. That drop is the gain. The tree tries every feature at every sensible cut point and keeps the largest gain. On this data the winner is rent at £697, worth 0.185 — close to the £700 the flats were actually generated around.

Having made that cut, the tree forgets it was ever part of a bigger problem and repeats the same procedure on each side independently. Cheap flats get their own best question. Expensive flats get theirs. Down and down until something stops it.

This is a greedy algorithm: it takes the best-looking step available right now and never revisits it. That is worth being suspicious of, because the best first question is not always part of the best overall tree. A pair of mediocre splits that work brilliantly together will lose to one good split followed by nothing, and the tree will never find out. Nobody solves this properly — searching every possible tree is computationally hopeless — so every tree you will ever use is greedy and slightly suboptimal by construction.

Drag the depth slider to 4 and look at the training score. It is 100%. Every one of the fifty flats it studied is now classified correctly, including the roughly one in eleven whose outcome was pure chance.

Now read the held-back line. It peaked at 82% back at depth 2 and has fallen to 68%. The tree spent depths 3 and 4 carving out tiny blocks around individual flats that happened to defy the pattern. Each of those blocks is the tree learning something true about one flat and false about everything else.

Left unrestrained, a tree will always reach this point. It can keep asking questions until every leaf holds a single flat, at which point it has stopped being a model and become a lookup table with extra steps. That is why every tree implementation ships with limits — a maximum depth, a minimum number of samples in a leaf, a minimum gain worth splitting for.

The same pattern on generated data with 15% of the labels flipped at random. Each line grows a tree to a different maximum depth.

from sklearn.datasets import make_classificationfrom sklearn.model_selection import train_test_splitfrom sklearn.tree import DecisionTreeClassifier # 600 rows, 2 useful features, and 15% of the labels flipped at random.X, y = make_classification(n_samples=600, n_features=2, n_informative=2,                           n_redundant=0, flip_y=0.15, random_state=1)X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0) for depth in [1, 2, 3, 5, 8, 12, None]:   # None means "grow until every leaf is pure"    tree = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X_train, y_train)    print(f"depth {str(depth):>4}: train {tree.score(X_train, y_train):.0%}"          f"   test {tree.score(X_test, y_test):.0%}   leaves {tree.get_n_leaves()}")

Training accuracy climbs all the way to 100%. Held-back accuracy peaks at 85% at depths 2 and 3, then slides to 78% once the tree has grown 63 leaves to fit the flipped labels.

Switch the view to the twenty-two held-back flats at depth 6 and you can watch the failure directly. The thin slivers the tree cut around awkward training flats now collect held-back flats that land in them for no reason at all, and each one is a confident wrong answer.

One tree, then, is easy to read, cheap to train, and reliably overfits. The next chapter takes that last flaw and turns it into the ingredient that fixes it.