Decision Trees in machine learning

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

Decision Trees, in more detail

A decision tree asks one question at a time and splits the data on the answer.

Each question is chosen to make the two resulting groups as pure as it can.

It keeps going until a group is pure or some limit stops it.

The result reads like a flowchart, which is why people like it.

You can point at a path and say exactly why a prediction happened.

It needs no feature scaling, since it only ever compares within one column.

It handles mixed data types with far less preparation than most models.

Left unrestricted it will grow until every training row has its own leaf.

That is perfect memorisation and useless on anything new.

Limiting the depth, or demanding a minimum group size, keeps it sane.

Small changes in the data can produce a completely different tree.

That instability is why single trees are rarely used on their own.

It splits one feature at a time, so diagonal boundaries come out as staircases.

It also favours features with many distinct values, which can mislead you.

Its real value today is as the building block of forests and boosting.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Decision Trees

What a split is chosen to reduce

A tree grows by asking, at every node, which single question about one feature best separates the labels.

G = 1 - \sum_{c=1}^{C} p_c^2

$p_c$ : the fraction of the samples at this node that carry class $c$ .
$C$ : the number of classes.

This is Gini impurity: 0 when a node holds one class only, and $1 - 1/C$ when the classes are spread evenly.

H = - \sum_{c=1}^{C} p_c \log_2 p_c

Entropy measures the same thing on a different scale, and in practice the two pick almost the same splits.

The gain a split has to earn

\Delta = I(\text{parent}) - \frac{n_L}{n} I(L) - \frac{n_R}{n} I(R)

$I$ : the impurity measure, Gini or entropy.
$n_L, n_R$ : how many samples go left and right.
$n$ : how many arrived at this node.

The children are weighted by size, so a split that peels off three clean samples out of a thousand scores almost nothing.

The split with the largest $\Delta$ is taken, and the process repeats on each child.

One tree, in order

Start with every training sample at the root.
For each feature, try every threshold that separates two observed values.
Score each candidate split by its weighted impurity drop.
Keep the best one and send the samples left or right.
Repeat on each child until a stopping rule fires.
Label each leaf with the majority class of the samples that reached it.

Regression trees change only the impurity

I = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2

Variance replaces Gini, the leaf predicts the mean of its samples instead of a majority, and every other step is identical.

Why an unstopped tree is useless

Grown without limit, a tree keeps splitting until every leaf holds one sample, which fits the training set perfectly and generalises to nothing.

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

$R(T)$ : the tree's error.
$|T|$ : the number of leaves.
$\alpha$ : the price charged per leaf.

Cost-complexity pruning grows the tree fully and then removes the branches that do not pay for themselves at a given $\alpha$ , chosen by cross-validation.

The cheaper controls are a maximum depth, a minimum number of samples per leaf, and a minimum gain, all of which stop the tree before it memorises.

The two properties that decide when to use one

A tree is invariant to monotone transforms of a feature, so scaling and log transforms change nothing about which splits it picks.

Its boundaries are axis-aligned rectangles, so a diagonal boundary has to be approximated by a staircase and a single rotation of the data can ruin it.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What happens to a decision tree with no depth limit?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →