Machine Learning Full Course · Episode 29. Every code sample below was run with Python 3.13, NumPy 2.5.3 and scikit-learn 1.9.1; the output shown is the real output. The kirana-shop customers are made up for teaching; the mini project uses the breast-cancer dataset bundled with scikit-learn.
The big idea: a decision tree is a learned flowchart of yes/no questions ("income ≤ 29 thousand?"). To learn it, try every threshold on every feature, keep the question that makes the two resulting groups as pure as possible (lowest Gini impurity or entropy, i.e. the biggest information gain), then repeat inside each group (recursive partitioning) until a group is pure or a depth limit is reached. This greedy recipe is CART. Deep trees memorise noise, so the depth must be limited.
Words you need first
- Feature / label: an input column (income, years known) / the answer to predict (repaid or not) (Episode 1).
- Classification: predicting a category. Accuracy: fraction of correct predictions (Episode 24).
- Training / test set: data to learn from / data held back to check on new cases (Episode 15).
- Overfitting: memorising noise in the training data, so new data does worse (Episode 20).
- Entropy: average surprise of an outcome, in bits (Episode 12).
- Recursion: a function that calls itself on a smaller piece of the problem.
The problem: Raju's udhaar
Raju's kirana shop gives udhaar (credit: buy now, pay at month-end) to regular customers. His khata (account book) has 2,000 past customers: monthly income in thousand rupees, years Raju has known them, and whether they repaid. Who should get credit?
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def raju(income, years): # Raju's rule, written by hand
if income > 25:
return 1
return 0
pred = np.array([raju(i, yr) for i, yr in X_te])
print("customers:", X_tr[:3].tolist(), "repaid:", y_tr[:3].tolist())
print(f"repaid overall: {y.mean():.1%}")
print(f"Raju's rule accuracy: {(pred == y_te).mean():.3f}")
Output:
customers: [[76, 10], [13, 1], [52, 4]] repaid: [1, 0, 0]
repaid overall: 61.4%
Raju's rule accuracy: 0.762
- 61.4% of customers repaid. Raju's hand-written rule ("income above 25 thousand") scores 0.762.
- But why 25? Why income first? What should he ask next? With 20 features, nobody can tune such rules by hand. We let the computer search.
(The data hides this pattern: repaid if income ≥ 30 and known ≥ 2 years, or income ≥ 60; then 10% of labels are flipped at random to imitate real-life surprises.)
Tree words: root, nodes, leaves
Real-life example: the game of twenty questions. "Is it an animal?" is asked first, about everything; the next question depends on the answer; "it's a fish!" ends the game.
- Decision tree: a flowchart of yes/no questions learned from data, drawn upside down (root at the top).
- Root node: the first question; all the data passes through it.
- Internal node: any question below the root.
- Split: the question at a node, here "is feature ≤ threshold?"; yes goes left, no goes right.
- Threshold: the cut-off value in a split (29 in "income ≤ 29").
- Leaf: a node with no question; it holds the prediction (the majority label of its training rows).
- Depth: the number of questions on the longest path from the root to a leaf.
Threshold search
Try every feature and every threshold; each side predicts its majority; count the mistakes.
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def errors(left, right): # mistakes if each side votes its majority
return sum(min(side.sum(), len(side) - side.sum()) for side in (left, right))
best = []
for f, name in [(0, "income"), (1, "years")]:
for t in np.unique(X_tr[:, f]): # try every threshold
mask = X_tr[:, f] <= t
best.append((errors(y_tr[mask], y_tr[~mask]), name, t))
best.sort()
print("tried", len(best), "questions; best 3:")
for e, name, t in best[:3]:
print(f" {name} <= {t}: {e} mistakes out of {len(y_tr)}")
Output:
tried 82 questions; best 3:
income <= 29: 245 mistakes out of 1500
income <= 30: 254 mistakes out of 1500
income <= 28: 258 mistakes out of 1500
- 82 candidate questions (71 income values + 11 year values).
- Best: income ≤ 29, 245 mistakes of 1,500 (83.7% right). Raju's guess of 25 was close, but the data says 29.
- Only thresholds between existing values matter; scikit-learn uses the midpoints (29.5).
Counting mistakes is too blunt: impurity
8 customers, 4 repaid and 4 not. Question A gives (3 ✓, 1 ✗) and (1 ✓, 3 ✗): 2 mistakes. Question B gives (2 ✓, 4 ✗) and (2 ✓, 0 ✗): also 2 mistakes, but B produced a completely pure group that needs no more questions. Mistakes can't see the difference.
- Impurity: how mixed the labels in a group are. 0 = pure (one class only).
- Gini impurity: 1 − Σ pᵢ². With two classes it runs from 0 (pure) to 0.5 (50/50). Meaning: the chance that two items drawn at random (with replacement) have different labels. Real-life example: a bag of marbles; all one colour → 0; half red, half blue → 0.5.
- Entropy: −Σ pᵢ log₂ pᵢ, measured in bits. Two classes: 0 (pure) to 1 bit (50/50, as surprising as a coin toss).
- Weighted impurity of a split: each child's impurity × (child size / parent size), added up. Without the weights, a tiny group of one customer (always pure) would look perfect.
- Information gain: parent impurity − weighted children impurity (usually with entropy). Best split = biggest gain = lowest weighted impurity.
import math
def gini(yes, no):
p = yes / (yes + no); return 1 - p**2 - (1 - p)**2
def entropy(yes, no):
return -sum(q * math.log2(q) for q in (yes / (yes + no), no / (yes + no)) if q > 0)
def score(fn, groups): # weighted average over the groups
total = sum(a + b for a, b in groups)
return sum((a + b) / total * fn(a, b) for a, b in groups)
parent = [(4, 4)] # 8 customers: 4 repaid, 4 didn't
A = [(3, 1), (1, 3)] # question A
B = [(2, 4), (2, 0)] # question B: one group is pure
for name, g in [("parent", parent), ("A", A), ("B", B)]:
print(f"{name:<6} mistakes {sum(min(a, b) for a, b in g)} gini {score(gini, g):.3f}"
f" entropy {score(entropy, g):.3f} gain {1 - score(entropy, g):.3f}")
Output:
parent mistakes 4 gini 0.500 entropy 1.000 gain 0.000
A mistakes 2 gini 0.375 entropy 0.811 gain 0.189
B mistakes 2 gini 0.333 entropy 0.689 gain 0.311
| Mistakes | Gini | Entropy | Information gain | |
|---|---|---|---|---|
| Parent (4, 4) | 4 | 0.500 | 1.000 | 0 |
| A: (3,1) (1,3) | 2 | 0.375 | 0.811 | 0.189 |
| B: (2,4) (2,0) | 2 | 0.333 | 0.689 | 0.311 |
Worked example for A: each child has p = 0.75 / 0.25, Gini = 1 − 0.75² − 0.25² = 1 − 0.5625 − 0.0625 = 0.375; both children are half the parent, so the weighted Gini is 0.375. For B: the 6-customer child has p = 1/3, Gini = 1 − 1/9 − 4/9 = 0.444, weighted 6/8 × 0.444 = 0.333; the pure child adds 0.
Recursive partitioning
Real-life example: a post office sorts a sack of letters by the first PIN-code digit (region), then sorts each pile again by district with the same method, and stops when a pile is ready for one postman.
- Recursive partitioning: split the data, then apply the same splitting to each part, again and again.
- Stopping rules: a group is pure, no split reduces impurity, or the depth limit is reached. Then the group becomes a leaf predicting its majority.
A decision tree from scratch (CART)
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def best_split(X, y): # try every feature and threshold
best = (gini(y), None, None) # (impurity, feature, threshold)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * gini(y[m]) + (~m).sum() * gini(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
def build(X, y, depth): # recursive partitioning
g, f, t = best_split(X, y)
if depth == 0 or f is None: return int(y.mean() >= 0.5) # leaf: majority vote
m = X[:, f] <= t
return (f, t, build(X[m], y[m], depth - 1), build(X[~m], y[~m], depth - 1))
def show(node, pad=""):
if not isinstance(node, tuple): return print(pad + "-> " + ["not repaid", "repaid"][node])
f, t, left, right = node; q = ["income", "years"][f]
print(f"{pad}{q} <= {t}"); show(left, pad + "| "); print(f"{pad}{q} > {t}"); show(right, pad + "| ")
show(build(X_tr, y_tr, 2))
Output:
income <= 29
| income <= 28
| | -> not repaid
| income > 28
| | -> not repaid
income > 29
| years <= 1
| | -> not repaid
| years > 1
| | -> repaid
best_splitis the threshold search, scored with weighted Gini.buildis the recursion: a node is a tuple(feature, threshold, left_subtree, right_subtree); a leaf is just 0 or 1.showprints the tree with indentation.- The tree discovers the hidden rule: income ≤ 29 → not repaid; otherwise years ≤ 1 → not repaid, else repaid.
- The left branch also splits at 28, but both leaves say "not repaid": Gini dropped slightly, yet the prediction didn't change. Pruning (Episode 30) removes such splits.
CART
- CART (Classification And Regression Trees): the algorithm above: binary splits "feature ≤ threshold", impurity to choose them (Gini for classification, variance for regression), recursive, majority/mean in the leaves. scikit-learn's trees use an optimised CART.
- Greedy: at each node it takes the best split now and never reconsiders; finding the globally best tree is computationally infeasible (NP-complete) for real data sizes, so greedy is the practical choice. Real-life example: a chess player who only looks one move ahead.
- Prediction: start at the root, answer each question for the new example, follow the branch, and return the leaf's label.
- Cost: training tries every feature × every threshold at every node; scikit-learn sorts each feature once to make this fast. Prediction is just
depthcomparisons.
Depth and overfitting (scikit-learn)
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
from sklearn.tree import DecisionTreeClassifier, export_text
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_tr, y_tr) # CART, Gini
print(export_text(tree, feature_names=["income", "years"]))
for d in [1, 2, 3, 5, 10, None]: # None = grow until pure
t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(X_tr, y_tr)
print(f"max_depth {str(d):<4} depth {t.get_depth():>2} leaves {t.get_n_leaves():>3}"
f" train {t.score(X_tr, y_tr):.3f} test {t.score(X_te, y_te):.3f}")
e = DecisionTreeClassifier(criterion="entropy", max_depth=3, random_state=0).fit(X_tr, y_tr)
print(f"entropy, max_depth 3: test {e.score(X_te, y_te):.3f}")
Output:
|--- income <= 29.50
| |--- income <= 28.50
| | |--- class: 0
| |--- income > 28.50
| | |--- class: 0
|--- income > 29.50
| |--- years <= 1.50
| | |--- class: 0
| |--- years > 1.50
| | |--- class: 1
max_depth 1 depth 1 leaves 2 train 0.837 test 0.822
max_depth 2 depth 2 leaves 4 train 0.867 test 0.856
max_depth 3 depth 3 leaves 8 train 0.903 test 0.880
max_depth 5 depth 5 leaves 26 train 0.905 test 0.878
max_depth 10 depth 10 leaves 159 train 0.912 test 0.864
max_depth None depth 23 leaves 284 train 0.917 test 0.818
entropy, max_depth 3: test 0.880
DecisionTreeClassifierwithmax_depth=2gives the same tree as ours (thresholds at midpoints: 29.5, 28.5, 1.5).export_textprints it.- Depth 3 (8 leaves) is best: test 0.880.
- No limit (
max_depth=None): depth 23, 284 leaves, train 0.917, test 0.818: overfitting. - Training accuracy never reaches 1.0 because some customers have identical income and years but different outcomes; no question can separate identical rows.
criterion="entropy"gives the same 0.880 here; Gini and entropy usually choose the same or very similar splits (Gini is slightly faster: no logarithm).

Green = tree predicts repaid; blue dots = repaid, red = didn't. Every split is a straight cut parallel to an axis, so trees carve the feature space into rectangles. Depth 1 is one vertical cut; depth 2 adds a horizontal cut at 1.5 years; no limit gives a patchwork of tiny rectangles.
Plotting code:
import numpy as np, matplotlib; matplotlib.use("Agg"); import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier as DT
rng = np.random.default_rng(29); n = 2000
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)]
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
gx, gy = np.meshgrid(np.linspace(10, 80, 400), np.linspace(-0.5, 10.5, 400)); G = np.c_[gx.ravel(), gy.ravel()]
fig, ax = plt.subplots(1, 3, figsize=(16, 4.9))
j = np.random.default_rng(0).uniform(-.3, .3, (400, 2)) # jitter so dots don't overlap
for a, d in zip(ax, [1, 2, None]):
m = DT(max_depth=d, random_state=0).fit(X_tr, y_tr); Z = m.predict(G).reshape(gx.shape)
a.contourf(gx, gy, Z, levels=[-.5, .5, 1.5], colors=["#f6c7b6", "#bfe3d0"], alpha=.8)
a.scatter(X_tr[:400, 0] + j[:, 0], X_tr[:400, 1] + j[:, 1], c=y_tr[:400], cmap="coolwarm_r", s=10)
a.set_title(f"max_depth={d}: {m.get_n_leaves()} leaves, test acc {m.score(X_te, y_te):.3f}")
a.set_xlabel("income (thousand Rs a month)"); a.set_ylabel("years known")
plt.tight_layout(); plt.savefig("regions.png", dpi=90)
Notes on trees
- No feature scaling needed: a threshold on rupees works as well as one on years, because no distances are computed.
- Axis-parallel splits: a diagonal boundary needs many small steps.
- Interpretable: a small tree can be read and explained as rules.
- Choose
max_depthby cross-validation (Episode 26); more knobs in Episode 30.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Guessing thresholds by hand | Raju's rule accuracy: 0.762 |
One guessed question | Threshold search |
| Scoring splits by mistakes | A and B both 2 mistakes | Blind to pure groups | Gini or entropy |
| Not weighting children by size | A 1-row child looks perfect | Size ignored | Weight by n_child / n_parent |
np.unique(X[:, f]) without [:-1] |
A split with an empty right side | The last value puts everything left | Skip the largest value |
| No depth limit | 284 leaves, test 0.818 | Memorises noise | max_depth by CV, pruning |
| Expecting train accuracy 1.0 | Max train 0.917 | Identical rows with different labels | It's noise, not a bug |
Entropy of a pure group with log2(0) |
RuntimeWarning: divide by zero encountered in log2 and nan |
0 × log 0 is undefined in code | Treat p = 0 or 1 as entropy 0 |
The last one, reproduced:
import numpy as np
p = np.array([1.0, 0.0]) # a pure group: all repaid
print("entropy:", -(p * np.log2(p)).sum()) # 0 * log2(0) = 0 * -inf
Output:
entropy: nan
main.py:3: RuntimeWarning: divide by zero encountered in log2
print("entropy:", -(p * np.log2(p)).sum()) # 0 * log2(0) = 0 * -inf
main.py:3: RuntimeWarning: invalid value encountered in multiply
print("entropy:", -(p * np.log2(p)).sum()) # 0 * log2(0) = 0 * -inf
Mini project: your tree on a real dataset
The breast-cancer dataset (bundled with scikit-learn) has measurements of cell nuclei from tumour images, labelled malignant or benign. Run the scratch tree and compare it with scikit-learn.
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
data = load_breast_cancer() # bundled with scikit-learn
X, y = data.data, data.target
print(X.shape, "classes:", [str(c) for c in data.target_names])
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0, stratify=y)
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def best_split(X, y): # try every feature and threshold
best = (gini(y), None, None) # (impurity, feature, threshold)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * gini(y[m]) + (~m).sum() * gini(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
def build(X, y, depth): # recursive partitioning
g, f, t = best_split(X, y)
if depth == 0 or f is None: return int(y.mean() >= 0.5) # leaf: majority vote
m = X[:, f] <= t
return (f, t, build(X[m], y[m], depth - 1), build(X[~m], y[~m], depth - 1))
def predict(node, x):
while isinstance(node, tuple):
f, t, left, right = node; node = left if x[f] <= t else right
return node
for d in [1, 2, 3, 4]:
mine = build(X_tr, y_tr, d)
acc = np.mean([predict(mine, x) == t for x, t in zip(X_te, y_te)])
sk = DecisionTreeClassifier(max_depth=d, random_state=0).fit(X_tr, y_tr).score(X_te, y_te)
print(f"depth {d}: my tree {acc:.3f} scikit-learn {sk:.3f}")
f, t = mine[0], mine[1]
print("root question:", data.feature_names[f], "<=", round(t, 3))
Output:
(569, 30) classes: ['malignant', 'benign']
depth 1: my tree 0.888 scikit-learn 0.888
depth 2: my tree 0.881 scikit-learn 0.888
depth 3: my tree 0.923 scikit-learn 0.916
depth 4: my tree 0.916 scikit-learn 0.909
root question: worst perimeter <= 106.0
The scratch tree is within about one percentage point of scikit-learn at every depth (small differences come from thresholds at values vs midpoints and from how ties between equally good splits are broken).
Practice
1. Add entropy as an option in best_split.
Solution
import numpy as np
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def entropy(y):
p = y.mean()
return 0.0 if p in (0, 1) else -(p * np.log2(p) + (1 - p) * np.log2(1 - p))
def best_split(X, y, impurity=gini): # impurity is now a parameter
best = (impurity(y), None, None)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * impurity(y[m]) + (~m).sum() * impurity(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
rng = np.random.default_rng(29); n = 2000
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)]
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int)
for fn in [gini, entropy]:
g, f, t = best_split(X[:1500], y[:1500], fn)
print(f"{fn.__name__:<8} best root split: {['income', 'years'][f]} <= {t} (weighted impurity {g:.3f})")
Output:
gini best root split: income <= 29 (weighted impurity 0.267)
entropy best root split: income <= 29 (weighted impurity 0.625)
Both measures choose the same root split here.
2. Write predict() for the scratch tree and measure test accuracy at several depths.
Solution
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def best_split(X, y): # try every feature and threshold
best = (gini(y), None, None) # (impurity, feature, threshold)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * gini(y[m]) + (~m).sum() * gini(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
def build(X, y, depth): # recursive partitioning
g, f, t = best_split(X, y)
if depth == 0 or f is None: return int(y.mean() >= 0.5) # leaf: majority vote
m = X[:, f] <= t
return (f, t, build(X[m], y[m], depth - 1), build(X[~m], y[~m], depth - 1))
def predict(node, x):
while isinstance(node, tuple): # walk down until we reach a leaf
f, t, left, right = node
node = left if x[f] <= t else right
return node
for d in [1, 2, 3, 5]:
tree = build(X_tr, y_tr, d)
acc = np.mean([predict(tree, x) == label for x, label in zip(X_te, y_te)])
print(f"depth {d}: test accuracy {acc:.3f}")
Output:
depth 1: test accuracy 0.822
depth 2: test accuracy 0.856
depth 3: test accuracy 0.880
depth 5: test accuracy 0.878
These are exactly scikit-learn's numbers from the depth table above.
3. Print the depth-3 scratch tree.
Solution
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def best_split(X, y): # try every feature and threshold
best = (gini(y), None, None) # (impurity, feature, threshold)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * gini(y[m]) + (~m).sum() * gini(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
def build(X, y, depth): # recursive partitioning
g, f, t = best_split(X, y)
if depth == 0 or f is None: return int(y.mean() >= 0.5) # leaf: majority vote
m = X[:, f] <= t
return (f, t, build(X[m], y[m], depth - 1), build(X[~m], y[~m], depth - 1))
def show(node, pad=""):
if not isinstance(node, tuple): return print(pad + "-> " + ["not repaid", "repaid"][node])
f, t, left, right = node; q = ["income", "years"][f]
print(f"{pad}{q} <= {t}"); show(left, pad + "| "); print(f"{pad}{q} > {t}"); show(right, pad + "| ")
show(build(X_tr, y_tr, 3))
Output:
income <= 29
| income <= 28
| | income <= 13
| | | -> not repaid
| | income > 13
| | | -> not repaid
| income > 28
| | years <= 3
| | | -> not repaid
| | years > 3
| | | -> not repaid
income > 29
| years <= 1
| | income <= 59
| | | -> not repaid
| | income > 59
| | | -> repaid
| years > 1
| | income <= 32
| | | -> repaid
| | income > 32
| | | -> repaid
Several splits end in two identical leaves: the impurity went down a little but the majority didn't change. The useful structure is still only three questions.
4. Add a minimum group size: stop splitting a node with fewer than min_rows rows.
Solution
import numpy as np
rng = np.random.default_rng(29); n = 2000 # made-up kirana customers
X = np.c_[rng.integers(10, 81, n), rng.integers(0, 11, n)] # income (thousand Rs), years known
ok = ((X[:, 0] >= 30) & (X[:, 1] >= 2)) | (X[:, 0] >= 60)
y = np.where(rng.random(n) < 0.1, ~ok, ok).astype(int) # 1 = repaid (10% noise)
X_tr, y_tr, X_te, y_te = X[:1500], y[:1500], X[1500:], y[1500:]
def gini(y): p = y.mean(); return 1 - p**2 - (1 - p)**2
def best_split(X, y): # try every feature and threshold
best = (gini(y), None, None) # (impurity, feature, threshold)
for f in range(X.shape[1]):
for t in np.unique(X[:, f])[:-1]:
m = X[:, f] <= t
g = (m.sum() * gini(y[m]) + (~m).sum() * gini(y[~m])) / len(y)
if g < best[0]: best = (g, f, t)
return best
def build(X, y, depth, min_rows=20): # stop if fewer than min_rows rows
g, f, t = best_split(X, y)
if depth == 0 or f is None or len(y) < min_rows: return int(y.mean() >= 0.5)
m = X[:, f] <= t
return (f, t, build(X[m], y[m], depth - 1, min_rows), build(X[~m], y[~m], depth - 1, min_rows))
def show(node, pad=""):
if not isinstance(node, tuple): return print(pad + "-> " + ["not repaid", "repaid"][node])
f, t, left, right = node; q = ["income", "years"][f]
print(f"{pad}{q} <= {t}"); show(left, pad + "| "); print(f"{pad}{q} > {t}"); show(right, pad + "| ")
def leaves(node): return leaves(node[2]) + leaves(node[3]) if isinstance(node, tuple) else 1
for mr in [2, 20, 200]:
print(f"min_rows {mr:>3}: depth-10 tree has {leaves(build(X_tr, y_tr, 10, mr))} leaves")
Output:
min_rows 2: depth-10 tree has 152 leaves
min_rows 20: depth-10 tree has 84 leaves
min_rows 200: depth-10 tree has 16 leaves
A bigger minimum keeps the tree small: this is the idea behind min_samples_split in Episode 30.
5. By hand: a node has 10 customers, 8 repaid. Gini? Entropy?
Solution
Gini = 1 − 0.8² − 0.2² = 1 − 0.64 − 0.04 = 0.32. Entropy = −(0.8 log₂ 0.8 + 0.2 log₂ 0.2) = 0.8 × 0.322 + 0.2 × 2.322 = 0.722 bits.
Quick quiz
- A leaf with 8 repaid and 2 not: Gini? 0.32.
- Which node sees all the training data? The root.
- Information gain = ? Parent impurity − weighted children impurity.
- Why is CART called greedy? It takes the best split at each node without looking ahead.
- Do trees need feature scaling? No.
Interview questions
- How does a decision tree choose a split? It tries every feature and threshold and picks the one with the lowest weighted impurity (Gini/entropy for classification, variance for regression).
- Gini vs entropy? Both measure impurity; Gini = 1 − Σp², entropy = −Σp log₂ p. They usually pick the same splits; Gini is a little faster.
- What is information gain? The reduction in impurity (usually entropy) from a split: parent − weighted children.
- Why are trees greedy, and what's the downside? The optimal tree is infeasible to find; greedy splits can miss combinations that only pay off two levels down (e.g. XOR patterns).
- Why do deep trees overfit? With enough splits each leaf holds a few training rows, so the tree memorises noise; limit depth, require minimum leaf sizes, or prune.
- Do trees need scaling or one-hot encoding? No scaling; categorical features must be numeric in scikit-learn (encode them), though trees handle ordinal encodings well.
- What is the time complexity of predicting with a tree? O(depth) comparisons per example.
- What shape are a tree's decision boundaries? Axis-parallel rectangles.
- What does a leaf predict? The majority class of its training rows (classification) or their mean (regression);
predict_probagives the class fractions. - What does CART stand for? Classification And Regression Trees.
Glossary
| Term | Meaning (plain words) | Example from this episode |
|---|---|---|
| Udhaar / khata | Credit at a shop / the shop's account book | Raju's 2,000 customers |
| Decision tree | A learned flowchart of yes/no questions | income ≤ 29 → years ≤ 1 → … |
| Root node | The first question, seen by all data | income ≤ 29 |
| Internal node | A question below the root | years ≤ 1 |
| Leaf | End node holding the prediction | "repaid" |
| Split | The question at a node: feature ≤ threshold | income ≤ 29 |
| Threshold | The cut-off value of a split | 29 (scikit-learn: 29.5) |
| Threshold search | Trying every threshold of every feature | 82 questions tried |
| Impurity | How mixed the labels in a group are | 0 = pure |
| Gini impurity | 1 − Σ pᵢ²: chance two random picks differ | 4/4 split → 0.5 |
| Entropy | −Σ pᵢ log₂ pᵢ: average surprise in bits | 4/4 split → 1 bit |
| Weighted impurity | Children's impurity averaged by size | question B: 0.333 |
| Information gain | Parent impurity − weighted children impurity | B: 0.311 |
| Pure node | All rows have the same label | (2 ✓, 0 ✗) |
| Recursive partitioning | Splitting each part again with the same method | PIN-code sorting |
| Recursion | A function calling itself on a smaller piece | build(X[m], y[m], depth - 1) |
| CART | Classification And Regression Trees: greedy binary splits | scikit-learn's trees |
| Greedy algorithm | Takes the best choice now, never reconsiders | best split at each node |
| Depth | Questions on the longest root-to-leaf path | max_depth=3 |
| Axis-parallel split | A cut along one feature only | vertical line at income 29.5 |
export_text |
Prints a scikit-learn tree as text | |--- income <= 29.50 |
Summary
- A decision tree asks yes/no questions from the root down to a leaf.
- Threshold search tries every threshold of every feature.
- Choose splits by Gini impurity or entropy: lowest weighted impurity = biggest information gain.
- Recursive partitioning + greedy binary splits = CART; 25 lines of Python match scikit-learn.
- Limit the depth: no limit gave 284 leaves and worse test accuracy.
- Next episode: decision trees in practice: pruning, regression trees, feature importance, instability.