Module 5: Decision trees · Lesson 5.3 · about 25 min
Information gain: choosing the best split
A tree tries every column and every cut, and keeps the one that lowers impurity the most. Slide a cut along twelve customers, watch the gain change, and work a split out by hand.
Module 5 · about 25 minutes · read first: 5.2. You’ll be able to compute the gain of a split, find the best threshold for a column by hand, and explain why trees prefer some columns.
1. Why this matters
This is the step that builds every tree, and so every random forest and boosting model: thousands of times per model, the algorithm searches for the split with the largest gain. Knowing it explains why trees love columns with many different values, why they are fast, and where feature importance (Lesson 6.4) comes from.
2. The gain of a split
A split sends the rows of a parent box into a left child ( rows) and a right child ( rows). The gain is how much impurity it removes:
Here is Gini impurity or entropy (Lesson 5.2). With entropy this is called information gain; with Gini, often Gini gain or “decrease in impurity”. The weights and are each child’s share of the rows. They stop a tiny child from winning: splitting off a single row makes that row “pure”, but it barely changes the big mixed group, so the weighted average hardly drops.
- I(parent)
- How mixed the group is before the question.
- nL/n, nR/n
- Each side's share of the rows, used as weights.
- gain
- How much tidier the groups are, on average, after the question. Never negative.
- Physical meaning
- Sorting a pile of mixed laundry with one question ("is it white?"). A good question leaves two piles that are each nearly one kind. The gain is how much sorting that single question did.
3. Searching for the best split
For each column:
- Sort the rows by that column.
- Try a threshold halfway between each pair of neighbouring different values.
- Work out the gain of each.
Keep the best (column, threshold) pair over all columns. Keeping running counts of each class as you move along the sorted list, every threshold costs only a few sums, so this is fast even for millions of rows.
Twelve customers, sorted by visits per month. Six stayed (S), six left (L). Gini of the whole group: 0.5.
Try a cut at 3.5 visits. Left: 3 customers, all L (Gini 0). Right: 9 customers, 6 S and 3 L (Gini 0.444).
Weigh and subtract. 3/12 × 0 + 9/12 × 0.444 = 0.333. Gain = 0.5 − 0.333 = 0.167.
Try a cut at 6.5 visits. Left: 1 S, 5 L (Gini 0.278). Right: 5 S, 1 L (Gini 0.278). Weighted 0.278, gain 0.222.
Keep the best. 6.5 wins. Two fairly clean halves beat one pure sliver and a messy rest. Then the tree repeats the search inside each half.
4. Stopping
Splitting stops in a box when:
- it is pure (no gain is possible), or
- no split has a gain above a small minimum, or
- a limit is hit: maximum depth, or the fewest rows allowed in a leaf (Lesson 5.5).
“A column with a big information gain is a real, useful signal.” It may be luck. A column with many different values, such as a customer ID or a timestamp, offers hundreds of possible cuts, and by chance one of them often looks good on the training data. Drop ID-like columns before training, and check importance on held-out data (Lesson 6.4).
Maths and principle
Principle: greedy search: at each box, take the split with the largest weighted drop in impurity.
Information gain with entropy is the mutual information between the question’s answer and the class: how many bits of uncertainty about the class the answer removes,
Analogy: a sorting hat that tries every possible question once and keeps the one after which the two piles are tidiest.
Try it: a parent of 8 (4 and 4, Gini 0.5) splits into 4 (3 and 1) and 4 (1 and 3). Gain? (Each child: , Gini 0.375. Weighted: 0.375. Gain = 0.5 − 0.375 = 0.125.)
5. Worked example
Made-up numbers, the same as the simulation. Twelve customers, sorted by visits per month (1 to 12), and whether they stayed (S) or left (L):
| visits | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| L | L | L | S | L | L | S | S | L | S | S | S |
Before splitting: 6 S, 6 L, Gini 0.5.
- Cut at 3.5: left 3 (all L): Gini 0. Right 9 (6 S, 3 L): Gini = 1 − (6/9)² − (3/9)² = 1 − 0.444 − 0.111 = 0.444. Weighted: 3/12 × 0 + 9/12 × 0.444 = 0.333. Gain = 0.5 − 0.333 = 0.167.
- Cut at 6.5: left 6 (1 S, 5 L): Gini = 1 − (1/6)² − (5/6)² = 0.278. Right 6 (5 S, 1 L): also 0.278. Weighted: 0.278. Gain = 0.222.
The cut at 6.5 wins, though neither child is pure.
6. Practice
- In the simulation, find a cut whose gain is 0. Why is it zero?
- Why is the gain of a split never negative?
- A column takes only the values 0 and 1. How many thresholds does the tree try?
Answers
- The cuts at 0.5 and 12.5 put every customer on one side: nothing changes, so nothing is gained.
- Impurity is a dome-shaped (concave) curve, so the weighted average of the children’s impurities can never be above the parent’s.
- One: 0.5.
- Gain = impurity before − weighted impurity after; with entropy it is called information gain.
- Weighting by child size stops a tiny pure group from winning.
- The tree tries the midpoints between neighbouring sorted values in every column and keeps the best.
- Columns with many distinct values (IDs, timestamps) can win by luck: drop them.
Try it on your own data: the small model trainer shows the question chosen at each node of a tree grown from your CSV.
New words: information gain, Gini gain, weighted impurity, threshold, greedy search, mutual information.
Check yourself
Sources
- Quinlan (1986), Induction of decision trees, Machine Learning 1, 81-106 https://doi.org/10.1007/BF00116251
- Hastie, Tibshirani and Friedman (2009), The Elements of Statistical Learning, 2nd edition, Springer, Section 9.2 (Tree-based methods)
- scikit-learn user guide: Decision trees, mathematical formulation https://scikit-learn.org/stable/modules/tree.html#mathematical-formulation
Your ticks stay in this browser. Save them as a file on the course home.
Updated 2026-11-22. Numbers in the examples are made up to show the idea unless a source is given. Simulations run in your browser; nothing you type is sent anywhere.