Bagging from Scratch

What is Bootstrap Sampling?

Bootstrap sampling is a resampling method that involves drawing samples from a dataset with replacement.

Imagine you have a bag of marbles. If you sample with replacement, you:

1. Draw one marble and note its color.
2. Put the marble back into the bag.
3. Repeat the process.

Because you put the marble back each time, you might draw the same one multiple times. By contrast, if you sample without replacement, each marble can only be drawn once.

In machine learning, we apply this to our training data. A bootstrap sample is a new dataset of the same size as the original, but created by sampling with replacement.

This process of creating datasets via bootstrapping and then training a model on each one is the core idea of Bagging (Bootstrap Aggregating).

Implementing Bootstrap Sampling in Python

Given your background, you'll appreciate that the most efficient way to implement this is with NumPy. We can generate random indices with replacement and then use those indices to select data from our original arrays. This is much faster than looping in pure Python.

The logic is straightforward:

1. Determine the number of samples, n_samples, in the original dataset.
2. Generate an array of n_samples random indices, from 0 to n_samples - 1. The key is to allow these indices to be chosen more than once (replace=True).
3. Use this array of indices to create the new bootstrapped dataset from the original X and y.

Here is a Python function that accomplishes this:

import numpy as np

def bootstrap_sample(X, y):
    """
    Creates a bootstrap sample from the dataset.

    Args:
        X (np.ndarray): The feature matrix.
        y (np.ndarray): The target vector.

    Returns:
        tuple[np.ndarray, np.ndarray]: The bootstrapped feature matrix and target vector.
    """
    n_samples = X.shape[0]
    
    # Step 1: Generate random indices with replacement
    # np.random.choice is perfect for this. 'replace=True' is the key.
    bootstrap_indices = np.random.choice(
        n_samples, 
        size=n_samples, 
        replace=True
    )
    
    # Step 2: Use the indices to create the new dataset
    X_bootstrapped = X[bootstrap_indices]
    y_bootstrapped = y[bootstrap_indices]
    
    return X_bootstrapped, y_bootstrapped

# --- Example Usage ---
# Create some dummy data
X_original = np.array([[1,1], [2,2], [3,3], [4,4], [5,5]])
y_original = np.array([1, 2, 3, 4, 5])

# Generate a bootstrap sample
X_boot, y_boot = bootstrap_sample(X_original, y_original)

print("Original y:\n", y_original)
print("\nBootstrapped y:\n", y_boot) 
# You will likely see repeated and missing numbers here!

As you can see, the implementation is concise and powerful, leveraging NumPy's optimized array operations.

The following video walks through an almost identical implementation within the context of a full RandomForest class. Watching this will help solidify how our standalone function will fit into the larger algorithm.

While the NumPy approach is standard, it's worth noting other ways to achieve this.

def get_oob_sample(X, y, bootstrap_indices):
    """
    Gets the out-of-bag sample.
    """
    n_samples = X.shape[0]
    
    # Get all original indices
    all_indices = np.arange(n_samples)
    
    # Find the indices that are in 'all_indices' but NOT in 'bootstrap_indices'
    oob_indices = np.setdiff1d(all_indices, bootstrap_indices)
    
    # Use these indices to get the OOB data
    X_oob = X[oob_indices]
    y_oob = y[oob_indices]
    
    return X_oob, y_oob

# --- Example Usage (building on the previous one) ---
# In a real scenario, you'd modify bootstrap_sample to return the indices
# For now, let's re-generate them to demonstrate
n_samples = X_original.shape[0]
bootstrap_indices = np.random.choice(n_samples, size=n_samples, replace=True)

X_boot = X_original[bootstrap_indices]
y_boot = y_original[bootstrap_indices]

X_oob, y_oob = get_oob_sample(X_original, y_original, bootstrap_indices)

print("Bootstrap indices:", bootstrap_indices)
print("OOB y:", y_oob) # This will contain the labels that were not picked

Conclusion

You have successfully implemented bootstrap sampling, a cornerstone of modern ensemble methods. This simple but powerful technique is what allows a Random Forest to build a diverse set of decision trees, leading to a model with lower variance and often higher accuracy than any single tree alone.

Key Takeaways:

• Bootstrap Sampling means sampling from a dataset with replacement.
• The resulting bootstrap sample has the same size as the original dataset but typically contains duplicate entries and omits some original entries.
• Bagging (Bootstrap Aggregating) is the process of training multiple models on different bootstrap samples and combining their predictions.
• The most efficient way to implement this in Python is using numpy.random.choice with the replace=True parameter.

Preview of the Next Lesson:
We are now fully equipped to build our Random Forest. In the next lesson, we will combine the DecisionTree class from the previous lesson with the bootstrap_sample function you created today. We will orchestrate the training of many trees on different bootstrapped datasets and introduce the second element of randomness—feature subsampling—to complete our RandomForest implementation.