Ch 8.2.1, 8.2.2: Bagging and Random Forests

Lecture 25 - CMSE 381

Michigan State University
::
Dept of Computational Mathematics, Science /span> Engineering

Fri, Mar 27, 2026

Announcements

Last time:

8.1 Decision Trees - regression
8.1 Decision Trees - classification

This lecture:

8.2.1 Bagging
8.2.2 Random forest

Announcements:

Homework 5 Due Sunday

Course schedule for weeks 21-33 covering
splines, trees, SVM, neural networks, with
Midterm 3 and project deadlines marked.

Section 1

Previously

First decision tree example

Table displaying
baseball hitter data
with columns for Hits,
Years, and LogSalary

Regression tree for baseball
player salaries splitting on Years
and Hits to produce three leaf
nodes

Viewing Regions Defined by Tree

Scatter plot of Hits versus Years
partitioned into three regions R1, R2, and
R3 by a regression tree.

How do we actually get the tree? Two steps

: We divide the predictor space – that is, the set of possible values for $X_{1}, X_{2}, \dots, X_{p}$ — into $J$ distinct and non-overlapping regions, $R_{1}, R_{2}, \dots, R_{J}$ .
: For every observation that falls into the region $R_{j}$ , we make the same prediction $=$ the mean of the response values for the training observations in $R_{j}$ .

A two-dimensional feature space
partitioned into five rectangular regions
R1 through R5 by vertical and horizontal
splits

Recursive binary splitting

Goal:

Find boxes $R_{1}, \dots, R_{J}$ that minimize

\sum_{j = 1}^{J} \sum_{i \in R_{j}} {(y_{i} - ŷ_{R_{j}})}^{2}

$ŷ_{R_{j}} =$ mean response for training observations in $j$ th box

Pick $s$ so that splitting into ${X ∣ X_{j} /mo> s} and {X ∣ X_{j} \geq s} results in largest possible reduction in RSS:$

\begin{array}{l} R_{1} (j, s) = {X ∣ X_{j} /mo> s} & R_{2} (j, s) = {X ∣ X_{j} \geq s} \end{array}

\sum_{i ∣ x_{i} \in R_{1} (j, s)} {(y_{i} - ŷ_{R_{1}})}^{2} + \sum_{i ∣ x_{i} \in R_{2} (j, s)} {(y_{i} - ŷ_{R_{2}})}^{2}

Classification version

Large, complex classification tree for heart
disease predicting Yes or No based on
numerous clinical features and splits

Plot of classification error versus tree size
for Training, Cross-Validation, and Test
sets, with error bars for each Classification
tree for heart disease predicting Yes or No
based on splits of Thal, Ca, MaxHR, and
ChestPain

Evaluating the splits:

${\hat{p}}_{𝑚𝑘} =$ proportion of training observations in $R_{m}$ from the $k$ th class
Error: $E = 1 - max_{k} ({\hat{p}}_{𝑚𝑘})$
Gini index:

G = \sum_{k = 1}^{K} {\hat{p}}_{𝑚𝑘} (1 - {\hat{p}}_{𝑚𝑘})

Linear models vs trees

Two plots comparing a linear decision
boundary with a decision tree
approximation using axis-aligned
rectangular splits in feature space

Two plots showing a decision tree
perfectly capturing a rectangular boundary
with axis-aligned splits, compared to a
linear boundary

What will your learn today?

What does bagging of decision trees accomplish?
How do you use out of bag error estimation for decision trees?
- You should be able to describe this for both regression and classification trees.
What problem of bagging does using random forest address?
What is the relationship between random forest and bagging?

Section 2

8.2.1 Bagging

Use ensemble of trees to reduce variance

Want to do (but can’t):
Build separate models from independent training sets, and average resulting predictions:

${\hat{f}}^{1} (x), \dots, {\hat{f}}^{B} (x)$ for $B$ separate training sets
Return the average

{\hat{f}}_{𝑎𝑣𝑔} (x) = \frac{1}{B} \sum_{b = 1}^{B} {\hat{f}}^{b} (x)

Boostrap modification:

Work with fixed data set
Take $B$ samples from this data set (with replacement)
Train method on $b$ th sample to get ${\hat{f}}^{* b} (x)$
Return average of predictions (regression)
${\hat{f}}_{𝑏𝑎𝑔} (x) = \frac{1}{B} \sum_{b = 1}^{B} {\hat{f}}^{* b} (x)$

or majority vote (classification)

Prediction on new data point

Cartoon illustration of multiple green trees, representing an ensemble of decision trees.

Example: Heart classification data

Line plot comparing Test and OOB error
for Bagging and Random Forest models as
the number of trees increases.

Out of Bag Error Estimation

On average, bootstrap sample uses about 2/3 of the data
Remaining observations not used are called out-of-bag (OOB) observations
For each observation, run through all the trees where it wasn’t used for building
Return the average (or majority vote) of those as test prediction! rather law of large number
Bootstraped version of LOOCV.

Diagram showing several red data
samples, each corresponding to an
individual green decision tree, representing
a bagging ensemble process.

Error using OOB

Test your understanding: PollEv

Section 3

Random Forests

The idea

Goal is to decorrelate the bagged trees:
- If there is a strong predictor, the first split of most trees will be the same
- Most or all trees will be highly correlated
- Averaging highly correlated quantities doesn’t decrease variance as much as uncorrelated

The random forest fix:
- Each time a split is considered, only use a random subset of $m$ the predictors
- Fresh sample taken every time
- Typically $m \approx \sqrt{p}$
- On average, $(p - m) ∕ p$ of splits won’t consider strong predictor
- $m = p$ gives back bagging

Example on gene expression

Plot of test classification error versus
number of trees comparing m=p, m=p/2,
and m=sqrt(p) for random forests.

TL:DR

Bagging: trees grown independently on random samples. Trees tend to be similar to each other, can result in getting caught in local optima
Random forest: trees independently on samples, but split is done using random subset of features