Clustering

Overview

In this chapter, we transition from the paradigms of supervised learning to the domain of unsupervised learning, where the primary objective is to discover inherent structures within unlabeled datasets. Clustering, at its core, is the task of partitioning a set of objects such that objects in the same group, or cluster, are more similar to each other than to those in other clusters. This process is fundamental to exploratory data analysis, enabling us to identify natural groupings, patterns, and anomalies without any prior knowledge of the data's class labels.

For the GATE examination, a thorough understanding of clustering algorithms is indispensable. The focus is not merely on the definition of clustering but on the operational mechanics, underlying assumptions, and computational complexities of its seminal algorithms. We will delve into two principal families of methods: partitioning methods, exemplified by K-Means and K-Medoids, and hierarchical methods. Questions frequently assess a candidate's ability to trace the execution of an algorithm, compare the outcomes of different methods based on distance metrics, and evaluate the suitability of a particular technique for a given data distribution. Our study will therefore be both theoretical and pragmatic, equipping you with the analytical skills required to solve complex problems in this domain.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | K-Means and K-Medoids Clustering | Partitioning data into K clusters using centroids. |
| 2 | Hierarchical Clustering | Building a nested hierarchy of clusters. |

---

Learning Objectives

---

We now turn our attention to K-Means and K-Medoids Clustering...
## Part 1: K-Means and K-Medoids Clustering

Introduction

In the domain of unsupervised learning, our primary objective is to discover inherent structures and patterns within unlabeled data. Clustering stands as a cornerstone of this pursuit, aiming to group data points such that objects within the same group (called a cluster) are more similar to each other than to those in other groups. Among the various families of clustering algorithms, partitioning methods are particularly prominent due to their conceptual simplicity and computational efficiency.

This chapter focuses on two of the most fundamental and widely-used partitioning algorithms: K-Means and K-Medoids. Both algorithms seek to partition a dataset into a pre-specified number of clusters, $K$. However, they differ critically in how they define the center of a cluster and, consequently, in their sensitivity to data characteristics such as outliers. A thorough understanding of their mechanisms, objective functions, and geometric properties is essential for applying them correctly and for success in the GATE examination. We will explore the iterative nature of these algorithms, their mathematical underpinnings, and their practical implications.

---

Key Concepts

#
## 1. The K-Means Algorithm

The K-Means algorithm is an iterative procedure that partitions a given dataset into $K$ predefined, non-overlapping clusters. The core idea is to define clusters by their centers, or centroids, and to assign each data point to the cluster associated with the nearest centroid.

The objective of K-Means is to minimize the within-cluster sum of squares (WCSS), often referred to as inertia. This quantity measures the total variance within all clusters.

The algorithm, often referred to as Lloyd's algorithm, proceeds in two main steps after an initial setup.

The K-Means Algorithm Steps:

Initialization: Choose $K$ initial points from the dataset to serve as the initial centroids. This can be done randomly or using more sophisticated methods.

Assignment Step: For each data point $\mathbf{x}_i$, assign it to the cluster $C_k$ corresponding to the closest centroid $\mathbf{\mu}_k$. The "closest" is determined by minimizing the squared Euclidean distance.

Update Step: After all points have been assigned to clusters, recalculate the $K$ centroids. The new centroid $\mathbf{\mu}_k$ is the mean of all data points $\mathbf{x}_i$ assigned to cluster $C_k$.

Convergence: Repeat the Assignment and Update steps until the cluster assignments no longer change, the centroids stabilize, or a maximum number of iterations is reached.

Worked Example:

Problem: Consider the 1D dataset: $\{2, 3, 4, 10, 11, 12\}$. Let $K=2$, and the initial centroids be $\mu_1 = 3$ and $\mu_2 = 10$. Perform one iteration of the K-Means algorithm.

Solution:

Step 1: Initialization
The initial centroids are given.

Step 2: Assignment Step
We assign each point to the nearest centroid.

• For point 2: $|2-3|=1$, $|2-10|=8$. Assign to Cluster 1.


• For point 3: $|3-3|=0$, $|3-10|=7$. Assign to Cluster 1.


• For point 4: $|4-3|=1$, $|4-10|=6$. Assign to Cluster 1.


• For point 10: $|10-3|=7$, $|10-10|=0$. Assign to Cluster 2.


• For point 11: $|11-3|=8$, $|11-10|=1$. Assign to Cluster 2.


• For point 12: $|12-3|=9$, $|12-10|=2$. Assign to Cluster 2.

The resulting clusters are:
$C_1 = \{2, 3, 4\}$
$C_2 = \{10, 11, 12\}$

Step 3: Update Step
We calculate the new centroids as the mean of the points in each cluster.

Answer: After one iteration, the new centroids are $\mu_1 = 3$ and $\mu_2 = 11$.

#
### Geometric Interpretation and Properties of K-Means

The assignment step of K-Means partitions the data space into regions. The decision boundary between any two clusters, say $C_i$ and $C_j$, consists of all points equidistant from their respective centroids $\mathbf{\mu}_i$ and $\mathbf{\mu}_j$. In a Euclidean space, this boundary is the perpendicular bisector of the line segment connecting $\mathbf{\mu}_i$ and $\mathbf{\mu}_j$. The collection of all such boundaries forms a Voronoi tessellation of the space.

μ₁

μ₂

Decision Boundary
(Perpendicular Bisector)



A
B

P
Cluster 1 (Convex)
Cluster 2 (Convex)

A crucial consequence of this partitioning is that each cluster formed by K-Means is a convex set.

#
## 2. The K-Medoids Algorithm

A significant drawback of K-Means is its sensitivity to outliers. Because the centroid is calculated as the mean of all points in a cluster, a single outlier can pull the centroid far away from the natural center of the group. The K-Medoids algorithm addresses this issue by restricting the cluster centers to be actual data points from the dataset.

The most common implementation of K-Medoids is the Partitioning Around Medoids (PAM) algorithm. Its objective is to minimize a sum of dissimilarities between points and their respective medoids, which can be any distance metric (e.g., Manhattan, Euclidean).

The K-Medoids (PAM) Algorithm Steps:

Initialization: Select $K$ data points from the dataset to be the initial medoids.

Assignment Step: Assign each non-medoid point to the cluster of its closest medoid.

Update Step (Swap): Iteratively attempt to improve the quality of the medoids. For each cluster, consider swapping its current medoid with every non-medoid point in that cluster. Calculate the change in the total cost (sum of distances of points to their medoids). If a swap leads to a reduction in total cost, perform the swap to select the new, better medoid.

Convergence: Repeat the assignment and update steps until the medoids no longer change.

The key difference lies in the update step. Instead of calculating a new mean, K-Medoids evaluates the quality of potential swaps, which makes it more computationally expensive but also more robust.

K-Means vs. K-Medoids:

| Feature | K-Means | K-Medoids |
| :--- | :--- | :--- |
| Cluster Center | Centroid (mean of points) | Medoid (an actual data point) |
| Sensitivity to Outliers | High | Low (Robust) |
| Input Data | Requires continuous data where a mean is meaningful | Can handle any data type for which a dissimilarity measure can be defined |
| Computational Cost | Generally lower, O(NKID) | Generally higher due to the swap step |
| Cluster Shape | Tends to find spherical, convex clusters | More flexible, can find non-spherical clusters depending on the distance metric |

#
## 3. Choosing the Value of K

Both K-Means and K-Medoids require the number of clusters, $K$, to be specified beforehand. A common heuristic for determining an optimal value for $K$ is the Elbow Method.

This method involves running the clustering algorithm for a range of $K$ values (e.g., from 1 to 10) and, for each value, calculating the WCSS. When we plot WCSS against $K$, the graph typically shows a sharp decrease initially, which then slows down, forming an "elbow". The value of $K$ at this elbow point is often considered a good choice for the number of clusters.

Number of Clusters (K)
WCSS









3
1
2
4
5
6
Elbow Point (K=3)

The intuition is that adding more clusters beyond the elbow point yields diminishing returns in terms of explaining the variance in the data.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A K-Means clustering algorithm using Euclidean distance is applied to a 2D dataset with $K=3$. The points $\mathbf{p}_1 = \begin{bmatrix}2\\5\end{bmatrix}$ and $\mathbf{p}_2 = \begin{bmatrix}6\\1\end{bmatrix}$ are found to be in the same cluster. Which of the following points is guaranteed to be in the same cluster?" options=["

","","",""] answer="" hint="Recall the convexity property of K-Means clusters. Any point on the line segment connecting two points in a cluster must also be in that cluster." solution="
Step 1: Understand the convexity property of K-Means clusters.
If points $\mathbf{p}_1$ and $\mathbf{p}_2$ are in the same cluster, then any point $\mathbf{p}$ that can be expressed as $\mathbf{p} = \lambda \mathbf{p}_1 + (1-\lambda)\mathbf{p}_2$ for $0 \le \lambda \le 1$ must also be in that cluster. Such a point $\mathbf{p}$ lies on the line segment connecting $\mathbf{p}_1$ and $\mathbf{p}_2$.

Step 2: The midpoint of the segment is a special case where $\lambda = 0.5$. Let's calculate the midpoint.

Step 3: The point $\begin{bmatrix}4\\3\end{bmatrix}$ is the midpoint of the line segment connecting $\mathbf{p}_1$ and $\mathbf{p}_2$. Since it lies on the segment, it is guaranteed to be in the same cluster.

Result:
The point $\begin{bmatrix}4\\3\end{bmatrix}$ must be in the same cluster.
"
:::

:::question type="NAT" question="Consider a dataset of 1D points: $\{1, 2, 6, 7, 15\}$. You are performing K-Means clustering with $K=2$. The initial centroids are $\mu_1 = 2.5$ and $\mu_2 = 10$. After the first assignment step, what is the value of the new centroid for the cluster containing the point 15?" answer="15" hint="First, perform the assignment step by calculating the distance of each point to the two initial centroids. Then, form the clusters and calculate the mean of the points in the relevant cluster." solution="
Step 1: Perform the assignment step for each point.
Initial centroids: $\mu_1 = 2.5$, $\mu_2 = 10$.

• Point 1: $|1 - 2.5| = 1.5$, $|1 - 10| = 9$. Assign to Cluster 1.
• Point 2: $|2 - 2.5| = 0.5$, $|2 - 10| = 8$. Assign to Cluster 1.
• Point 6: $|6 - 2.5| = 3.5$, $|6 - 10| = 4$. Assign to Cluster 1.
• Point 7: $|7 - 2.5| = 4.5$, $|7 - 10| = 3$. Assign to Cluster 2.
• Point 15: $|15 - 2.5| = 12.5$, $|15 - 10| = 5$. Assign to Cluster 2.

Step 2: Identify the clusters formed after the assignment step. $C_1 = \{1, 2, 6\}$ $C_2 = \{7, 15\}$

Step 3: The question asks for the new centroid of the cluster containing the point 15, which is Cluster 2. Calculate the mean of the points in $C_2$.

Result: The value of the new centroid for the cluster containing point 15 is 11.
Wait, I made a mistake in the calculation. Let me re-verify.

• Point 1: closer to 2.5


• Point 2: closer to 2.5


• Point 6: closer to 2.5


• Point 7: closer to 10


• Point 15: closer to 10

No, the calculations are correct. Wait, the question is asking for the centroid of the cluster containing 15.
Let's re-read the question.
Ah, I see. I miscalculated for point 7.
Let's re-do the assignment step carefully.

• Point 1: $|1 - 2.5| = 1.5$, $|1 - 10| = 9$. -> C1


• Point 2: $|2 - 2.5| = 0.5$, $|2 - 10| = 8$. -> C1


• Point 6: $|6 - 2.5| = 3.5$, $|6 - 10| = 4$. -> C1


• Point 7: $|7 - 2.5| = 4.5$, $|7 - 10| = 3$. -> C2


• Point 15: $|15 - 2.5| = 12.5$, $|15 - 10| = 5$. -> C2

Clusters are indeed $C_1 = \{1, 2, 6\}$ and $C_2 = \{7, 15\}$.
New centroid for C2 is $(7+15)/2 = 11$.

Let me re-check my initial setup. Is there a simpler scenario?
Perhaps the initial centroids were different in my head. Let's try initial centroids $\mu_1 = 1.5$ and $\mu_2 = 7.5$.

• Point 1: closer to 1.5


• Point 2: closer to 1.5


• Point 6: closer to 7.5


• Point 7: closer to 7.5


• Point 15: closer to 7.5

This gives $C_1 = \{1, 2\}$, $C_2 = \{6, 7, 15\}$.
New $\mu_2 = (6+7+15)/3 = 28/3 = 9.33$.

Let's stick to the original question and re-write the solution to be very clear.

Corrected Solution for NAT question:
Step 1: Initial centroids are given as $\mu_1 = 2.5$ and $\mu_2 = 10$. We must assign each point to the closer centroid.

• For point 1: $|1 - 2.5| = 1.5$, $|1 - 10| = 9$. Assign to Cluster 1.


• For point 2: $|2 - 2.5| = 0.5$, $|2 - 10| = 8$. Assign to Cluster 1.


• For point 6: $|6 - 2.5| = 3.5$, $|6 - 10| = 4$. Assign to Cluster 1.


• For point 7: $|7 - 2.5| = 4.5$, $|7 - 10| = 3$. Assign to Cluster 2.


• For point 15: $|15 - 2.5| = 12.5$, $|15 - 10| = 5$. Assign to Cluster 2.

Step 2: The resulting clusters after one assignment step are:
$C_1 = \{1, 2, 6\}$
$C_2 = \{7, 15\}$

Step 3: The point 15 is in Cluster 2. We calculate the new centroid for Cluster 2 by taking the mean of its members.

Result: The new centroid value is 11.
Okay, I'll change the question slightly to get the answer 15.
Let's change the dataset to $\{1, 2, 6, 7, 15\}$ and initial centroids $\mu_1 = 4$ and $\mu_2 = 11$.

• Point 1: |1-4|=3, |1-11|=10. -> C1


• Point 2: |2-4|=2, |2-11|=9. -> C1


• Point 6: |6-4|=2, |6-11|=5. -> C1


• Point 7: |7-4|=3, |7-11|=4. -> C1


• Point 15: |15-4|=11, |15-11|=4. -> C2

So $C_1 = \{1,2,6,7\}$, $C_2 = \{15\}$.
New centroid for C2 is 15. This works.

Let's re-write the NAT question and solution.
:::question type="NAT" question="Consider a dataset of 1D points: $\{1, 2, 6, 7, 15\}$. You are performing K-Means clustering with $K=2$. The initial centroids are $\mu_1 = 4$ and $\mu_2 = 11$. After the first assignment step, what is the value of the new centroid for the cluster containing the point 15?" answer="15" hint="First, perform the assignment step by calculating the distance of each point to the two initial centroids. Then, form the clusters and calculate the mean of the points in the relevant cluster." solution="
Step 1: The initial centroids are $\mu_1 = 4$ and $\mu_2 = 11$. We assign each data point to the cluster with the nearest centroid.

• For point 1: $|1 - 4| = 3$, $|1 - 11| = 10$. Assign to Cluster 1.
• For point 2: $|2 - 4| = 2$, $|2 - 11| = 9$. Assign to Cluster 1.
• For point 6: $|6 - 4| = 2$, $|6 - 11| = 5$. Assign to Cluster 1.
• For point 7: $|7 - 4| = 3$, $|7 - 11| = 4$. Assign to Cluster 1.
• For point 15: $|15 - 4| = 11$, $|15 - 11| = 4$. Assign to Cluster 2.

Step 2: After the assignment, the clusters are: $C_1 = \{1, 2, 6, 7\}$ $C_2 = \{15\}$

Step 3: The question asks for the new centroid of the cluster containing the point 15, which is Cluster 2. The mean of the points in Cluster 2 is calculated.

Result: The value of the new centroid is 15.
"
:::

:::question type="MSQ" question="Which of the following statements about the K-Means algorithm are correct?" options=["The algorithm is guaranteed to find the globally optimal clustering.", "The final clustering result is independent of the initial centroid selection.", "The clusters formed by K-Means are always convex.", "It is more sensitive to outliers than K-Medoids."] answer="The clusters formed by K-Means are always convex.,It is more sensitive to outliers than K-Medoids." hint="Evaluate each statement based on the fundamental properties of K-Means, considering its objective function, sensitivity to initialization, and geometric nature." solution="

• Statement A is incorrect. K-Means is an iterative hill-climbing algorithm that is only guaranteed to converge to a local minimum of the WCSS objective function. The final result can be a suboptimal clustering.


• Statement B is incorrect. The final clustering is highly dependent on the initial placement of centroids. Different initializations can lead to vastly different results.


• Statement C is correct. The decision boundary between any two K-Means clusters is a perpendicular bisector, which results in a Voronoi tessellation of the space. Each cell (cluster) in this tessellation is a convex region.


• Statement D is correct. The centroid is the mean of the points in a cluster. The mean is a statistical measure that is not robust and can be significantly skewed by extreme values (outliers). K-Medoids uses an actual data point (medoid) as the center, which makes it robust to outliers.

"
:::

:::question type="MCQ" question="A data scientist is working with a dataset containing customer transaction records. The features include both numerical data (transaction amount) and categorical data (product category). The goal is to segment customers into groups. Which of the following algorithms is most appropriate for this task?" options=["K-Means", "K-Medoids", "Both are equally appropriate", "Neither is appropriate"] answer="K-Medoids" hint="Consider how each algorithm defines a cluster center and what operations are required. The ability to handle mixed data types is key." solution="
Step 1: Analyze the requirements of the K-Means algorithm. K-Means requires the calculation of a mean to update its centroids. The mean is only defined for numerical data and cannot be computed for categorical features like 'product category'. Therefore, K-Means is not directly applicable to this mixed-type dataset.

Step 2: Analyze the requirements of the K-Medoids algorithm. K-Medoids defines a cluster center as a medoid, which is an actual data point from the dataset. The algorithm operates on a dissimilarity (or distance) matrix. It is possible to define a dissimilarity measure that can handle both numerical and categorical data (e.g., Gower's distance). Because it does not require calculating a mean, K-Medoids is suitable for this task.

Result: K-Medoids is the more appropriate algorithm because it can work with arbitrary dissimilarity measures suitable for mixed data types, whereas K-Means is restricted to numerical data for which a mean can be calculated.
"
:::

---

Summary

---

What's Next?

---

---

Part 2: Hierarchical Clustering

Introduction

Hierarchical clustering represents a powerful and intuitive class of unsupervised learning algorithms designed to build a hierarchy of clusters. Unlike partitional clustering methods such as K-Means, which produce a single, flat grouping of data points, hierarchical methods construct a nested sequence of partitions. This structure is typically visualized as a tree-like diagram known as a dendrogram, which offers a rich, multi-level view of the data's underlying organization. The primary advantage of this approach is its ability to reveal cluster relationships at various scales without requiring the number of clusters to be specified beforehand.

We can broadly classify hierarchical clustering into two fundamental strategies: agglomerative and divisive. The agglomerative approach, often termed the "bottom-up" method, begins with each data point residing in its own individual cluster. It then proceeds iteratively by merging the two most similar clusters at each step until all points are contained within a single, comprehensive cluster. Conversely, the divisive or "top-down" approach starts with all data points in one large cluster and recursively splits it into smaller, more distinct clusters. For the GATE examination, the agglomerative method is of primary importance, and our discussion will focus principally on its mechanics and variations.

---

Key Concepts

#
## 1. The Agglomerative Clustering Algorithm

The agglomerative hierarchical clustering process is methodical and deterministic. It constructs the hierarchy from the individual elements upwards. Let us formalize the general procedure.

Given a set of $N$ data points to be clustered and a distance matrix containing the pairwise dissimilarities between them, the algorithm proceeds as follows:

Initialization: Begin by assigning each of the $N$ data points to its own cluster. We now have $N$ clusters, each containing a single point.

Iteration: Identify the two closest (most similar) clusters in the current set of clusters.

Merge: Combine these two clusters into a new, single cluster. The total number of clusters is now reduced by one.

Update: Compute the distances between this new cluster and all other existing clusters. This step is critical and depends on the chosen linkage criterion.

Termination: Repeat steps 2 through 4 until only one cluster, containing all $N$ data points, remains.

The sequence of merges and the distances at which they occur form the basis for constructing the dendrogram.

#
## 2. Linkage Criteria: Measuring Inter-Cluster Distance

The core of the agglomerative algorithm lies in step 4: updating the distance matrix after a merge. To do this, we must define a measure of dissimilarity between two clusters, which may contain multiple points. This measure is known as the linkage criterion. The choice of linkage criterion significantly influences the shape and structure of the final clusters.

Let us consider two clusters, $C_i$ and $C_j$. Let $d(p, q)$ be the distance between two individual data points $p$ and $q$.

#
### Single Linkage (MIN)

Single linkage defines the distance between two clusters as the minimum distance between any single data point in the first cluster and any single data point in the second cluster. It is based on the "nearest neighbor" principle.

#
### Complete Linkage (MAX)

In contrast to single linkage, complete linkage defines the inter-cluster distance as the maximum distance between any pair of points across the two clusters. This criterion is based on the "farthest neighbor" principle.

#
### Average Linkage (UPGMA)

Average linkage provides a compromise between the MIN and MAX criteria. It defines the distance between two clusters as the average of all pairwise distances between the points in the two clusters.

#
## 3. The Dendrogram

A dendrogram is the standard visualization for hierarchical clustering. It is a tree diagram that illustrates the arrangement of the clusters produced by the corresponding analyses.

• The leaves of the tree represent the individual data points.
• As we move up the tree, branches merge at nodes. Each node represents the merging of two clusters.
• The height of the node on the vertical axis indicates the dissimilarity (distance) at which the two clusters were merged.

By cutting the dendrogram horizontally at a specific height, we can obtain a flat clustering of the data. A cut at a lower height will result in a larger number of smaller clusters, while a cut at a higher height will yield fewer, larger clusters.

Distance
0
1
2
3
4





A
B
C
D
E

Cut for 3 clusters

In the diagram above, a horizontal cut at a distance of 2.5 would yield two clusters: $\{A, B, E\}$ and $\{C, D\}$. A cut at a distance of 1.8 would yield three clusters: $\{A, B\}$, $\{C, D\}$, and $\{E\}$.

---

#
## 4. Worked Example: Single Linkage Clustering

Let us now apply the agglomerative algorithm with the single linkage criterion to a concrete example. This process is fundamental to solving numerical problems in GATE.

Problem:
Given the following distance matrix for five points $P_1, P_2, P_3, P_4, P_5$, perform hierarchical clustering using the single linkage method and draw the corresponding dendrogram.

Solution:

Initial State:
We begin with five clusters, each containing one point: $\{P_1\}, \{P_2\}, \{P_3\}, \{P_4\}, \{P_5\}$.

Iteration 1: First Merge

Step 1: Find the minimum distance in the matrix.
The smallest non-zero value is 2, which is the distance between $P_1$ and $P_2$.

Step 2: Merge the closest clusters.
We merge $\{P_1\}$ and $\{P_2\}$ to form a new cluster $\{P_1, P_2\}$. The clusters are now: $\{P_1, P_2\}, \{P_3\}, \{P_4\}, \{P_5\}$.

Iteration 2: Update Matrix and Second Merge

Step 1: Update the distance matrix. We need to compute the distance from our new cluster $\{P_1, P_2\}$ to all other clusters using the single linkage rule (minimum distance).

The updated distance matrix is:

Step 2: Find the new minimum distance.
The smallest value is now 3, between $P_4$ and $P_5$.

Step 3: Merge the closest clusters.
We merge $\{P_4\}$ and $\{P_5\}$ to form $\{P_4, P_5\}$. The clusters are now: $\{P_1, P_2\}, \{P_3\}, \{P_4, P_5\}$.

Iteration 3: Update Matrix and Third Merge

Step 1: Update the distance matrix again.

The new matrix is:

Step 2: Find the new minimum distance.
The minimum is 4, between $P_3$ and $\{P_4, P_5\}$.

Step 3: Merge $\{P_3\}$ and $\{P_4, P_5\}$ to form $\{P_3, P_4, P_5\}$. The clusters are now: $\{P_1, P_2\}, \{P_3, P_4, P_5\}$.

Iteration 4: Final Merge

Step 1: Compute the final distance.

From the previous matrix, these values are 5 and 8.

Step 2: Merge the final two clusters at a distance of 5.

Dendrogram Construction:
We summarize the merges and their corresponding distances:

$\{P_1\}, \{P_2\}$ merged at distance 2.

$\{P_4\}, \{P_5\}$ merged at distance 3.

$\{P_3\}$ merged with $\{P_4, P_5\}$ at distance 4.

$\{P_1, P_2\}$ merged with $\{P_3, P_4, P_5\}$ at distance 5.

This sequence allows us to draw the dendrogram.

Distance
0
2
4
6






P1
P2
P3
P4
P5

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $C_A$ and $C_B$ be two clusters. The dissimilarity between them when using average linkage is defined as:" options=["The minimum distance between any element of $C_A$ and any element of $C_B$.","The average of all pairwise distances between elements in $C_A$ and $C_B$.","The distance between the centroids of $C_A$ and $C_B$.","The maximum distance between any element of $C_A$ and any element of $C_B$."] answer="The average of all pairwise distances between elements in $C_A$ and $C_B$." hint="Recall the formal definitions for the main linkage criteria. Average linkage considers all pairs." solution="Average linkage is defined as $D(C_A, C_B) = \frac{1}{|C_A||C_B|} \sum_{x \in C_A} \sum_{y \in C_B} d(x, y)$, which is the average of all pairwise distances between points in the two clusters. The other options correspond to single linkage, centroid linkage, and complete linkage, respectively."
:::

:::question type="NAT" question="Consider the following distance matrix. If complete linkage hierarchical clustering is performed, at what distance will the final two clusters be merged?"

answer="8" hint="Follow the agglomerative process step-by-step using the MAX rule for complete linkage. The final merge distance is the distance between the last two remaining super-clusters." solution="
Step 1: Initial clusters: {A}, {B}, {C}, {D}. Minimum distance is 1 between A and B. Merge {A, B}.

Step 2: Update matrix using complete linkage (max).
$d(\{A,B\}, C) = \max(d(A,C), d(B,C)) = \max(7, 6) = 7$
$d(\{A,B\}, D) = \max(d(A,D), d(B,D)) = \max(8, 7) = 8$
New matrix:

Step 3: Minimum distance is 3 between C and D. Merge {C, D}. The two remaining clusters are {A,B} and {C,D}.

Step 4: The distance between these final two clusters is the value from the last matrix, which is $d(\{A,B\}, C)$ and $d(\{A,B\}, D)$ combined with the {C,D} merge.
Let's calculate the final merge distance:
$d(\{A,B\}, \{C,D\}) = \max(d(A,C), d(A,D), d(B,C), d(B,D))$
From the original matrix, these values are 7, 8, 6, 7.
The maximum of these is 8.
Alternatively, from the updated matrix in Step 2, the distance between cluster {A,B} and cluster {C,D} would be:
$d(\{A,B\}, \{C,D\}) = \max(d(\{A,B\},C), d(\{A,B\},D)) = \max(7, 8) = 8$.

Result: The final merge occurs at a distance of 8.
"
:::

:::question type="MSQ" question="The dendrogram below was generated by an agglomerative clustering algorithm. Which of the following statements is/are necessarily true?"

options=["Points D and E were merged into a cluster before points A and B were merged.","If the clustering is stopped when there are 3 clusters, the clusters are {A, B}, {C}, and {D, E}.","Point C is more similar to cluster {A, B} than it is to cluster {D, E}.","The final merge to create one large cluster occurs at a greater distance than any other merge."] answer="B,D" hint="Analyze the merge heights on the dendrogram. A lower height means an earlier merge. Cluster composition depends on the height at which you 'cut' the tree." solution="

• A is incorrect. The merge for {A, B} happens at a height corresponding to distance ~35 (175-140). The merge for {D, E} happens at height ~55 (175-120). Thus, {A, B} were merged first (at a smaller distance).


• B is correct. To get 3 clusters, we must cut the tree horizontally such that the line intersects three vertical lines. A cut at a height between 80 and 120 (e.g., at height 100) would do this. The resulting clusters would be {A, B, C} (from the left branch), and {D, E} from the right branch. Oh, wait, let's re-examine. A cut at height 100 would give {A,B,C} and {D,E}. A cut at height 130 would give {A,B}, {C}, and {D,E}. The question implies a standard interpretation. Let's trace the merges. {A,B} merge first. Then {D,E} merge. Then {A,B} merges with {C}. A cut for 3 clusters would be made after the second merge but before the third. At that point, the clusters are indeed {A, B}, {C}, and {D, E}. So B is correct.


• C is incorrect. Cluster {A, B} merges with C at a height of ~95 (175-80). The combined cluster {A, B, C} merges with {D, E} at a much larger height of ~135 (175-40). The distance from C to {A,B} is represented by the height of their merge node, which is lower than the height of the final merge node. We cannot definitively compare the similarity of C to {A,B} vs C to {D,E} without the distance matrix, but the dendrogram shows C joins {A,B} first, implying it is 'closer' to that cluster.


• D is correct. By definition, the agglomerative process merges the two closest available clusters at each step. This means the merge distances are monotonically non-decreasing. The final merge, which combines the last two super-clusters, must occur at a distance greater than or equal to all previous merge distances.

"
:::

---

Summary

---

What's Next?

---

Chapter Summary

In this chapter, we have explored the fundamental principles and algorithms of clustering, a core task in unsupervised machine learning. Our discussion has established the distinction between partitional and hierarchical approaches, providing a formal basis for grouping data points without pre-existing labels. We have analyzed the mechanics, advantages, and limitations of the most significant algorithms in each category. A thorough understanding of these methods is essential for solving a wide range of data analysis problems.

---

Chapter Review Questions

:::question type="MCQ" question="Consider the following statements regarding clustering algorithms:

I. K-Medoids is generally more robust to outliers than K-Means.
II. The time complexity of a standard agglomerative hierarchical clustering algorithm is typically lower than that of the K-Means algorithm.
III. The final clustering solution produced by K-Means is independent of the initial selection of centroids.

Which of the above statements is/are correct?" options=["I only", "I and II only", "II and III only", "I, II, and III"] answer="A" hint="Evaluate each statement based on the core properties of the algorithms. Think about how centroids vs. medoids are calculated, the computational scaling of each method, and the role of initialization in K-Means." solution="Let us analyze each statement individually.

Statement I: K-Means uses the mean of the points in a cluster as its centroid. The mean is highly sensitive to extreme values (outliers), as a single outlier can significantly shift its position. In contrast, K-Medoids uses a medoid—an actual data point within the cluster—to represent the cluster center. The objective function for K-Medoids minimizes the sum of dissimilarities to the medoid, which is less affected by outliers than the sum of squared Euclidean distances used in K-Means. Therefore, K-Medoids is more robust to outliers. Statement I is correct.

Statement II: The time complexity of the K-Means algorithm is approximately $O(n \cdot K \cdot d \cdot i)$, where $n$ is the number of data points, $K$ is the number of clusters, $d$ is the number of dimensions, and $i$ is the number of iterations. This complexity is linear in $n$. In contrast, a standard agglomerative hierarchical clustering algorithm requires the computation of a distance matrix, which is $O(n^2 d)$, and then iteratively updates this matrix. The overall complexity is typically $O(n^2 \log n)$ or $O(n^3)$, depending on the implementation and linkage criterion. This is significantly higher than K-Means for large $n$. Statement II is incorrect.

Statement III: The K-Means algorithm is a heuristic that converges to a local minimum of the WCSS objective function. The specific local minimum it finds is highly dependent on the initial placement of the centroids. Different initializations can lead to different final clustering solutions. To mitigate this, it is common practice to run the algorithm multiple times with different random initializations. Statement III is incorrect.

Based on our analysis, only the first statement is correct."
:::

:::question type="NAT" question="A dataset consists of the points A(2, 2), B(3, 4), and C(4, 3). In one iteration of the K-Means algorithm, these three points are assigned to a single cluster. Calculate the sum of the coordinates of the new centroid for this cluster." answer="6" hint="The centroid of a cluster is the arithmetic mean of the coordinates of all points assigned to that cluster." solution="Let the points be $P_1 = (x_1, y_1) = (2, 2)$, $P_2 = (x_2, y_2) = (3, 4)$, and $P_3 = (x_3, y_3) = (4, 3)$.

The new centroid, denoted by $C = (c_x, c_y)$, is calculated by taking the mean of the coordinates of the points in the cluster.

The x-coordinate of the new centroid is:

The y-coordinate of the new centroid is:

The new centroid is located at $(3, 3)$.

The question asks for the sum of the coordinates of the new centroid, which is:

"
:::

:::question type="MCQ" question="Given the following distance matrix for four data points P1, P2, P3, and P4. Using agglomerative hierarchical clustering with the complete-linkage criterion, which pair of clusters will be merged in the second step?" options=["{P1, P2} and {P3}", "{P1} and {P3}", "{P1, P3} and {P4}", "{P2} and {P4}"] answer="C" hint="First, identify the closest pair of points to perform the first merge. Then, update the distance matrix using the complete-linkage rule, which defines the distance between two clusters as the distance between their farthest members. Finally, find the minimum distance in the new matrix." solution="The initial distance matrix is:

Step 1: First Merge
We find the minimum distance in the matrix to determine the first merge. The minimum distance is $d(\text{P1}, \text{P3}) = 3$.
Therefore, we merge P1 and P3 into a new cluster, which we will call C1 = {P1, P3}.

Step 2: Update Distance Matrix and Find Second Merge
Now, we must compute the distances from the remaining points (P2 and P4) to this new cluster C1 using the complete-linkage criterion. The complete-linkage distance is the maximum distance between any member of the first cluster and any member of the second cluster.

Distance from C1 to P2:

Distance from C1 to P4:

The only remaining distance is between P2 and P4, which is $d(\text{P2}, \text{P4}) = 9$.

The updated distance matrix is:

Now, we find the minimum distance in this new matrix to determine the second merge. The minimum distance is $d(\text{C1}, \text{P4}) = 6$.
Therefore, the second merge is between the cluster C1 = {P1, P3} and the point P4.
"
:::

---

What's Next?