k-means & k-medoid Clustering

Last lesson took away the answer key. No more labels — just points scattered in space and a hunch that they fall into natural groups. Clustering is the task of acting on that hunch. It asks a single question: which points belong together? A grouping is “good” when each point sits close to the centre of its own group. The loop that finds one is simple enough to run by hand.

That loop is k-means, and the prompt’s last hint named its trick exactly: alternate between guessing the groups and refining them. Pick k centroids — a centroid is simply the current guess at where one cluster’s centre sits — then repeat two moves until nothing changes:

• Every point joins the nearest centroid.
• Every centroid slides to the average of the points that just joined it.

That is the entire method, and it is the workhorse behind customer segmentation, image colour-quantisation, and quick exploratory grouping whenever you have no labels to learn from.

The two-step loop

Think of the centroids as magnets and the points as iron filings. Each round, the filings snap to the closest magnet (assign), then each magnet recentres itself on its own cluster of filings (update). Repeat until the magnets stop moving.

The assign step is one comparison per centroid. You can skip the square roots because whichever centroid is nearest by squared distance is nearest by ordinary distance too. Say the point is (4, 4) and the centroids are C1 = (1, 1) and C2 = (6, 6). Then d² to C1 = 3² + 3² = 18 and d² to C2 = 2² + 2² = 8. Eight is smaller, so the point joins C2.

The loop is not aimless: it is greedily minimising the within-cluster sum of squares (WCSS) — the total squared distance from each point to its own centroid. That number is the precise meaning of “a good grouping.”

Each step can only decrease (or hold) WCSS, so the loop always halts. But it halts in whatever valley the starting centroids happened to roll into — a local optimum, not necessarily the best one.

That gap is worth naming, because “it converged” and “it found the best clustering” are two different sentences. People routinely read the first as the second. Convergence here means only that the loop reached a standoff: no point wants to switch given where the centroids are, and no centroid wants to move given who is assigned to it.

That is a stability condition, not an optimality one. A different starting set of centroids can reach a completely different standoff, with a completely different WCSS — and neither run has any way of knowing it lost.

How GATE asks this

The signature question is a NAT: you are given a set of points and told (or you must work out) which points were assigned to a centroid. You are then asked for the updated centroid after one iteration. The recipe is fixed — collect the assigned points, average their coordinates. (GATE DA 2024 ran a related conceptual MCQ: given two points in a cluster, which other point must also be in it — the same nearest-centroid reasoning.)

Worked example — one centroid-update iteration

Among a set of 2-D points, the ones nearest to centroid C3 = (6, 6) are (6, 6) and (9, 9). After one update step, where does C3 move?

The update rule says the new centroid is the mean of its assigned points. Average the coordinates separately:

assigned to C3:  (6, 6)  and  (9, 9)

new x = (6 + 9) / 2 = 15 / 2 = 7.5
new y = (6 + 9) / 2 = 15 / 2 = 7.5

C3  →  (7.5, 7.5)

So the updated centroid is (7.5, 7.5) — the midpoint of the two assigned points, exactly as the prediction prompt suggested. The whole task is “assign, then average,” nothing more.

For data with outliers, reach for k-medoid instead. It works the same way, but a cluster’s centre must be an actual data point — the medoid, the point with the smallest total distance to the rest — not an abstract mean. Because no averaging is involved, a single far-flung outlier cannot drag the centre away. That makes k-medoid more robust than k-means.

In one breath

k-means clusters unlabelled points by alternating two moves until nothing changes:

• assign each point to its nearest centroid;
• update each centroid to the mean of its assigned points.

This greedily lowers the within-cluster sum of squares (the total squared point-to-centroid distance) every step, so it always halts. But it reaches only a local optimum that depends on the random initialisation (hence multiple restarts). k-medoid swaps the mean for a real data point as the centre, trading a little cost for robustness to outliers.

Practice

A question to carry forward

k-means works, but look at what it asked of you up front: a number, k, the count of clusters — guessed before you have seen a single grouping. Guess wrong and the whole result is wrong. Because it rolls into whatever valley its random start finds, two runs can hand back two different answers.

Imagine instead a method that demands no k at all and never gambles on a random start. It begins with every point alone, then:

• Fuses the two closest, followed by the next two closest.
• Keeps going, recording the entire history as a tree.
• Lets you slice that tree at any height to read off however many clusters you want.

Here is the thread onward:

• How does this merge-from-the-bottom approach work?
• What does it even mean to measure the distance between two clusters (not two points)?
• Why does the rule you pick for that — nearest pair versus farthest pair — completely change the shape of the clusters you get?