ML for Robotics

Duration: 120 min BCSE424L Dr. Harini S

Module 4: Unsupervised
Learning
• Data Mining: Concepts and Techniques, Jiawei Han, Micheline Kamber, Jian Pei→ Chapter 10
• Pattern Recognition and Machine Learning, Christopher M. Bishop → Chapter 9
Module Overview

• Introduction to Clustering
• Types of Clustering
• Partition Based
• Hierarchical Clustering
• Density-Based Clustering
• K-Means Clustering
• K-Modes Clustering
• Principal Component Analysis (PCA)
• Ensemble Learning
Introduction
Session to Clustering
Overview

• What is Clustering?
• Clustering is an unsupervised learning technique used to group similar data points
together based on their characteristics, without using predefined labels.

• Why is it unsupervised?
• Unlike classification:
➢ There is no target/output label
➢ The algorithm discovers structure on its own
Difference
Session between Classification, Regression and Clustering
Overview

• Classification
• Predicts a category/label – Assign Class
• Supervised
• Predicts output

• Regression
• Predicts a continuous numerical value – Estimate value
• Supervised
• Predicts Output

• Clustering
• Groups similar data without labels – Discover structure
• Unsupervised
• No Pre-defined output
Types ofOverview
Session Clustering

1. Partition Based Clustering

2. Hierarchical Clustering
3. Density Based Clustering
Feature Partition Based Clustering Hierarchical Clustering Density Based Clustering

Concept • Divides data into K non- • Builds Tree like structure – Clusters are formed
overlapping clusters Dendogram based on dense regions
• Each point belongs to exactly
one cluster
Examples / K-Means, K-Modes, K-Medoids • Agglomerative (Bottom –Up) DBSCAN
Types • Divisive (Top-Down)
Advantages Simple, Fast, Scalable Good for small datasets Handles noise, detects
arbitrary shaped clusters
Limitations Sensitive to initialization, Need to Computationally expensive Parameter sensitive,
choose correct ‘k’ difficult with varying
densities
K-Means
Session Clustering
Overview
• K-Means clustering is a partition-based unsupervised learning
algorithm that divides a dataset into K distinct clusters based on
similarity

• Points within the same cluster are close to each other

• Points in different clusters are far from each other

• Each cluster is represented by a centroid (mean of the points in that

cluster).

• The algorithm tries to minimize the total distance between data points
and their respective cluster centroids.
Mathematical
Session Objective
Overview

1. Choose K- no. of clusters

2. Randomly initialize k-centroids
3. Assign datapoint to each centroid
4. Recalculate Centroids (Mean)
5. Repeat steps 3-4 until centroids stops changing
(iterative refinement)
K-Modes
Session Overview
• Categorical

• Cluster Center : Mode

• Distance Measure : Matching dissimilarity

Hierarchical Clustering
Hierarchical Clustering
There are two main types of hierarchical clustering:

• Agglomerative: Initially, each object is considered to be its own cluster.

According to a particular procedure, the clusters are then merged step by
step until a single cluster remains. At the end of the cluster merging process,
a cluster containing all the elements will be formed.

• Divisive: The Divisive method is the opposite of the Agglomerative method.

Initially, all objects are considered in a single cluster. Then the division
process is performed step by step until each object forms a different cluster.
The cluster division or splitting procedure is carried out according to some
principles that maximum distance between neighboring objects in the
cluster.
Agglomerative Clustering
• Single Linkage
• Average Linkage
• Complete Linkage
Hierarchical Clustering

Hierarchical clustering is another unsupervised machine learning

algorithm, which is used to group the unlabeled datasets into a cluster
and also known as hierarchical cluster analysis or HCA.
Agglomerative Clustering is a type of hierarchical clustering
algorithm.
Hierarchical clustering has a couple of key benefits:
There is no need to pre-specify the number of clusters.

Agglomerative:
Initially, each object is considered to be its own cluster. According to a
particular procedure, the clusters are then merged step by step until a
single cluster remains. At the end of the cluster merging process, a
cluster containing all the elements will be formed.

Step 1: Compute the proximity matrix using a particular distance metric

Step 2: Each data point is assigned to a cluster
Step 3:Merge the clusters based on a metric for the similarity between clusters
Step 4: Update the distance matrix
Step 5: Repeat Step 3 and Step 4 until only a single cluster remains

Computing a proximity matrix

The first step of the algorithm is to create a distance matrix. The values of the matrix are calculated
by applying a distance function between each pair of objects. The Euclidean distance function is
commonly used for this operation.
Suppose we have two clusters in the sample data set, as shown in
Figure 2. There are different approaches to calculate the distance
between the clusters. Popular methods are listed below.
Min (Single) Linkage

One way to measure the distance between clusters is to find the minimum distance
between points in those clusters. That is, we can find the point in the first cluster
nearest to a point in the other cluster and calculate the distance between those points
 How the Agglomerative Hierarchical clustering Work?
The working of the AHC algorithm can be explained using the below steps:
Step-1: Create each data point as a single cluster. Let's say there are N data points, sothe
number of clusters will also be N.

oStep-2: Take two closest data points or clusters and merge them to form one [Link],
there will now be N-1 clusters.
 Step-3: Again, take the two closest clusters and merge them together to form
one cluster. There will be N-2 clusters.

o Step-4: Repeat Step 3 until only one cluster left. So, we will get the following
clusters.
Step-5: Once all the clusters are combined into one big
cluster, develop the dendrogram to divide the clusters
as per the problem.
Measure for the distance between two clusters
As we have seen, the closest distance between the two
clusters is crucial for the hierarchical clustering. There
are various ways to calculate the distance between two
clusters, and these ways decide the rule for clustering.
These measures are called Linkage methods. Some of
the popular linkage methods are given below:
 Single Linkage: It is the Shortest Distance between the closest points of the clusters.
1.

Complete Linkage: It is the farthest distance between the two points of two different
clusters. It is one of the popular linkage methods as it forms tighter clusters than single-
linkage.

Average Linkage: It is the linkage method in which the distance between each pair of
datasets is added up and then divided by the total number of datasets to calculate the
average distance between two clusters. It is also one of the most popular linkage
methods.
Centroid Linkage: It is the linkage method in which the distance between the
centroid of the clusters is calculated.

From the above-given approaches, we can apply any of them according to

the type of problem or business requirement.
 Example 1: Simple Linkage

Poi P1 P2 P3
X Y P1 0 0.234 0.216
nt
P2 0 0.143
P1 0.40 0.53 P3 0
P2 0.22 0.38
P3 0.35 0.32 P1 P2,P3
P1 0 0.216
P2,P3 0

Distance between cluster (P2,P3) and P1

Single linkage = minimum distance:
d((P2,P3),P1)=min(d(P2,P1),d(P3,P1))d((P2,P3),P1)
min(0.234,0.216)= =0.216
 Example 1: Average Linkage

Poi P1 P2 P3
X Y P1 0 0.234 0.216
nt
P2 0 0.143
P1 0.40 0.53 P3 0
P2 0.22 0.38
P3 0.35 0.32 P1 P2,P3
P1 0 0.225
P2,P3 0
Distance between cluster (P2,P3) and P1
Average linkage = average distance
d((P2,P3),P1)= average (0.234,0.216)= =0.225
Principal Component Analysis (PCA)
• The Principal Component Analysis(PCA) technique was introduced by the
mathematician Karl Pearson in 1901.
• Principal Component Analysis (PCA) is an unsupervised learning algorithm
technique used to examine the interrelations among a set of variables. It is
also known as a general factor analysis where regression determines a line of
best fit.
• The main goal of Principal Component Analysis (PCA) is to reduce the
dimensionality of a dataset while preserving the most important patterns or
relationships between the variables without any prior knowledge of the
target variables.
Steps in PCA
 Singular Value Decomposition (SVD)
• Singular value decomposition (SVD) is a powerful technique in linear algebra that can
help you perform various tasks in machine learning, such as dimensionality reduction,
data compression, noise reduction, feature extraction, and latent factor analysis.
• It is an unsupervised algorithmic technique.
• SVD is the decomposition of a matrix A into 3 matrices – U, S, and V
• S is the diagonal matrix of singular values. Think of singular values as the important
values of different features in the matrix
• U, V are the orthogonal matrices
• The rank of a matrix is a measure of the unique information stored in a matrix. The
higher the rank, more the information
• Eigenvectors of a matrix are directions of maximum spread or variance of data
 Example
Student Math(x) Physics(y)

S1 90 85
S2 80 78
S3 70 65
S4 60 60

• Step 1: Compute Mean

Student Math(x- Physics(y-
Mean (x) = 75 75) 72)
Mean (y) =72 S1 15 13
S2 5 6
• Step 2: Subtract Mean from Each value S3 -5 -7
S4 -15 -12
 Example
• Step 3: Compute Co-Variance Matrix

Cov(x,y) = 1/3 * (15*13+5*6+(-5)*(-7)+(-15)*(-12)) = 146.67

Var(x)=1/3*(152+52+(-5)2+(-15)2)=166.67
Var(y)=1/3*(132+62+(-7)2+(-12)2)=132.67

• Step 4: Find Eigenvalues

 Example
• Step 4(Continued):

Largest eigenvalue = 297.33 → gives PC1

• Step 5: Find Eigenvector (PC1 Direction)
 Example
• Step 6: Normalize v1

Here for our vector v1, ||v1|| = sqrt(12+0.892) = 1.3387

After norm, vectors are 0.75 and 0.66 (1/1.3387, 0.89/1.3387 respectively)
PC1 Equation

Student Math Physics PC1

(x) (y) score
S1 15 13 19.83
• Step 7: Project Data onto PC1 S2 5 6 7.71
For student S1, PC1 = 19.83 S3 -5 -7 -8.37
S4 -15 -12
Similarly for other students → compute -19.17

Apply to centered values→ always subtract mean before applying PC

 Example
• How to decide PC1 is good enough?
• Total Variance : 297.33+2.02=299.35

• Explained Variance Ratio:

• PC1 = 297.33/299.35 = 99.3%
• PC2 = 2.02 / 299.35 = 0.7%

• So in this example PC1 is enough

• Keep components that explain most of the variance

• Common thresholds:
• 95% (standard)
• 99% (strict)
PCA in 3 Dimensions
• Example of Principal Component Analysis (PCA)
• Reducing 3D data to lower dimensions

• Example 2:
• Features:
• Math(x), Physics(y), Chemistry(z)
• (90,85,88)
• (80,78,82)
• (70,65,68)
• (60,60,62)
Step 1: Mean Calculation
• Compute mean of each feature

• Meanx = 90+80+70+60/4 = 75
• Meany = 85+78+65+60 / 4 = 72
• Meanz = 88+82+68+62/4 = 75

• Mean = (75 72, 75)

Step 2: Data Centering
• Subtract mean from each value

• Example:
• (15,13,13)
• (5,6,7)
• (-5,-7,-7)
• (-15,-12,-13)
Step 3: Covariance Matrix
• Compute 3x3 covariance matrix

• Represents relationships between features

• Cov(x,x)=166.67
• Cov(y,y)=132.67
• Cov(z,z)=145.33
• cov(x,y) =146.67
• cov(x,z) = 153.33
• cov(y,z)=138.67
Step 4: Eigenvalues & Eigenvectors
• Solve |A - λI| = 0

• Eigenvalues → variance
• Eigenvectors → directions
• 𝜆1≈430, 𝜆2≈14, 𝜆3≈0.67

• Explained Variance: 430+14+0.67=444.67

• PC1 =430/444.67 =96.7%
• PC2 = 14//444.67 =3.1%
• PC3 = 0.67 /444.67 = 0.2 %

• Decision: Keep PC1, PC2 → optional, PC3 → drop

Step 5: Principal Components
• PC1 → highest variance

• PC2 → second highest

• PC3 → least important

Step 6: Dimensionality Reduction
• Project 3D data onto PC1 and PC2

• PC1 : 0.60x+0.53y+0.60z

• PC2: z2​=0.70x−0.71y+0.05z

• For point (15,13,13): (Apply to centered values→ always subtract

mean before applying PC)
• Z1 = 23.69, Z2 = 1.92 (Same way all transformed values can be computed)
Ensemble Learning
Why single Model Fails?

• A single model fails due to bias, variance, noise sensitivity, and

inability to capture complex patterns in data
What is Ensemble Learning?

• Ensemble Learning is a technique where multiple models are

combined to make a better prediction than a single model
Why ensemble Model works when single model fails?

• Instead of relying on one model, we combine many models to

improve accuracy and robustness.
How Ensemble Helps When a Single Model Fails?
• Reduces Variance (Overfitting)
• Single model (like decision tree) overfits
→ Train multiple models on different samples, Average their output
Eg: Random Forest
• Reduces Bias (Underfitting)
• Single model too simple, misses out patterns
→Combine weak learners sequentially, Each corrects previous outputs
Eg: Boosting
• Handles Noise Better
• Single model learns noise
→multiple models → noise effects average out
• Improves Generalization
• Model works only on training data
→Different models learn different patterns
• Combines Strengths of Different Models
• One model good at one thing, bad at another
→ Combine multiple models
• Eg: Stacking
Random Forest

• Random Forest = many decision trees + voting

• It is an ensemble learning method (bagging) where:

• Multiple decision trees are created
• Each tree gives a prediction
• Final answer = majority vote (classification) or average (regression)
How to choose random Data?
• Random Data (Bootstrap Sampling)Each tree gets a different subset of
data
• Randomly select samples WITH replacement from the original dataset
• With replacement → put the selected data in the dataset so it can be chosen
again in another random set
• Example: D=[A,B,C,D]
• Pick 4 points randomly → [A, C, C, D], [B, B, D, A]
• Random Features: Each split considers only a subset of features
• Randomly select subset of features
• Example: Features: [x, y, z]
• Tree 1 uses: [x, y]
• Tree 2 uses: [y, z]
How Random Forest Works?

1. Take dataset
2. Create multiple random samples
3. Train a decision tree on each sample
4. Each tree makes a prediction
5. Combine Results
• Voting (classification)
• Averaging (regression)
Example
Student Study Hours Attendance Result
S1 2 Low Fail
S2 5 Medium Pass
S3 8 High Pass
S4 1 Low Fail

• Build Multiple Trees:

• Tree 1 (trained on random sample) : Predicts pass
• Tree 2 → predicts fail
• Tree 3 → predicts pass
• Final Voting: 2 votes pass, 1 vote fail → pass
Do’s and Don’ts in Random Sampling
✓Use sampling with replacement
✓Keep same dataset size
✓Ensure randomness
✓Use many trees (e.g., 100+)
✓Shuffle data properly

☒Using same dataset for all trees

☒Too few trees
☒No feature randomness
☒Very small dataset
Boosting

• Sequential learning where each model learns from previous mistakes

How Boosting works?

• Train First Model (on full dataset)

• Some points are misclassified
• Identify these points
• Give More weight to these misclassified points
• Train on next model
• Repeat → Keep correcting Errors
Stacking

• Combines predictions of multiple models using a meta-model to

produce a better final prediction
 How Stacking Works?
• Train Base Models
• For Ex:
• Model 1 → Decision Tree
• Model 2 → Logistic Regression
• Model 3 → SVM
• Get Predictions
• Ex:
• M1 (Model 1)-- > D1 (Data 1) : 1 , D2 : 0
• M2 → D1 : 0 , D2 : 1
• M3 → D1 : 1, D2 : 1
• Create New Dataset
• Ex:
• M1 : 1 0
• M2 : 0 1
• M3 : 1 1
• Actual : 1 0
• Train Meta- Model:
• Ex: this model could be logistic regression
• Which base model to trust more, More precisely, when to trust which model more?
• Ex: M1 : Pass, M2: Fail, M3: Pass → M1 is usually more accurate so choose Pass