Decision trees

A game of yes-or-no questions can sort dots too. Below, a tree asks them one at a time. Before it plays: will a deeper tree make fewer mistakes on new dots?

Reading a tree

A decision tree is a list of questions arranged so that each answer leads to the next question. Each question asks about one feature: “is feature 2 above this value?”. Start at the top, the root, answer, follow the branch, and keep going until no question is left. That last stop is a leaf, and it gives the prediction: the class most of the training dots that reach it belong to (a tie goes to class A), or, when the labels are numbers, their average.

On the plane, each question is a straight cut across or down, because it looks at one feature only. A tree of questions cuts the plane into boxes, one box per leaf. The depth of a tree is the largest number of questions asked on the way to any leaf.

The first cut in the clip runs across the plane, at about $x_2=-0.09$: above it mostly class A, below it mostly class B. That one question leaves only 12 of the 100 dots on the wrong side. The next two cut down, near the left and right edges, and trim the crescents’ outer tips, where each crescent reaches past the other. The cuts at depth 3 change no box’s class: they only carve off boxes that hold one class, so the mistakes stay at 8.

Choosing a cut

Which question first? The tree tries every one: each feature, and each threshold halfway between two neighbouring values of that feature among the dots in the box. It keeps the cut that makes the two new boxes purest. That needs a measure of how mixed a box is.

A box whose dots are all one class is pure. Write $p_c$ for the share of the box’s dots that are class $c$; here it is a share of dots, not a probability. The Gini impurity of the box is

It is 0 for a pure box, and for two classes it is largest, 0.5, when the box is half and half. A cut splits a box of $m$ dots into a left side of $m_\text{left}$ dots with impurity $G_\text{left}$ and a right side of $m_\text{right}$ with $G_\text{right}$. Their impurity together is the weighted average

and the tree chooses the cut whose weighted impurity falls furthest below the box’s own. If two cuts fall by exactly the same amount, the one on the lower-numbered feature wins, then the one with the lower threshold.

A second measure, the entropy $-\sum_cp_c\log_2p_c$ in bits, is used in the same way and usually picks the same cuts.

Growing and stopping

The tree is greedy: it picks the best single cut now and never goes back. Trying every whole tree at once would mean far too many to compare, so the tree it finds is not necessarily the best possible.

Left alone, it keeps cutting until every box is pure. Then it makes no mistakes on its training dots, but the last cuts are thin strips round single stray dots, which is noise, not shape. So a tree is stopped early: at a maximum depth, or when a box holds too few dots to split.

Now the answer to the question. On the training dots, the mistakes never rise as the tree grows: 12 at depth 1, 8 at depths 2 and 3, and on down to 0 at depth 9, where every box is pure. On new dots they fall from 22 to 9 at depth 2, and never improve after that: they are lowest at depths 2 to 4, 9 of 100, and from depth 5 on they come and go between 10 and 16 as the strips chase the training dots’ noise.

That is the trade of Bias and variance of a model again: a shallow tree is too simple to follow the crescents, and a deep one changes with every stray dot. Depth plays the part that $k$ plays in Nearest neighbours, in the opposite direction: a small $k$ and a deep tree both follow the noise.

What trees cannot draw

Every cut is across or down, so a tree can only draw boundaries made of horizontal and vertical pieces.

A slanted boundary costs a tree many cuts, and it still only approximates it, where Logistic regression draws it with one line. Each kind of model has shapes it draws easily and shapes it struggles with.

Worked example

Ten pumps, made-up data: 6 healthy and 4 faulty. Before any cut the box has $p_\text{healthy}=0.6$ and $p_\text{faulty}=0.4$, so its Gini impurity is

Cut A, “vibration above 4 mm/s”. The “no” side has 4 healthy and 0 faulty, Gini 0. The “yes” side has 2 healthy and 4 faulty, Gini $1-\big((1/3)^2+(2/3)^2\big)=1-(1/9+4/9)=0.4444$. Weighted: $0.4\times0+0.6\times0.4444=0.2667$. The fall is $0.48-0.2667=0.2133$.

Cut B, “temperature above 70 °C”. The two sides have 4 healthy and 1 faulty (Gini $1-(0.64+0.04)=0.32$) and 2 healthy and 3 faulty (Gini $1-(0.16+0.36)=0.48$). Weighted: $0.5\times0.32+0.5\times0.48=0.40$. The fall is $0.48-0.40=0.08$.

Cut A wins, by a wide margin: it makes one side pure.

With entropy. The box before any cut has $-(0.6\log_20.6+0.4\log_20.4)=0.9710$ bits. After cut A: $0.6\times0.9183=0.5510$ bits, a gain of 0.4200. After cut B: $0.5\times0.7219+0.5\times0.9710=0.8464$ bits, a gain of 0.1245. Entropy agrees: cut A.

Two edge cases. A box that is half and half has Gini $1-(0.25+0.25)=0.5$. A pure box has Gini 0.

Where you’ll meet this

Decisions that must be explained. A tree can be read aloud, question by question, so it suits rules that must be justified to the people they affect, such as credit decisions or triage in a hospital.

Fault-finding. A checklist that asks one reading at a time to locate a machine’s fault is a tree, and a fitted tree can suggest which readings to ask first.

Forests and boosting. Many trees together make some of the most used models for tables of business and sensor data. Random forests average many trees grown on resampled data, and Boosting adds small trees one at a time, each correcting the last.

Reference card