Content
Summary
Decision trees split data by asking questions that make the resulting groups as pure as possible. Entropy measures the impurity of a group, and information gain tells us how much a split reduces it. The tree greedily picks the split with the highest gain at each node.
Intuition
Imagine playing twenty questions. A good question cuts your uncertainty sharply, while a poor one leaves you almost as confused as before. Entropy quantifies that uncertainty: a group that is half sick and half healthy is maximally uncertain, while a group that is all healthy has zero uncertainty. A split is good if the child groups, weighted by size, are much less uncertain than the parent. The algorithm tries candidate questions, computes the weighted entropy of the children, and keeps the one with the biggest drop.
Key equations
Entropy of set S, where p_k is the fraction of samples in class k (0 log 0 is taken as 0).
Weighted average entropy of the child nodes S_j after a split.
Information gain: the reduction in entropy achieved by the split.
Derivation
- Start with a node containing samples from several classes; let p_k be the proportion of class k.
- Surprise of seeing class k is -log2 p_k bits; rare outcomes are more surprising.
- Average the surprise over the class distribution to get H(S) = -sum p_k log2 p_k.
- For two classes, H is 0 when p=0 or 1 and reaches its maximum of 1 bit at p=0.5.
- A split sends fractions |S_j|/|S| of the data to children; weight each child's entropy by its fraction.
- Information gain is parent entropy minus weighted child entropy; it is never negative.
- Greedy rule: evaluate all candidate features and thresholds, choose the largest gain, then recurse on each child until nodes are pure or a stopping rule applies.
Worked example
A node has 10 patients: 6 diseased, 4 healthy. A test splits them into Left (5 diseased, 1 healthy) and Right (1 diseased, 3 healthy). Compute the information gain.
- Parent: p=0.6 and 0.4. H = -(0.6 log2 0.6 + 0.4 log2 0.4) = 0.6(0.737) + 0.4(1.322) = 0.971 bits.
- Left (6 samples): p=5/6 and 1/6. H = (5/6)(0.263) + (1/6)(2.585) = 0.219 + 0.431 = 0.650 bits.
- Right (4 samples): p=1/4 and 3/4. H = 0.25(2) + 0.75(0.415) = 0.5 + 0.311 = 0.811 bits.
- Weighted: (6/10)(0.650) + (4/10)(0.811) = 0.390 + 0.325 = 0.715 bits.
- IG = 0.971 - 0.715 = 0.256 bits.
Answer Information gain is about 0.26 bits.
Common mistakes
- Forgetting to weight child entropies by their sample fractions, which overrates tiny pure children.
- Using natural log in one place and log base 2 in another, so values are not comparable.
- Thinking a high-entropy node is one with many samples; entropy depends on class mix, not size.
- Assuming greedy splitting finds the globally optimal tree.
- Growing the tree until every leaf is pure, which overfits; information gain also favors features with many distinct values.