Random Forests --- Inventing Ensemble Learning

The classification tree asked: "how mixed are the labels in this group?" For numbers the question becomes: "how spread out are the values?"

Look at these two groups of house prices (in lakhs):

group_a = [10, 10, 10, 10, 10]     # everyone agrees
group_b = [1, 50, 3, 80]           # wild disagreement

If a leaf of your tree contains group_a, predicting their mean (10) is perfect. If it contains group_b, predicting the mean (33.5) is terrible for every single house.

Invent a single number that is 0 when all values are identical and grows as the values spread out. Try to come up with your own formula before reading on.

The classic answer is variance: the average squared distance from the mean. (Why squared? So that being 10 below the mean can't cancel out being 10 above it --- and big misses get punished extra hard.)

Write variance(values).

Take this group: values = [10, 9, 11, 8, 10, 1]. It has one troublemaker.

Split it into left = [10, 9, 11, 8, 10] and right = [1]. Now left is nearly pure and right is exactly pure (a single value has zero variance).

But there's a trap: [1] having zero variance shouldn't count as much as a five-element group having zero variance --- otherwise the tree learns to slice off one element at a time.

Your challenge: Simply adding the two variances treats a 1-element group the same as a 5-element group --- that can't be right. How should you combine the two variances so that a larger group's variance counts more? Think about what "fraction of elements" each side holds and use that to weight the variances.

Write total_variance(left, right).

A split is good when the children are much purer (lower variance) than the parent. You have the parent's variance and the children's combined (weighted) variance. How would you capture "how much purer did the split make things" in one number?

Write variance_reduction(parent, left, right).

Then check: for [10, 9, 11, 8, 10, 1], splitting the troublemaker off should score much higher than splitting down the middle.

In the classification decision tree chapter, you used impurity (mixing of labels) to evaluate splits. Now for regression, you use variance instead. Why the change?

A. Variance is faster to compute than impurity

B. Regression targets are continuous numbers, not categories --- you can't count "how mixed" the labels are when labels are numbers like 23.5 or 41.2, but you CAN measure how spread out they are

C. Variance works for classification too, so impurity was unnecessary

D. Python's standard library only has a variance function, not an impurity function

Here is a tiny housing dataset. Each row is [size_sqft, bedrooms]; the target is the price.

Using your variance_reduction, compute the reduction for two candidate splits, and see which feature the tree should ask about first:

• Size <= 1000: prices split into [50, 55, 65] vs [150, 160, 170]
• Bedrooms < 3: prices split into [50, 55] vs [65, 150, 160, 170]

Trying splits by hand doesn't scale. Write find_best_split(X, y, feature_indices=None) that:

1. Considers every feature index (or only feature_indices if given --- you'll see why that parameter matters in Part 4).
2. For each feature, takes the midpoints between consecutive sorted unique values as candidate thresholds (e.g. sizes 500, 600, 900, ... give thresholds 550, 750, 1200, ...).
3. For each candidate t, splits the targets into rows with x[feature] <= t (left) and the rest (right), and computes the variance reduction.
4. Returns the best (feature, threshold, reduction) --- keep the first candidate when there's a tie.

If there is nothing to split (no candidates), return (None, None, 0.0).

Left alone, the tree splits until every leaf holds a single house --- that's not learning, it's memorization: perfect on training data, brittle on anything new. Two brakes prevent it:

• max_depth --- the maximum number of questions from root to leaf. A shallow tree is forced to generalize.
• min_samples_split --- the smallest group still allowed to be split. Splitting a 2-house group into two 1-house "groups" scores a perfect variance reduction, and learns nothing.

There's nothing to compute here --- just convince yourself why each brake prevents memorization. You'll wire both into the tree next.

A tree is made of nodes. A decision node holds a question (feature, threshold) and two children; a leaf holds only a value (the prediction: the mean of the targets that reached it). Run this as-is.

Now assemble everything into a DecisionTree class:

class DecisionTree:
    def __init__(self, max_depth=5, min_samples_split=2,
                 feature_indices=None):
        ...
    def fit(self, X, y):
        ...
    def predict(self, X):
        ...

fit grows the tree recursively, starting at depth 0. A group becomes a leaf (value = mean of its targets) when any brake fires:

• depth has reached max_depth, or
• the group has fewer than min_samples_split rows, or
• find_best_split finds no split with reduction > 0.

Otherwise: split the rows on the best (feature, threshold) and recurse into each side with depth + 1. Pass feature_indices through to find_best_split.

predict walks each row from the root --- go left if row[feature] <= threshold --- and returns the leaf's value.

Your deep tree scored a perfect 0.00 RMSE on its training data. That should make you suspicious, not proud --- it memorized.

Here's the big idea: train many trees and average their predictions. Individual mistakes point in different directions and cancel out; the shared signal survives. (The same reason a crowd's average guess of a jar's jellybean count beats almost every individual guess.)

But wait. If every tree sees exactly the same data, every tree is identical:

tree1 predicts 50,  tree2 predicts 50,  tree3 predicts 50 ... average: 50

Averaging identical trees gives you... one tree. To benefit from a crowd, the trees must be different. Random Forests inject randomness in two places.

Give each tree its own dataset by sampling n rows from the original n rows with replacement --- some rows appear twice, some not at all. This is called a bootstrap sample.

Write bootstrap_sample(X, y) that returns a new (X_sample, y_sample) of the same length, where each position holds a uniformly random row of the original data --- and each y stays paired with its X row. Use random.randint.

Bootstrap samples still look similar, so most trees would still put the strongest feature (here: size) at the root --- the crowd stays too agreeable. Second injection of randomness: let each tree see only a random subset of the features.

Write choose_features(n_features, max_features) that returns max_features distinct feature indices chosen at random from 0 .. n_features - 1. (random.sample is your friend.)

This is why find_best_split takes that feature_indices parameter.

In a random forest, each tree is trained on a random bootstrap sample AND considers only a random subset of features at each split. Why does this randomness improve the final prediction?

A. Random trees run faster because they see less data

B. Randomness makes each tree different, so their errors are independent --- averaging independent errors cancels them out, while averaging identical errors would not

C. It prevents Python from running out of memory

D. Random selection always finds better splits than checking all features

Write RandomForestRegressor:

class RandomForestRegressor:
    def __init__(self, n_estimators=10, max_depth=3,
                 min_samples_split=2, max_features=None):
        ...
    def fit(self, X, y):
        ...
    def predict(self, X):
        ...

fit: for each of n_estimators trees --- take a bootstrap sample, choose a random feature subset (all features if max_features is None), train a DecisionTree on the sample with those feature_indices, and store it in self.trees.

predict: ask every tree, and return the average of their answers for each row.

Look at your numbers. The single deep tree hit 0.00 train RMSE (memorization) --- yet on this tiny, perfectly clean dataset its test error may still beat the forest's. So was all this for nothing?

No --- but the win shows up under real conditions. Reason through each:

1. Add measurement noise to the prices (e.g. y + random.gauss(0, 15) per row). Which model's test error degrades more, and why? (Try it!)
2. The single tree changes drastically if you delete one training row --- the forest barely moves. Why does averaging make predictions stable?
3. Why is max_features more valuable when you have 50 features than when you have 2?

You have now invented, from scratch, the algorithm behind scikit-learn's RandomForestRegressor. The next big idea in tree ensembles --- training each new tree on the errors of the previous ones --- is called gradient boosting (XGBoost, LightGBM). You already own every ingredient it needs.