Decision Trees

You have a bag of mixed-up marbles. Some are red, some blue. You want to separate them. What’s the best way to split the bag? You’ll invent a measure of “mixedness”, use it to find the cleanest split, then discover that repeating this process builds a decision tree.

You have two bags of marbles — red and blue:

Bag	Red	Blue	Total
A	10	0	10
B	5	5	10

Which bag is more “mixed up”?

Bag A has only red — it’s pure.
Bag B is half-and-half — it’s maximally mixed.

Can you assign a number to “how mixed” a bag is?

The number should be 0 when the bag is pure and highest when it’s 50/50.

Let $p$ = fraction of red, $q$ = fraction of blue, and $p + q = 1$.

Bag	p (red)	q (blue)	impurity(p, q) = ?
A (all red)	1.0	0.0	should be 0
B (all blue)	0.0	1.0	should be 0
C (half-half)	0.5	0.5	should be 1
D (mostly red)	0.8	0.2	should be between 0 and 1

Write a function that satisfies all four cases:

def impurity(p, q):
    """p = fraction of red, q = fraction of blue, p + q = 1.
    Returns 0 when pure, 1 when maximally mixed."""
    return ???

Try $p \times q$:

A: 1.0 × 0.0 =	0.00 ✓
B: 0.0 × 1.0 =	0.00 ✓
C: 0.5 × 0.5 =	0.25 — not 1!

Pure gives 0 ✓ — but 50/50 gives 0.25, not 1.

Fix: multiply by 4 → $\text{impurity} = 4pq$

A: 4 × 1.0 × 0.0 =	0.0 ✓
B: 4 × 0.0 × 1.0 =	0.0 ✓
C: 4 × 0.5 × 0.5 =	1.0 ✓
D: 4 × 0.8 × 0.2 =	0.64 ✓

Your impurity formula: $\;\text{impurity}(p) = 4p(1-p)$

$p = 0$ or $p = 1$ → 0 (pure)
$p = 0.5$ → 1 (max mixed)
Symmetric — it doesn’t matter which color is “p”

This is your impurity function. It measures how mixed a group is.

(The standard “Gini impurity” is $2pq$ — same shape, just scaled by ½. Both rank splits identically.)

Given a list of labels, compute its impurity:

items = ["R", "R", "B", "R", "B"]

Count: 3 red, 2 blue → $p = 3/5 = 0.6$, $q = 2/5 = 0.4$

$\text{impurity} = 4 \times 0.6 \times 0.4 = \mathbf{0.96}$

Write a function list_impurity(items):

def list_impurity(items):
    # count the most common label
    # p = count / total, q = 1 - p
    # return 4 * p * q
    pass

def list_impurity(items):
    from collections import Counter
    c = Counter(items)
    most = c.most_common(1)[0][1]
    p = most / len(items)
    return 4 * p * (1 - p)

Now split a list into two halves and measure the total impurity:

items = ["R", "R", "B", "R", "B", "B", "B", "R"]

Split at	Left	Right	Left imp.	Right imp.
position 3	[R, R, B]	[R, B, B, B, R]	0.89	0.96
position 4	[R, R, B, R]	[B, B, B, R]	0.75	0.75

Total impurity = weighted average:

$\text{total} = \dfrac{|L|}{|L|+|R|} \times \text{imp}(L) + \dfrac{|R|}{|L|+|R|} \times \text{imp}(R)$

Split at 3: $\frac{3}{8}(0.89) + \frac{5}{8}(0.96) = \mathbf{0.93}$
Split at 4: $\frac{4}{8}(0.75) + \frac{4}{8}(0.75) = \mathbf{0.75}$ ← better!

The best split has the lowest total impurity.

Try every position and pick the one with minimum total impurity:

def total_impurity(left, right):
    n = len(left) + len(right)
    # weighted average of left and right impurity
    pass

def find_best_split(items):
    # try every position from 1 to len-1
    # return the position with minimum total impurity
    pass

def total_impurity(left, right):
    n = len(left) + len(right)
    wL = len(left) / n
    wR = len(right) / n
    return wL * list_impurity(left) + wR * list_impurity(right)

def find_best_split(items):
    best_pos, min_imp = 0, float('inf')
    for i in range(1, len(items)):
        imp = total_impurity(items[:i], items[i:])
        if imp < min_imp:
            min_imp = imp
            best_pos = i
    return best_pos, min_imp

This is the core algorithm: try every split, keep the cleanest one.

20 students — each with a height (cm) and gender (M/F):

heights = [158, 162, 165, 167, 168, 170, 171, 172, 174, 175,
     176, 178, 179, 180, 181, 182, 183, 185, 187, 190]
genders = ["F","F","F","F","M","F","M","M","F","M",
     "M","M","M","M","F","M","M","M","M","M"]

Question: Can you predict gender from height?

If you had to pick one height threshold to separate M from F, what would it be?

Short heights are mostly F, tall heights are mostly M — but there’s overlap in the middle.

Instead of splitting at a position, split at a threshold value:

Left group: height ≤ threshold
Right group: height > threshold

Try threshold = 170:

Group	Heights	Genders	Impurity
Left (≤170)	158,162,165,167,168,170	F,F,F,F,M,F	0.56
Right (>170)	171…190	M,M,F,M,M,M,M,M,F,M,M,M,M,M	0.41

Total: $\frac{6}{20}(0.56) + \frac{14}{20}(0.41) = \mathbf{0.45}$

But is 170 the best threshold? Try them all!

Try every unique height as a threshold:

def split_by_threshold(heights, genders, t):
    left  = [g for h, g in zip(heights, genders) if h <= t]
    right = [g for h, g in zip(heights, genders) if h > t]
    return left, right

def find_best_threshold(heights, genders):
    best_t, min_imp = None, float('inf')
    for t in sorted(set(heights)):
        left, right = split_by_threshold(heights, genders, t)
        if not left or not right:
            continue
        # compute total_impurity, track the best
        pass
    return best_t, min_imp

def find_best_threshold(heights, genders):
    best_t, min_imp = None, float('inf')
    for t in sorted(set(heights)):
        left, right = split_by_threshold(heights, genders, t)
        if not left or not right:
            continue
        imp = total_impurity(left, right)
        if imp < min_imp:
            min_imp = imp
            best_t = t
    return best_t, min_imp

best_t, best_imp = find_best_threshold(heights, genders)
# best_t = 167 — left is pure [F,F,F,F], right is mostly M

The best threshold is height ≤ 167. Left group: all F (pure!). Right group: mostly M with a few F outliers.

Now add a second feature — weight:

data = [
    {"height": 158, "weight": 52, "gender": "F"},
    {"height": 162, "weight": 55, "gender": "F"},
    ...
    {"height": 190, "weight": 98, "gender": "M"},
]

Which feature separates M from F better — height or weight?

Try every (feature, threshold) pair:

def find_decision_boundary(data, features, label):
    best_feature, best_threshold = None, None
    min_imp = float('inf')
    for feature in features:
        for t in sorted(set(row[feature] for row in data)):
            left  = [row[label] for row in data if row[feature] <= t]
            right = [row[label] for row in data if row[feature] > t]
            if not left or not right:
                continue
            # track the best (feature, threshold, impurity)
    return best_feature, best_threshold, min_imp

def find_decision_boundary(data, features, label):
    best_feature, best_threshold = None, None
    min_imp = float('inf')
    for feature in features:
        for t in sorted(set(row[feature] for row in data)):
            left  = [row[label] for row in data if row[feature] <= t]
            right = [row[label] for row in data if row[feature] > t]
            if not left or not right:
                continue
            imp = total_impurity(left, right)
            if imp < min_imp:
                min_imp = imp
                best_feature = feature
                best_threshold = t
    return best_feature, best_threshold, min_imp
# weight wins — it separates M/F more cleanly!

Imagine deciding whether to accept a job offer:

Is salary > 1000?
├── NO  → Reject
└── YES → Is distance <= 40?
           ├── YES → Accept
           └── NO  → Reject

Trace each case:

Salary	Distance	Result
800	20	salary ≤ 1000 → Reject
1200	30	salary > 1000, dist ≤ 40 → Accept
1500	60	salary > 1000, dist > 40 → Reject

This is a decision tree. It has two kinds of nodes:

Boundary node: asks a question, has two children
Leaf node: gives a final answer

Design a class DecisionTreeNode:

class DecisionTreeNode:
    def __init__(self, decision=None, boundary=None,
                 boundary_value=None, left=None, right=None):
        # leaf: stores decision (a label)
        # boundary: stores feature name, threshold, left, right
        pass

    def check(self, features):
        # if leaf → return decision
        # else → compare features[boundary] to threshold
        #         go left or right
        pass

def YES(): return DecisionTreeNode(decision=True)
def NO():  return DecisionTreeNode(decision=False)

class DecisionTreeNode:
    def __init__(self, decision=None, boundary=None,
                 boundary_value=None, left=None, right=None):
        self.decision = decision
        self.boundary = boundary
        self.boundary_value = boundary_value
        self.left = left
        self.right = right

    def check(self, features):
        if self.decision is not None:
            return self.decision
        if features[self.boundary] <= self.boundary_value:
            return self.left.check(features)
        else:
            return self.right.check(features)

Build the job-offer tree by nesting nodes:

job_tree = DecisionTreeNode(
    boundary="salary", boundary_value=1000,
    left=NO(),                        # salary <= 1000 → reject
    right=DecisionTreeNode(
        boundary="distance", boundary_value=40,
        left=YES(),                   # distance <= 40 → accept
        right=NO()                    # distance > 40  → reject
    )
)

job_tree.check({"salary": 1200, "distance": 30})  # True ✓
job_tree.check({"salary": 800,  "distance": 20})  # False ✓
job_tree.check({"salary": 1500, "distance": 60})  # False ✓

The check() method traverses the tree recursively: at each boundary node it goes left or right, until it hits a leaf.

After the first split on height ≤ 167:

height <= 167
├── Left:  [F, F, F, F]           ← pure! → LEAF: F
└── Right: [M, F, M, M, F, M, M, M, M, M, F, M, M, M, M, M]
                                   ← still mixed!

The right group is impure. What do you do?

Split it again! Find the best threshold in the right group, split, repeat.

Stop when:

The group is pure (all same label)
The group has 1 element
At the leaf, predict the majority label

This is recursion — the same algorithm applied to smaller and smaller subsets.

build_tree(data, features, label) — the recursive algorithm:

def majority_label(labels):
    # return the most common label
    pass

def is_pure(labels):
    # return True if all labels are the same
    pass

def build_tree(data, features, label):
    labels = [row[label] for row in data]
    # Base case: pure or single element → return leaf
    # Recursive case:
    #   find_decision_boundary → best feature, threshold
    #   split data into left_data, right_data
    #   build_tree(left_data), build_tree(right_data)
    #   return boundary node
    pass

def majority_label(labels):
    from collections import Counter
    return Counter(labels).most_common(1)[0][0]

def is_pure(labels):
    return len(set(labels)) <= 1

def build_tree(data, features, label):
    labels = [row[label] for row in data]
    if len(data) <= 1 or is_pure(labels):
        return DecisionTreeNode(decision=majority_label(labels))
    feat, thresh, _ = find_decision_boundary(data, features, label)
    left_data  = [r for r in data if r[feat] <= thresh]
    right_data = [r for r in data if r[feat] >  thresh]
    if not left_data or not right_data:
        return DecisionTreeNode(decision=majority_label(labels))
    return DecisionTreeNode(
        boundary=feat, boundary_value=thresh,
        left=build_tree(left_data, features, label),
        right=build_tree(right_data, features, label))

Build the tree and print it:

tree = build_tree(data, ["height", "weight"], "gender")

def print_tree(node, depth=0):
    indent = "  " * depth
    if node.decision is not None:
        print(f"{indent}LEAF → {node.decision}")
    else:
        print(f"{indent}{node.boundary} <= {node.boundary_value}?")
        print_tree(node.left,  depth + 1)
        print_tree(node.right, depth + 1)

weight <= 63?
  weight <= 54?
    LEAF → F
    height <= 170?
      LEAF → F
      LEAF → M
  LEAF → M

Your algorithm split on weight first (it separates M/F better than height), then height to handle the tricky cases in the middle.

Real ML libraries use this interface:

fit(X, y) — train the model
predict(X) — return predictions

class SimpleDecisionTree:
    def fit(self, X, y):
        # X: list of dicts (features)
        # y: list of labels
        # combine X and y, call build_tree
        pass

    def predict(self, X):
        # return [self.root.check(row) for row in X]
        pass

class SimpleDecisionTree:
    def fit(self, X, y):
        features = list(X[0].keys())
        combined = [{**x, "__label__": yi}
                    for x, yi in zip(X, y)]
        self.root = build_tree(combined, features, "__label__")

    def predict(self, X):
        return [self.root.check(row) for row in X]

Train on the height+weight dataset:

X = [{"height": r["height"], "weight": r["weight"]} for r in data]
y = [r["gender"] for r in data]

clf = SimpleDecisionTree()
clf.fit(X, y)
predictions = clf.predict(X)

correct = sum(p == t for p, t in zip(predictions, y))
print(f"Accuracy: {correct}/{len(y)} = {correct/len(y)*100:.0f}%")

Accuracy: 20/20 = 100%

100% on training data — the tree splits until every leaf is pure.

Predict on new people:

clf.predict([
    {"height": 163, "weight": 54},   # → F
    {"height": 185, "weight": 91},   # → M
    {"height": 172, "weight": 65},   # → ?
])

Is 100% training accuracy a good thing?

Not necessarily. The tree has memorized the training data — including its noise and outliers.

This is overfitting. Solutions:

max_depth: stop splitting after N levels
min_samples: don’t split groups smaller than K
Random Forest: build many trees on random subsets, take a vote

What you just invented:

You built	Real name
$4pq$ mixing formula	Gini impurity (scaled)
Weighted split score	Information gain
Try every (feature, threshold)	Greedy split search
Recursive splitting	CART algorithm
`SimpleDecisionTree`	`sklearn.tree.DecisionTreeClassifier`

You didn’t learn decision trees. You invented them.

Glossary

Impurity: A number measuring how mixed a group is. Pure (all same label) = 0, maximally mixed (50/50) = 1.
Gini Impurity: The standard impurity formula: 2p(1−p). Equivalent to our 4pq up to a constant factor.
Threshold: A value that splits data into two groups: feature ≤ threshold goes left, feature > threshold goes right.
Decision Boundary: The best (feature, threshold) pair — the split that minimizes total impurity.
Leaf Node: A tree node with no children — it stores the final prediction (a label).
Boundary Node: A tree node with a splitting rule and two children (left and right subtrees).
Overfitting: When a model memorizes training data (including noise) and performs poorly on new data.

Part 1: The Mixing Problem~5 min

Part 2: Splitting a List~10 min

Part 3: Real Data — Height & Gender~10 min

Part 4: The Decision Node~5 min

Part 5: Growing the Tree~10 min

Part 6: The Payoff — fit & predict~5 min

Glossary