SyntaxPilot
Courses/Machine Learning/Lesson 29
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Machine Learning · Lesson 29 of 90

Decision trees from scratch

decision treeroot nodeinternal nodeleafsplitthreshold searchimpurityGini impurityentropyinformation gainrecursive partitioningCART algorithmtree depthimplementing a tree in Python

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.

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_split is the threshold search, scored with weighted Gini.
  • build is the recursion: a node is a tuple (feature, threshold, left_subtree, right_subtree); a leaf is just 0 or 1.
  • show prints 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 depth comparisons.

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
  • DecisionTreeClassifier with max_depth=2 gives the same tree as ours (thresholds at midpoints: 29.5, 28.5, 1.5). export_text prints 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).

Decision regions

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_depth by 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

  1. A leaf with 8 repaid and 2 not: Gini? 0.32.
  2. Which node sees all the training data? The root.
  3. Information gain = ? Parent impurity − weighted children impurity.
  4. Why is CART called greedy? It takes the best split at each node without looking ahead.
  5. Do trees need feature scaling? No.

Interview questions

  1. 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).
  2. Gini vs entropy? Both measure impurity; Gini = 1 − Σp², entropy = −Σp log₂ p. They usually pick the same splits; Gini is a little faster.
  3. What is information gain? The reduction in impurity (usually entropy) from a split: parent − weighted children.
  4. 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).
  5. 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.
  6. 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.
  7. What is the time complexity of predicting with a tree? O(depth) comparisons per example.
  8. What shape are a tree's decision boundaries? Axis-parallel rectangles.
  9. What does a leaf predict? The majority class of its training rows (classification) or their mean (regression); predict_proba gives the class fractions.
  10. 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.