Scribd
Upload
4 views22 pages

13.clustering Algorithm - K-Means Algorithm

The document discusses clustering algorithms, focusing on the K-means clustering method within the context of unsupervised learning. It explains the process of partitioning data into clusters based on proximity to centroids and highlights the algorithm's limitations, particularly with outliers. Additionally, it includes exercises for applying the K-means algorithm using Euclidean and Manhattan distance functions.

Uploaded by

yordanos.ugr-2250-15
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views22 pages

13.clustering Algorithm - K-Means Algorithm

The document discusses clustering algorithms, focusing on the K-means clustering method within the context of unsupervised learning. It explains the process of partitioning data into clusters based on proximity to centroids and highlights the algorithm's limitations, particularly with outliers. Additionally, it includes exercises for applying the K-means algorithm using Euclidean and Manhattan distance functions.

Uploaded by

yordanos.ugr-2250-15
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Science and Analytics

13. Clustering Algorithm

Hassen Redwan, Ph.D


hassenred1@[Link]

2026
Learning Objectives

n Unsupervised Learning
n K-means Clustering Algorithm

2
Unsupervised Learning

n In supervised learning
q Data come with the labels (classification) or outputs (regression)
n In unsupervised learning
q No such target outputs
q Finding patterns in the data
q Clustering

3
What is Cluster Analysis?

n 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.
n Evaluation criterion: a good clustering will produce high quality clusters in which
q the intra-cluster similarity is high
q the inter-cluster similarity is low

4
K-means Clustering Algorithm
K-means Clustering

6
K-means Clustering

n Partitioning method: construct a partition of N objects into K clusters


n Number of clusters, K, must be specified.
n Each cluster is associated with a centroid (center point)
n Each point is assigned to the cluster with the closest centroid
n K-means Clustering Algorithm

7
K-means Clustering example for K=2 and 5 Objects

8
K-means Clustering

n Initial centroids are often chosen randomly.


q Clusters produced vary from one run to another.
n The centroid is (typically) the mean of the points in the cluster.
n K-means will converge for common similarity measures
n Most of the convergence happens in the first few iterations.
n Limitations of K-means
q K-means has problems when the data contains outliers

9
K-means Clustering: Exercise

n Look at the problem in the next page and cluster the data points (objects) into three
clusters.
n For distance computation between each data point and the Centroids of each
cluster, use
q (1) the Euclidean distance function (widely used)

q (2) the Manhattan distance function: the Manhattan distance between two points

is defined as:

10
K-means
Clustering:
Exercise

11
Computing Centroids

Centroids
q C1 = ((2+8)/2, (10+4)/2) = (5, 7)
q C2 = ((5+7)/2, (8+4)/2) = (6, 6)
q C3 = ((1+3)/2, (2+4)/2) = (2, 3)

12
Distance Computation: Euclidean

13
Distance Computation: Euclidean
Results after the first Iteration

14
Reassign points to Clusters

15
Reassign points to Clusters

16
Distance Computation: Euclidean
Calculate the new Centroids based on the first Iteration result

New Centroids
n C1 = ((2+5)/2, (10+8)/2) = (3.5, 9)
n C2 = ((8+7)/2, (4+4)/2) = (7.5, 4)
n C3 = ((1+3)/2, (2+4)/2) = (2, 3)
17
Recompute New Centroids

New Centroids
n C1 = ((2+5)/2, (10+8)/2) = (3.5, 9)
n C2 = ((8+7)/2, (4+4)/2) = (7.5, 4)
n C3 = ((1+3)/2, (2+4)/2) = (2, 3)
18
Repeat Compute and Re-compute until Convergence

Repeat
n Compute distance to each centroid and re- assign points to clusters
n Re-compute each cluster centroid
Until convergence

19
Repeat Compute and Re-compute until Convergence

20
R Code

21
22

You might also like