Decision Trees

Most models hand you coefficients or scores. A decision tree hands you something rarer: 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 superpower — and the way it can grow itself into memorizing noise is its cautionary tale. Both are visible in a single picture.

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, carving the feature space into axis-aligned rectangles, each finally 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 drops the (size-weighted) impurity the most. "Greedily" matters: it grabs the best split available right now, never reconsidering, which is what makes trees fast, and also a little short-sighted.

Gini is not the only ruler. The other standard choice is entropy, borrowed from information theory: a 50/50 group costs one full bit to describe, a pure group costs none. The drop in entropy that a split buys has its own name, 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: an impurity drop of 0.1875, or an information gain of 0.296 bits. Different units, same verdict, and that is the usual outcome. Across 4,000 simulated datasets with every possible threshold enumerated, the best Gini split and the best information-gain split were the identical threshold 85% of the time. Which ruler you use is a footnote; how far you let the tree grow is not.

Depth is a dial — watch it turn into overfitting

Each level of depth lets the tree ask one more round of questions, drawing finer rectangles. A shallow tree captures the big picture; a very deep tree can wall off every single training point in its own box. Grow the tree below one split at a time and keep an eye on the two accuracy lines: training accuracy marches upward toward a perfect 100%, but accuracy on a held-out test set rises, peaks, and then falls as the deep splits start fitting noise. That peak-then-fall is overfitting, made visible.

Notice the asymmetry the interactive drives home: training accuracy can never warn you, because it keeps improving right up to memorization. Only the held-out line reveals the sweet spot. This is why a lone tree is usually kept shallow (for readability) or grown large and then pruned back to the cross-validated best depth.

Pruning, and the rent a leaf has to pay

Every guide says to grow a big tree and prune it, which leaves the obvious question unanswered: prune back to what? The standard answer is cost-complexity pruning, and it is one line of arithmetic. Score a tree not by its error alone but by its error plus rent for every leaf it keeps: R(T) + α × (number of leaves). At α = 0 the largest tree always wins. Raise α and each leaf has to earn its keep, so branches buying almost nothing get collapsed, producing a nested sequence of ever-smaller trees.

A worked case: a four-leaf subtree misclassifies 6 of 200 training cases, and collapsing it into a single leaf misclassifies 14. The subtree survives only while α < (0.07 − 0.03) ÷ 3 = 0.0133. Above that price, three extra leaves are not worth four percentage points of training error. You then pick α the way you pick depth, with cross-validation rather than by eye: R's rpart calls the knob 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. For a stakeholder who needs to know why, nothing else comes close.
• 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 flip the first split — and rebuild the entire tree beneath it into something that looks completely different. A single tree is a high-variance model.

That last weakness is the whole motivation for what comes next. If one tree is jumpy, grow many of them on resampled data and average their votes — the individual jitters cancel out, and you get a far more stable predictor. That's the idea behind random forests, and it's where this course heads next.