Classification trees
The same yes/no questions as a regression tree, but each leaf votes for its most common category, and the splits are chosen to make the leaves as "pure" (one category) as possible.
Question type: classification.
Week: 4.
Book: ISLP 8.1.2.
Techniques on this page: majority vote and leaf probabilities, the error rate, the Gini index and entropy, information gain.
The problem it solves
A regression tree predicts the average of a leaf and picks splits by RSS. Neither makes sense for categories: you can’t average “yes” and “no”, and the codes 0, 1, 2 are just labels.
So two pieces change. A leaf predicts the most common class, and can give a probability for every class by counting. And a split is good if it makes the leaves purer, so we need a number that measures how mixed a leaf is.
Words you’ll hear
| Word | Plain meaning |
|---|---|
| \(\hat p_{mk}\) | fraction of the training points in leaf \(m\) that are class \(k\) |
| pure leaf | all its points are one class |
| impurity | how mixed a leaf is (0 = pure) |
| error rate | fraction of the leaf not in its majority class |
| Gini index | \(\sum_k\hat p_{mk}(1 - \hat p_{mk})\), a smoother impurity score |
| entropy | \(-\sum_k\hat p_{mk}\log\hat p_{mk}\), another one, similar to Gini |
| information gain | impurity before a split minus the (size-weighted) impurity after |
Technique 1: majority vote and leaf probabilities
Problem it solves: turning a leaf into a prediction.
Count the classes among the leaf’s training points. A leaf with 7 “Yes” and 3 “No” predicts Yes, with \(\hat P(\text{Yes}) = 0.7\). That’s the Bayes classifier rule with the probabilities estimated by counting inside the box, much like KNN counts among neighbours.
Technique 2: measuring impurity
Problem it solves: a number for “how mixed is this leaf?”.
| two-class fraction \(p\) | error \(1 - \max(p, 1-p)\) | Gini \(2p(1-p)\) | entropy |
|---|---|---|---|
| 0 or 1 (pure) | 0 | 0 | 0 |
| 0.1 | 0.10 | 0.18 | 0.33 |
| 0.3 | 0.30 | 0.42 | 0.61 |
| 0.5 (evenly mixed) | 0.50 | 0.50 | 0.69 |
All three are 0 for a pure leaf and biggest at 50/50. Gini and entropy are curved, which turns out to matter (Technique 4).
Technique 3: information gain
Problem it solves: scoring a candidate split.
\[\text{gain} = G(\text{parent}) - \frac{n_{\text{left}}\,G(\text{left}) + n_{\text{right}}\,G(\text{right})}{n_{\text{parent}}}\]
Weight each half by its share of the points. Pick the split with the biggest gain. (Entropy can replace \(G\).)
Worked example. A box with 6 A and 4 B: Gini \(0.6 \times 0.4 + 0.4 \times 0.6 = 0.48\).
| split | left | right | Gini after | gain | error after |
|---|---|---|---|---|---|
| 1 | (4 A, 0 B) | (2 A, 4 B) | \(0.6 \times 0.444 = 0.267\) | 0.213 | 0.2 |
| 2 | (3 A, 1 B) | (3 A, 3 B) | \(0.4 \times 0.375 + 0.6 \times 0.5 = 0.45\) | 0.030 | 0.4 |
| 3 | (5 A, 1 B) | (1 A, 3 B) | \(0.6 \times 0.278 + 0.4 \times 0.375 = 0.317\) | 0.163 | 0.2 |
Split 1 wins. Splits 1 and 3 have the same error rate afterwards, so the error rate couldn’t choose; Gini rewards split 1’s perfectly pure leaf.
Technique 4: why grow with Gini, not the error rate
Problem it solves: the error rate often can’t see progress.
Box (8 A, 2 B), error 0.2. Split into (4 A, 2 B) and (4 A, 0 B). Both halves still predict A, so the error rate is still \(0.6 \times \frac13 = 0.2\): no gain. But Gini drops from 0.32 to \(0.6 \times 0.444 = 0.267\): a pure group has been carved out, and the remaining mixed group is smaller and easier to split next time. A greedy algorithm needs a score that notices this. That’s ISLP’s RestECG example (p341). The error rate is still fine for judging the final tree.
Classification tree vs other classifiers
| logistic regression / LDA | KNN | classification tree | |
|---|---|---|---|
| boundary | straight line | wiggly | staircase of axis-parallel steps |
| readable | coefficients | no | a flow chart |
| scaling needed | for gradient descent | yes | no |
| categories as inputs | dummy variables | awkward | split on them directly (ISLP p340) |
What to read in the book
| Section | Read? | Why |
|---|---|---|
| 8.1.2 Classification trees (p337–341) | Read | Core: error, Gini, entropy (8.5–8.7), the Heart example |
| — splits on qualitative predictors (Thal:a, ChestPain:bc) | Skim | Not on the slides |
| — the RestECG<1 paragraph (p341) | Read | The clearest reason to prefer Gini |
Practice prompt
I'm studying CS5100 Data Analysis (textbook ISLP, section 8.1.2). I want practice questions on CLASSIFICATION TREES, done by hand:
- a leaf's majority-vote prediction and its class probabilities from counts
- the error rate, Gini index and entropy of a leaf (two and three classes, natural logs)
- information gain of a candidate split, weighting each half by its size
- comparing two or three candidate splits and choosing the best
- examples where the error rate shows no improvement but Gini does, and why that matters for greedy growing
- how a classification tree's decision boundary looks compared with logistic regression and KNN
Please:
1. Use plain, everyday language and explain any technical term in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.