Random Forest
Applied Multivariate Statistics – Spring 2012

Overview Intuition of Random Forest The Random Forest Algorithm De-correlation gives better accuracy

 Out-of-bag error (OOB-error)
Healthy Variable importance

Healthy
Diseased

Diseased

Diseased1

Intuition of Random Forest

Tree 2

Tree 1

young

old
young

old

diseased

healthydiseased

healthymale

tall

femaleshorthealthyhealthyhealthydiseased
Tree 3New sample:

retiredworking

healthyhealthyold, retired, male, short
Tree predictions:diseased, healthy, diseasedtall

Majority rule:diseased

healthyshortdiseased2

The Random Forest Algorithm

3Differences to standard tree Train each tree on bootstrap resample of data
(Bootstrap resample of data set with N samples:
Make new data set by drawing with replacement N samples; i.e., some samples willprobably occur multiple times in new data set)

 For each split, consider only m randomly selected variables
 Don’t prune Fit B trees in such a way and use average or majority
voting to aggregate results

4Why Random Forest works 1/2
 Mean Squared Error = Variance + Bias2
 If trees are sufficiently deep, they have very small bias
 How could we improve the variance over that of a singletree?

5Why Random Forest works 2/2

i=jDecreaes, if
𝜌 decreases, i.e., if

De-correlation gives
better accuracy

m decreases

Decreases, if number of trees Bincreases (irrespective of 𝜌)
6

Estimating generalization error:
Out-of bag (OOB) error
 Similar to leave-one-out cross-validation, but almost
without any additional computational burden
 OOB error is a random number, since based on random
resamples of the data
Data:

Resampled Data:

Out of bag samples:old, tall – healthyold, tall – healthy

young, short – diseased

old, short – diseased

old, short – diseased

young, tall – healthy

young, tall – healthy

young, short – diseased

young, tall – healthy

young, short – healthy
young, tall – healthyold, short – diseased

young, short – healthy

young, tall – healthyold, short– diseasedtallhealthyoldyoung

diseased

healthyshortdiseased

Out of bag (OOB) error rate:¼ = 0.25

Variable Importance for variable i
Datausing Permutations
Resampled

Resampled

Dataset 1

Dataset m

OOB…

Data 1OOB

Data mPermute values ofvariable i in OOBTree 1

Tree mdata set
OOB error e1

OOB error em
d1 = e1–p1

dm =em-pm
OOB error pm

OOB error p1
1d= m

Pm

1s2d = m¡1i=1 diPm

2i=1 (di ¡ d)dvi = sd8

Treesvs.

Random Forest+ Trees yield insight intodecision rules+ Rather fast+ Easy to tune
parameters+ RF as smaller prediction
variance and therefore
usually a better general
performance+ Easy to tune parameters- Prediction of trees tend
to have a high variance- Rather slow
- “Black Box”: Rather hardto get insights into decision
rules

9

Comparing runtime(just for illustration)• Up to “thousands” of variables• Problematic if there are categorical predictors with many levels (max: 32 levels)

RF: First predictor cut into 15 levels
RFTree10

RFvs.

+ Can model nonlinear
class boundaries+ OOB error “for free” (noCV needed)+ Works on continuous andcategorical responses(regression / classification)+ Gives variable
importance+ Very good performancex- “Black box”
- Slowxx xxxxxxxx xx

LDA+ Very fast
+ Discriminants for visualizing
group separation+ Can read off decision rule- Can model only linear classboundaries- Mediocre performance- No variable selection- Only on categorical response- Needs CV for estimating
prediction error
x xxxxxxx xx x
11Concepts to know
 Idea of Random Forest and how it reduces the prediction
variance of trees
 OOB error Variable Importance based on Permutation

12

R functions to know Function “randomForest” and “varImpPlot” from package“randomForest”

13