Learning Decision Trees by Inventing Them

Imagine a bag of coloured balls — some Red, some Black.

We want a number that captures how mixed the bag is:

• A bag of all Red → not mixed at all → impurity = 0
• A bag of all Black → not mixed at all → impurity = 0
• A bag of half Red, half Black → maximally mixed → impurity = 1

impurity(0.5, 0.5)  →  1       # maximally mixed: impurity is 1
impurity(0, 1)      →  0       # all one colour:  impurity is 0
impurity(1, 0)      →  0

Important: Here impurity = 0 means completely pure (easy to classify), and impurity = 1 means maximally mixed (hard to classify).

Before coding, answer these questions:

1. If a bag has 80% Red and 20% Black, would its impurity be closer to 0 or 1? Why?
2. What is impurity(0.9, 0.1)? Higher or lower than impurity(0.8, 0.2)?
3. What mathematical property must the function impurity(p, q) have when p = 1 - q?
4. Is impurity(p, q) the same as impurity(q, p)? Why should it be?

We're going to invent the formula for impurity(p, q) where:

• p = fraction of Red balls (between 0 and 1)
• q = fraction of Black balls (between 0 and 1)
• p + q = 1 always

Step A: Consider the function $f(p) = p \times (1 - p)$. Fill in the table below by computing it:

Tasks:

1. Compute the table values in Python and print them.
2. What is the maximum value of $p \times (1 - p)$? At what p does it occur?
3. What are the minimum values? When do they occur?
4. Plot $f(p) = p \times (1 - p)$ for $p \in [0, 1]$ using the helper below.
5. Does this function behave like our desired impurity? Where are its max and min?

From Exercise 1.2, you found that $f(p) = p \times (1-p)$ peaks at $p = 0.5$ with a value of $0.25$.

But we want impurity(0.5, 0.5) = 1 (max impurity = 1, not 0.25).

So we need a function that:

• Returns 1 when p = 0.5 (most uncertain)
• Returns 0 when p = 0 or p = 1 (most certain)

Your task:

Take $f(p) = p \times (1 - p)$ and apply a simple transformation so that its maximum becomes 1.

1. Find the transformation mathematically (algebra only, no code yet).
2. Write the resulting formula.
3. Verify by plugging in: $p = 0.5$, $p = 0$, $p = 1$.
4. Write it in Python as def impurity(p, q) and plot it.

Your derivation:

• Maximum of f(p) = p*(1-p) is ... at p = ...
• Transformation: ...
• Final formula: impurity(p) = ...
• Check p=0.5: ...
• Check p=0: ...
• Check p=1: ...

Now that you have impurity(p, q), explore it.

Tasks:

1. Compute and print the impurity for the following bags. Do the results match your intuition?

2. Is bag A more or less certain than bag B? Does impurity agree?
3. Is impurity(0.3, 0.7) equal to impurity(0.7, 0.3)? Why should it be?
4. What is the impurity of a bag with 50 Red, 50 Black, and 50 Green (3 classes)?
   • Bonus: Can you extend your formula? Think about what $p \times (1-p)$ means for each pair of classes.

A group contains 50 apples and 50 oranges. Another group contains 95 apples and 5 oranges. Which group has higher impurity?

A. The 95/5 group — it has more items

B. The 50/50 group — it is the most mixed, so predicting the label of a random item is hardest

C. Both have the same impurity

D. Impurity can only be computed with the formula, not by intuition

So far, impurity(p, q) takes fractions directly. But in practice, you have a list like:

["R", "B", "B", "R", "R"]

You need to compute p and q from the list yourself.

Tasks:

1. For the list ["R", "B", "B", "R", "R"], manually compute:
   • Count of "R"
   • Count of "B"
   • Total count
   • p (fraction of R)
   • q (fraction of B)
2. Write a function list_impurity(items) that:
   • Takes a list of "R" and "B" strings
   • Computes p and q
   • Returns impurity(p, q)
   • Edge case: What should it return for an empty list []? Decide and document your choice.

3. Test your function:

   list_impurity(["R", "B", "B", "R", "R"])   # what do you expect?
   list_impurity(["R", "R", "R", "R"])         # all same → what value?
   list_impurity(["B", "B", "B", "B"])         # all same → what value?
   list_impurity(["R", "B"])                   # exactly half → what value?
   list_impurity([])                           # empty → your decision
   

4. Try these additional lists and rank them by impurity (most mixed to least mixed):

   list_A = ["R", "R", "R", "R", "R", "R", "R", "R", "B", "B"]
   list_B = ["R", "R", "R", "R", "R", "B", "B", "B", "B", "B"]
   list_C = ["R", "R", "R", "R", "R", "R", "R", "B", "B", "B"]
   

When we split a list into two parts, we get two separate impurity values — one for each part.

But how do we combine them into one number?

Think about it: If one group has 100 items and another has 2 items, should they count equally?

Your task:

1. Invent a formula for the total impurity of two groups, left and right, that accounts for their sizes.
   • What should happen if one group is empty?
   • What should happen if both groups are identical?
2. Write a function total_impurity(left, right) that takes two lists and returns a single number.

3. Test it:

   total_impurity(["R", "R", "R"], ["B", "B", "B"])  # perfectly separated
   total_impurity(["R", "B", "R"], ["B", "R", "B"])  # each group is mixed
   total_impurity(["R"]*9 + ["B"], ["B"])             # unequal sizes
   

4. Reflection: For the last test case, the right group has 1 item (["B"]) so it's pure (impurity = 0). But it only has 1 item out of 11 total. Does your formula give it less weight? It should.

You are given an ordered list:

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

You can split it at position k (0-indexed), meaning:

• Left part: items[:k] — the first k items
• Right part: items[k:] — the remaining items

For example, splitting at position k=2:

• Left: ["R", "B"]
• Right: ["B", "R", "R"]

Tasks:

1. For items = ["R", "B", "B", "R", "R"], print the left and right parts for every possible split position k = 1, 2, 3, 4.
   • (Why not k=0 or k=5? What would those give?)
2. For each split position, compute total_impurity(left, right). Print all values.
3. Which split position gives the minimum total impurity?
   • What are the left and right groups at that position?
   • Does that split make intuitive sense?

Now automate it: write a function find_best_split_position(items) that:

• Tries every possible split position k = 1 to len(items) - 1
• Computes total_impurity at each position
• Returns the position k that gives the minimum total impurity

Tasks:

1. Implement find_best_split_position(items). It should return the best k and the minimum total impurity.

2. Test it on these lists:

   ["R", "B", "B", "R", "R"]
   ["R", "R", "R", "B", "B", "B"]
   ["B", "R", "B", "R", "B", "R"]
   ["R", "R", "R", "R", "B"]
   

3. For ["R", "R", "R", "B", "B", "B"], the answer should be obvious from visual inspection. Does your function agree?

4. For ["B", "R", "B", "R", "B", "R"] (perfectly alternating), what split position does it find? Are there multiple "tied" positions?

Use the plotting helper below to visualise how total impurity changes at each split position.

Tasks:

1. Run plot_split_scores on all four test lists from Exercise 3.2.
2. For ["R", "R", "R", "B", "B", "B"]: is the minimum sharp or flat? Why?
3. For ["B", "R", "B", "R", "B", "R"]: what does the plot look like? Is there a clear winner?

You are given a dataset of students in a class. Each student has a height (in cm) and a gender ("M" or "F").

Before coding, answer these questions:

1. Just by looking at the data, at roughly what height does gender start being predominantly Male?
2. If you had to draw a single horizontal line through the data to separate M from F as cleanly as possible, where would you draw it?
3. Is a perfect separation possible? Why or why not?

Run the plotting helper below to see the data.

Call plot_height_gender(heights, genders) to see the scatter plot.

Now the key idea: instead of splitting at a position in a list, we split at a threshold value in a feature.

For a given threshold t:

• Left group: all rows where height <= t
• Right group: all rows where height > t

Tasks:

1. Write a function split_by_threshold(heights, genders, t) that:
   • Splits the data at threshold t
   • Returns (left_genders, right_genders)
2. Test it: split_by_threshold(heights, genders, 172) should return the genders of everyone with height <= 172 and height > 172.

3. For the thresholds below, compute and print total_impurity(left, right):

   t = 160, 165, 170, 172, 175, 178, 182, 185, 188
   

4. Which threshold gives the lowest total impurity? Verify visually using plot_height_gender with split_height=t.

Instead of manually trying thresholds, automate it.

Key insight: You only need to try thresholds at the unique values in your data. Why? Because splitting at 173.5 vs 174 makes no difference if there's no data point between them.

Tasks:

1. Write find_best_threshold(heights, genders) that:
   • Tries every unique height value as a threshold
   • Computes total_impurity for each
   • Returns the threshold with minimum total impurity, and that minimum impurity value
2. Run it and print the result. Does it match your manual inspection?
3. Visualise the best threshold using plot_height_gender(heights, genders, split_height=best_t).
4. Reflection: What are the genders in the left and right groups at the best threshold? Is the split clean?

Use the plotting helper below to visualise how impurity changes as the threshold varies.

Run plot_threshold_scores(heights, genders) and observe the curve.

Your algorithm found that the best split for a height-based gender classifier is at 167 cm. What does this threshold mean for prediction?

A. Everyone shorter than 167 cm is male

B. People below 167 cm get the majority label of the left group, and people at or above get the majority label of the right group

C. 167 cm is the average height in the dataset

D. People exactly at 167 cm cannot be classified

Before we build a full tree from data, let's understand the structure of a decision tree by constructing one by hand.

A decision tree is made of nodes. There are two kinds:

• Boundary node: Has a rule — "if feature X <= value, go left; else go right." Has two children.
• Leaf node: Has a final answer — just True (YES) or False (NO). No children.

Here is a tree for deciding whether to accept a job offer:

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

Before coding, answer these questions:

1. If a job pays 800 and is 20km away — what does the tree say?
2. If a job pays 1200 and is 30km away — what does the tree say?
3. If a job pays 1500 and is 60km away — what does the tree say?
4. If a job pays 1000 exactly — which branch do you take? (Careful: the rule is salary > 1000.)

Your answers:

1. salary=800, distance=20 → ...
2. salary=1200, distance=30 → ...
3. salary=1500, distance=60 → ...
4. salary=1000, distance=any → ...

Design a class DecisionTreeNode that can be either a boundary node or a leaf node.

Requirements:

• A leaf node stores a boolean decision (True = YES, False = NO).
• A boundary node stores:
  • boundary — the feature name (a string, e.g. "salary")
  • boundary_value — the threshold (a number)
  • left — the child node for when feature <= boundary_value
  • right — the child node for when feature > boundary_value
• A method check(features) that:
  • Takes a dict like {"salary": 1200, "distance": 30}
  • Traverses the tree
  • Returns the leaf's boolean decision

Also create two helper functions:

• YES() — returns a leaf node with decision True
• NO() — returns a leaf node with decision False

Tasks:

1. Implement DecisionTreeNode, YES(), and NO().
2. Build the job offer tree manually:

   Is salary <= 1000? → NO()
   Else: Is distance <= 40? → YES() else NO()
   

3. Test it against your answers from Exercise 5.1.

Class structure hint:

class DecisionTreeNode:
    def __init__(self, ...):
        # your attributes here
        pass

    def check(self, features):
        # if leaf: return decision
        # if boundary: go left or right
        pass

Now build a more complex tree by hand. This tree has 3 levels:

Is salary <= 1000?
├── YES → NO (reject)
└── NO (salary > 1000):
    Is distance <= 40?
    ├── YES (close enough):
    │   Is coffee == 1?         ← 1 means "office has free coffee"
    │   ├── YES → YES (accept)
    │   └── NO  → NO (reject)
    └── NO (too far) → NO (reject)

Tasks:

1. Build this tree using DecisionTreeNode, YES(), and NO().
2. Test with these job offers:

3. Extend the tree by adding one more rule of your own. Document what you added.

Now the dataset has two features: height and weight. We want to find which feature and which threshold gives the best split.

The question: Should we split on height or weight, and at what value?

Write a function find_decision_boundary(data, features, label) that:

• Takes a list of dicts (data), a list of feature names (features), and the label column name (label)
• For each feature:
  • Tries every unique value of that feature as a threshold
  • Computes total_impurity for that split
• Returns the best feature name, the best threshold, and the minimum impurity

Tasks:

1. Implement find_decision_boundary.
2. Run it on the dataset with features=["height", "weight"] and label="gender".
3. Print the result. Which feature won? At what threshold?
4. Does this match what you expected from looking at the data?

Use the helper below to visualise both the height split and the weight split.

Tasks:

1. Use find_decision_boundary on each feature separately.
2. Plot the best height split and the best weight split.
3. Which feature gives a cleaner separation?

After the first split, you have two groups. Each group may still be impure (mixed).

The idea: repeat the splitting on each group independently, until each group is pure or has only 1 element.

Before coding, trace through manually using the height-only dataset from Part 4:

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"]

1. What is the best first split threshold? (You found this in Part 4.)
2. After splitting, what are the left and right groups?
3. Is the left group pure? Is the right group pure?
4. For the impure group(s), what is the best next split?
5. Draw this out as a tree structure.

Your manual tree sketch:

height <= ???
├── Left: ???  (pure? yes/no)
│   └── If not pure, split again at height <= ???
│       ├── ...
│       └── ...
└── Right: ???  (pure? yes/no)
    └── If not pure, split again at height <= ???
        ├── ...
        └── ...

Before writing the recursive function, think about when to stop.

When should we NOT split further?

1. The group has only 1 element — nothing to split.
2. The group is completely pure — all same label. No need to split.
3. (Optional): All elements have the same feature values — we can't find a meaningful threshold.

When we stop, what do we return? A leaf node with the majority label in that group.

Tasks:

1. Write a helper majority_label(labels) that takes a list of labels and returns the most common one. Document your tie-breaking rule.
2. Write a helper is_pure(labels) that returns True if all labels are the same.
3. Test both helpers:

   majority_label(["M", "M", "F", "M"])  # → "M"
   majority_label(["F", "M"])            # → tie: your choice
   is_pure(["M", "M", "M"])             # → True
   is_pure(["M", "M", "F"])             # → False
   

Now write build_tree(data, features, label) that:

1. Base case: If data is empty, or has 1 element, or is pure — return a DecisionTreeNode leaf with the majority label.
2. Recursive case:
   • Find the best feature and threshold using find_decision_boundary.
   • Split data into left_data and right_data.
   • Recursively call build_tree on each.
   • Return a DecisionTreeNode boundary node with the two subtrees.

Important: The leaf node now stores a label string (like "M" or "F"), not just True/False. You may need to adapt your DecisionTreeNode slightly.

Tasks:

1. Implement build_tree(data, features, label).
2. Run it on the height+weight dataset from Part 6.
3. Write a helper print_tree(node, depth=0) that prints the tree in an indented format:

[height <= 175]
  LEFT:
    [weight <= 63]
      LEFT:  LEAF → F
      RIGHT: LEAF → M
  RIGHT:
    LEAF → M

Now use your built tree to predict the gender of each row in the original data.

Tasks:

1. Use tree.check(row) to predict the gender for each row.
2. Compare the prediction to the true label.
3. Count how many predictions are correct. What is the accuracy (correct / total)?
4. Which rows does the tree get wrong? Can you explain why?

A decision tree is allowed to grow until every leaf contains exactly one data point. It achieves 100% accuracy on the training data. Is this a good model?

A. Yes — 100% accuracy means perfect predictions

B. Probably not — it has likely memorized the training data (including noise) and will perform poorly on new, unseen data

C. It depends on whether the data is sorted

D. No — decision trees can never achieve 100% accuracy

Real ML libraries use a standard interface:

• fit(X, y) — train the model on data X (features) and labels y
• predict(X) — given new data, return predictions

Here, X will be a list of dicts (one per sample), and y will be a list of labels.

Before coding, think about these questions:

1. In fit(X, y): how do you know which features to try splitting on?
2. In predict(X): X is a list of rows — so predict should return a list of predictions.
3. What should a leaf return when check is called on it?

Your answers:

1. Features to split on: ...
2. predict returns: ...
3. Leaf behaviour: ...

Wrap everything into a clean class:

class SimpleDecisionTree:
    def fit(self, X, y):
        """
        X : list of dicts (each dict is one row of features)
        y : list of labels (strings or booleans)
        Builds the decision tree and stores it in self.root.
        """
        pass

    def predict(self, X):
        """
        X : list of dicts
        Returns a list of predicted labels, one per row.
        """
        pass

Tasks:

1. Implement SimpleDecisionTree using build_tree inside fit.
2. Combine X and y inside fit to pass to build_tree.

3. Test it on the height+weight dataset:

   X = [{"height": row["height"], "weight": row["weight"]}
        for row in data]
   y = [row["gender"] for row in data]
   
   clf = SimpleDecisionTree()
   clf.fit(X, y)
   predictions = clf.predict(X)
   

4. Compute accuracy.

5. Now predict on some new unseen data:

   new_people = [
       {"height": 163, "weight": 54},   # your guess: F or M?
       {"height": 185, "weight": 91},   # your guess: F or M?
       {"height": 172, "weight": 65},   # your guess: F or M?
   ]
   

Use your print_tree function to display the tree learned by SimpleDecisionTree.

Tasks:

1. Call print_tree(clf.root).
2. How deep is the tree? Count the levels.
3. Does the tree make intuitive sense? Are the splits reasonable?
4. What would happen if you trained on a dataset with more noise — would the tree be deeper or shallower? Why?

If you've made it here, you've built a decision tree from scratch — impurity formula, split search, recursive tree growth, and a full ML-style class. Here are open-ended extensions.

Your tree keeps splitting until each leaf is pure. This can lead to overfitting — the tree memorises the training data but won't generalise to new data.

Add a max_depth parameter to SimpleDecisionTree (and build_tree):

• If the current depth equals max_depth, stop and return a leaf regardless of purity.

Tasks:

1. Try max_depth=1, 2, 3. How does accuracy on the training set change?
2. What does the tree look like with max_depth=1? This is called a decision stump.
3. In general: deeper tree = higher training accuracy. Is that always better? Why not?

Another way to prevent overfitting: don't split a group if it has fewer than min_samples rows.

Add a min_samples parameter: if len(data) < min_samples, return a leaf.

Try min_samples=1 (default) vs min_samples=3 vs min_samples=5. How does the tree structure change?

Try your tree on the Iris dataset — a classic ML benchmark.

from sklearn.datasets import load_iris
iris = load_iris()

feature_names = iris.feature_names  # 4 features
X_iris = [dict(zip(feature_names, row)) for row in iris.data]
y_iris = [iris.target_names[t] for t in iris.target]

Tasks:

1. Fit your SimpleDecisionTree on the Iris dataset.
2. Compute training accuracy.
3. Print the tree. How deep is it?
4. Compare to sklearn.tree.DecisionTreeClassifier. Do they make the same splits?
5. Bonus: Split into train/test sets (80/20) and measure test accuracy.

The impurity function you invented is based on $p(1-p)$. Look up Gini impurity:

$$\text{Gini} = 1 - \sum_k p_k^2$$

where the sum is over all classes $k$, and $p_k$ is the fraction of class $k$.

Tasks:

1. For two classes (R and B), write out the Gini formula in full.
2. Is it the same as your formula, or different?
3. Replace your impurity function with the Gini formula and re-run everything. Do the results change?
4. Look up Entropy as another impurity measure. Try implementing that too.

Take a moment to answer these questions in your own words.

1. What is impurity? Why does it matter for decision trees?
2. What is a decision boundary? How did you find the best one?
3. What is recursive splitting? When does it stop?
4. What is overfitting? How does a decision tree overfit, and how can you prevent it?
5. What does fit do? What does predict do?
6. What would a Random Forest be? (Think: what if you built many trees on random subsets of data and features, then took a vote?)

What you just invented: a complete decision tree classifier — from the impurity measure ($4pq$, equivalent to Gini impurity up to a constant factor), through the greedy split-search algorithm (try every feature and threshold, pick the one that minimizes weighted impurity), to recursive tree growth with stopping conditions, and finally a scikit-learn-style fit/predict interface. This is exactly how sklearn.tree.DecisionTreeClassifier works under the hood.