Decision Trees

A decision tree sorts rows by asking one yes-or-no question at a time, so each leaf reads as a plain rule you can say aloud.

Three axis-aligned splits make four rectangles, so a diagonal battery limit shows as a staircase

Why Does This Exist?

Dispatch wants a rule they can read before takeoff, not a score they can't act on. For each flight you know payload in kilograms and round trip distance in kilometres, plus whether it came home with charge to spare.

You could mix the two numbers into one score, but no one in dispatch can act on a sum. A tree keeps the numbers separate: payload over some threshold, then distance over another, each step a question with a yes or no. That's why crews trust it, and why it teaches well.

This page covers how one tree picks those questions, why its boundary looks like stairs, and how pruning keeps it honest. Random forests average many such trees, gradient boosting builds them in sequence to fix errors, and overfitting and underfitting names the failure pruning fights.

You need one idea to start: a classifier maps rows to labels. Trees do it with nested questions, one feature at a time. Gini impurity scores how mixed a pile is, and the next section uses it.

Think of It Like This

The sorting office with one gauge per worker

Parcels ride a belt past three stations. At the first station a worker reads one gauge, weight, and pushes each parcel left or right. Two workers downstream read a different gauge, distance, and split again. Three stations, four chutes.

A chute is good when almost everything in it shares a label. That's the whole objective: pick the gauge and cutoff that leave the chutes least mixed.

Where it stops: no worker may add weight to distance and act on the sum, because that sum is not a gauge on the wall. When the rule you need mixes both gauges at once, the office fakes it with extra stations, each shaving a corner. Close, never diagonal.

How It Actually Works

A tree grows by greedy search. At each node it tries every feature and every gap between observed values, keeps the split with the largest gain, then repeats on each child. Greedy means it takes the best now, never the best sequence.

How the split is scored

Mix needs a number. Gini impurity is $1 - \sum_k p_k^2$ , where $p_k$ is the share of rows at the node in class $k$ , the chance two rows drawn from the node disagree. Entropy is $-\sum_k p_k \log_2 p_k$ , the average surprise of a label drawn from the node, using base two so the units read as bits. Both sit at zero on a pure node and peak on a 50/50 split, and they rank splits the same most of the time. Gini skips the logarithm, so libraries such as sklearn.tree.DecisionTreeClassifier keep it as the default. For a numeric target both give way to variance reduction, how much a split shrinks the spread in each child.

The score is one subtraction, the parent impurity minus the row weighted average of the children:

\text{gain} = I(\text{parent}) - \frac{n_L}{n}\,I(\text{left}) - \frac{n_R}{n}\,I(\text{right})

$I$ is whichever impurity you chose, $n$ is the parent row count, $n_L$ and $n_R$ are how many rows land left and right. Those weights matter: a split that peels three rows into a pure child earns almost nothing.

Worked example: Gini falls from 0.50 to 0.32

Take ten flights: five came home with charge, five ran flat. The root holds $[5, 5]$ , meaning five of one label and five of the other:

I(\text{root}) = 1 - 0.5^2 - 0.5^2 = 0.50

Try payload over one threshold. Left takes five flights with four that made it and one that ran flat, $[4, 1]$ . Right takes the mirror, $[1, 4]$ :

I(\text{left}) = 1 - 0.8^2 - 0.2^2 = 1 - 0.64 - 0.04 = 0.32

Right matches it at $0.32$ . Equal halves keep the weighted average at $0.32$ , so:

\text{gain} = 0.50 - 0.32 = 0.18

A gain of $0.18$ on ten rows is large, which is why this split wins. The code below repeats these same three numbers.

Why the boundary is a staircase

Every split compares one feature against one threshold, a cut at right angles to an axis. Regions stay rectangles with sides parallel to the axes.

Your battery limit mixes payload and distance, so its frontier runs diagonally. The tree approaches it by stacking steps: cut payload once, then cut distance differently on each side. Every extra split halves a step. None tilts one.

The picture shows it: three splits, four rectangles, one diagonal limit. Two amber dots sit inside the true limit yet on the fail side of the stairs. That is the tax. Hand the tree a rotated frontier and it spends depth approximating what one line nails. Add payload times distance as a feature and it gets there in one split. No scaling needed, mixed types fine, rotation never.

How pruning keeps the tree honest

Left alone, recursion runs until every leaf is pure. On noisy flights that means leaves with one flight that caught a tailwind.

Pre pruning refuses to grow: cap depth, demand a minimum rows per leaf, demand a minimum gain. Almost free, and greedy in the damaging sense. A split that looks worthless alone can set up a good one two levels down, and pre pruning kills the parent first.

Post pruning grows out, then collapses branches that did not pay. Cost complexity pruning charges per leaf:

R_\alpha(T) = R(T) + \alpha\,|T|

$R(T)$ is the tree error, $|T|$ is its leaf count, $\alpha$ is the price per leaf. Raise $\alpha$ from zero and the tree collapses through nested subtrees. Pick the $\alpha$ that wins on held out validation. One number sets depth for you.

Code

The point is the check: score the ten flight split by hand, then confirm it in code.

1def gini(counts: list[int]) -> float:2    total: float = sum(counts)3    return 1.0 - sum((c / total) ** 2 for c in counts)4
5root: float = gini([5, 5])6child: float = gini([4, 1])7gain: float = root - child  # equal halves, so the weighted average stays 0.328
9print(f"{root:.2f} {child:.2f} {gain:.2f}")  # -> 0.50 0.32 0.18

The printout matches the hand computation: root 0.50, each 4 and 1 child 0.32, gain 0.18.

Watch Out For

A tree that scores 1.00 on its own training set

Perfect training accuracy is the default for an unpruned tree, not an achievement.

Symptom: training reads 1.00 while validation sits near a coin flip, with leaves holding one or two rows. More rows rarely fix it. The tree grows deeper and isolates the new oddities too.

Fix: cap depth, raise the minimum rows per leaf, or sweep $\alpha$ and let held out validation choose. Then measure again on overfitting and underfitting curves.

Believing the printed feature importances

Impurity importance sums how much each feature cut impurity across the tree. It reads as a ranking of what matters. It partly ranks how many cut points each feature offered.

Symptom: a customer identifier or raw timestamp outranks a feature you know drives the outcome, because a column with many distinct values gets many chances to look useful while a binary flag gets one.

Fix: use permutation importance on held out data. Shuffle one column, measure how far validation drops, restore it, repeat. Slower, and it answers the question you asked. Feature importance shows the honest version.

The Quick Version

Decision trees ask one yes or no question per node, keep the split with the largest impurity drop, then recurse.
A 5 and 5 root has Gini 0.50, each 4 and 1 child has Gini 0.32, so the gain is 0.18.
Gain is parent impurity minus the row weighted child average, which stops tiny pure leaves from looking good.
Cost complexity pruning picks the subtree that minimizes error plus $\alpha$ per leaf, with $\alpha$ chosen on held out validation.
Axis aligned splits make rectangles only, so a diagonal frontier becomes a staircase that extra depth never tilts.
One unpruned tree has high variance, so ensembles average many trees or build them in sequence to fix errors.