Page 1 of 14
MODULE 7: CLUSTERING
SYLLABUS
1. K-Means Clustering
2. Hierarchical Clustering
a. Single Linkage
b. Complete Linkage
c. Average Linkage
3. Ward’s Algorithm
4. MST Clustering
5. BIRCH Clustering
1. K-Means Clustering
DATA POINTS DISTANCE TO CLUSTERS
2 10 5 8 1 2 (Ki)
A1 2 10 0.00 8.61 8.06 1
A2 2 5 5.00 4.24 3.16 3
A3 8 4 8.49 5.00 7.28 2
B1 5 8 3.61 0.00 7.21 2
B2 7 5 7.07 3.61 6.71 2
B3 6 4 7.21 4.12 5.39 2
C1 1 2 8.06 7.21 0.00 3
C2 4 9 2.24 1.41 7.62 2
*Table 1: Initial calculation of clusters (Iteration 0)
Suppose, initial centroids for clusters K1, K2, K3: A1(2, 10), B1(5, 8), C1(1, 2)
New centroid coordinates for cluster K1:
x = 2, y = 10 (no change)
New centroid coordinates for cluster K2:
x = (8 + 5 + 7 + 6 + 4) / 5 = 6, y = (4 + 8 + 5 + 4 + 9) / 5 = 6
New centroid coordinates for cluster K3:
x = (2 + 1) / 2 = 1.5, y = (5 + 2) / 2 = 3.5
*The Euclidean distance needs to be calculated for every data point from the centroid at every iteration, and
updated in the table accordingly. Then it is checked how close that data point is to the centroids, and the data point
is assigned to the cluster with the closest centroid. Euclidean distance d = √{(x2 – x1)2 + (y2 – y1)2}
Page 2 of 14
DATA POINTS DISTANCE TO OLD NEW
2 10 6 6 1.5 3.5 CLUSTERS CLUSTERS
(Ki) (Ki)
A1 2 10 0.00 5.66 6.52 1 1
A2 2 5 5.00 4.12 1.58 3 3
A3 8 4 8.49 2.83 6.52 2 2
B1 5 8 3.61 2.24 5.70 2 2
B2 7 5 7.07 1.41 5.70 2 2
B3 6 4 7.21 2.00 4.53 2 2
C1 1 2 8.06 6.40 1.58 3 3
C2 4 9 2.24 3.61 6.04 2 1
*Table 2: Calculation of clusters with the updated centroids (Iteration 1)
As is evident from Table 2 that the clusters have not converged for all the data points, we need
to re-calculate the centroid coordinates for K1, K2 and K3.
New centroid coordinates for cluster K1:
x = (2 + 4) / 2 = 3 , y = (10 + 9) / 2 = 9.5
New centroid coordinates for cluster K2:
x = (8 + 5 + 7 + 6) / 4 = 6.5, y = (4 + 8 + 5 + 4) / 4 = 5.25
New centroid coordinates for cluster K3:
x = (2 + 1) / 2 = 1.5, y = (5 + 2) / 2 = 3.5 (no change)
DATA POINTS DISTANCE TO OLD NEW
3 9.5 6.5 5.25 1.5 3.5 CLUSTERS CLUSTERS
(Ki) (Ki)
A1 2 10 1.12 6.54 6.52 1 1
A2 2 5 4.61 4.51 1.58 3 3
A3 8 4 7.43 1.95 6.52 2 2
B1 5 8 2.50 3.13 5.70 2 1
B2 7 5 6.02 0.56 5.70 2 2
B3 6 4 6.26 1.35 4.53 2 2
C1 1 2 7.76 6.39 1.58 3 3
C2 4 9 1.12 4.51 6.04 1 1
*Table 3: Calculation of clusters with the updated centroids (Iteration 2)
As is evident from Table 3 that the clusters have not converged for all the data points, we need
to re-calculate the centroid coordinates for K1, K2 and K3.
*The Euclidean distance needs to be calculated for every data point from the centroid at every iteration, and
updated in the table accordingly. Then it is checked how close that data point is to the centroids, and the data point
is assigned to the cluster with the closest centroid. Euclidean distance d = √{(x2 – x1)2 + (y2 – y1)2}
Page 3 of 14
New centroid coordinates for cluster K1:
x = (2 + 5 + 4) / 3 = 3.67 , y = (10 + 8 + 9) / 3 = 9
New centroid coordinates for cluster K2:
x = (8 + 7 + 6) / 3 = 7, y = (4 + 5 + 4) / 3 = 4.33
New centroid coordinates for cluster K3:
x = (2 + 1) / 2 = 1.5, y = (5 + 2) / 2 = 3.5 (no change)
DATA POINTS DISTANCE TO OLD NEW
3.67 9 7 4.33 1.5 3.5 CLUSTERS CLUSTERS
(Ki) (Ki)
A1 2 10 1.94 7.56 6.52 1 1
A2 2 5 4.33 5.04 1.58 3 3
A3 8 4 6.62 1.05 6.52 2 2
B1 5 8 1.67 4.18 5.70 1 1
B2 7 5 5.21 0.67 5.70 2 2
B3 6 4 5.52 1.05 4.53 2 2
C1 1 2 7.49 6.44 1.58 3 3
C2 4 9 0.33 5.55 6.04 1 1
*Table 4: Calculation of clusters with the updated centroids (Iteration 3)
As the clusters have converged, i.e., old cluster configuration equals new cluster configuration,
we will stop the algorithm.
Thus,
Data points in K1: {A1, B1, C2}
Data points in K2: {A3, B2, B3}
Data points in K3: {A2, C1}
*The Euclidean distance needs to be calculated for every data point from the centroid at every iteration, and
updated in the table accordingly. Then it is checked how close that data point is to the centroids, and the data point
is assigned to the cluster with the closest centroid. Euclidean distance d = √{(x2 – x1)2 + (y2 – y1)2}
Page 4 of 14
2. Hierarchical Clustering
a. Single Linkage
CLUSTERS a b c d e
a 0 9 3 6 11
b 9 0 7 5 10
c 3 7 0 9 2
d 6 5 9 0 8
e 11 10 2 8 0
Table 1
Given the dataset {a, b, c, d, e} and the following distance matrix, we need to construct a
dendrogram by single-linkage hierarchical clustering using the agglomerative method.
Let the initial clusters be C1: {a}, {b}, {c}, {d}, {e} (singleton sets)
From the table we need to identify the minimum distance. Thus, the minimum distance is the
distance between the clusters {c} and {e}. So, d({c}, {e}) = 2.
Next, we merge {c} and {e} to form the cluster {c, e}.
The new set of clusters is C2: {a}, {b}, {d}, {c, e}
As the distance of {c, e} to other clusters is unknown, let’s calculate them.
d({c, e}, {a}) = min{d(c, a), d(e, a)} = min{3, 11} = 3
d({c, e}, {b}) = min{d(c, b), d(e, b)} = min{7, 10} = 7
d({c, e}, {d}) = min{d(c, d), d(e, d)} = min{9, 8} = 8
The values are updated in Table 2.
CLUSTERS a b c, e d
a 0 9 3 6
b 9 0 7 5
c, e 3 7 0 8
d 6 5 8 0
Table 2
From the table, the minimum distance is the distance between the clusters {a} and {c, e}. So,
d({a}, {c, e}) = 3.
Next, we merge {a} and {c, e} to form the cluster {a, c, e}.
The new set of clusters is C3: {a, c, e}, {b}, {d}
Page 5 of 14
As the distance of {a, c, e} to other clusters is unknown, let’s calculate them.
d({a, c, e}, {b}) = min{d(a, b), d(c, b), d(e, b)} = min(9, 7, 10) = 7
d({a, c, e}, {d}) = min{d(a, d), d(c, d), d(e, d)} = min(6, 9, 8) = 6
The values are updated in Table 3.
CLUSTERS a, c, e b d
a, c, e 0 7 6
b 7 0 5
d 6 5 0
Table 3
From the table, the minimum distance is between {b} and {d}. So, d({b}, {d}) = 5.
Next, we merge the clusters {b} and {d} to form the cluster {b, d}.
The new set of clusters is C4: {a, c, e}, {b, d}
As the distance between the clusters {a, c, e} and {b, d} is unknown, let’s calculate it.
d({a, c, e}, {b, d}) = min{d(a, b), d(a, d), d(c, b), d(c, d), d(e, b), d(e, d)}
= min{9, 6, 7, 9, 10, 8} = 6
The values are updated in Table 4.
CLUSTERS a, c, e b, d
a, c, e 0 6
b, d 6 0
Table 4
Only 2 clusters are left, so we merge them to form a single cluster containing all data points.
The resulting dendrogram is the figure given below.
Page 6 of 14
Single-Linkage Dendrogram
Page 7 of 14
b. Complete Linkage
CLUSTERS a b c d e
a 0 9 3 6 11
b 9 0 7 5 10
c 3 7 0 9 2
d 6 5 9 0 8
e 11 10 2 8 0
Table 1
Given the dataset {a, b, c, d, e} and the following distance matrix, we need to construct a
dendrogram by complete-linkage hierarchical clustering using the agglomerative method.
Let the initial clusters be C1: {a}, {b}, {c}, {d}, {e} (singleton sets)
From the table we need to identify the minimum distance. Thus, the minimum distance is the
distance between the clusters {c} and {e}. So, d({c}, {e}) = 2.
Next, we merge {c} and {e} to form the cluster {c, e}.
The new set of clusters is C2: {a}, {b}, {d}, {c, e}
As the distance of {c, e} to other clusters is unknown, let’s calculate them.
d({c, e}, {a}) = max{d(c, a), d(e, a)} = max{3, 11} = 11
d({c, e}, {b}) = max{d(c, b), d(e, b)} = max{7, 10} = 10
d({c, e}, {d}) = max{d(c, d), d(e, d)} = max{9, 8} = 9
The values are updated in Table 2.
CLUSTERS a b c, e d
a 0 9 11 6
b 9 0 10 5
c, e 11 10 0 9
d 6 5 9 0
Table 2
From the table, the minimum distance is the distance between the clusters {b} and {d}. So,
d({b}, {d}) = 5.
Next, we merge {b} and {d} to form the cluster {b, d}.
The new set of clusters is C3: {a}, {b, d}, {c, e}
Page 8 of 14
As the distance of {b, d} to other clusters is unknown, let’s calculate them.
d({b, d}, {a}) = max{d(b, a), d(d, a)} = max(9, 6) = 9
d({b, d}, {c, e}) = max{d(b, c), d(b, e), d(d, c), d(d, e)} = max(7, 10, 9, 8) = 10
The values are updated in Table 3.
CLUSTERS a b, d c, e
a 0 9 11
b, d 9 0 10
c, e 11 10 0
Table 3
From the table, the minimum distance is the distance between the clusters {a} and {b, d}. So,
d({a}, {b, d}) = 9.
Next, we merge {a} and {b, d} to form the cluster {a, b, d}.
The new set of clusters is C4: {a, b, d}, {c, e}
As the distance between the clusters {a, b, d} and {c, e} is unknown, let’s calculate it.
d({a, b, d}, {c, e}) = max{d(a, c), d(a, e), d(b, c), d(b, e), d(d, c), d(d, e)}
= max{3, 11, 7, 10, 9, 8} = 11
The values are updated in Table 4.
CLUSTERS a, b, d c, e
a, b, d 0 11
c, e 11 0
Table 4
Only 2 clusters are left, so we merge them to form a single cluster containing all data points.
The resulting dendrogram is the figure given below.
Page 9 of 14
Complete-Linkage Dendrogram
Page 10 of 14
c. Average Linkage
CLUSTERS a b c d e
a 0 9 3 6 11
b 9 0 7 5 10
c 3 7 0 9 2
d 6 5 9 0 8
e 11 10 2 8 0
Table 1
Given the dataset {a, b, c, d, e} and the following distance matrix, we need to construct a
dendrogram by average-linkage hierarchical clustering using the agglomerative method.
Let the initial clusters be C1: {a}, {b}, {c}, {d}, {e} (singleton sets)
From the table we need to identify the minimum distance. Thus, the minimum distance is the
distance between the clusters {c} and {e}. So, d({c}, {e}) = 2.
Next, we merge {c} and {e} to form the cluster {c, e}.
The new set of clusters is C2: {a}, {b}, {d}, {c, e}
As the distance of {c, e} to other clusters is unknown, let’s calculate them.**
d({c, e}, {a}) = avg{d(c, a), d(e, a)} = (3 + 11) / (2 * 1) = 7
d({c, e}, {b}) = avg{d(c, b), d(e, b)} = (7 + 10) / (2 * 1) = 8.5
d({c, e}, {d}) = avg{d(c, d), d(e, d)} = (9 + 8) / (2 * 1) = 8.5
The values are updated in Table 2.
CLUSTERS a b c, e d
a 0 9 7 6
b 9 0 8.5 5
c, e 3 8.5 0 8.5
d 6 5 8.5 0
Table 2
From the table, the minimum distance is the distance between the clusters {b} and {d}. So,
d({b}, {d}) = 5.
Next, we merge {b} and {d} to form the cluster {b, d}.
The new set of clusters is C3: {a}, {b, d}, {c, e}
**Average distance between 2 clusters d(A, B) = (Σ d(x, y): x ϵ A, y ϵ B) / (|A| * |B|)
Page 11 of 14
As the distance of {b, d} to other clusters is unknown, let’s calculate them. **
d({b, d}, {a}) = avg{d(b, a), d(d, a)} = (9 + 6) / (2 * 1) = 7.5
d({b, d}, {c, e}) = avg{d(b, c), d(b, e), d(d, c), d(d, e)} = (7 + 10 + 9 + 8) / (2 * 2) = 8.5
The values are updated in Table 3.
CLUSTERS a b, d c, e
a 0 7.5 7
b, d 7.5 0 8.5
c, e 7 8.5 0
Table 3
From the table, the minimum distance is the distance between the clusters {a} and {c, e}. So,
d({a}, {c, e}) = 7.
Next, we merge {a} and {c, e} to form the cluster {a, c, e}.
The new set of clusters is C4: {a, c, e}, {b, d}
As the distance between the clusters {a, c, e} and {b, d} is unknown, let’s calculate it. **
d({a, c, e}, {b, d}) = avg{d(a, b), d(a, d), d(c, b), d(c, d), d(e, b), d(e, d)}
= (9 + 6 + 7 + 9 + 10 + 8) / (3 * 2) = 8.16
The values are updated in Table 4.
CLUSTERS a, c, e b, d
a, c, e 0 8.16
b, d 8.16 0
Table 4
Only 2 clusters are left, so we merge them to form a single cluster containing all data points.
The resulting dendrogram is the figure given below.
**Average distance between 2 clusters d(A, B) = (Σ d(x, y): x ϵ A, y ϵ B) / (|A| * |B|)
Page 12 of 14
Average-Linkage Dendrogram
Page 13 of 14
3. Ward’s Algorithm
DATA POINTS x y
P1 4 4
P2 8 4
P3 15 8
P4 24 4
P5 24 12
Table 1
We begin Ward’s minimum variance method by combining any two data points at a time and
calculating their squared error. For example, if we take P1 and P2 to form a cluster, then we
keep the other data points as singleton sets. Thus, cluster set C1: {P1, P2}, {P3}, {P4}, {P5}
Now, for {P1, P2} the mid-point coordinates are: x = (4 + 8) / 2 = 6, y = (4 + 4) / 2 = 4
x = 6, y = 4, x1 = 4, x2 = 8, y1 = 4, y2 = 4
Thus, the squared error for {P1, P2} = (x – x1)2 + (y – y1)2 + (x – x2)2 + (y – y2)2
= (6 - 4)2 + (4 - 4)2 + (6 - 8)2 + (4 - 4)2 = 4 + 0 + 4 + 0 = 8
Similarly, we calculate the squared error for other combinations of clusters, as shown in Table
2. Then, we need to identify the cluster set with the least squared error, and in this case, it is
the cluster set C1.
CLUSTER SETS CLUSTERS SQUARED ERROR
C1 {P1, P2}, {P3}, {P4}, {P5} 8.0
C2 {P1, P3}, {P2}, {P4}, {P5} 68.5
C3 {P1, P4}, {P2}, {P3}, {P5} 200.0
C4 {P1, P5}, {P2}, {P3}, {P4} 235.0
C5 {P2, P3}, {P1}, {P4}, {P5} 32.5
C6 {P2, P4}, {P1}, {P3}, {P5} 128.0
C7 {P2, P5}, {P1}, {P3}, {P4} 160.0
C8 {P3, P4}, {P1}, {P2}, {P5} 48.5
C9 {P3, P5}, {P1}, {P2}, {P4} 48.5
C10 {P4, P5}, {P1}, {P2}, {P3} 32.0
Table 2
Page 14 of 14
Keeping C1 constant, we need to explore other combinations, as shown in Table 3.
CLUSTER SETS CLUSTERS SQUARED ERROR
C11 {P1, P2, P3}, {P4}, {P5} 72.7
C12 {P1, P2, P4}, {P3}, {P5} 224.0
C13 {P1, P2, P5}, {P3}, {P4} 266.7
C14 {P1, P2}, {P3, P4}, {P5} 56.5
C15 {P1, P2}, {P3, P5}, {P4} 56.5
C16 {P1, P2}, {P4, P5}, {P3} 40.0
Table 3
In Table 3, C16 has the least squared error. Keeping C16 constant, we need to explore other
combinations, as shown in Table 3.
CLUSTER SETS CLUSTERS SQUARED ERROR
C17 {P1, P2, P3}, {P4, P5} 104.7
C18 {P1, P2, P4, P5}, {P3} 380.0
C19 {P1, P2}, {P3, P4, P5} 94.0
Table 4
In Table 4, C19 has the least squared error. Only 2 clusters are left, so we merge them to form
a single cluster containing all data points.
Next, we construct the dendrogram according to C1, C16 and C19.
For that the Euclidean distances between the data points and clusters need to be calculated first.
Distance between {P1} and {P2}: d({P1}, {P2}) = √{(8 – 4)2 + (4 – 4)2} = 4
Distance between {P4} and {P5}: d({P4}, {P5}) = √{(24 – 24)2 + (12 – 4)2} = 8
Now, centroid of {P4, P5}: x = (24 + 24) / 2 = 24, y = (4 + 12) / 2 = 8
Distance between {P3} and centroid of {P4, P5}:
d({P3}, {P4, P5}) = √{(24 – 15)2 + (8 – 8)2} = 9
Now, centroid of {P1, P2}: x = (4 + 8) / 2 = 6, y = (4 + 4) / 2 = 4
And, centroid of {P3, P4, P5}: x = (15 + 24 + 24) / 3 = 21, y = (8 + 4 + 12) / 3 = 8
Distance between centroid of {P1, P2} and centroid of {P3, P4, P5}:
d({P1, P2}, {P3, P4, P5}) = √{(21 – 6)2 + (8 – 4)2} ≈ 15.5