INTRO TO RANDOM FOREST
BY ANTHONY ANH QUOC DOAN
MOTIVATION FOR RANDOM
FOREST
• Random forest is a great
statistical learning model.
• It works well with small to
medium data. Unlike Neural
Network which requires large
data to train. (1)
• Example: Ted's Cancer Thesis
• source: "An Empirical
Comparison of Supervised
Learning Algorithms" - https://
www.cs.cornell.edu/~caruana/
ctp/ct.papers/caruana.icml06.pdf
EXAMPLE: PREDICTING CANCER
• Clinical data have few
observations ranging from 5
patients to 200 patients (for
phase 3).
• Medical data cost money. Very
expensive to run trials and to
find patient willing to volunteer,
especially rare disease.
• Of course 5 is small but 200 is
great for random forest. Bad for
Neural Network.
• Ted's Thesis
ROADMAP
SECTIONS
1. CART
2. Bagging
3. Random Forest
4. References
1. CART (CLASSIFICATION AND REGRESSION TREE)
CART
SECTION OVERVIEW
1. History
2. Quick Example
3. CART Overview
4. Recursive Data Partition (CART)
5. Classifying with Terminal Nodes
6. Basis Function
7. Node Splitting
8. Tree Pruning
9. Regression Tree
CLASSIFICATION TREE -
(BINARY TREE DATA STRUCTURE)
CLASSIFICATION TREE - QUICK
EXAMPLE
• We have several predictors (x's) and one response
(y, the thing we're trying to predict)
• Let's do cancer with a simple model.
1. response Y is either 0,1 where the person
have cancer or not
2. predictor - age (value range: 0 year old to 99
year old)
HOW CART (DATA PARTITION
ALGORITHM) WORKS
1. For each predictor, all possible splits of the
predictor values are considered
2. For each predictor, the best split is selected.
(we'll get to best split criteria)
3. With the best split of each predictor is
determined, we pick the best predictor in that
group.
CART Uses Binary Tree Data Structure
CART - DATA PARTITION
EXAMPLES
• Examples of step 1:
• marital status (categorical data: never married, married, and divorced)
• never married vs [married and divorced]
• married vs [never married and divorced]
• divorced vs [never married and married]
• age (value range: 21 to 24)
• So the possible split (maintaining order)
• 21 vs 22-24
• 21-22 vs 23-24
• 21-23 vs 24
VISUAL EXAMPLE
• The best way to do this is adding another predictor to our
model.
• We're going to add exercise per week (hours)
• recap our response:
• y (0 - no cancer or 1- cancer)
• our predictors:
• age (value range: 0 to 99 year)
• exercise per week (value: 0 to 168 hours).
Note here we can either partition the data
horizontally or vertically. We're choosing the
best split/partition.
REPEAT DATA PARTITION ALGORITHM,
CART, AGAIN FOR THE PARTITIONED DATA
RECURSIVELY...
R - CODE
flowers_data <- iris
flowers_data <- flowers_data[!
(flowers_data$Species ==
'virginica'),]
library(rpart)
tree.model <- rpart(Species ~ . ,
data = flowers_data)
library(party)
library(partykit)
tree.model.party <-
as.party(tree.model)
plot(tree.model.party)
R - CODE
flowers_data <- iris
library(rpart)
tree.model <- rpart(Species
~ . , data = flowers_data)
library(party)
library(partykit)
tree.model.party <-
as.party(tree.model)
plot(tree.model.party)
BASIS FUNCTIONS
• X is a predictor
• M transformations of X
• β_m is the weight given to the mth transformation (the coefficient)
• h_m is the m-th transformation of X
• f(x) is the linear combination of transformed values of X
BASIS FUNCTION EXAMPLE
THE BASIS EXAMPLE WE CARE ABOUT
THIS IS CART BASIS FUNCTION
The new summation is for multiple predictors. P = total
number of predictors.
NODE SPLITTING
QUESTION HOW IS SPLIT
DETERMINED?
• The goal is to split/partition the data until each
node is homogenous in data, or as little
"impurity" (few outcomes that we want in the
particular node and mostly outcome that we want).
HOW IS NODE IMPURITY
CALCULATED?
NODE IMPURITY - SETUP
• Our data to train is a random sample from a well
defined population
• given a node, node A
• p(y = 1 | A)
• impurity of node A is the probability that y = 1
given it is node A.
IMPURITY FUNCTION
• I(A) represent Impurity function that takes in a node
as our parameter.
• The restriction tells us that the impurity function is
nonnegative, symmetric when A contains all 0s or 1s,
and a maximum of half of each (coin toss).
IMPURITY - DEFINING Φ (PHI)
• There are several Φ functions that people uses.
• The most commonly use is the Gini Index: Φ(p) = p (1-p)
• Others
• Bayes Error: Φ(p) = min(p, 1-p)
• Cross Entropy Function: Φ(p) = -p log(p) - (1-p) log(1-p)
GINI INDEX
• p(i|t) denote the fraction of records belonging to
class i at a given node t
• c is the number of classes (example: cancer, no
cancer)
PRUNING TREE
WHY PRUNE?
• Reduce complexity of the
model
• Reduce overfitting.
• Note: Random Forest
doesn't Prune trees so
we're not going to go
into Tree pruning.
REGRESSION TREE
REGRESSION TREE - SPLITTING
NODE
• The only difference is the impurity function of the
node
• Which is just a within-node sum of squares for the
response
• Where the summation of all cases in node τ minus
the mean those cases squared.
• This is SSTO (sum square total) in Linear Regression
REGRESSION TREE EXAMPLE
Warning:
We're going to do it on classification data as an
example to show how to use the equation.
Because I don't believe I have time to go over
linear regression in here to do a proper example.
• = (1/n)*sum(y_i)
• = (1/6)*(0+0+0+0+1+1)
• = 2/6
• = 1/3
• represents one data
point in the partition
(0,0,0,1,1)
REGRESSION TREE - PRUNING
• Uses AIC or some other regression criteria, it's a
penalty function for using too many predictors and
sacrificing degree of freedom.
• AIC and such are outside the scope of this talk
because it's a huge topic and rabbit hole into
linear regression.
2. BAGGING (BOOTSTRAP AGGREGATION)
BAGGING
SECTION OVERVIEW
1. Benefit
2. Bootstrap Algorithm
3. Bootstrap example
4. Bagging Algorithm
5. Flaws
6. Why does this work?
WHY? BENEFITS.
• Reduce overfitting
• Reduce bias
• Break the bias-variance trade-off
BOOTSTRAP
• Before we dive into
bagging algorithm we
should go over bootstrap
• Bootstrap is a statistical
resample method.
• When you can't afford
to get more sample
(think medical data,
poor grad student, cost,
etc..)
BOOTSTRAP ALGORITHM
1. Used in statistic when you want to estimate a statistic of a random sample
(a statistic: mean, variance, mode, etc...)
2. Using bootstrap we diverge from traditional parametric statistic, we do not
assume a distribution of the random sample
3. What we do is sample our only data set (aka random sample) with
replacement. We take up to the number of observations in our original
data.
4. We repeat step 3 for a large number of time, B times. Once done we have
B number of bootstrap random samples.
5. We then take the statistic of each bootstrap random sample and average it
BOOTSTRAP EXAMPLE
• Original data (random sample):
• {1,2,3,1,2,1,1,1} (n = 8)
• Bootstrap random sample data:
• {1,2,1,2,1,1,3} (n = 8); mean = 1.375
• {1,1,2,2,3,1,1} (n = 8); mean = 1.375
• {1,2,1,2,1,1,2} (n = 8); mean = 1.25
• The estimated mean for our original data is the mean of the statistic for
each bootstrap sample (1.375+1.375+1.25)/3 = ~1.3333
BAGGING (BOOTSTRAP
AGGREGATION) ALGORITHM
1. Take a random sample of size N with replacement
from the data
2. Construct a classification tree as usual but do not
prune
3. Assign a class to each terminal node, and store the
class attached to each case coupled with the
predictor values for each observation
BAGGING ALGORITHM
4. Repeat Steps 1-3 a large number of times.
5. For each observation in the dataset, count the number of
times over tress that it is classified in one category and the
number of times over trees it is classified in the other category
6. Assign each observation to a final category by a majority
vote over the set of tress. Thus, if 51% of the time over a large
number of trees a given observation is classified as a "1", that
becomes its classification.
7. Construct the confusion table from these class assignments.
FLAWS
• The problem with Bagging algorithm is it's using
CART.
• CART uses Gini-Index, a greedy algorithm to find the
best split.
• So we end up with trees that are structurally similar to
each other. The trees are highly correlated among the
predictions.
• Random Forest address this.
WHY DOES THIS WORK?
• Outside the scope of this talk.
3. RANDOM FOREST
RANDOM FOREST
SECTION OVERVIEW
1. Problem RF solve
2. Building Random Forest
Algorithm
3. Breaking Down Random
Forest Algorithm Parts by
Parts
4. How to use Random Forest to
Predict
5. R Code
1. PROBLEM RANDOM FOREST
IS TRYING TO SOLVE
BAGGING PROBLEM
With bagging we have an ensemble of
structurally similar trees. This causes
highly correlated trees.
RANDOM FOREST SOLUTION
Create trees that have no correlation or weak
correlation.
2. BUILDING RANDOM FOREST
ALGORITHM
RANDOM FOREST ALGORITHM
1. Take a random sample of size N with
replacement from the data.
2. Take a random sample without replacement of
the predictors.
3. Construct the first CART partition of the data.
BUILDING RANDOM FOREST
ALGORITHM
4. Repeat Step 2 for each subsequent
split until the tree is as large as desired.
Do not prune.
5. Repeat Steps 1–4 a large number of
times (e.g., 500).
3. BREAKING DOWN RANDOM
FOREST ALGORITHM PARTS BY PARTS
1. TAKE A RANDOM SAMPLE OF SIZE
N WITH REPLACEMENT FROM DATA
• This is just bootstrapping on our data (recall
bagging section)
2. TAKE A RANDOM SAMPLE WITHOUT
REPLACEMENT OF THE PREDICTORS
• Predictor sampling / bootstrapping
• Notice this is bootstrapping our predictors and it's
without replacement.
• This is Random Forest solution to highly correlated
trees that arises from bagging algorithm.
Question (for step 2):
Max number when sampling predictors/
features?
Answer:
2 to 3 sample for predictors/features
3. CONSTRUCT THE FIRST CART
PARTITION OF DATA
• We partitioned our first bootstrap and use Gini-
index on our bootstrapped predictors sample in
step 2 to decided the split.
4. REPEAT STEP 2 FOR EACH SUBSEQUENT
SPLIT UNTIL THE TREE IS AS LARGE AS
DESIRED. DO NOT PRUNE.
• Self explanatory.
5. REPEAT STEPS 1–4 A LARGE NUMBER OF
TIMES (E.G., 500).
• Steps 1 to 4 is to build one tree.
• You repeat step 1 to 4 a large number of times to build a
forest.
• There's no magic number for large number. You can build
101, 201, 501, 1001, etc.. There's research paper that suggest
certain numbers but it base on your data. So just check model
performance via model evaluation using cross validation.
• I have no idea why suggested numbers are usually even, but I
choose odd number of trees in case of ties.
4. HOW TO USE RANDOM
FOREST TO PREDICT
• You have an observation that you want to predict
• Say the observation is x = male, z = 23 year old
• You plug that in your your random forest.
• Random Forest takes those predictors and give it to each decision
trees.
• Each decision trees give one prediction, cancer or no cancer (0,1).
• You take all of those predictions (aka votes) and take the majority.
• This is why I suggest odd number of trees to break ties for binary
responses.
5. R CODE
set.seed(415)
library(randomForest)
iris_train <- iris[-1,]
iris_test <- iris[1,]
rf.model <- randomForest(Species ~ ., data = iris_train)
predict(rf.model,iris_test)
REFERENCES
• Statistical Learning from a Regression Perspective
by Richard A. Berk
• Introduction to Data Mining by Pang-Ning Tan
(http://www-users.cs.umn.edu/~kumar/dmbook/
index.php)
• 11.12 From bagging to forest (https://
onlinecourses.science.psu.edu/stat857/node/181)
• "An Empirical Comparison of Supervised Learning
Algorithms" - https://www.cs.cornell.edu/~caruana/
ctp/ct.papers/caruana.icml06.pdf
• Random Forest created and trademarked by Leo
Breiman (https://www.stat.berkeley.edu/~breiman/
RandomForests/cc_home.htm#workings)
• "Bagging and Random Forest Ensemble Algorithms
for Machine Learning" By Jason Brownlee (http://
machinelearningmastery.com/bagging-and-
random-forest-ensemble-algorithms-for-machine-
learning/)
