Classification Algorithms:

Random Forest Algorithm

Prof. A. G. Patil
TKIET, Warananagar
 Introduction
• The Random Forest algorithm is a supervised machine learning technique
belonging to the broader category of ensemble learning methods. It is
primarily used for both classification and regression tasks. The algorithm
was introduced by Leo Breiman in 2001 as an extension of bagging
(Bootstrap Aggregating).
• Random Forest constructs a multitude of decision trees during training
and outputs:
• The mode (majority vote) for classification tasks
• The mean prediction for regression tasks
 Concepts
1. Ensemble Learning:
• Ensemble learning combines multiple models to improve overall performance. Random Forest is
based on the principle that: “A group of weak learners can come together to form a strong learner.”
2. Decision Trees:
• Each tree in the forest is a decision tree, built using a subset of the data and features. However,
individual decision trees are prone to overfitting, which Random Forest aims to reduce.
• Overfitting occurs when a model learns too much from training data, including noise, and performs
poorly on unseen data.
• Characteristics: 1. High training accuracy and 2. Low testing accuracy
• It happens because: Model too complex (e.g., deep decision tree), Small dataset, Noise in data
3. Bagging (Bootstrap Aggregating):
• Bagging is an ensemble technique where multiple models are trained independently on different
bootstrap samples (random samples with replacement), and their outputs are combined (usually by
averaging or voting).
4. Feature Randomness:
• At each split in a tree:
1. A random subset of features is selected
2. The best split is chosen only among these features
3. This introduces diversity among trees and reduces correlation.
 Why Random Forest is Needed?
• A single Decision Tree has some serious limitations:
1. Overfitting Problem
• A tree can memorize training data instead of learning patterns
• Leads to poor performance on new data
• Random Forest solves this by combining many trees → reduces overfitting.
2. High Variance (Instability)
• Small change in data → completely different tree
• Predictions become unstable
• Random Forest averages many trees → stable output
3. Limited Generalization
• A single tree depends heavily on training data
• Cannot capture all patterns reliably
• Random Forest combines multiple views of data → better generalization
• Instead of trusting one weak model, trust a group of models.
𝑨𝒗𝒆𝒓𝒂𝒈𝒆
• 𝑭𝒊𝒏𝒂𝒍 𝑷𝒓𝒆𝒅𝒊𝒄𝒕𝒊𝒐𝒏 =
𝑴𝒂𝒋𝒐𝒓𝒊𝒕𝒚 𝒐𝒇 𝒎𝒖𝒍𝒕𝒊𝒑𝒍𝒆 𝒕𝒓𝒆𝒆𝒔
 Types of Ensemble Methods
Method Idea
Bagging is an ensemble technique where multiple models are trained independently on
Bagging different bootstrap samples (random samples with replacement), and their outputs are
combined (usually by averaging or voting). (e.g. Random Forest)
Boosting is an ensemble technique where models are trained sequentially, and each new
Boosting
model focuses on correcting the errors of the previous one. (e.g. AdaBoost, XGBoost)
Stacking combines multiple different models and uses a meta-model to learn how to best
Stacking
combine their predictions. (e.g., Decision Tree + SVM + Logistic Regression + Meta-Model)

• Random Forest uses Bagging

• Random Forest is needed to overcome the weaknesses of a single
decision tree by using ensemble learning (many trees together) to
produce more accurate and stable predictions.
 Algorithm Steps
• The working of the Random Forest algorithm can be described as follows:
• Input Dataset with 𝑁 samples and 𝑀 features
• For each of 𝑇 trees:
• Draw a bootstrap sample from the dataset
• Build a decision tree:
• At each node, randomly select 𝑘 𝑓𝑒𝑎𝑡𝑢𝑟𝑒𝑠 (where 𝑘 < 𝑀 )
• Choose the best split among those features
• Repeat until all trees are constructed
• For prediction:
• Classification: Use majority voting
• Regression: Compute the average output
 Mathematical Formulation
a) Dataset Representation
• Let the dataset be: 𝐷 = 𝑥𝑖 , 𝑦𝑖 i = 1 to n
• Where: 𝑥 i = feature vector and 𝑦𝑖 ​ = target variable
b) Bootstrap Sampling (Bagging)
• From dataset 𝐷, we generate 𝐵 bootstrap samples:
• 𝐷𝑏 ∼ 𝑆𝑎𝑚𝑝𝑙𝑒 𝑤𝑖𝑡ℎ 𝑟𝑒𝑝𝑙𝑎𝑐𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝐷
• Each tree is trained on a different 𝐷𝑏
c) Random Feature Selection
• At each split, instead of considering all features 𝑝, a subset 𝑚 is selected:
• 𝑚 ≪ 𝑝 This introduces decorrelation among trees.
d) Tree Prediction
• Each tree produces a prediction: 𝑦 ^(𝑏) = (𝑥)
e) Final Prediction
• Classification (Majority Voting): 𝒚^ = 𝒎𝒐𝒅𝒆{𝒚^(𝟏) , 𝒚^(𝟐) , … , 𝒚^(𝑩) }
𝟏
• Regression (Averaging): σ𝑩 𝒃=𝟏 𝑦
^(𝑏)
𝑩
 Summarized Mathematical Representation
• Classification:
• Given trees ℎ1 𝑥 , ℎ2 𝑥 , … , ℎ𝑇(𝑥) the final prediction is:
𝑦 ^ = 𝑚𝑜𝑑𝑒{ℎ1 𝑥 , ℎ2 𝑥 , … , ℎ𝑇 𝑥 }
• Regression:
1
• 𝑦^ = σ𝑇𝑖=1 ℎ𝑖 (𝑥)
𝑇
• Key Features
• Reduction of Overfitting: By averaging multiple trees
• Robustness: Handles noise and missing values effectively
• Non-linearity: Captures complex relationships
• Implicit Feature Selection: Due to random feature subsets
 Working Mechanism
Bootstrap Sampling
• Create multiple datasets from the original dataset using sampling with replacement.
• Grow Decision Trees
For each dataset:
• Select random subset of features at each split
• Grow tree fully (no pruning)
• Prediction Phase
• Each tree predicts independently
• Combine predictions using voting/averaging
 Final Algorithm
• Input: Training data D, number of trees B
For b = 1 to B:
Draw bootstrap sample Db from D
Train decision tree Tb on Db:
At each node:
Randomly select m features
Choose best split among m features

• Output:
Ensemble of trees {T1, T2, ..., TB}

• Prediction:
Classification → majority vote
Regression → average
 Important Concepts
• Bagging
• Reduces variance
• Uses sampling with replacement
• Random Feature Selection
• Reduces correlation between trees
• Improves generalization
• Out-of-Bag (OOB) Error
• Data not selected in bootstrap (~1/3)
• Used as validation set
 Advantages & Limitation
• Advantages:
• Handles high-dimensional data
• Reduces overfitting
• Works for both classification & regression
• Robust to noise and missing values
• Limitations
• Computationally expensive
• Less interpretable than a single decision tree
• Large model size
 Bias-Variance Perspective
• Decision Trees → Low bias, High variance
• Random Forest → Low bias, Reduced variance
1 1−𝜌 2
• 𝑉𝑎𝑟𝑅𝐹 = 𝜌𝜎2 + 𝜎
𝐵 𝐵
• Where:
• 𝜌 = 𝑐𝑜𝑟𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑡𝑟𝑒𝑒𝑠
• 𝜎2 = 𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒 𝑜𝑓 𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙 𝑡𝑟𝑒𝑒
• Bias is the error caused by over-simplifying
the model, leading to failure in capturing the
true pattern in data. i.e. Model makes strong High bias → Underfitting
assumptions about data & Learns too little Poor performance on both training and testing data
• Variance is the error caused by a model being Example: Using a straight line to fit curved data
too sensitive to training data, capturing noise Model cannot capture complexity
instead of general patterns. i.e. Model learns
too much detail (including noise) and High variance → Overfitting
Changes a lot with small data variations High training accuracy, low testing accuracy
Example: A decision tree that memorizes training
data exactly
Random Forest: Block Diagram
Thank You