To grow a classification tree we need a precise answer to one question: what makes a split good? The answer is purity — a good split produces child nodes whose samples are as close to a single class as possible. This chapter defines the two purity measures (Gini and entropy), shows how information gain chooses splits, and walks through building a tree by hand.

Impurity: how mixed is a node?

For a node with class proportions \(p_1,\dots,p_K\), the two standard impurity measures are \[\Gini = 1-\sum_{k=1}^K p_k^2,\qquad \Entropy = -\sum_{k=1}^K p_k\log_2 p_k.\] Both are \(0\) when the node is pure (one class) and maximal when classes are evenly mixed.

Impurity measures disorder. A node of all one class has nothing to disagree about (impurity \(0\)); a 50/50 node is maximally confused. Gini is the probability that two random draws from the node have different labels; entropy is the average number of bits to encode the label. They almost always pick the same splits — Gini is slightly faster (no logarithm) and is scikit-learn’s default; entropy comes from information theory and underlies ID3/C4.5.

Information gain: scoring a split

A split sends fractions of the parent’s samples to child nodes. Its information gain is the impurity removed — parent impurity minus the weighted average of child impurities: \[\Gain = I(\text{parent}) - \sum_{c\in\text{children}}\frac{n_c}{n}\,I(c),\] where \(I\) is Gini or entropy and \(n_c/n\) is the fraction of samples in child \(c\). The tree-growing algorithm tries every feature and every threshold and greedily picks the split with the largest gain.

A node has 40 positives and 10 negatives, so \(p=0.8\) and \(\Gini=1-(0.8^2+0.2^2)=0.32\). A candidate split yields children \(\{30^+,2^-\}\) and \(\{10^+,8^-\}\), with Gini \(1-((\tfrac{30}{32})^2+(\tfrac{2}{32})^2)=0.117\) and \(1-((\tfrac{10}{18})^2+(\tfrac{8}{18})^2)=0.494\). The weighted child impurity is \(\tfrac{32}{50}(0.117)+\tfrac{18}{50}(0.494)=0.253<0.32\), so the gain is \(0.067\) and the split is worth making.

Greedy recursive growth

The algorithm is simple and greedy: at each node, scan all features and split points, choose the highest-gain split, partition the data, and recurse on each child — stopping when a node is pure, too small, or a depth limit is hit. “Greedy” means it never looks ahead; it takes the locally best split, which is fast but not globally optimal (finding the optimal tree is NP-hard). In practice the greedy choice works remarkably well.

Probabilities, not just labels

A leaf can report class proportions, not just the majority label, giving predicted probabilities \(\hat p_k\). These power ROC/AUC analysis and threshold tuning — but, as the pitfall warns, raw tree probabilities are often poorly calibrated.

Three traps. (1) Greedy myopia: the best first split is not always part of the best tree; a feature that only helps after another split can be overlooked. (2) Bias toward many-valued features: information gain favors features with many distinct values (an ID column gives “perfect” but useless splits) — C4.5’s gain ratio and CART’s binary splits mitigate this. (3) Uncalibrated probabilities: a pure leaf claims probability \(1.0\) even from two samples; trust the predicted class more than the exact probability, and calibrate (Platt/isotonic) if you need reliable probabilities.

The impurity measures here are the same ones that score splits inside every random forest and gradient-boosting library — billions of Gini/entropy evaluations underpin tabular ML. Entropy and information gain are the bridge to information theory used throughout deep learning (cross-entropy loss, KL divergence). And the “predict class proportions in a region” idea reappears as the leaf values in gradient-boosted trees, where leaves hold not class votes but real-valued scores fit to gradients (Chapter [ch:boosting]).

import numpy as np
def gini(y):
    _, c = np.unique(y, return_counts=True); p = c/c.sum()
    return 1 - (p**2).sum()
def best_split(x, y):
    best = (None, -1)
    for t in np.unique(x):
        left, right = y[x <= t], y[x > t]
        if len(left)==0 or len(right)==0: continue
        g = (len(left)*gini(left)+len(right)*gini(right))/len(y)   # weighted child Gini
        gain = gini(y) - g
        if gain > best[1]: best = (t, gain)
    return best
x = np.array([1,2,3,4,5,6]); y = np.array([0,0,0,1,1,1])
print(best_split(x, y))     # threshold ~3 gives the perfect split (gain = 0.5)

Chapter summary

  • A split is good if it increases purity; measure impurity with Gini \(=1-\sum p_k^2\) or entropy \(=-\sum p_k\log_2 p_k\).

  • Information gain \(=\) parent impurity \(-\) weighted child impurity; the tree greedily picks the highest-gain split.

  • Growth is greedy and recursive — fast, locally optimal, not globally optimal (optimal trees are NP-hard).

  • Leaves can report class proportions for probabilities, but these are often uncalibrated.

  • Watch greedy myopia and bias toward many-valued features; these impurity measures drive all tree ensembles.