Choosing a Decision Tree Split with Entropy

A decision tree asks yes/no questions that sort examples into purer groups. Entropy measures how mixed a group's labels are (the expected surprise of a label), and the best question is the one that removes the most entropy: the biggest information gain.

How it works

Entropy as expected surprise, and information gain

In one sentence

The entropy of a set with a fraction $p$ of positive examples is $H = -p\log_2 p - (1-p)\log_2(1-p)$ , the expected value of $-\log_2$ of a label's probability. The information gain of splitting it into subsets of sizes $n_L$ and $n_R$ is $H_{\text{parent}} - \frac{n_L}{n}H_L - \frac{n_R}{n}H_R$ .

General formula

{\htmlData{sym=0}{H}} = -{\htmlData{sym=1}{p}}\log_2 {\htmlData{sym=1}{p}} - (1-{\htmlData{sym=1}{p}})\log_2(1-{\htmlData{sym=1}{p}}), \qquad \text{Gain} = {\htmlData{sym=0}{H}}_{\text{parent}} - \frac{{\htmlData{sym=2}{n_L}}}{\htmlData{sym=4}{{n}}}{\htmlData{sym=5}{H_L}} - \frac{{\htmlData{sym=3}{n_R}}}{\htmlData{sym=4}{{n}}}{\htmlData{sym=6}{H_R}}

Entropy is how surprised you expect to be by the next label. A good question leaves groups where the answer is predictable.

What the symbols mean

$H$
Entropy
How mixed a group's labels are, in bits: 0 when pure, 1 for a 50/50 mix.
$p$
Share of positives
The fraction of the group's days when people played.
$n_L$
Left count
Examples sent left by the split (temperature below c).
$n_R$
Right count
Examples sent right (temperature at or above c).
$n$
Total examples
All 16 days.
$H_L$
Left entropy
How mixed the left group is.
$H_R$
Right entropy
How mixed the right group is.

Entropy $H = -p\log_2 p - (1-p)\log_2(1-p)$ measures how mixed a group is: 0 bits if every example has the same label, 1 bit for a 50/50 mix. It's the expected value of the surprise $-\log_2 P(\text{label})$ .
A split "temperature < c" sends $n_L$ examples left and $n_R$ right. Weight each side's entropy by its share of the examples.
Information gain is the parent's entropy minus that weighted average: how much uncertainty the question removes. The tree picks the split with the largest gain.
Here people play at moderate temperatures, so two splits score well: the tree takes the best one first, then splits again inside each branch.

Learn the math

Expected Value and Standard DeviationStats · Lesson 14, Discrete Random Variables