Decision Trees

Press the ideal case button in the box above. Eleven people, five children and six adults, and the whole model is one question.

Is height less than 151.5 cm?
  yes → predict child
  no  → predict adult

That is a decision tree with one question in it. The plane is cut in two at 151.5 on the height axis, everyone to the left is called a child and everyone to the right an adult, and the printed tree under the plot is the same rule as text. A tree predicts by routing an observation through a sequence of questions, and here the sequence has length one.

A tree is a hierarchy with questions at the nodes and predictions at the leaves. Load the muddled crowd above and set the depth cap to two for a tree that has all of these, a root, two internal questions beneath it, and four leaves.

A grown tree is a route map, and the way to feel that is to send someone down it. The crowd below is sixteen people chosen so that both questions matter, and the tree is kept two questions deep so the whole map fits in one look.

A person’s height reaches the root question. The answer picks a branch. On one branch a second question checks weight. The person reaches a leaf, and the leaf supplies the prediction. Nothing else in the tree is consulted. Prediction uses only the questions encountered along that observation’s own path.

Send the small child down and they are settled by the root alone, since everyone under 153.5 cm here is a child, and their weight is never read. Send the slender teenager down and the root cannot settle them, so a second question about weight is asked. Same tree, one question for one person and two for another.

Path length varies across observations, and a shorter path is not a better or more confident answer. It is a cheaper one. The tree asked as much as it needed to reach a leaf and no more, which is a quiet efficiency, and it says nothing about which prediction is more likely to be right.

Every question compares one measurement with one number. “Height less than 151.5” is a vertical line on the plane, with everyone sent left or right of it. “Weight less than 55” is a horizontal line, with everyone sent below or above. A threshold question divides the current region along one feature axis, and it can only ever divide it that way.

Start with one vertical cut. Add a horizontal cut to one side only. That side is now two rectangles and the other side is still one, and every further question splits one existing rectangle into two. The tree below grows one split at a time, with its rectangles growing alongside.

…

Slide from zero to eight splits and watch each new question carve one rectangle. Every leaf is one rectangle and every rectangle is one leaf, and the path to a leaf is the list of cuts that fenced its rectangle off. A standard axis-aligned tree builds its decision map by repeatedly dividing existing rectangles into rectangles, which is why the map can never hold a slanted edge.

Fit both models to one crowd and the difference is the shape of the boundary. Logistic regression draws one straight line at whatever angle the data asks for. The tree draws vertical and horizontal cuts, and where the true boundary is slanted it needs a staircase of them.

On the slanted crowd the line does in one cut what the tree needs several rectangles to approximate. On the muddled crowd, where the classes interleave in a way no line can follow, the tree reaches an accuracy of 0.857 with nine rectangles and the line manages 0.429. Neither is the better model in general. They make different geometric assumptions, and each is right where its assumption is.

Before any formula, compare three questions on the clean crowd by eye. The inspector below starts on a poor one.

A useful question creates child groups whose mixtures are cleaner than the parent’s. Which of the three is best needs no arithmetic. What needs arithmetic is ranking the seventeen other candidates the search also tries, and that is what the next Part builds.

Cleaner is the right test because of what a node is for. A node that stops splitting becomes a leaf, and a leaf predicts its majority for everyone who reaches it, so every person in the minority of a mixed node is a mistake the tree is committed to making. The third question above leaves no minority on either side, and so gets all eleven people right on its own. The first leaves three children among six adults on its nine-person side, three mistakes waiting to happen, and the second leaves one. A question is useful to the extent that knowing its answer tells you something about the label, and a smaller mixture on each side is what that means.

A node is pure when every observation in it has the same label. Five children and no adults is pure. Four children and one adult is mildly mixed. Five and five is as mixed as two classes can be. The split score has to measure the degree of mixture, so that a question can be scored by how much mixture it removes, and section 10 is that measure.

The measure has to be a number rather than a judgement, so that nineteen candidates can be ranked rather than three compared by eye, and two things are fixed about it before any formula is chosen. It must be zero for a pure node, since there is no mixture left to remove, and it must be largest at an even split, since five and five is the most mixed two classes can be. Any measure with those two properties, rising as the mixture does, ranks the three questions above the same way. Which one is used decides the arithmetic in between, and the next Part picks the one with the simplest story behind it.

Write the share of children in a node as p and the share of adults as 1 − p.

G = 1 − p² − (1 − p)²

Zero for a pure node, one half at an even mixture, and symmetric, so a node that is three quarters adults scores the same 0.375 as one that is three quarters children.

The formula is a thought experiment written down. Treat the node’s class shares as a probability distribution, draw one label from it, draw a second label from it independently, and ask whether the two differ.

P(the two agree) = Σₖ pₖ²
G = P(the two differ) = 1 − Σₖ pₖ²

A pure node cannot produce a disagreeing pair. An even mixture disagrees half the time. The simulator under the curve draws pairs from the mixture and its disagreement rate settles on the Gini value as the pairs accumulate.

Five children and six adults.

p_child = 5/11        p_adult = 6/11
G_root = 1 − (5/11)² − (6/11)² = 1 − 25/121 − 36/121 = 60/121 ≈ 0.496

Close to the two-class maximum of 0.5, so the root is highly mixed, which is right. What the number does not yet say is which question to ask. It describes the mixture before any question, and a question is scored by how much of it is removed.

Go back to the inspector in section 8 and pick the middling question, height less than 146. The left side holds four children and nothing else, so its Gini is zero. The right side holds one child and six adults.

G_right = 1 − (1/7)² − (6/7)² = 1 − 1/49 − 36/49 = 12/49 ≈ 0.245

A candidate split creates two new nodes, each with its own mixture and its own impurity, and the inspector shows both containers with their counts, shares and Gini for whichever question is chosen.

Height less than 121 makes a tiny pure node of two and a large mixed node of nine. A plain average of the two impurities, 0 and 0.444, is 0.222, and it gives the two-person node as much say as the nine-person one. So the children are weighted by how many observations each holds.

G_after = (n_left / n)·G_left + (n_right / n)·G_right

G_after = (2/11)·0 + (9/11)·0.444 = 0.364

gain = G_parent − (n_left / n)·G_left − (n_right / n)·G_right

Parent impurity is the mixture before the question. Weighted child impurity is what remains after it. The gain is what the question removed.

The tree prefers the question that removes the most weighted impurity right now, and section 20 is about the word now.

For a continuous feature, sort the observations by it, find each pair of neighbouring distinct values, and put a candidate threshold halfway between them. A threshold anywhere else in the same gap divides the observations identically, so it cannot score differently, and a threshold beyond the ends divides nothing.

Eleven distinct heights give ten candidates, and the slider in the inspector snaps to exactly those. The weights give nine more. Nineteen questions in all, which is the whole search space for this crowd.

Score every candidate on every feature and the search is a leaderboard. The chart below is every question the root weighed on the clean crowd, placed by its threshold and raised by its gain.

The winner is the tallest mark, height below 151.5 at a gain of 0.496. The selected question is the feature-and-threshold pair with the largest immediate impurity reduction, and nothing more subtle than that.

Two candidates can earn exactly the same gain. On the clean crowd, height below 146 and weight below 47 both score 0.340, because both peel off the same four children. A complete implementation has to say what happens then, and the usual answers are feature order, threshold order, the order the search scanned in, or a seeded random choice.

The rule matters because different tie policies produce different trees with identical immediate gain, and the multiclass and ensemble pages both met cases where two implementations broke a tie differently and grew apart from there. Every tree on this page keeps the first candidate scanned, with a small tolerance so that two gains reached by different arithmetic and differing in the last bits count as a tie.

After the root splits, send each observation to the left or right child, treat each child as a smaller dataset, and run the same candidate search inside it. Repeat until a stopping rule applies. The growth widget in section 6 is this, split by split, on the muddled crowd.

A decision tree is built by applying one local search, over and over, to smaller and smaller subsets of the data. There is no global step anywhere in it.

At each node the search takes the best immediate gain. It does not construct every possible tree, weigh what a split might make possible later, or guarantee the smallest or best tree. Searching every complete tree is impractical, so the construction makes locally strong choices, and locally strong is not globally optimal.

The crowd below is the case that shows it. Four children on one diagonal, four adults on the other, so the classes are perfectly separable by two questions, height and then weight. But the root cannot see that far.

Every one of the six candidate questions leaves both sides exactly as mixed as the parent, so every gain is zero, the search admits nothing, and the tree stays one leaf calling everyone the same class at an accuracy of 0.5. A search with one step of lookahead would find the two-question tree that gets all eight right. The greedy search cannot, because the first question earns nothing on its own, and it is only worth asking for what it makes the second question able to do.

A pure leaf is the easy case. Every training observation in it is a child, it predicts child, and its observed shares are one and zero. A tree may stop before a leaf is pure, though, and then the leaf predicts its majority and can report its observed shares.

prediction = child
P̂(child | leaf) = 6/8 = 0.75        P̂(adult | leaf) = 2/8 = 0.25

Click any leaf in the section 6 widget, in the tree or on the map, and its card gives who reached it, the counts, the majority and the shares. Set the depth cap to two there and several leaves are mixed.

When one split leaves both children pure, the tree stops, because no question inside a pure node can remove any mixture. Every number in the table is linked to the box at the top of the page with the ideal case loaded.

With no restriction a tree keeps dividing until every leaf is pure, or every observation is alone in its own rectangle, or no eligible split is left. On the muddled crowd that takes ten splits and eleven leaves, seven questions deep, to reach a training accuracy of 1.000, with the last two splits each fencing off a single person at depth six. The growth widget below caps the depth at six, so it stops two splits short of that, at nine leaves and 0.857 with its two deepest leaves still mixed. Pure training leaves do not mean good predictions for new observations, and a tree needs rules for when more specialisation is no longer justified.

Growth can be held back before it happens, and there are several controls, each limiting it differently.

…

Change one control at a time and watch the tree, the map and the leaf count. A minimum of four people per leaf stops the single-person rectangles the unrestricted tree grew, and the tree stops at three leaves and a training accuracy of 0.714 with the root question unmoved. Depth is only one of these controls, and an extra level of depth can at most double the number of leaves, which is not the same as doubling the questions available, since most nodes stop splitting before they reach the cap.

The alternative is to grow a large tree first and cut it back. Measure whether each branch improves things enough to be worth its complexity, and replace the ones that do not with a leaf. Cost-complexity pruning writes that down as one objective.

adjusted objective = training leaf error + α × number of leaves

A larger α buys fewer leaves, and the sequence of trees as α grows is a sequence of ever simpler candidates to judge on held-out data. Pruning simplifies an already grown tree by removing branches that do not earn their complexity, where the controls above stop them being grown at all.

Forty-four people whose classes overlap the way real measurements do, thirteen of them held back by a seeded shuffle, and a tree grown on the other thirty-one at every depth cap from one to six.

…

A deeper tree describes the training data more closely while becoming less reliable on people it never saw. The two extra leaves that took training accuracy from 0.935 to perfect cost two of the thirteen held-out people, because they fenced off rectangles around individual training observations that the held-out observations do not respect.

Go back to the growth widget in section 24 with the controls at their defaults and step to the last two splits. The seventh acts on six people at depth four, earns a gain of 0.044, and leaves one person alone in a rectangle, and the eighth acts on five people at depth five, earns 0.013, and leaves both of its sides still mixed. Five questions were spent to fence off one observation, and the cap is the only reason more were not.

Whether that was worth spending depends on what the observation is, and the tree cannot know. It might be a measurement error, a mislabelled person, a genuine rare case, a sign that a feature is missing, or a sign that the real pattern is complicated. A tree spends questions on an observation either way. What the held-out score in section 26 measures is whether the fence around it turned out to be a repeatable pattern.

Depth trades structural simplicity for sensitivity to the particular sample. Section 29 shows the sensitivity directly, and it is what the forests page is built to average away.

Change one label in the muddled crowd and grow the tree again.

…

A single relabelled person can move the root question, and everything beneath the root is decided inside the halves it made, so the branches reorganise and large regions of the map change their prediction. The second mode grows a tree on each of five random four-fifths of the crowd and overlays their root cuts, which land in different places for a reason that is mostly which people happened to be left out. A single decision tree is unstable because an early split changes every decision below it.

That instability is the motivation for the next page, and the motivation is more precise than a crowd of memorisers somehow generalising. Individual deep trees have high variance. Train many of them on deliberately varied samples and feature subsets, so their errors are not the same errors, and average their predictions or take their vote. Averaging reduces variance when the trees are diverse enough, and random forests are engineered to make them diverse. How the varying is done is bagging and random forests, and belongs there.

Measure the heights in metres instead of centimetres and the question becomes height less than 1.515. The same people are on each side of it, because dividing every value by a hundred keeps their order, and a threshold question reads nothing but the order.

So an ordinary tree generally does not need standardisation, and any monotonic transformation of a feature leaves the tree it grows unchanged apart from the numbers printed at the thresholds. Preprocessing can still be needed for other reasons, missing values and encodings among them, and the gradient-descent models on earlier pages needed scaling for reasons that do not apply here at all.

In the walking widget of section 3, weight is never consulted for anyone under 153.5 cm and decides everything for anyone over it. That is a conditional interaction, weight mattering only within one height range, and a tree expresses it without being told to, because a later question is only asked inside the region an earlier answer selected. A linear model would need the interaction built into its columns by hand.

Everything on this page is a numeric threshold. Categorical features and missing values are handled differently by different implementations, and there is no single behaviour to describe. Categories may be one-hot encoded, ordered, or partitioned natively. Missing values may be imputed, sent a learned default direction, routed by a surrogate question, or given a branch of their own. How a tree handles them is a decision an implementation has to make explicitly, and the trees here take finite numeric columns only.

A one-question tree can be read in a glance. The nine-leaf tree on the muddled crowd can be read with effort. A tree with twenty levels and thousands of leaves is still technically a list of rules, and nobody reads it in full. Depth, leaf count, average path length and the number of rules all grow, and past a point the structure is explicit without being understandable. A tree is readable when it is small, and being a tree does not keep it small.

If the tree asks about weight after height, that means the question improved prediction on the training data inside that branch. It does not show that weight causes the outcome, that 55 kilograms is a natural line in the world, that changing someone’s weight would change their class, that the training data was unbiased, or that the rule is fit for a decision with consequences. A path explains how the model produced its prediction. It does not explain why the real outcome happened.

Part 5 scored a split as the parent’s impurity less the weighted impurity of its two children, and the weights were argued for rather than derived. The whole score comes from one thought experiment, draw two labels from a node and ask whether they differ, applied once to the parent and once to the node a random observation lands in after the question.

height < 151.5:  gain = 0.496 − (5/11)·0 − (6/11)·0 = 0.496
height < 146:    gain = 0.496 − (4/11)·0 − (7/11)·0.245 ≈ 0.496 − 0.156 = 0.340

Positive gain means the split reduces the expected impurity. Zero means it leaves it unchanged, which is section 20’s crossed crowd at every candidate. Larger means a cleaner immediate division, and impurity gain is nothing more than the expected label mixture a question removes.

For several classes, count each class in the node and turn its count into a share. The Gini calculation includes every class.

G = 1 − Σₖ pₖ²

The rest of the procedure stays the same: compare candidate splits, choose one, and predict the majority class at a leaf. A tie between classes needs a stated policy, just as a tie between splits does.

A tree can predict a number instead of a class. At a regression leaf the prediction is the mean target of the training observations that reached it, and a split is scored by how much it reduces the squared error, or equivalently the variance, of the targets on the two sides.

The structure is not tied to classification. The leaf summary and the split score change with the task, and the gradient boosting page fits trees of exactly this kind to residuals.

A complete tree implementation has to define what it does with the cases the tidy description passes over.

The comparison convention is the one people forget. An observation exactly equal to a threshold has to go the same way every time, in growth and in prediction, and here strictly-less-than goes to the left and everything else to the right, through the one routing rule both the walk in section 3 and the bulk prediction call. It also refuses the empty and non-finite cases by name rather than growing a tree on nothing.

Each row is a place where two implementations that agree on the tidy description can grow different trees, or grow one silently on nothing, so the trees here decide every row once. An empty column, a non-finite value and a target holding one class are each refused by name before any growth, since a tree has nothing to separate in any of them. A constant feature offers no candidate thresholds, so the search never asks about it. On the clean crowd with every height held at one value the tree grows on weight alone, rooting at weight below 47 and reaching four leaves at a training accuracy of 0.909, and reports that height contributed nothing. A leaf minimum larger than the crowd leaves the root as the only leaf, predicting the majority, which on the eleven people is adult at an accuracy of 0.545. And a person standing exactly on a threshold goes right, in growth and in prediction alike, because the question asks for strictly less.