Decision Trees

Information gain, Gini, pruning, depth-accuracy tradeoff

The last module put a precise name on a kind of failure: variance — a model so twitchy that swapping a handful of training rows produces a completely different fit, even though nothing about the underlying problem changed. Decision trees are about to make that failure vivid and countable, on numbers small enough to check by hand — and, one module from now, they're also the fix.

Start with the game of twenty questions. Someone picks a secret — a person, a place, a thing — and you guess it with yes/no questions. A good player never asks at random, and a good question isn't just one that splits the field in half — it's one that leaves each half as *unambiguous* as possible, ideally sorting candidates cleanly into "clearly this" and "clearly not this" rather than an even split that's still a jumble of both. That is almost exactly what a decision tree does with data — and a moment from now, on real numbers, half-splitting and clean-splitting will turn out to give different answers.

Here is a job where it shines and a straight-line model struggles. Say you want to flag loan applicants likely to default, using their income and their debt-to-income ratio. The real pattern is a set of rules: "if income is low *and* debt is high, risky — but a big income excuses a fair bit of debt." That is not a smooth weighted sum. It is the space of applicants carved into regions, each with its own answer. A linear model draws one line and gives up. A tree carves.

One question at a time

A decision tree asks a single yes/no question, splitting everyone into two groups, then asks the next question inside each group, and so on. The whole skill is choosing the *right* question at each step. And "right" has a clear meaning: the question that leaves the two groups as pure as possible — each side mostly one class.

So we need a way to measure how mixed a group is. Here's a natural way to do it: grab a random person from the group and guess their class from the group's own mix — how often would that guess be wrong? Take a group that's all defaulters: you would never be wrong, so call it perfectly pure. Take a group split 50/50: you would be wrong half the time, as messy as a two-class group can get. That guessing-error idea has a name and a formula: Gini impurity, $1 - Σpₖ²$, where pₖ is the share of class k — it comes out to 0 for the all-defaulters group and 0.5 for the 50/50 group, matching the guessing game exactly.

Watching it pick a split, on numbers you can check by hand

Eight loan applicants, income in thousands and debt-to-income ratio, four defaulted and four didn't: Ann (28, 0.50, default), Bob (33, 0.45, default), Cid (40, 0.55, default), Dee (44, 0.20, safe), Eve (52, 0.60, default), Fay (58, 0.15, safe), Gus (63, 0.10, safe), Hal (70, 0.05, safe). Notice Dee (low income, low debt) and Eve (high income, high debt) don't fit a clean story — that's deliberate, so no single question gets this for free. Four of eight defaulted, so the starting mix has Gini = 1 − 0.5² − 0.5² = 0.5 — as messy as a group can be.

Pause and predict: two candidate questions are on the table, "is income below 48k?" and "is debt-to-income at or above 0.35?" — both come from the standard way a tree generates candidates: sort each feature's values and try the midpoint between every adjacent pair, so 48k sits between two neighbouring incomes and 0.35 between two neighbouring debt ratios, not picked by hand. Which one do you expect splits these eight people more purely?

Try income first. Below 48k: Ann, Bob, Cid, Dee — three defaulters, one safe (Dee), so p=0.75 and Gini = 1 − 0.75² − 0.25² = 0.375. At or above 48k: Eve, Fay, Gus, Hal — one defaulter (Eve), three safe, same arithmetic by symmetry: Gini = 0.375. Both groups land at 0.375, so the weighted Gini after this split is 0.375 — down from 0.5, but Dee and Eve are still sitting on the wrong side, muddying both halves.

Now try debt. At or above 0.35: Ann, Bob, Cid, Eve — every one of them defaulted, Gini = 0 (perfectly pure). Below 0.35: Dee, Fay, Gus, Hal — every one of them stayed safe, Gini = 0 (perfectly pure too). Weighted Gini after this split: 0. The debt question separates all four defaulters from all four safe applicants in one move — Dee's low income didn't matter, Eve's high income didn't matter, only the debt ratio decided their fate correctly. It wins by the full margin available (0.5 → 0), against income's partial win (0.5 → 0.375), so the tree keeps it as the root.

Both children are already pure, so the tree stops after one split. The resulting tree has exactly two leaves: debt ≥ 0.35 → predict default (4 of 4 training rows, 100%); debt < 0.35 → predict safe (0 of 4, 0%). That's the whole training algorithm on this data: at every node, try every candidate question, keep the one that purifies the most, recurse until a group is pure or too small to split.

What a leaf says

A leaf just reports the mix of training points that landed in it — the debt≥0.35 leaf above says "100% chance of default" because all four training rows there defaulted. For predicting a number instead of a class — a loan amount, say — a regression leaf hands back the average of the training values that landed in it instead of a class vote.

That averaging hides a sharp limit worth remembering: a regression tree cannot extrapolate. If the priciest house it ever trained on was 800k, the tree can only ever answer with an average of prices it has already seen — it will never say 1.2M, no matter how big and fancy the new house is. Its answers are trapped inside the range of its training data.

The catch: trees are twitchy

Now the deep part. A tree is greedy — at each step it grabs the single best question available right now, with no thought for what that locks in later. It does not find the best tree *overall*; searching for that truly best tree is hopeless, because the number of possible trees is astronomical. Greedy is fast, but it comes at a price, and the eight applicants above are about to show exactly what price.

Change the labels on just two of the eight rows — nothing else — and flip Dee from safe to defaulted and Eve from defaulted to safe. Six of eight rows, 75% of the data, are untouched. Rerun both candidate splits. Debt at or above 0.35 now catches Ann, Bob, Cid (still defaulters) and Eve (now safe) — three of four defaulted, Gini = 1 − 0.75² − 0.25² = 0.375. Below 0.35 catches Dee (now defaulted), Fay, Gus, Hal — one of four defaulted, Gini = 0.375 too. Weighted Gini after the debt split: 0.375 — no longer the clean win it was. Income below 48k now catches Ann, Bob, Cid, Dee — and all four defaulted (Dee flipped to match them), Gini = 0 — pure. At or above 48k catches Eve, Fay, Gus, Hal, and all four are now safe, Gini = 0 — pure too. Weighted Gini after the income split: 0. The winner just reversed. Income is now the pure split; debt is the muddy one.

Here's the part that matters more than the flip itself: imagine a new applicant, Ivy, who was in neither training run — income 46k, debt-to-income 0.30. Feed her into the first tree (root: debt ≥ 0.35?): 0.30 is below the line, so the "safe" leaf fires — predicted safe. Feed the identical Ivy into the second tree (root: income < 48k?): 46 is below the line, so the "default" leaf fires — predicted default. Two trees, each 100% accurate on the data it was trained on, each built from data that agrees on 75% of its rows, hand Ivy opposite verdicts. Neither tree is *wrong* about its own training data — the disagreement is the variance the last module named, made concrete: which feature becomes the root is fragile, and everything downstream of the root inherits that fragility. This is high variance, and it is not a bug you can tune away — it is baked into greedy splitting.

Hold onto that fact, because next lesson it flips from weakness into superpower: a crowd of different, twitchy trees, averaged together, cancels out its own wobble. That is the whole idea behind random forests, built directly on top of the instability just measured here.

Two more things to know

Trees cut one feature at a time, so every boundary they draw is a straight, axis-aligned line — a horizontal or vertical fence. If the real boundary runs on a diagonal ("income plus debt above some total"), a tree can only approximate it with a staircase of many little fences, while a linear model draws that diagonal in a single stroke. So trees are clumsy exactly where lines are graceful, and graceful (carving boxes) exactly where lines are clumsy.

And left unchecked, a tree keeps splitting until nearly every leaf holds a single training point — 100% right on the training data, and badly overfit. The cure is pruning. You either stop early (cap the depth, or refuse splits that would leave too few samples in a leaf) or grow the full tree and then cut back the branches that do not earn their keep. Either way you give up a little training accuracy for a lot of test accuracy, and you choose how hard to prune by trying a few levels and keeping the one that generalises best.

Gini's cousin: entropy and information gain

Gini isn't the only way to measure mixedness, and the same eight applicants show why the alternative has a different name. Ask a different question about a group's mix: how many yes/no questions would it take, on average, to nail down one person's class? A perfectly pure group needs zero — you already know the answer before asking. A 50/50 group needs exactly one — a single fair coin-flip-style question settles it, and no cleverer strategy does better. That "average number of yes/no questions" is exactly what information theory calls entropy — the number of bits of surprise in the group's class mix — with formula −Σpₖ log₂pₖ. Score it on the eight applicants: the starting 4-defaulted/4-safe mix gives entropy = −(0.5 log₂0.5 + 0.5 log₂0.5) = 1 bit, the maximum possible for a two-way split, matching the "exactly one question" intuition exactly.

Score the original (unflipped) debt split the same way. Both children are pure, so both have entropy 0, and the weighted entropy after the split is 0. The drop from parent to children, 1 − 0 = 1 full bit, is called information gain — literally "how many bits of uncertainty did this question remove," and here the answer is all of it, in one question. Score the income split instead: each child is a 3-of-4 group, entropy = −(0.75 log₂0.75 + 0.25 log₂0.25) ≈ 0.811 bits per side, so the weighted entropy after the split is also ≈0.811, and the information gain is only 1 − 0.811 ≈ 0.189 bits — a small fraction of a bit, next to debt's full bit. Same ranking as Gini (debt still wins, income still second), because for a binary split the two measures nearly always agree on which question is best; entropy is the quantity ID3/C4.5-style trees maximise directly. Because of that near-agreement, the whole topic is often loosely titled "information gain" even when the tree underneath is actually scoring with Gini — there, "information gain" is shorthand for the *Gini-impurity drop*, not the literal bits-of-entropy quantity defined above; the two agree on which split wins far more often than they agree in value. Gini is slightly cheaper to compute (no logarithm) and is scikit-learn's default — pick either in practice.

How regression trees actually choose splits

For classification the tree purifies class mix. For regression there are no classes, so it purifies *spread*: it picks the split that most reduces the variance (equivalently, mean squared error) of the target within each child. A split that cleanly separates cheap houses from expensive ones drops the within-group variance a lot, so the tree takes it. If you care about robustness to outliers you can instead split on MAE (mean absolute error in place of squared error, so one huge-priced outlier house can no longer dominate which split looks best the way it would under squaring), and count-style targets (claim counts, visit counts) use a Poisson criterion, which scores a split by how well each child's mean predicts its own spread — the assumption built into count data, where variance and mean move together — instead of squared distance from the mean. But variance/MSE reduction is the default and the one to name.

The knobs: a hyperparameter map and real pruning

A single tree is controlled by a handful of parameters worth knowing by name. `max_depth` caps how deep it grows; `min_samples_split` and `min_samples_leaf` refuse splits that would leave too few examples; `max_leaf_nodes` caps total leaves; `class_weight` up-weights a rare class. Those are *pre-pruning* (stop early). The principled *post-pruning* is cost-complexity pruning (the CART method): grow the full tree, then minimise (impurity + `ccp_alpha` × number of leaves) — a penalty on tree size exactly analogous to regularisation. Bigger `ccp_alpha` means a smaller tree, and you pick it by cross-validation.

Categoricals and missing values: mind the implementation

"Trees handle mixed types" is true in principle but depends on the library. scikit-learn's classic trees actually need numeric input — you must encode categories yourself (and one-hot encoding a high-cardinality category can fragment the tree). True native categorical splits and native missing-value handling live in specific implementations (LightGBM, CatBoost, and newer histogram-based trees). So don't claim "trees just take categoricals" in an interview without naming which implementation.

When one class is rare

Under imbalance a tree happily chases the majority: it can make pure-looking leaves that are almost all the common class and score high accuracy while never catching the rare one. And its leaf probabilities become unreliable. Fixes are the usual family: `class_weight='balanced'` so rare examples count more at each split, threshold moving on the leaf probabilities, stratified CV so folds keep the rare class, and judging with PR-AUC rather than accuracy — the `class_imbalance_classical_ml` module ahead works this out with its own worked numbers.

Leaf probabilities lie a little

A classification leaf reports the *frequency* of each class among its training points. The debt-split tree above said "100% chance of default" and "0% chance of default" from its two leaves — and that's exactly the failure mode to distrust: each leaf held only four training rows, so "100%" really means "4 out of 4 seen so far," not "certainty." A single deep tree tends to give overconfident near-0/near-1 probabilities precisely because small, pure-looking leaves are easy to produce and easy to over-trust. If you need trustworthy probabilities from a tree, enforce a minimum leaf size and calibrate (Platt or isotonic) on a held-out set rather than trusting the raw leaf fractions.

Key points

• What a decision tree is, and when to reach for it: a flowchart of yes/no questions you can actually read. Trees are the model to use when you need to explain every prediction in plain words — "debt-to-income at or above 0.35, so we flagged it." They take mixed feature types (numbers and categories) as they come, need no scaling, and pick up feature interactions on their own, since splitting on income and then on debt is exactly an income-and-debt rule. The catch: a single tree is twitchy and overfits easily. So use one tree when you need a human-readable explanation, and an ensemble (random forest or boosting) when you need the accuracy in production.
• The instability isn't hypothetical: flip two rows out of eight and the root question can reverse. On the worked applicant data, the root split is debt-to-income (Gini 0.5 → 0, a full 1 bit of information gain) with income a clear runner-up (Gini 0.5 → 0.375, ≈0.189 bits). Change just two of the eight labels and income becomes the pure split while debt becomes the muddy one — six of eight rows never moved. A brand-new applicant who wasn't in either training set can get opposite predictions from the two trees, even though each tree is 100% accurate on its own data. That's variance from the last module, made concrete: which feature lands at the root is fragile, and everything beneath the root inherits that fragility.
• The trap that fools people: trusting the tree's built-in feature-importance scores. A tree's default importance counts how much each feature cut down impurity across all its splits. But a fine-grained number like income has many possible cut points, so it gets far more chances to split than a plain yes/no flag — and it ends up looking more important than it really is, just from having more opportunities. Do not rank features by this. Use permutation importance instead: shuffle one feature's values, measure how much accuracy drops, and repeat. A feature that truly mattered will hurt when scrambled; a useless one will not.
• The check to run: sweep how hard you prune, and watch train versus test accuracy. With no pruning a tree scores nearly perfectly on training data and poorly on test — pure overfitting. As you prune harder, test accuracy climbs (noise removed), peaks, then falls again (now you are cutting real structure). That peak is the right amount of pruning, and you find it with cross-validation, not by eyeballing a single split. Also watch leaf sizes: a leaf built from only two or three examples gives a probability you should not trust, so require a minimum number of samples per leaf.
• Know the split criteria and the hyperparameter map by name. Classification splits maximise purity via Gini (1 − Σpₖ²) or entropy/information gain (−Σpₖ log₂pₖ) — on the eight-applicant example, the winning debt split took Gini from 0.5 to 0 and entropy's information gain was a full 1 bit, while the losing income split only reached Gini 0.375 and ≈0.189 bits of gain. The two measures nearly always rank splits the same way; Gini is cheaper (no logarithm) and is scikit-learn's default. Regression splits minimise variance/MSE within children (MAE or Poisson as alternatives). The knobs: `max_depth`, `min_samples_split`, `min_samples_leaf`, `max_leaf_nodes`, `class_weight` for pre-pruning, and `ccp_alpha` for cost-complexity post-pruning — minimise (impurity + ccp_alpha × #leaves), pick ccp_alpha by CV.
• Mind implementation limits, imbalance, and leaf-probability calibration. scikit-learn's classic trees need numeric-encoded inputs — native categorical and missing-value handling lives in LightGBM/CatBoost/histogram trees, so don't claim "trees just take categoricals" without naming the library. Under imbalance a tree chases the majority and its leaf probabilities get unreliable — use `class_weight='balanced'`, threshold moving, stratified CV, and PR-AUC. And a leaf reports raw training frequencies (the debt-split leaves above reported 4/4 = 100% and 0/4 = 0%, from just four rows each), which are poorly calibrated for small leaves and overconfident overall, so enforce a minimum leaf size and calibrate on held-out data if you need trustworthy probabilities.

Recap

• Decision tree = flowchart of yes/no questions, each split chosen to make groups purer.
• Gini = 1 − Σpₖ²; entropy = −Σpₖ log₂pₖ, its drop = information gain (bits). Nearly always rank splits the same way.
• Worked split: 8 applicants, Gini 0.5 → debt split: Gini 0 (1 bit gained) vs income split: Gini 0.375 (≈0.189 bits) → debt wins, becomes root.
• Twitchy, concretely: flip 2 of 8 labels → root flips debt↔income → a new applicant gets opposite predictions from each tree, both 100% accurate on their own data.
• That instability is a feature — it makes trees the perfect base for random forests, built on canceling exactly this wobble.
• Axis-aligned cuts only — diagonal boundaries need a clumsy staircase.
• Regression leaves = average of training values landing there → cannot extrapolate past the training range.
• Don't trust built-in feature importances — biased toward high-cardinality features; use permutation importance.
• Prune to control depth: cost-complexity pruning minimises (impurity + ccp_alpha × leaves), tuned by CV.
• Small pure leaves overstate confidence — the debt-split leaves above hit 100%/0% from just 4 rows each; calibrate before trusting raw leaf fractions.

Check your understanding