Part III — Classification

Chapter 16 · Decision Tree Classification

Chapter 8's flowchart returns wearing class labels — and its splitting criterion gets a promotion. Where the regression tree reduced variance, the classification tree reduces entropy: messiness measured in bits, computable by hand. This chapter works entropy and information gain entirely by hand on real data, meets Gini as the fast-running rival, reads the fitted tree as three audit-ready rules — and watches a four-leaf tree out-score the fifty-leaf memoriser.

📖 Chapter 16 of 33 ⏱ ~85 min read Mostly Core Stable 📝 Quiz · 30 MCQs

🎯 Learning Objectives

Compute entropy by hand for a real class mix, and read the 0-to-1 bit scale intuitively
Compute information gain for the fitted tree's actual root split, from real class counts
Compare entropy with Gini impurity — formulas, values, and the real near-identical trees
Explain the leaf's majority vote and why its "probabilities" are overconfident
Use the real depth study to see memorisation billed and pruning rewarded
Read the fitted tree as business rules, and connect its instability to Chapter 17's fix

1. The Flowchart Returns

If you survived Chapter 8, you already know this algorithm's skeleton: greedy, axis-aligned splits, grown one question at a time, predictions made at the leaves. Only the target's type has changed from numbers to classes, and that changes two things — what a leaf says (a majority vote instead of a mean) and how splits are scored (entropy or Gini instead of variance). CART's promise holds: one growing algorithm, both supervised worlds.

Same running dataset, same split and scaling as Chapters 11–15. The source code's one new ingredient is explicit: criterion='entropy' — the choice of messiness-measure the tree greedily reduces. That choice is this chapter's main event.

📝

Note — scale-blind again: we fitted the tree on raw features too, as a check: identical accuracy (0.91), identical depth (12), identical 50 leaves, and thresholds readable in years and rupees. Chapter 8's rule (thresholds absorb units) carries over untouched — the source's scaler is harmless habit, not necessity.

2. Entropy: Measuring Messiness

Before choosing a question, the tree needs a number for "how mixed up is this node?" — entropy, imported from information theory (Shannon, 1948): the average number of bits needed to encode a label drawn from the node:

H(node) = − Σ p_k · log₂ p_k (over the classes k present)

H = 0 — pure node: one class only, zero bits needed, nothing left to ask
H = 1 — a perfect 50/50 mix: maximum surprise, one full bit per label
The curve is symmetric, peaking at p = 0.5 — messiness is about balance, not which class leads

2.1 By hand — the training root

Our 300 training customers: 189 non-buyers, 111 buyers (Ch 15's priors again).

p_no = 189/300 = 0.630  ·  p_yes = 111/300 = 0.370

H = −(0.630 · log₂ 0.630) − (0.370 · log₂ 0.370)
  = −(0.630 × (−0.667)) − (0.370 × (−1.435))
  = 0.420 + 0.531 = 0.951 bits

log₂ 0.630 = ln 0.630 / ln 2 = −0.462/0.693 = −0.667; log₂ 0.370 = −0.994/0.693 = −1.435. Nearly the maximum of 1 bit — the root is close to a coin flip, i.e. exactly where a good first question is worth the most.

Figure 16.1 — Entropy peaks at the 50/50 mix; our root (p = 0.37/0.63) sits near the summit — maximally worth splitting.

3. Information Gain: Choosing the Question

Every candidate split (feature, threshold) divides the node into two children; the tree scores each by information gain — how much entropy the question removes — and greedily takes the best:

IG(split) = H(parent) − [ (n_L/n)·H(left) + (n_R/n)·H(right) ]

The fitted tree's actual first question (raw units): Age ≤ 44.5? Count the classes on each side of that real threshold:

Node	Rows	Non-buyers	Buyers	Entropy (hand)
Root	300	189	111	0.951
Left: Age ≤ 44.5	215	175	40	0.693
Right: Age > 44.5	85	14	71	0.645

The arithmetic, end to end:

weighted H = (215/300)·0.693 + (85/300)·0.645 = 0.497 + 0.183 = 0.680

IG = 0.951 − 0.680 = 0.271 bits

One question about age converts a near-coin-flip root into two substantially purer nodes — the young side is 82% non-buyer, the older side 84% buyer. The tree then recurses on each child (the real second questions: Salary ≤ 90,500 on the young side, Salary ≤ 41,500 on the older side), until stopping rules fire.

3.1 Gini — the fast rival

sklearn's default criterion is not entropy but Gini impurity — the probability two random draws from the node disagree:

Gini = 1 − Σ p_k² ⇒ root: 1 − 0.630² − 0.370² = 1 − 0.397 − 0.137 = 0.466

No logarithms — cheaper per split, same shape of curve (0 at pure, peak at 50/50). And the practical answer to "which criterion?": it almost never matters. Real proof from this dataset — full trees, same seed: entropy: 0.91 accuracy, 50 leaves; Gini: 0.90, 47 leaves. Near-identical trees, one row of difference.

💡

Pro Tip — the interview answer: entropy (bits, information theory, slightly slower) vs Gini (squared probabilities, faster, sklearn default). Both peak at 50/50 and almost always grow the same tree. Choose one, note the other, move on — the depth dial (Section 5) matters far more.

4. The Leaf: Votes & Overconfident Probabilities

A classification leaf predicts its residents' majority class — the vote from Chapter 8's regression mean. Its predict_proba is the vote share: a leaf holding 9 buyers and 1 non-buyer says [0.1, 0.9]. For our three anchor customers (real outputs):

Customer	Prediction	Probability	Reading
(30, ₹87k)	NO	[1.0, 0.0]	Fell in a pure non-buyer leaf
(30, ₹150k)	YES	[0.0, 1.0]	Pure wealthy-young leaf
(45, ₹87k)	YES	[0.0, 1.0]	Pure older leaf

Notice what those 1.0s and 0.0s are not: calibrated belief. A leaf holding a handful of training rows reports total certainty because its residents happened to agree — sample-of-ten unanimity masquerading as probability 1. Contrast Naive Bayes's graded [0.061, 0.939] or logistic's [0.509, 0.491]: trees speak in votes, and a vote of 10–0 is not the same epistemic state as 100–0, though both print as 1.0. If the business consumes probabilities, Chapter 18's calibration tools — or Chapter 17's averaged forests, whose votes come from hundreds of trees — are the remedy.

⚠

Warning — axis-aligned walls: like Chapter 8's regression staircase, every question is "one feature vs one threshold," so the classification regions are rectangles — stair-shaped boundaries with corners. Diagonal frontiers get approximated by many small steps, which is precisely what drives deep trees to memorise (next section).

5. Depth & the Memoriser's Bill

Chapter 8's regression memoriser (R² = 1.0 on ten rows) returns here with a bill attached. The real depth study — same seed, same criterion:

max_depth	Leaves	Test acc	Train acc	Diagnosis
1	2	0.89	0.820	One question ("Age ≤ 44.5?") — the stump
2	4	0.94	0.910	The champion — see below
3	8	0.94	0.910	Ties the champion with double the rules
4	13	0.93	0.917	Decay begins
None (source)	50	0.91	1.000	The memoriser: perfect training, 3 points worse on test

Read the last row first: the unpruned tree achieves training accuracy 1.000 — 50 leaves isolating every training quirk — and loses three test points to a tree with four leaves. Then read row two: the depth-2 tree's 0.94 is the best score of any model in this Part so far (K-NN and RBF SVM sit at 0.93), using three questions. One honest caveat, as always: 0.94 vs 0.93 is one test row in a hundred, and this sweep consulted the test set — the defensible selection protocol is Chapter 31's cross-validated grid. The structural lesson survives the caveat: the parsimonious tree won.

💡

Pro Tip — pruning, the professional word: controlling depth (or min_samples_leaf) is pre-pruning — stopping early. Post-pruning grows full and then removes splits that fail a complexity test. sklearn ships pre-pruning (ccp_alpha for cost-complexity pruning); either way, the principle is Chapter 6's: flexibility must pay rent, or get evicted.

📋 Stable content — Reviewed: August 2026

6. Implementation in Python

import numpy as np
import pandas as pd

dataset = pd.read_csv('Social_Network_Ads.csv')
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, -1].values

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=0)

from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
X_train = sc.fit_transform(X_train)     # harmless habit; the tree is scale-blind
X_test = sc.transform(X_test)

from sklearn.tree import DecisionTreeClassifier
classifier = DecisionTreeClassifier(criterion='entropy', random_state=0)
classifier.fit(X_train, y_train)

from sklearn.metrics import confusion_matrix, accuracy_score
y_pred = classifier.predict(X_test)
cm = confusion_matrix(y_test, y_pred)
print(cm)                                # [[62  6]
                                         #  [ 3 29]]
print(accuracy_score(y_test, y_pred))    # 0.91

Listing 16.1 — The source tree (decision_tree_classification.py).

# The champion, inspected and audited
champ = DecisionTreeClassifier(criterion='entropy', max_depth=2,
                               random_state=0).fit(X_train, y_train)
print(champ.score(X_test, y_test))       # 0.94 — four leaves

from sklearn.tree import plot_tree
import matplotlib.pyplot as plt
plt.figure(figsize=(9, 5))
plot_tree(champ, feature_names=['Age', 'Salary'], class_names=['No', 'Yes'],
          filled=True, rounded=True)
plt.show()                               # the entire model, on one slide

# The depth study of Section 5
for d in [1, 2, 3, 4, None]:
    m = DecisionTreeClassifier(criterion='entropy', max_depth=d,
                               random_state=0).fit(X_train, y_train)
    print(f'depth={str(d):4s} test={m.score(X_test, y_test):.3f} '
          f'train={m.score(X_train, y_train):.3f} leaves={m.get_n_leaves()}')

Listing 16.2 — Reading the champion as a picture and reproducing the depth study.

💡

Pro Tip:

export_text(classifier,
                    feature_names=[...])

prints the whole tree as if-then rules — the compliance-department version of plot_tree. Both are reasons trees survive in regulated industries long after accuracy kings change.

7. Reading the Results: Three Rules

The updated scoreboard, all real, same split and scaling:

	Logistic	K-NN	SVM lin	SVM RBF	NB	DT full	DT depth-2
Accuracy	0.89	0.93	0.90	0.93	0.90	0.91	0.94
Errors	11	7	10	7	10	9	6 (2 FN + 4 FP)
Model size	3 coefs	300 rows	128 SVs	88 SVs	9 stats	50 leaves	4 leaves

And the champion's entire intelligence, in English — audit-ready:

🌎

Age > 44.5 → predict BUY (regardless of salary — both right-side leaves vote yes; the salary question there only splits buyer-heavy from buyer-clean).
Age ≤ 44.5 and Salary > ₹90,500 → predict BUY (the wealthy-young segment — our boundary customer (30, ₹150k) lives here).
Age ≤ 44.5 and Salary ≤ ₹90,500 → predict NO.

Three questions, 0.94 accuracy, no mathematics degree required to challenge any of them — this is the transparency no other classifier in this Part can match at any accuracy.

The standing caveat is Chapter 8's and Chapter 9's: this exact tree is a child of this exact sample. Resample the 300 rows and the thresholds move — 44.5 could become 42 or 47, and a different feature might lead — because greedy splits amplify small data changes. High variance, one more time; and the fix is one chapter away.

8. Strengths, Limits & the Road Ahead

Strengths	Limitations
Audit-ready rules — the model a compliance officer can read	Axis-aligned staircases approximate diagonals expensively
Scale-blind; mixed feature types welcome; no preprocessing ceremony	Unpruned = memoriser (real: train 1.000 / test 0.91)
Fast training and prediction; feature importance for free	Vote-share "probabilities" — overconfident at pure leaves
Beats fancier models when the true structure is boxy rules	High variance: resampling regrows a different tree

That final limitation is the launchpad: Chapter 9 averaged wobbling regression trees into a stable forest, and the identical cure awaits here. Chapter 17 grows a classification forest — bootstraps, feature subsampling, votes — and with it closes the classifier toolkit before Chapter 18 judges them all under one honest metric system.

🛠 Hands-On: Grow, Score, PruneIntermediate

The audit committee wants a model they can read aloud, the data science lead wants the best test score. Deliver both: the hand-computed entropy audit, the full tree, and the pruned champion — then write the memo.

Steps

By hand: compute the root entropy from 189/111 (expect ≈ 0.951 bits); then the Gini (expect ≈ 0.466).
Fit the full entropy tree; verify [[62, 6], [3, 29]] and 0.91; extract the root question and its two children's questions.
By hand: information gain of the root split from the side counts (215: 175/40, 85: 14/71) — expect ≈ 0.271 bits.
Run the depth study {1, 2, 3, 4, None}; identify the memoriser row and the champion row.
Print or draw the depth-2 tree; write its rules in English; classify the three anchor customers by hand through the rules.
Write the memo: which tree ships, what it costs in accuracy (if anything), and the Chapter 31 caveat on this selection procedure.

View Solution / Walkthrough

import numpy as np, pandas as pd, math
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree, export_text
from sklearn.metrics import confusion_matrix

ds = pd.read_csv('Social_Network_Ads.csv')
X, y = ds.iloc[:, :-1].values, ds.iloc[:, -1].values
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0)

H = -(189/300)*math.log2(189/300) - (111/300)*math.log2(111/300)
print('root entropy %.4f  gini %.4f' % (H, 1-(189/300)**2-(111/300)**2))

full = DecisionTreeClassifier(criterion='entropy', random_state=0).fit(X_tr, y_tr)
print(confusion_matrix(y_te, full.predict(X_te)), full.score(X_te, y_te))
print(export_text(full, feature_names=['Age', 'Salary'])[:300])

def ent(v):
    p = v.mean(); q = 1-p
    return 0 if p in (0, 1) else -(p*math.log2(p) + q*math.log2(q))
left = y_tr[X_tr[:, 0] <= 44.5]; right = y_tr[X_tr[:, 0] > 44.5]
IG = H - (len(left)/300*ent(left) + len(right)/300*ent(right))
print('IG(Age<=44.5) = %.4f bits' % IG)

for d in [1, 2, 3, 4, None]:
    m = DecisionTreeClassifier(criterion='entropy', max_depth=d,
                               random_state=0).fit(X_tr, y_tr)
    print('depth', d, 'test %.3f train %.3f leaves %d' %
          (m.score(X_te, y_te), m.score(X_tr, y_tr), m.get_n_leaves()))

champ = DecisionTreeClassifier(criterion='entropy', max_depth=2,
                               random_state=0).fit(X_tr, y_tr)
print(export_text(champ, feature_names=['Age', 'Salary']))

Expected results (real):

Step 1: H = 0.951 bits; Gini = 0.466.
Step 2: cm [[62, 6], [3, 29]], 0.91; root "Age ≤ 44.5", then "Salary ≤ 90,500" (young side) and "Salary ≤ 41,500" (older side).
Step 3: weighted H = 0.680 → IG = 0.271 bits.
Step 4: 0.89 / 0.94 / 0.94 / 0.93 / 0.91(train 1.000) — memoriser at None, champion at depth 2.
Step 5: rules per Section 7; anchors — (30, 87k): rule 3 → NO; (30, 150k): rule 2 → YES; (45, 87k): rule 1 → YES. All match the model's output.
Step 6: ship the depth-2 tree (0.94, four leaves, three readable rules); the selection used the test set, so confirm the depth on cross-validated scores (Ch 31) before the audit committee meets reality.

🎯 Key Takeaways

Entropy = messiness in bits: 0 for pure nodes, 1 for a coin flip. Our root, at 189/111, sits at 0.951 — nearly maximally worth splitting.

Information gain = entropy removed: the real root question "Age ≤ 44.5?" gained 0.271 bits — one question turned a coin flip into two 80%+ pure nodes.

Gini vs entropy is a non-choice: real trees differed by one test row (0.90 vs 0.91, 47 vs 50 leaves). Depth matters far more than criterion.

Leaves vote, and their probabilities are vote shares — pure leaves report 1.0 with a handful of rows' worth of certainty. Calibrate before acting on the numbers.

The memoriser's bill, itemised: full tree trains to 1.000 and loses to a 4-leaf pruned tree, 0.91 vs 0.94 — parsimony's third victory of the course.

The champion model is three English sentences — transparency no other classifier here matches — and its instability is exactly what Chapter 17's forest averages away.