How a tree chooses where to cut

Twenty loans

Twenty applications, six of which defaulted. The tree has to pick one feature and one threshold to split on. How does it decide?

It tries every threshold on every feature and scores each one by how much purer the two resulting groups are than the parent.

Impurity, measured

Gini impurity for a node is 1 - sum of p_k^2 over the classes. It is the probability that two items drawn at random from the node have different labels.

The parent: 6 defaults in 20, so p = 0.3.

Gini(parent) = 1 - (0.3^2 + 0.7^2) = 1 - (0.09 + 0.49) = 0.42

Now try the split income < 300000. It sends 8 rows left, of which 5 defaulted, and 12 right, of which 1 defaulted.

Gini(left)  = 1 - (0.625^2 + 0.375^2) = 0.469
Gini(right) = 1 - (0.083^2 + 0.917^2) = 0.153
weighted    = (8/20)*0.469 + (12/20)*0.153 = 0.188 + 0.092 = 0.280
gain        = 0.42 - 0.280 = 0.14

Try age < 30: 9 left with 3 defaults, 11 right with 3 defaults.

Gini(left)  = 1 - (0.333^2 + 0.667^2) = 0.444
Gini(right) = 1 - (0.273^2 + 0.727^2) = 0.397
weighted    = 0.45*0.444 + 0.55*0.397 = 0.418
gain        = 0.42 - 0.418 = 0.002

Income wins, decisively. The tree takes it, then repeats the whole procedure inside each child.

That is the entire algorithm. Try everything, take the best local gain, recurse. It is greedy (it never reconsiders an earlier split in light of a later one) which means a tree can miss a combination that a two-step lookahead would have found. Nobody does the lookahead, because it is exponentially expensive and the greedy version works well enough.

Entropy, and whether it matters

The alternative impurity measure is entropy, -sum of p_k * log2(p_k), borrowed from information theory. The gain is then called information gain.

In practice the two produce nearly identical trees. Entropy is slightly more expensive because of the logarithm, and its differences from Gini show up mainly in how they treat very unbalanced nodes. Gini is the default in scikit-learn, and the choice is not worth an experiment.

For regression the criterion is different: minimise the variance within each child, which is the same as minimising squared error. Each leaf predicts the mean of its training rows.

What a tree can and cannot represent

Worth being concrete, because it explains most of the algorithm’s behaviour.

Can: any axis-aligned region. Interactions of any order, for free: split on income, then on age inside that branch, and you have expressed “young people with low income” without anyone specifying an interaction term. Non-monotonic relationships. Missing values as their own branch.

Cannot, without difficulty: a diagonal boundary. If the true rule is income > 3 * expenses, a tree approximates it with a staircase and needs many splits to do badly what one ratio does exactly. This is why the engineered-ratio advice in module 3 helps trees too.

Cannot, at all: extrapolate. Every prediction is a leaf mean computed from training rows, so a tree’s output is bounded by the range of the training targets. Ask a tree trained on houses up to 130 square metres about a 400 square metre house and it returns the mean of its rightmost leaf. That is arguably safer than a linear model’s confident extrapolation, and it is definitely different: know which failure mode you prefer.

A single tree overfits, spectacularly

Grown without limits, a tree keeps splitting until every leaf is pure, which usually means one training row per leaf. Training accuracy 100%, validation accuracy poor, and the tree is a lookup table.

The controls:

DecisionTreeClassifier(
    max_depth=5,             # hard cap on levels
    min_samples_leaf=20,     # the most useful one
    min_samples_split=50,
    max_features="sqrt",     # consider a subset at each split
    ccp_alpha=0.01,          # cost-complexity pruning
)

min_samples_leaf is the one to reach for first. It directly says “do not make a claim based on fewer than 20 examples”, which is the honest version of what you want.

Why a single tree is rarely the answer

The fatal property is instability. Change 5% of the training rows and the top split may change, which changes every split beneath it, and you get a structurally different tree. Two trees fitted on 95% overlapping data can look nothing alike.

That is high variance in the module 4 sense, and it has a direct remedy: fit many trees and average them. Which is the next lesson, and the reason single trees are used today mostly for explanation rather than prediction: a depth-3 tree that a manager can read is worth something even when a forest predicts better.