# Un-Supervised Learning

course: Module 2 — Machine Learning Algorithms
module: Module-2-Machine-Learning-Algorithms
type: pdf
source_url: https://personal-learn.armco.dev/files/Module-2-Machine-Learning-Algorithms/General/Un-Supervised_Learning.pdf
pages: 36

---
[page 1]
IIT Roorkee – Futurense
PG Certification 
GenAI and Agentic AI for Engineers
Un-Supervised Learning
Dr Durga Toshniwal
Professor
Department of Computer Science & Engg.
Indian Institute of Technology Roorkee
durga.toshniwal@cs.iitr.ac.in 
GenAI and Agentic AI for Engineers

[page 2]
Cluster Analysis
◼ Cluster: a collection of data objects
❑ Similar to one another within the same cluster
❑ Dissimilar to the objects in other clusters
◼ Cluster analysis
❑ Finding similarities between data according to the 
characteristics found in the data and grouping 
similar data objects into clusters
◼ Unsupervised learning: no predefined classes
GenAI and Agentic AI for Engineers

[page 3]
Cluster Analysis
◼ Finding groups of objects such that the objects in 
a group will be similar (or related) to one another 
and different from (or unrelated to) the objects in 
other groups
Inter-cluster 
distances are 
maximized
Intra-cluster 
distances are 
minimized
GenAI and Agentic AI for Engineers

[page 4]
How many clusters ?
How many clusters?
Four Clusters Two Clusters 
Six Clusters 
GenAI and Agentic AI for Engineers

[page 5]
Similarity and Dissimilarity
◼ Similarity
❑ Numerical measure of how alike two data objects are.
❑ Is higher when objects are more alike.
❑ Often falls in the range [0,1]
◼ Dissimilarity
❑ Numerical measure of how different two data objects are
❑ Lower when objects are more alike
❑ Minimum dissimilarity is often 0
❑ Upper limit varies
◼ Proximity refers to a similarity or dissimilarity
GenAI and Agentic AI for Engineers

[page 6]
Euclidean Distance
◼ Euclidean Distance
   
◼ Standardization is necessary, if scales differ.

=
−=
n
k kk qpdist
1
2)(
D(Q,C)
GenAI and Agentic AI for Engineers

[page 7]
Generalization : Minkowski Distance
◼ Minkowski Distance is a generalization of 
Euclidean Distance
   
   
rn
k
r
kk qpdist
1
1
)||( 
=
−=
GenAI and Agentic AI for Engineers

[page 8]
Requirements of  Clustering  
◼ Discovery of clusters with arbitrary shape
◼ Able to deal with noise and outliers
◼ Ability to handle dynamic data 
◼ Ability to deal with different types of attributes
◼ Minimal requirements for domain knowledge to 
determine input parameters
◼ Insensitive to order of input records
◼ Incorporation of user-specified constraints
◼ Interpretability and usability
◼ Scalability
GenAI and Agentic AI for Engineers

[page 9]
Data Structures for Clustering
Clustering operates typically on 2 data 
structures –
◼ Data matrix
◼ Dissimilarity matrix
GenAI and Agentic AI for Engineers

[page 10]
Data Structures
◼ Data matrix
❑ Object-by-variable structure
❑ There are n objects 
❑ Each has p attributes
❑ n objects X p variables matrix


















npx...nfx...n1x
...............
ipx...ifx...i1x
...............
1px...1fx...11x
GenAI and Agentic AI for Engineers

[page 11]
Data Structures
◼ Dissimilarity matrix
❑ Object-by-object structure
❑ Stores proximities (dissimilarity) for 
all pairs of n objects
❑ n x n table
❑ 0 entry means objects are highly 
similar & the larger the value 
becomes, the more different the 
objects are
















0...)2,()1,(
:::
)2,3()
...ndnd
0dd(3,1
0d(2,1)
0
GenAI and Agentic AI for Engineers

[page 12]
Classification vs. Clustering
Classification: Supervised learning: 
Learns a method for predicting the 
instance class using pre-labeled 
(classified)  instances
GenAI and Agentic AI for Engineers

[page 13]
Major Clustering Approaches  
◼ Partitioning approach: 
❑ Construct various partitions and then evaluate 
them by some criterion, e.g., minimizing the sum 
of square errors
❑ Typical method: 
◼ k-means
GenAI and Agentic AI for Engineers

[page 14]
Major Clustering Approaches  
◼ Partitioning approach Contd.: 
❑ Given a DB with n objects, construct k partitions 
where k <= n
❑ k is the no of clusters
❑ Each group must have 1 object
❑ Each object belongs to exactly 1 group
❑ Based on iterative relocation technique
GenAI and Agentic AI for Engineers

[page 15]
10
1 2 3 4 5 6 7 8 9 10
1
2
3
4
5
6
7
8
9
How can we tell the 
right
 
number of 
clusters?
In general, this is a unsolved problem. However there are many approximate 
methods. In the next few slides we will see an example.
However, in this case we are imagining 
that we do NOT know the class labels. 
We are only clustering on the X and Y 
axis values. 
GenAI and Agentic AI for Engineers

[page 16]
1 2 3 4 5 6 7 8 9 10
When k = 1, the objective function is 873.0
GenAI and Agentic AI for Engineers 
How can we tell the 
right
 
number of 
clusters?

[page 17]
1 2 3 4 5 6 7 8 9 10
When k = 2, the objective function is 173.1
GenAI and Agentic AI for Engineers 
How can we tell the 
right
 
number of 
clusters?

[page 18]
1 2 3 4 5 6 7 8 9 10
When k = 3, the objective function is 133.6
GenAI and Agentic AI for Engineers 
How can we tell the 
right
 
number of 
clusters?

[page 19]
0.00E+00
1.00E+02
2.00E+02
3.00E+02
4.00E+02
5.00E+02
6.00E+02
7.00E+02
8.00E+02
9.00E+02
1.00E+03
1 2 3 4 5 6
We can plot the objective function values for k equals 1 to 6…
The abrupt change at k = 2, is highly suggestive of two clusters in the data. 
This technique for determining the number of clusters is known as “knee 
finding” or “elbow finding”.
k
Objective Function
GenAI and Agentic AI for Engineers

[page 20]
Another K-means example, step 1-
Random assignment of  points
k1
k2
k3
X
Y
Pick 3 
initial
cluster
centers
(randomly)
GenAI and Agentic AI for Engineers

[page 21]
K-means example, step 2 – 
calculating means
k1
k2
k3
X
Y
Assign
each point
to the closest
cluster
center
GenAI and Agentic AI for Engineers

[page 22]
K-means example, step 4b – New 
Cluster Centers
X
Y
re-compute 
cluster 
means
k1
k3
k2
GenAI and Agentic AI for Engineers

[page 23]
K-means example, step 5 – 
Reassigning points (no change this 
time)
X
Y
move cluster 
centers to 
cluster means
k2
k1
k3
GenAI and Agentic AI for Engineers

[page 24]
The K-Means Clustering Method 
◼ Example
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
K=2
Arbitrarily choose 
K initial cluster 
centers
Assign 
each 
object 
to most 
similar 
center
Update 
the 
cluster 
means
Update 
the 
cluster 
means
reassign
GenAI and Agentic AI for Engineers

[page 25]
K-means Clustering – Details
◼ Initial centroids are often chosen randomly.
❑ Clusters produced vary from one run to another.
◼ The centroid is (typically) the mean of the points in 
the cluster.
◼ ‘Closeness’ is measured by Euclidean distance.
GenAI and Agentic AI for Engineers

[page 26]
K-means Clustering
◼ The Objective Function which measures the quality of the clusters is: 
Sum of Squared Error (SSE)
❑ For each point, the error is the distance to the nearest cluster
❑ To get SSE, we square these errors and sum them.
❑ x is a data point in cluster Ci and mi is the representative point for 
cluster Ci 
◼ mi corresponds to the center (mean) of the cluster

= 
=
K
i Cx
i
i
xmdistSSE
1
2 ),(
GenAI and Agentic AI for Engineers

[page 27]
K-means Clustering
◼ Step 1: Begin with a decision on the value of k = 
       number of clusters .
◼ Step 2:  Put any initial partition that classifies the 
       data into k  clusters. You may  assign the 
       training samples randomly, or systematically 
       as the following: 
       1.Take the first k training sample as single-
 element clusters      
       2. Assign each of the remaining (N-k) training 
sample to the cluster with the nearest 
centroid. After each  assignment, re-compute 
the centroid of the gaining  cluster. 
GenAI and Agentic AI for Engineers

[page 28]
K-means Clustering
◼ Step 3: Take each sample in sequence and          
       compute its distance from the centroid of           
       each of the clusters. If a sample is not               
       currently in the cluster with the closest          
       centroid, switch this sample to that cluster         
       and update the centroid of the cluster          
       gaining the new sample and the cluster         
       losing the sample. 
◼ Step 4: Repeat step 3 until convergence is           
        achieved, that is until a pass through the         
        training sample causes no new assignments. 
GenAI and Agentic AI for Engineers

[page 29]
K-means Clustering – Details
◼ Most of the convergence happens in the first few 
iterations.
❑ Often the stopping condition is   - Until relatively 
few points change clusters
◼ Complexity is O( n * K * I * d )
❑ n = number of points, K = number of clusters, 
I = number of iterations, d = number of attributes
GenAI and Agentic AI for Engineers

[page 30]
Choice of the initial cluster centers can 
greatly affect k-means clustering
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
Sub-optimal Clustering
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yOptimal Clustering
Original/Actual 
Clusters 
GenAI and Agentic AI for 
Engineers

[page 31]
Evaluating K-means Clusters
❑ Given two clusters, we can choose the one with the 
smallest error
❑ One easy way to reduce SSE is to increase K, the 
number of clusters
◼  A good clustering with smaller K can have a 
lower SSE than a poor clustering with higher K
GenAI and Agentic AI for Engineers

[page 32]
Partitioning - Limitations of  K-means
◼ K-means has problems when clusters are of 
differing 
❑ Sizes
❑ Densities
❑ Non-globular shapes
◼ K-means has problems when the data contains 
outliers/noise
◼ K-means is restricted to data for which there is a 
notion of a center
GenAI and Agentic AI for Engineers

[page 33]
Limitations of  K-means: Differing Sizes
Original Clusters K-means (3 Clusters)
GenAI and Agentic AI for Engineers

[page 34]
Limitations of  K-means: Differing Density
Original Clusters
 K-means (3 Clusters)
GenAI and Agentic AI for Engineers

[page 35]
Limitations of  K-means: Non-globular Shapes
Original Clusters
 K-means (2 Clusters)
GenAI and Agentic AI for Engineers

[page 36]
K-means clustering summary
Advantages
◼ Simple, understandable
◼ items automatically 
assigned to clusters
◼ Efficient: O(knIt)
Disadvantages
◼ Need to specify k, the number 
of clusters, in advance
◼ All items forced into a cluster, 
Unable to handle noisy data 
and outliers
◼ Too sensitive to outliers
◼ Applicable only when mean is 
defined 
◼ Not suitable to discover 
clusters with non-convex 
shapes
GenAI and Agentic AI for Engineers