Đại học Kinh tế Quốc dân – National Economics UniversityMICRO4ASIA
🏆 Arena
Sign inSign up
MICRO4ASIAThe six micro-credentials

Courses are delivered on the Limio learning platform. Limio

← Fundamental of Machine Learning

You are viewing a public preview

Sign in to save your progress, do assignments, join discussions and get feedback.

Sign in
Module 2: Core Machine Learning Algorithms

2.5 Bootstrapping and Random Forest

Print / Save as PDF

2.5 Bootstrapping and Random Forest

After this unit you will be able to: describe bootstrapping and explain how a Random Forest differs from a single decision tree.

Key Points

  • Bootstrapping = random sampling with replacement from the original set, so an element can appear several times (for example {b, a, b, b}).
  • Random Forest = many decision trees, each trained on a different bootstrap set.
  • The final prediction (Prediction) is aggregated from the predictions of many trees instead of trusting a single tree.
  • Many different trees “voting” together make the model more stable than a single tree.

Study notes

By the end of this lesson you can:

  • Explain why a single decision tree is unstable and prone to overfitting
  • Describe bootstrapping as random sampling with replacement and recognise valid bootstrap samples
  • Explain how a Random Forest makes its trees different from each other
  • Describe how the forest combines predictions: majority vote for classification, average for regression
  • Name the scikit-learn classes for Random Forest

Key idea: A Random Forest trains many decision trees, each on a different bootstrap sample (and with random feature choices), then combines their predictions; the diversity of the trees makes the ensemble more robust and accurate than any single tree.

Why one tree is not enough

The lecture compares a single tree with a forest of eight colourful trees. Individual decision trees have a well-known weakness: they are unstable and prone to overfitting. They can learn the training data too specifically, including its noise, and then perform poorly on new, unseen data.

The fix is to build many different trees, each trained slightly differently, and then average or vote across all of them. Combining many individual models to get a better collective result is called an ensemble method, and Random Forest is one of the most popular ensemble methods in machine learning.

Bootstrapping: sampling with replacement

An obvious question: if every tree uses the same training data, won't all the trees be identical? The answer is bootstrapping, the key trick behind Random Forest.

Start with the full original dataset, for example the items A, B, C, D, E, F, G. Create several smaller random samples from it, and sample with replacement: after an item is picked, it goes back into the pool, so it can be picked again.

  • Sample D, E, F, D: D appears twice, while A and B do not appear at all.
  • Sample B, A, B, B: B appears three times, A once, and no other letter.

Each sample is a slightly different, randomly duplicated mix of the original data. A sample such as {a, a, d, g} drawn from {a, ..., g} is perfectly valid.

Making the trees diverse

If every tree trained on identical data, they would learn very similar patterns and the point of combining them would be lost: there would be no diversity of opinions. Random Forest creates diversity in two ways:

  1. each tree trains on its own bootstrap sample of the rows;
  2. in practice, each tree is also randomly restricted in which features it may consider when it splits.

As a result, each tree ends up a little different. This diversity is exactly what makes the ensemble more robust than a single tree.

The complete Random Forest pipeline

  1. Start from the original training set.
  2. Create several bootstrap samples (with replacement).
  3. Train one independent decision tree on each sample. The diagram shows three (yellow, green, orange); real forests often use 100 to 1,000 trees.
  4. For a brand-new example, every tree makes its own prediction.
  5. Combine the predictions:
    • classification: majority voting; the category with the most votes wins;
    • regression: the simple average of all the trees' predictions.

This "wisdom of the crowd" idea explains why Random Forest is still one of the most reliable algorithms in practice. In scikit-learn it is RandomForestClassifier for classification and RandomForestRegressor for regression.

Worked example

A forest of 7 trees is asked about a new loan application. The trees predict: Reject, Accept, Reject, Reject, Accept, Accept, Reject.

  1. Count the votes: Reject = 4, Accept = 3.
  2. Majority vote: Reject wins, so the forest predicts Reject.
  3. If this were a regression forest predicting a loan amount, say 100, 120, 110, 90, 130, the forest would output the average, 110.

The bootstrap step and the vote can be simulated in a few lines:

import numpy as np
from collections import Counter

rng = np.random.default_rng(0)
data = np.array(list("ABCDEFG"))

for i in range(3):
    sample = rng.choice(data, size=4, replace=True)  # with replacement
    print("bootstrap sample", i, sample)

votes = ["Reject", "Accept", "Reject", "Reject", "Accept", "Accept", "Reject"]
print(Counter(votes).most_common(1)[0][0])

Expected output: three random samples of 4 letters in which some letters may repeat and others are missing (the exact letters depend on the seed), followed by Reject, the majority vote.

In scikit-learn the whole pipeline is one object:

from sklearn.ensemble import RandomForestClassifier

model = RandomForestClassifier(n_estimators=100, random_state=100)
model.fit(x_train, y_train)
y_pred = model.predict(x_test)

Common mistakes

  • Thinking bootstrapping splits the data into separate pieces. It samples with replacement, so an item can appear several times in one sample and not at all in another.
  • Believing the trees differ only because of random luck. The difference is engineered: different bootstrap samples plus random feature restrictions.
  • Averaging class labels. For classification the forest uses a majority vote; averaging is for regression.
  • Assuming more trees always means overfitting. Adding trees mainly makes predictions more stable; the main risk of overfitting comes from individual deep trees, not the number of trees.

Summary

  • Single decision trees are unstable and tend to overfit.
  • Bootstrapping draws random samples with replacement, so each sample is a different mix of the data.
  • Each tree in a Random Forest trains on its own bootstrap sample and considers random subsets of features.
  • The forest combines trees by majority vote (classification) or averaging (regression).
  • scikit-learn: RandomForestClassifier and RandomForestRegressor.

Flashcards · 2.5 Bootstrapping and Random Forest

8 words
WordMeaningExample
  • Ensemble method

    A strategy that combines many individual models to produce a better collective prediction than any one of them.

    Random Forest combines many decision trees.

  • Bootstrapping

    Creating new samples by drawing randomly with replacement from the original dataset.

    From A..G, the sample D, E, F, D is valid.

  • Sampling with replacement

    Each picked item is returned to the pool, so it can be picked again in the same sample.

    B, A, B, B contains B three times.

  • Random Forest

    An ensemble of decision trees, each trained on a different bootstrap sample with random feature choices.

    100 trees vote on whether to approve a loan.

  • Majority voting

    How a classification forest combines trees: the class predicted by the most trees wins.

    4 trees say Reject, 3 say Accept -> Reject.

  • Averaging (regression forest)

    How a regression forest combines trees: it outputs the mean of all the trees' predictions.

    Trees predict 100, 120, 110 -> forest predicts 110.

  • Overfitting

    Learning the training data too specifically, including noise, so performance on new data is poor.

    A deep tree scores 100% on train but much lower on test.

  • RandomForestClassifier

    The scikit-learn class for Random Forest classification; RandomForestRegressor is the regression version.

    RandomForestClassifier(n_estimators=100, random_state=100)