A tree grows one question at a time, and at every step it faces the same choice: which question should it ask next? Ask a useless question and the data comes out no more sorted than it went in; ask a sharp one and the classes fall neatly into separate piles. To choose well, the tree needs a way to measure how mixed up a group of labels is, both before a split and after. That measure is entropy, borrowed wholesale from information theory, and the amount of mixing a split removes is called information gain. Together they answer the single question every tree must ask, over and over, at every node: does this split actually help? This lesson builds both from scratch, because the whole logic of tree-growing is hiding in these two small functions.
Entropy: how mixed is this node?
Entropy is one number that summarises the impurity of a set of labels. The formula looks terse but reads simply: for each class, take the fraction p of labels that belong to it, multiply by log2(p), sum those products across every class, and negate. In symbols, H = -sum(p * log2(p)). A node whose labels are all one class is perfectly pure, so its entropy is 0 — there is nothing left to sort out. A node split exactly evenly between two classes has entropy 1 bit, the most uncertain a yes/no question can be. Spread evenly across four classes and the entropy rises to 2 bits. Entropy is measured in bits because of the log2, and a bit is precisely the currency of a yes/no answer.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
print('pure ', round(entropy([10, 0]), 3))
print('lopsided ', round(entropy([3, 1]), 3))
print('balanced ', round(entropy([2, 2]), 3))
print('four-way ', round(entropy([1, 1, 1, 1]), 3))
flowchart LR A["all one class<br/>entropy = 0"] --> B["lopsided mix<br/>0 to 1"] B --> C["balanced two classes<br/>entropy = 1"] C --> D["more equal classes<br/>entropy above 1"] style A fill:#166534,color:#fff style C fill:#b45309,color:#fff
Reading the extremes
Run that code and two landmarks jump out. The pure node scores 0, because its single class has p = 1 and log2(1) is exactly zero, so the one term in the sum vanishes. The even two-class node scores 1, because each class is p = 0.5 and 0.5 * log2(0.5) is -0.5, and two of them sum to -1 before the negation flips it positive. Everything else lands between. The lopsided [3, 1] node is mostly one class, so it is fairly sure of itself and sits near 0.81 — impure, but not wildly so. Bigger, more even mixes produce higher entropy, which is exactly what you want: a number that grows as the node becomes harder to call.
Information gain: did the split help?
Entropy measures one node; information gain measures a change between nodes. Take a parent node, split its labels into a left group and a right group, and ask how much entropy disappeared. The parent's entropy minus the weighted average of the children's entropy is the information gain of that split: IG = H(parent) - (n_left/n) * H(left) - (n_right/n) * H(right). The weights matter — a child holding most of the data contributes most to the average. A perfect split sends each class entirely to one side, leaving two pure children, so the child entropy is zero and the gain equals the parent's full entropy. A useless split produces children just as mixed as the parent, so the gain is roughly zero. The tree, at every node, picks the split with the largest gain.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
def information_gain(parent, groups):
n = sum(parent)
before = entropy(parent)
after = 0.0
for g in groups:
after += (sum(g) / n) * entropy(g)
return before - after
print('mixed split ', round(information_gain([4, 4], [[3, 1], [1, 3]]), 3))
print('perfect split', round(information_gain([4, 4], [[4, 0], [0, 4]]), 3))
flowchart TD P["parent entropy"] --> MINUS["subtract"] CL["left child entropy"] --> MINUS CR["right child entropy"] --> MINUS MINUS --> IG["information gain"] style IG fill:#10b981,color:#fff
Why the weights are there
The children are rarely the same size, so you cannot just average their entropies directly. If a split sends nine examples left and one right, the left child's purity should dominate the after-picture, because it holds almost all the data. Multiplying each child's entropy by its share of the total — n_left / n and n_right / n — does exactly that: bigger children count for more. Skip the weights and a split that shunts a single noisy example into its own pure leaf would look fantastic, when really it sorted one example and left the other nine in a muddle. The weights keep the gain honest, rewarding splits that clean up most of the data rather than a convenient corner of it.
flowchart TD D["labels at this node"] --> T["try every feature and threshold"] T --> G["score each split by gain"] G --> B["keep the split with the highest gain"] style B fill:#10b981,color:#fff
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
def information_gain(parent, groups):
n = sum(parent)
before = entropy(parent)
after = 0.0
for g in groups:
after += (sum(g) / n) * entropy(g)
return before - after
def counts_of(labels):
c = {}
for x in labels:
c[x] = c.get(x, 0) + 1
return list(c.values())
values = [1, 2, 3, 6, 7, 8]
labels = ['a', 'a', 'a', 'b', 'b', 'b']
parent = counts_of(labels)
for t in [1.5, 2.5, 4.5, 6.5, 7.5]:
left = [labels[i] for i in range(len(values)) if values[i] <= t]
right = [labels[i] for i in range(len(values)) if values[i] > t]
gain = information_gain(parent, [counts_of(left), counts_of(right)])
print('threshold', t, '-> gain', round(gain, 3))
What does this print? Entropy of three yes-ish and one no, rounded to three decimals.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
print(round(entropy([3, 1]), 3))
Three quarters are one class, one quarter the other: p = 0.75 and 0.25.
0.75 * log2(0.75) is about -0.311, and 0.25 * log2(0.25) is -0.5; negate their sum.
Write entropy(counts) where counts is a list of integer class counts (for example [3, 1] means three of class A and one of class B). Return -sum(p * log2(p)) over the non-zero classes, using math.log2.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
# skip a zero count, then add p * log2(p)
pass
return h
Compute p = c / total for each non-zero count.
Subtract p * math.log2(p) from h. Skip counts of zero, or log2(0) crashes.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
This entropy works on mixed nodes but CRASHES on a pure one, because math.log2(0) raises ValueError when a class count is zero. By convention a zero count contributes nothing, so guard it: skip any count of zero before taking the log.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
p = c / total
h -= p * math.log2(p)
return h
A pure node has one non-zero count and the rest zero.
Add
if c == 0: continueat the top of the loop so the log is never taken of zero.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
Write information_gain(parent, groups) where parent is a list of class counts and groups is a list of child count-lists (for example [[3, 1], [1, 3]] for a left and right child). Return the parent entropy minus the size-weighted sum of the child entropies. You must include your guarded entropy from above, because some children are pure.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
def information_gain(parent, groups):
n = sum(parent)
before = entropy(parent)
after = 0.0
# add (sum(g) / n) * entropy(g) for each child group g
pass
return before - after
Weight each child by its share of the total: sum(g) / n.
A perfect split has pure children, so the after-term is 0 and the gain equals the parent entropy.
import math
def entropy(counts):
total = sum(counts)
h = 0.0
for c in counts:
if c == 0:
continue
p = c / total
h -= p * math.log2(p)
return h
def information_gain(parent, groups):
n = sum(parent)
before = entropy(parent)
after = 0.0
for g in groups:
after += (sum(g) / n) * entropy(g)
return before - after
A balanced parent node [4, 4] is split perfectly, so every yes goes left and every no goes right. What is the information gain of this split?
A perfect split leaves two pure children, each with entropy 0, so the weighted child entropy is 0. The gain is then the full parent entropy, 1 bit. Gain can never exceed the parent entropy — a split cannot remove more uncertainty than existed.
Recap
- Entropy
H = -sum(p * log2(p))measures how mixed a node is, in bits: pure is0, an even two-class split is1, and bigger equal mixes go higher. - A pure node has a zero class count, and
log2(0)crashes — so every entropy implementation mustcontinuepast zero counts, treating them as contributing nothing. - Information gain is the entropy a split removes: parent entropy minus the size-weighted child entropy. Weighting by
n_child / nkeeps big children dominant. - A perfect split drives child entropy to zero (gain = parent entropy); a useless split changes nothing (gain ≈ 0).
- At every node, the tree tries each candidate split and keeps the one with the highest gain — that single rule is what grows the entire structure.
You now have the split criterion. The next lesson wires it into a recursive loop that grows a full tree, caps its depth, and classifies examples it has never seen.