# How a decision tree chooses a split

By @omar · Published Nov 2, 2026 · From the roadmap [Machine Learning from First Principles](https://ornix.io/u/omar/machine-learning-first-principles)

A decision tree is twenty questions played greedily. At each node it asks the single yes/no question about one feature that makes the answers on each side as pure as possible, then repeats on each side. All the work is in the phrase "as pure as possible", so this note does one small example slowly enough that you can check every number by hand.

## Impurity

For a node with a fraction $p_k$ of class $k$, two measures are standard:

$$\text{Gini} = 1 - \sum_k p_k^2 \qquad\qquad \text{Entropy} = -\sum_k p_k \log_2 p_k$$

Both are zero for a pure node and largest when classes are evenly mixed. For two classes with positive rate $p$, Gini is $2p(1-p)$. A split is scored by the impurity of its children, weighted by their sizes:

$$\text{score}(s) = \frac{n_L}{n}\,G(L) + \frac{n_R}{n}\,G(R)$$

The tree chooses the split with the lowest score. The decrease from the parent, $G(\text{parent}) - \text{score}(s)$, is the gain.

## Ten rows, every split

One feature, age, and a label saying whether the person bought:

- **Age:** 22, 25, 31, 35, 40, 45, 52, 58, 63, 70
- **Bought:** 0, 0, 0, 1, 0, 1, 1, 1, 1, 1

Six of ten bought, so the parent has $p = 0.6$ and Gini $= 2 \cdot 0.6 \cdot 0.4 = 0.48$. Candidate thresholds sit midway between neighbouring ages. Three of them:

- **Age ≤ 28:** left has 2 rows, both 0 (Gini 0); right has 8 rows, 6 positive, so $p = 0.75$, Gini $= 0.375$. Score $= 0.2 \cdot 0 + 0.8 \cdot 0.375 = 0.30$.
- **Age ≤ 33:** left has 3 rows, all 0; right has 7 rows, 6 positive, Gini $= 2 \cdot \tfrac{6}{7}\cdot\tfrac{1}{7} \approx 0.245$. Score $= 0.7 \cdot 0.245 \approx 0.171$.
- **Age ≤ 42.5:** left has 5 rows, 1 positive, Gini $= 2 \cdot 0.2 \cdot 0.8 = 0.32$; right has 5 rows, all positive, Gini 0. Score $= 0.5 \cdot 0.32 + 0.5 \cdot 0 = 0.16$.

I scored all nine thresholds. The winner is 42.5 with 0.16, narrowly ahead of 33 at 0.171. Entropy picks the same threshold: information gain is 0.610 bits at 42.5 versus 0.557 at 33. (The parent entropy is $-0.6\log_2 0.6 - 0.4\log_2 0.4 = 0.971$ bits.) In practice Gini and entropy almost always agree.

```mermaid
%% ornix:id=mlk1d004
flowchart TD
    R["Root: 6 of 10 bought, Gini 0.48"] -->|"age <= 42.5"| L["Left: 1 of 5 bought, Gini 0.32"]
    R -->|"age > 42.5"| Q["Right: 5 of 5 bought, Gini 0 - leaf"]
    L -->|"age <= 33"| L1["22, 25, 31: all no - leaf"]
    L -->|"age > 33"| L2["35, 40: one yes - still mixed"]
```

## Why it overfits

The left child still has one buyer, the 35-year-old, hiding among the non-buyers. To make every leaf pure the tree must carve out 35 specifically: split at 33, then at 37.5, and so on. Those splits fit one point that may just be noise. This is the variance problem from last week in miniature: a fully grown tree can always reach zero training error, and its structure depends heavily on which samples it saw. The fixes are to stop early (`max_depth`, `min_samples_leaf`), prune afterwards, or average many trees, which is next week's other half.

## The algorithm

For each feature, sort the values once, sweep a threshold through them and keep running class counts, so scoring all thresholds costs $O(n)$ after the sort. Pick the best split over all features, then recurse until a stopping rule fires.

```python
import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = y.mean()
    return 2 * p * (1 - p)

def best_threshold(x, y):
    order = np.argsort(x)
    xs, ys = x[order], y[order]
    n = len(ys)
    left_pos = np.cumsum(ys)
    best = (None, np.inf)
    for i in range(n - 1):
        if xs[i] == xs[i + 1]:
            continue
        nl = i + 1
        pl = left_pos[i] / nl
        pr = (ys.sum() - left_pos[i]) / (n - nl)
        score = nl / n * 2 * pl * (1 - pl) + (n - nl) / n * 2 * pr * (1 - pr)
        if score < best[1]:
            best = ((xs[i] + xs[i + 1]) / 2, score)
    return best

age = np.array([22, 25, 31, 35, 40, 45, 52, 58, 63, 70])
bought = np.array([0, 0, 0, 1, 0, 1, 1, 1, 1, 1])
print(best_threshold(age, bought))  # (42.5, 0.16)
```

## Common mistakes

- **Using the impurity of the whole dataset as the score.** You must weight the children by their sizes, or a split that isolates one pure row looks perfect.
- **Thresholds at data values instead of midpoints.** It works, but midpoints generalize better to unseen values.
- **Treating high-cardinality categories like numbers.** A feature with a unique value per row, such as an ID, can split perfectly and mean nothing. Trees built on it are the textbook case of fooling yourself.
- **Reading impurity-based feature importance as truth.** It favours features with many distinct values. Prefer permutation importance on held-out data.
- **Assuming greedy equals optimal.** The best first split need not belong to the best tree. It is a heuristic that works well.

## Check yourself

- Recompute the score of the split at 55 by hand.
- Why is a node with $p = 0.5$ the worst case for Gini, and what is its Gini value?
- What happens to a tree's training error and validation error as `max_depth` grows from 1 to 20?
- Why can a split with zero gain still be worth making?

---

Roadmap: https://ornix.io/u/omar/machine-learning-first-principles (Markdown: https://ornix.io/u/omar/machine-learning-first-principles.md)

Canonical page: https://ornix.io/u/omar/machine-learning-first-principles/how-a-decision-tree-chooses-a-split
