Decision Tree: Information Gain
At every node a decision tree searches for the feature and threshold that most reduces impurity. This page covers the two impurity measures, the information-gain formula, and a complete hand trace of a split search on a 10-point loan-approval dataset.
The dataset to split
10 applicants, feature = age, label = 1 (approved) / 0 (denied):
| Age | 22 | 25 | 28 | 30 | 33 | 36 | 40 | 45 | 50 | 60 |
|---|---|---|---|---|---|---|---|---|---|---|
| Label | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Root node: 5 approvals, 5 denials.
Measuring impurity with Gini
- Pure node (one class):
- Maximum impurity (50/50):
Root node:
Measuring impurity with entropy
- Pure node: bits
- Maximum impurity (50/50): bit
Root node:
Gini vs Entropy
Both measures are near-equivalent in practice. Gini avoids the logarithm (slightly faster); scikit-learn defaults to it. ID3/C4.5 use Entropy. When both are applied to the same split they give the same winner.
The information-gain formula
The second term is the weighted child impurity — a large impure child hurts more than a small one.
One worked split (Age ≤ 31.5) end to end
This threshold puts ages 22, 25, 28, 30 left and ages 33, 36, 40, 45, 50, 60 right.
- Left = : labels → 0 approved, 4 denied (pure)
- Right = : labels → 5 approved, 1 denied
Step 1: Left child Gini. Pure node ():
Step 2: Right child Gini. , :
Step 3: Weighted child impurity. Left has of rows, right has :
Step 4 — Gini gain:
Cross-check with Entropy. Left entropy = 0. Right entropy: , :
Both measures agree this is a large improvement.
Scanning every candidate threshold
The tree checks every midpoint between consecutive sorted ages. The best split is the one with the highest gain (equivalently the lowest weighted child impurity). In the table below, P = approvals (positive class) and N = denials (negative class) that fall on each side of the threshold. For example, "Age ≤ 23.5" puts only the age-22 applicant (a denial) on the left, so Left (P/N) = 0/1:
| Test (Age ≤ t) | Left (P/N) | Right (P/N) | Weighted Gini | Gini Gain |
|---|---|---|---|---|
| 23.5 | 0 / 1 | 5 / 4 | 0.4444 | 0.0556 |
| 26.5 | 0 / 2 | 5 / 3 | 0.3750 | 0.1250 |
| 29.0 | 0 / 3 | 5 / 2 | 0.2857 | 0.2143 |
| 31.5 | 0 / 4 | 5 / 1 | 0.1667 | 0.3333 ← best |
| 34.5 | 1 / 4 | 4 / 1 | 0.3200 | 0.1800 |
| 38.0 | 2 / 4 | 3 / 1 | 0.4167 | 0.0833 |
| 42.5 | 2 / 5 | 3 / 0 | 0.2857 | 0.2143 |
| 47.5 | 3 / 5 | 2 / 0 | 0.3750 | 0.1250 |
| 55.0 | 4 / 5 | 1 / 0 | 0.4444 | 0.0556 |
Winner: Age ≤ 31.5, Gini gain = 0.3333. The tree makes this the root split and recurses on each child.
The gain is largest here because the left child is perfectly pure (all denials), while the right child is nearly pure (5 approvals, 1 denial). The gain decreases when the threshold moves away from 31.5 because either the pure side starts picking up mixed labels (going lower) or the mix on the right worsens (going higher).
Watch the scan run
Every row of that table, computed one at a time, with the running leader tracked as the scan proceeds:
Decision tree — scoring every candidate split
Ten loan applicants sorted by age, 5 approved and 5 denied. A 50/50 node is the most impure a binary node can be: Gini = 1 − (0.5² + 0.5²) = 0.500. The tree's job at this node is to find the single age threshold that reduces that impurity the most.
What a decision tree actually does at a single node: sort the feature, try every midpoint between consecutive values, and score each one by how much it lowers weighted child impurity. All nine candidate thresholds on the 10-applicant loan dataset are scored here, with the running leader tracked as you step. The last step re-runs the whole scan with entropy instead of Gini and lands on the same winner.
What to notice as you step:
- The gain is not monotone in the threshold. It climbs to 31.5, drops at 34.5, rises again at 42.5. There is no shortcut — a greedy tree finds the peak by brute force at every node, which is why training cost scales with the number of distinct feature values.
- Weighting is what makes the criterion work. At Age ≤ 55 the right child is perfectly pure (Gini 0), but it holds one row out of ten, so it barely moves the weighted average. Purity in a tiny child is nearly worthless.
- The last step swaps Gini for entropy and re-scores all nine thresholds. The numbers change, the winner does not — the practical reason nobody agonizes over which impurity measure to use.
Implementing the split search in code
import numpy as np
def gini(labels):
_, counts = np.unique(labels, return_counts=True)
p = counts / counts.sum()
return 1 - np.sum(p**2)
def information_gain(y, left_mask):
right_mask = ~left_mask
n = len(y)
weighted = (left_mask.sum()/n * gini(y[left_mask])
+ right_mask.sum()/n * gini(y[right_mask]))
return gini(y) - weighted
def best_split(X_col, y):
thresholds = (np.sort(np.unique(X_col))[:-1] + np.sort(np.unique(X_col))[1:]) / 2
gains = [information_gain(y, X_col <= t) for t in thresholds]
best_idx = np.argmax(gains)
return thresholds[best_idx], gains[best_idx]
ages = np.array([22, 25, 28, 30, 33, 36, 40, 45, 50, 60], dtype=float)
labels = np.array([0, 0, 0, 0, 1, 1, 0, 1, 1, 1])
t, gain = best_split(ages, labels)
print(f"Best threshold: {t}, gain: {gain:.4f}") # 31.5, 0.3333
Related concepts
- Decision Trees: source lesson: pruning, feature importance, sklearn API
- Bagging & Random Forests: averaging many trees built with this exact split criterion
- Boosting: building trees sequentially to target residuals