Classification trees
Same boxes, but each leaf votes for a class. To grow the tree you need a measure of how mixed a leaf is: the error rate, the Gini index or the entropy. The past papers end their tree questions with exactly these calculations.
2024 Q2 and 2025 Q1 both asked for the entropy or Gini formula, a decision stump on a 3-to-5-point data set, a prediction with the Bayes classifier inside a leaf, and an entropy or purity calculation. All of that is here, with fresh-number drills.
Book: what to read for this stage
ISLP 8.1.2 Classification trees: read (error rate, Gini, entropy, eqs. 8.5 to 8.7, the Heart example). Read the RestECG<1 paragraph on p. 341 carefully: it is the best explanation of why Gini beats the error rate. Skim the page on splitting qualitative inputs (Thal:a, ChestPain:bc); it’s not on the slides.
1. Leaves that vote
In leaf \(R_m\), let \(\hat p_{mk}\) be the fraction of its training points in class \(k\). It estimates \(P(Y = k \mid X \in R_m)\). The leaf predicts the class with the biggest \(\hat p_{mk}\): the Bayes classifier rule (stage 4) with probabilities estimated by counting, much like KNN.
A leaf with 7 “yes” and 3 “no” predicts “yes”, with \(\hat P(\text{yes}) = 0.7\).
A leaf holds 9 points of class 0 and 3 of class 1. What is \(\hat P(Y = 1)\) in that leaf?
\(3/12 = 0.25\). The leaf predicts class 0.
2. Three impurity measures
A leaf is pure if all its points share one class. With class fractions \(\hat p_{mk}\) (\(\log\) = natural log, and \(0\log 0 = 0\)):
\[E = 1 - \max_k\hat p_{mk},\qquad G = \sum_k\hat p_{mk}(1 - \hat p_{mk}),\qquad H = -\sum_k\hat p_{mk}\log\hat p_{mk}.\]
(error rate, Gini index, entropy). For two classes with fractions \(p\) and \(1 - p\): \(G = 2p(1 - p)\) and \(H = -p\log p - (1 - p)\log(1 - p)\). In the exam’s notation with \(D = \{(X_n, Y_n)\}\): \(p_{yes} = \frac1N\sum_n\mathbb 1(Y_n = \text{yes})\).
All three are 0 for a pure leaf and largest at an even mix:
| \(p\) | error | Gini | entropy |
|---|---|---|---|
| 0 or 1 | 0 | 0 | 0 |
| 0.1 | 0.10 | 0.18 | 0.33 |
| 0.3 | 0.30 | 0.42 | 0.61 |
| 0.5 | 0.50 | 0.50 | 0.69 |
3. Scoring a split: information gain
A split of \(R_m\) into \(R_{low}\) and \(R_{high}\) is scored by how much it lowers the size-weighted impurity:
\[\Delta = G(R_m) - \frac{|R_{low}|\,G(R_{low}) + |R_{high}|\,G(R_{high})}{|R_m|}.\]
Pick the split with the largest gain (entropy works the same way). Why not just the error rate? It isn’t sensitive enough. A region with 8 A and 2 B split into (4 A, 2 B) and (4 A, 0 B): the error stays at 0.2 (no improvement), but Gini drops from 0.32 to 0.267, because the split isolated a pure group and left a smaller mixed one that a later split can clean up. A one-step-greedy algorithm needs a measure that rewards that progress. (The error rate is still fine for pruning.)
Worked example. A region of 10 points, 6 A and 4 B: Gini \(0.48\).
| split | left | right | Gini after | gain | error after |
|---|---|---|---|---|---|
| 1 | (4 A, 0 B) | (2 A, 4 B) | \(0.4(0) + 0.6(0.444) = 0.267\) | 0.213 | 0.2 |
| 2 | (3, 1) | (3, 3) | \(0.4(0.375) + 0.6(0.5) = 0.45\) | 0.030 | 0.4 |
| 3 | (5, 1) | (1, 3) | \(0.6(0.278) + 0.4(0.375) = 0.317\) | 0.163 | 0.2 |
Splits 1 and 3 tie on error rate; Gini prefers split 1, which makes a pure leaf.
4. Decision stumps: the exam calculations
A decision stump is a tree with one split. The papers give a tiny data set and ask you to split, predict and compute an impurity.
Worked example (2024 Q2d-e). \(D = \{(-1, \text{no}), (1, \text{no}), (4, \text{yes}), (10, \text{no}), (13, \text{no})\}\), threshold \(\xi = 2\).
- \(B_1 = \{X < 2\} = \{-1, 1\}\): both “no”. \(B_2 = \{X \ge 2\} = \{4, 10, 13\}\): one “yes”, two “no”.
- Predict at \(X = 5\): it’s in \(B_2\), where \(\hat p_{yes} = 1/3\), so the Bayes classifier says no.
- \(H(B_1) = 0\) (pure). \(H(B_2) = -\frac13\log\frac13 - \frac23\log\frac23\).
- The paper’s weighted entropy \(H^*(T_1) = |B_1|H(B_1) + |B_2|H(B_2) = 0 + 3\big(-\frac13\log\frac13 - \frac23\log\frac23\big) = \log 3 + 2\log\frac32 \approx 1.91\) (natural log).
Worked example (2025 Q1e). \(D = \{(1, \text{yes}), (\frac12, \text{yes}), (\frac13, \text{no})\}\). Which threshold gives purer regions?
- \(\xi_1\) between \(\frac13\) and \(\frac12\): left \(\{\frac13: \text{no}\}\), right \(\{\frac12, 1: \text{yes, yes}\}\). Both pure.
- \(\xi_2\) between \(\frac12\) and 1: left \(\{\frac13, \frac12\}\) is mixed.
- \(\xi_1\) wins. \(X = 0\) falls in the left region, so \(P(Y = \text{yes} \mid X = 0) = \mathbf 0\).
Data \(\{(2, \text{yes}), (3, \text{yes}), (0.5, \text{no}), (1, \text{no})\}\). Using the purest one-split stump, what is \(P(Y = \text{yes} \mid X = 0.2)\)?
Splitting between 1 and 2 gives left \(\{0.5, 1\}\) = no, no and right \(\{2, 3\}\) = yes, yes: both pure. \(X = 0.2\) is on the left, where \(\hat p_{yes} = 0\).
Stage test
(4 marks, exam format 2; 2025 Q1.) Write the entropy and the Gini index of a data set \(D = \{(X_n, Y_n)\}_{n=1}^N\) with \(Y_n \in \{\text{yes}, \text{no}\}\), defining every symbol, and say which value each takes for a pure set.
Let \(p_{yes} = \frac1N\sum_{n=1}^N\mathbb 1(Y_n = \text{yes})\) be the fraction of “yes” labels and \(p_{no} = 1 - p_{yes}\). The entropy is \(H(D) = -p_{yes}\log p_{yes} - p_{no}\log p_{no}\) (taking \(0\log 0 = 0\)), and the Gini index is \(G(D) = p_{yes}(1 - p_{yes}) + p_{no}(1 - p_{no}) = 2p_{yes}(1 - p_{yes})\). Both measure how mixed the labels are: both are 0 when the set is pure (all yes or all no) and both are largest when \(p_{yes} = 0.5\) (entropy \(\log 2\), Gini \(0.5\)).
Three classes with fractions \((0.5, 0.25, 0.25)\). Compute the Gini index.
\(0.5 \times 0.5 + 0.25 \times 0.75 + 0.25 \times 0.75 = 0.25 + 0.1875 + 0.1875 = 0.625\).
True or false: a split whose two halves predict the same class can never be chosen when the tree is grown with the Gini index.
Splitting (8 A, 2 B) into (4 A, 2 B) and (4 A, 0 B) leaves both halves predicting A, but the Gini index still drops (0.32 to 0.267), so it can be chosen. ISLP’s Heart tree has splits like this.