Machine Learning
Topic 17 · Supervised algorithms · ⏱ about 3 h

Decision Trees

A flowchart of yes/no questions learned from data.

Show:
In this topic
Beginner

How a tree is built

A decision tree makes predictions by asking a sequence of yes/no questions about the features, like a flowchart. To decide whether to approve a loan, a tree might first ask "is the applicant's income above $50,000?". If yes, it follows the left branch and asks another question, perhaps "is their existing debt below $10,000?"; if no, it follows the right branch and asks something different. Each question narrows the possibilities, until the path reaches an end point called a leaf, which gives the prediction.

income > 50k?noyesdebt < 10k?leaf: approvedeclineapproveincome = 50kdebt = 10kdeclineapproveapprove
A decision tree (left) and the axis-aligned regions it carves out of feature space (right).

The interesting part is how the tree chooses its questions from data. It works from the top down. At the start, all the training examples sit together in the root. The algorithm considers every feature and every possible threshold for that feature, and for each candidate question it imagines splitting the examples into the two groups that would answer yes and no. It then picks the question whose two groups are the purest, meaning each group is dominated as much as possible by a single class. It then repeats the same process separately inside each group, and so on, until the groups are pure or some stopping rule is reached. This procedure is called CART (classification and regression trees).

"Purity" is measured by an impurity score, which is zero for a group containing only one class and highest for a group where the classes are evenly mixed. The two standard choices are

Gini=1−∑kpk2andEntropy=−∑kpklog⁡2pk, \text{Gini} = 1 - \sum_k p_k^2 \qquad\text{and}\qquad \text{Entropy} = -\sum_k p_k \log_2 p_k,

where pkp_k is the fraction of the group belonging to class kk. For a pure group, one pkp_k equals 1 and both scores are 0; for a 50/50 group of two classes, the Gini score is 0.5 and the entropy is 1 bit. The quality of a split is the drop in impurity it achieves; with entropy, this drop is called the information gain. Regression trees work the same way, but measure impurity by the variance of the target values in a group, and each leaf predicts the average target of the examples that reach it.

One important property is that the procedure is greedy: at each step it picks the split that looks best right now, without considering whether a less impressive split might enable much better splits later. Searching over all possible trees would be computationally impossible, and the greedy approach works well in practice.

Interactive: this part runs in your browser.

Interactive. Drag the split threshold and watch the impurity of each side; the curve shows every possible split.
Beginner

Watch it: How a decision tree grows, one question at a time

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Try it

Try it: tree depth

The true pattern is a circle, with 8% label noise. Shallow trees underfit; very deep trees carve tiny boxes around noisy points.

Interactive: this part runs in your browser.

Beginner

Controlling overfitting & pros/cons

Left to grow without limits, a decision tree keeps splitting until every leaf is pure, which usually means memorising the training data, noise included. Controlling this growth is therefore essential, and there are two approaches.

Pre-pruning stops the tree from growing too far in the first place, by setting limits in advance: a max_depth (how many questions can be asked in a row), a min_samples_leaf (the smallest number of training examples a leaf may contain), a min_samples_split (how many examples a group must have before it may be split), or a max_leaf_nodes. These are hyperparameters, chosen by cross-validation. Post-pruning takes the opposite approach: grow the tree fully, then cut back the branches that don't earn their keep. The standard method, cost-complexity pruning, charges a price for every leaf and keeps only the branches whose improvement in accuracy outweighs their cost; in scikit-learn the price is the ccp_alpha parameter.

Decision trees have a distinctive set of strengths. They are among the most interpretable models: a small tree can be drawn on a page and explained to anyone, which matters in fields such as medicine and lending. They need no feature scaling, because a question like "income above 50,000?" is unaffected by the units. They handle numerical and categorical features together, capture non-linear patterns and interactions between features naturally, and report which features were most useful.

Their weaknesses are equally distinctive. They overfit easily unless pruned. They are unstable: because each split depends on the ones above it, a small change in the training data can change an early split and produce a completely different tree. And their decision boundaries are made of horizontal and vertical segments, so they approximate smooth or diagonal boundaries with blocky staircases.

The instability turns out to be the key to their most successful use. Because individual trees are unstable and high-variance, averaging many different trees cancels out much of that variance, and this is the idea behind random forests and gradient boosting, which are among the most accurate methods for tabular data.

Intermediate · Maths

Impurity, information gain: a worked example

📐 Maths you'll need: m-notation · m-prob
💡 The idea in plain words

A good question splits a mixed group into purer groups. Gini and entropy are just two ways to score how "mixed" a group is: 0 when everyone is the same class, highest when classes are evenly mixed. The tree tries every possible question and picks the one that reduces mixedness the most.

🔤 Symbols in this section
pkp_kfraction of the node in class k
H(t)H(t)entropy of node t (bits, log base 2)
I(t)I(t)impurity of node t (Gini, entropy or variance)
nL, nRn_L,\ n_Rnumber of points going left / right
ΔI\Delta Iimpurity decrease (information gain for entropy)

This section makes the split criterion precise and works through a complete example, so you can see exactly how a tree compares two candidate questions.

For a node tt in which a fraction pkp_k of the examples belong to class kk, the two impurity measures are

Gini(t)=1−∑kpk2,H(t)=−∑kpklog⁡2pk. \text{Gini}(t) = 1 - \sum_k p_k^2, \qquad H(t) = -\sum_k p_k\log_2 p_k.

A candidate split ss sends nLn_L of the node's nn examples to a left child tLt_L and nRn_R to a right child tRt_R. Its quality is the weighted impurity decrease, the parent's impurity minus the average impurity of the children, each child weighted by its share of the examples:

ΔI(s)=I(t)−nLnI(tL)−nRnI(tR). \Delta I(s) = I(t) - \frac{n_L}{n}I(t_L) - \frac{n_R}{n}I(t_R).

The weighting matters: a split that produces one tiny pure child and one large mixed child should not score as well as a split that makes both large children purer. When II is entropy, ΔI\Delta I is called the information gain. The algorithm evaluates ΔI\Delta I for every candidate split and chooses the largest.

A worked example. A node contains 10 examples, 5 positive and 5 negative. A candidate split sends 5 examples left, of which 4 are positive and 1 negative, and 5 examples right, of which 1 is positive and 4 negative.

Step 1: parent entropy. With p=0.5p = 0.5 for each class, H=−0.5log⁡20.5−0.5log⁡20.5=0.5+0.5=1H = -0.5\log_2 0.5 - 0.5\log_2 0.5 = 0.5 + 0.5 = 1 bit, the maximum possible for two classes.
Step 2: child entropy. Each child has proportions 0.8 and 0.2, so H=−0.8log⁡20.8−0.2log⁡20.2=0.8(0.322)+0.2(2.322)=0.258+0.464=0.722H = -0.8\log_2 0.8 - 0.2\log_2 0.2 = 0.8(0.322) + 0.2(2.322) = 0.258 + 0.464 = 0.722 bits.
Step 3: information gain. Both children hold half the examples, so the weighted average child entropy is 12(0.722)+12(0.722)=0.722\tfrac12(0.722) + \tfrac12(0.722) = 0.722, and the gain is 1−0.722=0.2781 - 0.722 = 0.278 bits.
Step 4: the same with Gini. The parent's Gini impurity is 1−0.52−0.52=0.51 - 0.5^2 - 0.5^2 = 0.5. Each child's is 1−0.82−0.22=1−0.64−0.04=0.321 - 0.8^2 - 0.2^2 = 1 - 0.64 - 0.04 = 0.32. The decrease is 0.5−0.32=0.180.5 - 0.32 = 0.18.

Another candidate split would be scored in exactly the same way, and the larger decrease wins. In practice, Gini and entropy almost always choose the same split; Gini is slightly faster because it avoids logarithms, which is why it is scikit-learn's default.

For regression trees, impurity is the variance of the targets in the node, I(t)=1nt∑i∈t(yi−yˉt)2I(t) = \frac{1}{n_t}\sum_{i\in t}(y_i - \bar y_t)^2, and each leaf predicts its mean yˉt\bar y_t. Splitting therefore aims to create groups whose target values are as similar as possible. A useful mathematical fact is that all of these impurity measures are concave functions of the class proportions, which guarantees that ΔI\Delta I is never negative: splitting can never make the weighted impurity worse, only equal or better.

Key takeaway. Each split maximises the weighted impurity decrease; for the 5/5 → (4,1)/(1,4) example, information gain = 0.278 bits and the Gini drop = 0.18.
Advanced

Greedy search cost, pruning and feature importance

📐 Maths you'll need: m-notation
💡 The idea in plain words

Growing a tree is greedy and fast, but a fully grown tree memorises noise. Pruning trades training accuracy for simplicity, with a "price per leaf" α. And the built-in feature importance can be misleading, so check importance on held-out data instead.

🔤 Symbols in this section
R(T)R(T)training error of tree T
∣T∣|T|number of leaves
α\alphaprice per leaf (ccp_alpha)
Rα(T)R_\alpha(T)penalised error
O(d nlog⁡n)O(d\,n\log n)cost of finding the best split

This section looks at three practical details of trees: how fast the best split can be found, how cost-complexity pruning works, and why the default feature-importance scores can mislead.

Finding the best split efficiently. For a numerical feature, the only thresholds worth trying lie between consecutive distinct values, since any threshold in the same gap produces the same split. So the algorithm sorts the examples by that feature, which takes time proportional to nlog⁡nn\log n, and then sweeps through the sorted list once, moving one example at a time from the right group to the left and updating the class counts as it goes. Each candidate split can then be scored in constant time, so a whole sweep costs time proportional to nn. Doing this for all dd features gives a cost of roughly d nlog⁡nd\,n\log n per level of the tree. Finding the single best possible tree, rather than growing one greedily, is an NP-hard problem, which is why every practical algorithm is greedy. Modern libraries such as LightGBM and scikit-learn's histogram-based estimators go further by grouping each feature's values into about 256 bins in advance, which makes split-finding roughly proportional to d nd\,n and much faster on large datasets.

Cost-complexity pruning. Breiman and colleagues proposed judging a subtree TT by its training error R(T)R(T) plus a charge α\alpha for each of its ∣T∣|T| leaves:

Rα(T)=R(T)+α ∣T∣. R_\alpha(T) = R(T) + \alpha\,|T|.

When α=0\alpha = 0, leaves are free and the full tree is best. As α\alpha increases, leaves become expensive, and it pays to collapse branches whose improvement in training error is smaller than the cost of their extra leaves. For every value of α\alpha there is a unique smallest subtree that minimises RαR_\alpha, and as α\alpha increases these subtrees are nested, each one a pruned version of the previous. An efficient procedure called weakest-link pruning finds the whole sequence by repeatedly removing the branch that gives the smallest increase in error per leaf removed. We then choose the value of α\alpha (and therefore the tree) with the best cross-validation score. In scikit-learn, cost_complexity_pruning_path returns the candidate values and ccp_alpha sets the chosen one.

Feature importance. Trees report a feature importance called mean decrease in impurity (MDI), which adds up, over every split that uses a feature, the impurity decrease weighted by the fraction of examples reaching that split. It is free to compute, but it has two weaknesses. It is calculated on the training data, so it rewards features the tree used to fit noise. And it is biased towards features with many distinct values, such as IDs or continuous measurements, because such features offer many more candidate thresholds and therefore more chances to find a split that looks good by luck. More reliable alternatives are permutation importance, which randomly shuffles one feature in held-out data and measures how much the model's score drops, and SHAP values, which share out each individual prediction fairly among the features.

Two more properties are worth knowing. Because splits only compare a feature with a threshold, trees are completely unaffected by any transformation that preserves order, such as taking a logarithm. And many modern implementations handle missing values directly, by learning, at each split, which branch examples with a missing value should follow.

Key takeaway. Choose α for cost-complexity pruning by cross-validation, and prefer permutation importance or SHAP over impurity-based importance.
Code

Code: a split finder from scratch, and pruning in scikit-learn

The scratch code finds the best Gini split for one node, exactly as CART does at each step.

Python · NumPy from scratch
import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    return 1 - np.sum(p ** 2)

def best_split(X, y):
    best = (None, None, gini(y))                    # (feature, threshold, impurity)
    n = len(y)
    for j in range(X.shape[1]):
        order = np.argsort(X[:, j])
        xs, ys = X[order, j], y[order]
        for i in range(1, n):
            if xs[i] == xs[i - 1]:
                continue                            # no threshold between equal values
            left, right = ys[:i], ys[i:]
            imp = (i * gini(left) + (n - i) * gini(right)) / n
            if imp < best[2]:
                best = (j, (xs[i] + xs[i - 1]) / 2, imp)
    return best

rng = np.random.default_rng(0)
X = rng.uniform(size=(200, 2))
y = ((X[:, 0] > 0.6) | (X[:, 1] > 0.8)).astype(int)
j, t, imp = best_split(X, y)
print(f"split on feature {j} at {t:.3f}: impurity {gini(y):.3f} -> {imp:.3f}")
Open in playground ↗
Python · scikit-learn
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.inspection import permutation_importance

X, y = load_breast_cancer(return_X_y=True, as_frame=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, stratify=y, random_state=0)

full = DecisionTreeClassifier(random_state=0).fit(Xtr, ytr)
path = full.cost_complexity_pruning_path(Xtr, ytr)   # candidate alphas
scores = [(a, cross_val_score(DecisionTreeClassifier(ccp_alpha=a, random_state=0),
                              Xtr, ytr, cv=5).mean()) for a in path.ccp_alphas[:-1]]
best_alpha = max(scores, key=lambda s: s[1])[0]
pruned = DecisionTreeClassifier(ccp_alpha=best_alpha, random_state=0).fit(Xtr, ytr)

print("leaves: full", full.get_n_leaves(), "-> pruned", pruned.get_n_leaves())
print("test acc: full", round(full.score(Xte, yte), 3), " pruned", round(pruned.score(Xte, yte), 3))
print(export_text(pruned, feature_names=list(X.columns), max_depth=2))

imp = permutation_importance(pruned, Xte, yte, n_repeats=10, random_state=0)
top = imp.importances_mean.argsort()[::-1][:5]
print([(c, round(float(v), 3)) for c, v in zip(X.columns[top], imp.importances_mean[top])])
Open in playground ↗
Check yourself

Quiz

1. A node containing only one class has Gini impurity…

2. Do decision trees need feature scaling?

3. A main weakness of a single decision tree is…

4. A node with 5 positives and 5 negatives has entropy…

5. Mean-decrease-in-impurity importance is biased toward…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready