Random Forest Classifier: Bagging and Feature Randomness

The "Random" in Random Forest

As we discussed, a Random Forest builds multiple decision trees and aggregates their votes. This is an example of ensemble learning. We already have one source of randomness from our bootstrap_sample function, a technique known as bagging.

However, relying on bagging alone can be problematic. If our dataset has a few very strong, dominant features, most of the bootstrapped trees will discover these features and use them for the top splits. This results in highly correlated trees that all behave similarly. The ensemble doesn't gain much from combining many near-identical models.

To solve this, Random Forests introduce a second source of randomness:

Feature Randomness: At each split point within each tree, only a random subset of the total features is considered.

By forcing each tree to consider a different subset of features at each split, we prevent any single feature from dominating all the trees. This de-correlates the trees, making them more diverse. When we average their predictions, the errors from individual trees tend to cancel each other out, leading to a more robust and accurate final model.

Implementing the RandomForest Class

We will structure our RandomForest classifier as a Python class. This class will orchestrate the creation, training, and prediction processes of all the individual decision trees it contains. We'll build it method by method.

1. The __init__ Method

The constructor will initialize the hyperparameters for the forest and create a list to hold the individual trees. The key hyperparameters are:

• n_trees: The number of decision trees to build in the forest.
• min_samples_split: Passed down to each decision tree.
• max_depth: Passed down to each decision tree.
• n_feats: The number of features to consider at each split. If None, all features are used. This is the parameter that controls feature randomness.

import numpy as np
from collections import Counter

# Assume you have your DecisionTree class from the previous lesson
# and the bootstrap_sample function in the same file or imported.

class RandomForest:
    def __init__(self, n_trees=100, min_samples_split=2, 
                 max_depth=100, n_feats=None):
        self.n_trees = n_trees
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.n_feats = n_feats
        self.trees = []

    # fit() and predict() methods will go here

To implement this, you'll first need to modify your DecisionTree's building logic (e.g., in your _grow_tree or _best_split method) to accept the n_feats parameter. Before iterating through features to find the best split, you'll select a random subset of them:
subset_feature_indices = np.random.choice(all_feature_indices, self.n_feats, replace=False)

2. The fit Method

This is where the training happens. The logic is a direct translation of the Random Forest algorithm:

1. Initialize an empty list for the trees.
2. Loop n_trees times.
3. In each iteration:
   a. Create a bootstrapped sample of the data using the function from our last lesson.
   b. Instantiate a new DecisionTree with the specified hyperparameters (max_depth, min_samples_split, n_feats).
   c. Train this tree on the bootstrapped sample.
   d. Add the trained tree to the list.

The following video provides an excellent walkthrough of implementing the fit method.

Here is the code for the fit method, integrating the concepts from the video:

# Continuing the RandomForest class
    def fit(self, X, y):
        """Trains the random forest model."""
        self.trees = []
        for _ in range(self.n_trees):
            # 1. Create a DecisionTree instance
            tree = DecisionTree(
                min_samples_split=self.min_samples_split,
                max_depth=self.max_depth,
                n_feats=self.n_feats
            )
            
            # 2. Create a bootstrapped sample
            X_sample, y_sample = bootstrap_sample(X, y)
            
            # 3. Train the tree on the sample
            tree.fit(X_sample, y_sample)
            
            # 4. Add the trained tree to the forest
            self.trees.append(tree)

3. The predict Method

Once the forest is trained, making a prediction involves getting a vote from every tree and choosing the most popular one. This is called majority voting.

The predict method implements this logic:

1. For a given set of input samples X, get the predictions from each tree in self.trees. This will give you a list of prediction arrays.
2. Transpose this structure so you have, for each input sample, a list of all the votes it received from the trees.
3. For each sample's list of votes, find the most common label. This is the final prediction for that sample.

The video you just watched also covers the implementation of the predict method.

Drawing from the video, the predict method would look like this. Note that we need a helper function for the majority vote, which is the same _most_common_label function from your DecisionTree implementation.

# Helper function (can be outside the class)
def most_common_label(y):
    """Finds the most common label in a list of labels."""
    counter = Counter(y)
    most_common = counter.most_common(1)[0][0]
    return most_common

# Continuing the RandomForest class
    def predict(self, X):
        """Makes predictions with the trained random forest."""
        # Get predictions from all trees
        tree_preds = np.array([tree.predict(X) for tree in self.trees])
        
        # tree_preds shape is (n_trees, n_samples). We want (n_samples, n_trees)
        # to easily iterate over each sample's predictions.
        tree_preds = np.swapaxes(tree_preds, 0, 1)
        
        # For each sample, get the most common prediction (majority vote)
        y_pred = [most_common_label(tree_pred) for tree_pred in tree_preds]
        
        return np.array(y_pred)

For a complete, text-based code example that ties everything together, you can refer to the following article.

Conclusion

Congratulations! You have now assembled a fully functional Random Forest classifier from scratch. You've combined your DecisionTree weak learner with the two core concepts of ensemble learning that define this algorithm:

• Bootstrap Aggregating (Bagging): Training each tree on a different random subset of the data (with replacement).
• Feature Subsampling: Considering only a random subset of features at each split to de-correlate the trees.

The final prediction is made by aggregating the votes of all trees in the forest. You have successfully implemented the fit method to orchestrate the training and the predict method to perform the majority vote.

Key Takeaways:

• A RandomForest is an ensemble of DecisionTrees.
• It uses bagging and feature randomness to create a diverse set of trees, making the model robust to overfitting.
• The fit method trains many individual trees on bootstrapped data samples.
• The predict method aggregates predictions from all trees using a majority vote.

Preview of the Next Lesson:
In the previous lesson, we touched on the idea of "Out-of-Bag" (OOB) samples—the data points that are not selected in a particular bootstrap sample. These OOB samples provide a powerful way to evaluate our model's performance without needing a separate validation set. In the next lesson, we will implement out-of-bag (OOB) error estimation to get a reliable measure of our model's generalization ability "for free" during the training process.