Decision Tree: Information GainOpen in Colab

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):

Age22252830333640455060
Label0000110111

Root node: 5 approvals, 5 denials.

Measuring impurity with Gini

Gini(S)=1−∑k=1Kpk2\text{Gini}(S) = 1 - \sum_{k=1}^{K} p_k^2
  • Pure node (one class): Gini=0\text{Gini} = 0
  • Maximum impurity (50/50): Gini=0.5\text{Gini} = 0.5

Root node: p1=p0=0.5p_1 = p_0 = 0.5

Gini(root)=1−(0.52+0.52)=0.5\text{Gini}(\text{root}) = 1 - (0.5^2 + 0.5^2) = 0.5

Measuring impurity with entropy

Entropy(S)=−∑k=1Kpklog⁡2pk\text{Entropy}(S) = -\sum_{k=1}^{K} p_k\log_2 p_k
  • Pure node: Entropy=0\text{Entropy} = 0 bits
  • Maximum impurity (50/50): Entropy=1\text{Entropy} = 1 bit

Root node: log⁡20.5=−1\log_2 0.5 = -1

Entropy(root)=−(0.5(−1)+0.5(−1))=1.0\text{Entropy}(\text{root}) = -\bigl(0.5(-1) + 0.5(-1)\bigr) = 1.0

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

IG=I(parent)−(nLn I(left)+nRn I(right))\text{IG} = I(\text{parent}) - \left(\frac{n_L}{n}\,I(\text{left}) + \frac{n_R}{n}\,I(\text{right})\right)

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 (p0=1p_0 = 1):

Gini(left)=1−(12+02)=0\text{Gini}(\text{left}) = 1 - (1^2 + 0^2) = 0

Step 2: Right child Gini. p1=5/6≈0.8333p_1 = 5/6 \approx 0.8333, p0=1/6≈0.1667p_0 = 1/6 \approx 0.1667:

Gini(right)=1−(0.83332+0.16672)=1−(0.6944+0.0278)=0.2778\text{Gini}(\text{right}) = 1 - (0.8333^2 + 0.1667^2) = 1 - (0.6944 + 0.0278) = 0.2778

Step 3: Weighted child impurity. Left has 4/104/10 of rows, right has 6/106/10:

410(0)+610(0.2778)=0.1667\frac{4}{10}(0) + \frac{6}{10}(0.2778) = 0.1667

Step 4 — Gini gain:

IGGini=0.5−0.1667=0.3333\text{IG}_{\text{Gini}} = 0.5 - 0.1667 = \mathbf{0.3333}

Cross-check with Entropy. Left entropy = 0. Right entropy: log⁡2(5/6)=−0.2630\log_2(5/6) = -0.2630, log⁡2(1/6)=−2.5850\log_2(1/6) = -2.5850:

Entropy(right)=−(56(−0.2630)+16(−2.5850))=0.6500\text{Entropy}(\text{right}) = -\bigl(\tfrac{5}{6}(-0.2630) + \tfrac{1}{6}(-2.5850)\bigr) = 0.6500 IGEntropy=1.0−(410(0)+610(0.6500))=0.6100\text{IG}_{\text{Entropy}} = 1.0 - \bigl(\tfrac{4}{10}(0) + \tfrac{6}{10}(0.6500)\bigr) = 0.6100

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 GiniGini Gain
23.50 / 15 / 40.44440.0556
26.50 / 25 / 30.37500.1250
29.00 / 35 / 20.28570.2143
31.50 / 45 / 10.16670.3333 ← best
34.51 / 44 / 10.32000.1800
38.02 / 43 / 10.41670.0833
42.52 / 53 / 00.28570.2143
47.53 / 52 / 00.37500.1250
55.04 / 51 / 00.44440.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

1/12

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.

python
1def best_split(ages, labels):
2 best = (None, -1)
3 parent = gini(labels)
4 for t in midpoints(sorted(ages)):
5 left = [y for a, y in rows if a <= t]
6 right = [y for a, y in rows if a > t]
7 # a big impure child hurts more
8 child = (len(left) / n * gini(left)
9 + len(right) / n * gini(right))
10 gain = parent - child
11 if gain > best[1]:
12 best = (t, gain)
13 return best
14
15def gini(ys):
16 if not ys:
17 return 0.0
18 p = sum(ys) / len(ys)
19 return 1 - (p ** 2 + (1 - p) ** 2)
state
age → label (1 = approved)
220
250
280
300
331
361
400
451
501
601
root node
approved → 5denied → 5Gini → 0.500

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

Python
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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
Decision Tree: Information GainAdaBoost AlgorithmDecision TreesBagging & Random ForestsBoosting