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
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, so the
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