Clustering: Finding Groups in Data

A satellite photo with no labels

Imagine you are handed a satellite image of a district — say, a strip of land captured by a remote-sensing satellite. For every tiny patch of ground (a pixel), the sensor has recorded how much light it reflects in several bands: visible red, visible green, near-infrared, and so on. Your job is to sort these pixels into land types — water body, dense vegetation, bare soil, built-up urban area. This is exactly the kind of task unsupervised classification is used for in remote sensing and GIS software.

Here is the catch: nobody has told you which pixel is which. There is no answer key that says "this pixel is water." All you have are numbers — four or five reflectance values per pixel, repeated over millions of pixels. You cannot train a model the way you would for handwriting recognition, where every image already comes stamped with the correct digit. You must look at the raw numbers themselves and discover that they naturally fall into a small number of tight groups — pixels representing water will have very similar reflectance patterns to each other and very different patterns from vegetation pixels — without ever being told what those groups mean.

This is clustering: the task of partitioning a set of data points into groups (clusters) such that points inside a group are more similar to each other than to points in other groups — using only the data itself, with no pre-existing labels. It is the central technique of unsupervised learning, and it is the subject of this chapter.

Clustering is not classification — a misconception to kill early

Students who have already met classification (spam vs. not-spam, pass vs. fail) often assume clustering is "classification without much difference." It is not, and the difference matters for how you think about every algorithm below.

In classification, you are given a training set where every example already carries the correct label (email 1 = spam, email 2 = not spam). The algorithm's job is to learn a rule that maps features to one of these known labels, so that it can predict the label of a new, unseen example. There is a ground truth to check answers against.

In clustering, there are no labels anywhere — not in training, not ever. Nobody has decided in advance how many groups exist or what to call them. The number of clusters, k, is either chosen by you or estimated using a heuristic (you will meet one, the elbow method, later in this chapter). Once the algorithm finishes, it hands you groups named "Cluster 0," "Cluster 1," and so on — labels that carry zero inherent meaning. A human has to look at what ended up inside Cluster 0 and interpret it ("oh, these are all the low-reflectance, high-near-infrared pixels — that's vegetation"). Classification predicts a known answer; clustering discovers a structure that didn't have a name yet.

Measuring "similar": the distance a cluster is built on

Before any algorithm can group points by similarity, "similarity" has to become a number. The standard choice is Euclidean distance, and it is worth deriving rather than memorizing, because every step of k-means later depends on it.

For two points in a 2-D plane, P = (x₁, y₁) and Q = (x₂, y₂), draw the right triangle formed by the horizontal gap (x₁ − x₂), the vertical gap (y₁ − y₂), and the straight-line segment PQ as the hypotenuse. By the Pythagorean theorem:

d(P, Q)² = (x₁ − x₂)² + (y₁ − y₂)², so d(P, Q) = √( (x₁ − x₂)² + (y₁ − y₂)² )

Nothing about this derivation is special to two dimensions — it generalizes directly. If a data point has n numeric features (in remote sensing, n reflectance bands; in a student dataset, maybe "hours of self-study" and "hours of sleep"), two points P = (p₁, p₂, …, pₙ) and Q = (q₁, q₂, …, qₙ) have distance:

d(P, Q) = √( (p₁ − q₁)² + (p₂ − q₂)² + … + (pₙ − qₙ)² )

Squaring each coordinate difference, summing, and taking a square root — this single formula is what "closeness" means for the rest of this chapter. Notice something important already: every feature contributes to this sum in the same units it was measured in. If one feature is measured in rupees (say, ranging into the thousands) and another in a count from 1 to 10, the rupee feature will dominate the sum purely because its numbers are bigger — not because it is more important. Keep this in mind; it becomes a real bug later.

What a cluster "should" look like: the k-means objective

The most widely used clustering algorithm, k-means, formalizes "good clustering" with a single number to minimize: the total squared distance from each point to the centre of the cluster it belongs to. This quantity is called the within-cluster sum of squares (WCSS):

WCSS = Σ over all clusters C   Σ over all points x in C   d(x, centroid of C)²

A smaller WCSS means points sit tighter around their cluster's centre — a "tighter," more coherent grouping. k-means tries to choose both (a) which points go in which cluster, and (b) where each cluster's centre sits, to make WCSS as small as possible.

This raises an exact question: given a fixed set of points already assigned to one cluster, where should that cluster's centre be to minimize the sum of squared distances to them? Do not take the answer ("the average") on faith — derive it.

Work in one dimension first, since the same logic extends coordinate-by-coordinate to any number of dimensions. Suppose a cluster contains points x₁, x₂, …, xₙ, and you want to choose a single number c (the centroid) that minimizes:

f(c) = Σᵢ (xᵢ − c)²

Differentiate with respect to c and set the derivative to zero, the standard first-year calculus test for a minimum:

f′(c) = Σᵢ −2(xᵢ − c) = −2Σᵢxᵢ + 2nc

Setting f′(c) = 0:   2nc = 2Σᵢxᵢ   ⟹   c = (1/n) Σᵢxᵢ

That is exactly the arithmetic mean of the points. Checking it is a minimum and not a maximum: f″(c) = 2n, which is positive for any n ≥ 1, confirming c is indeed the minimizer, not the maximizer. So the mathematically correct centre of a cluster — the point that minimizes total squared distance to its members — is precisely its mean. This is why the algorithm is called k-means: at every step, each cluster's representative point is recomputed as the mean of its current members. In more than one dimension, the same derivative-and-set-to-zero argument applies independently to each coordinate, so the centroid of a multi-dimensional cluster is simply the coordinate-wise mean of its points.

Lloyd's algorithm: how k-means actually iterates

With "distance" and "best centre" both nailed down, the algorithm (formally called Lloyd's algorithm, though everyone just calls it k-means) is four steps repeated until nothing changes:

1. Choose k, the number of clusters, and pick k initial centroids (often just k of the actual data points, chosen randomly).
2. Assign: for every data point, compute its distance to all k centroids and put it in the cluster of the nearest one.
3. Update: recompute each cluster's centroid as the mean of the points now assigned to it (this is exactly the minimizer derived above).
4. Repeat steps 2–3 until no point changes cluster (equivalently, until the centroids stop moving). At this point WCSS can no longer be reduced by re-assignment or re-averaging, and the algorithm has converged to a local minimum.

Each assignment step can only decrease or hold WCSS (every point is moved to a strictly closer centroid or stays put), and each update step can only decrease or hold it too (the mean is the exact minimizer for the current grouping). Since WCSS is bounded below by zero and never increases, the algorithm is guaranteed to stop — though not necessarily at the best possible clustering, a point returned to shortly.

Working the algorithm by hand

Take five numbers as a one-dimensional dataset — think of them as, say, marks scored by five students on a 100-mark test: {2, 4, 10, 12, 20}. Run k-means with k = 2, deliberately starting from a poor initialization: the two smallest values, C1 = 2 and C2 = 4.

Iteration 1. Assign each point to its nearer centroid using |x − c|, the 1-D version of Euclidean distance:

• 2: distance to C1 is 0, to C2 is 2 → joins Cluster 1
• 4, 10, 12, 20: each is at least as close to C2 (4) as to C1 (2) → all join Cluster 2

New centroids: C1 = mean(2) = 2.0. C2 = mean(4, 10, 12, 20) = 46 / 4 = 11.5.

Iteration 2. Re-assign using the updated centroids C1 = 2.0, C2 = 11.5:

• 2: |2 − 2.0| = 0 vs |2 − 11.5| = 9.5 → Cluster 1
• 4: |4 − 2.0| = 2 vs |4 − 11.5| = 7.5 → Cluster 1 (this point has switched clusters)
• 10, 12, 20: each still closer to 11.5 → Cluster 2

New centroids: C1 = mean(2, 4) = 3.0. C2 = mean(10, 12, 20) = 42 / 3 = 14.0.

Iteration 3. Re-assign using C1 = 3.0, C2 = 14.0: every point lands in the same cluster as before (check 4: |4−3|=1 vs |4−14|=10, still Cluster 1). Since the assignment did not change, the means don't change either — WCSS cannot be reduced further. The algorithm has converged: Cluster 1 = {2, 4}, Cluster 2 = {10, 12, 20}.

This trace is important for a reason beyond arithmetic practice: the bad initial guess (2 and 4, both from the same "true" group) still self-corrected within two iterations, because reassignment is checked fresh at every step. That is the mechanism, not a coincidence.

Here is the same logic as runnable code — trace it yourself against the hand-worked iterations above:

points = [2, 4, 10, 12, 20]
c1, c2 = 2, 4  # deliberately poor initial centroids

for iteration in range(1, 6):
    cluster1, cluster2 = [], []
    for x in points:
        if abs(x - c1) <= abs(x - c2):
            cluster1.append(x)
        else:
            cluster2.append(x)
    new_c1 = sum(cluster1) / len(cluster1)
    new_c2 = sum(cluster2) / len(cluster2)
    print(f"Iteration {iteration}: C1={cluster1} mean={new_c1}, "
          f"C2={cluster2} mean={new_c2}")
    if new_c1 == c1 and new_c2 == c2:
        break
    c1, c2 = new_c1, new_c2

Running this prints exactly three lines, matching the hand trace:

Iteration 1: C1=[2] mean=2.0, C2=[4, 10, 12, 20] mean=11.5
Iteration 2: C1=[2, 4] mean=3.0, C2=[10, 12, 20] mean=14.0
Iteration 3: C1=[2, 4] mean=3.0, C2=[10, 12, 20] mean=14.0

The loop prints iteration 3 before checking that nothing changed, then breaks — which is why the converged state appears twice, once as the freshly computed result and once confirming stability.

Choosing k: the elbow method

k-means needs k handed to it — it will not tell you how many groups "really" exist. But you can compare WCSS across different values of k on the same data and look for the point of diminishing returns. Using the same five marks {2, 4, 10, 12, 20}:

• k = 1 (one cluster, centroid = mean of all five = 48/5 = 9.6): WCSS = (2−9.6)² + (4−9.6)² + (10−9.6)² + (12−9.6)² + (20−9.6)² = 57.76 + 31.36 + 0.16 + 5.76 + 108.16 = 203.2
• k = 2 (the converged clusters above, centroids 3.0 and 14.0): WCSS = 1 + 1 + 16 + 4 + 36 = 58
• k = 3 (natural split {2,4}, {10,12}, {20}, centroids 3, 11, 20): WCSS = 1 + 1 + 1 + 1 + 0 = 4
• k = 4 (e.g. {2}, {4}, {10,12}, {20}): WCSS = 0 + 0 + 1 + 1 + 0 = 2
• k = 5 (every point its own cluster): WCSS = 0

WCSS always falls (or stays flat) as k grows, and hits exactly zero when k equals the number of points — because then every "cluster" is a single point at distance zero from its own mean. That extreme is useless: it is the clustering equivalent of overfitting, memorizing the data instead of describing its structure. This is the second misconception worth naming directly: lower WCSS does not mean a better clustering. The elbow method instead looks at how much WCSS drops with each additional cluster: 203.2 → 58 is a drop of 145.2, then 58 → 4 is a drop of 54, then 4 → 2 is a drop of only 2. The sharp flattening after k = 3 is the "elbow" — beyond it, extra clusters buy almost nothing. Note this heuristic gives a range, not a single provably correct answer; on this tiny dataset, both k = 2 (the two obvious groups of small vs. large marks) and k = 3 (splitting off the outlier 20) are defensible, and picking between them needs domain judgment, not just the graph.

Why initialization matters, and k-means++

The worked example above started from a poor guess and still converged to the right answer, but that was not guaranteed — it happened to recover in this case. In general, since Lloyd's algorithm only ever decreases WCSS, it converges to whichever local minimum its starting centroids happen to fall into, not necessarily the smallest possible WCSS overall (the global minimum). Two different random starting centroids can converge to two different final clusterings on the same data. The standard fix is k-means++: instead of picking all k initial centroids uniformly at random, pick the first one randomly, then pick each subsequent centroid with probability proportional to its squared distance from the nearest centroid already chosen. This actively spreads the initial centroids apart across the data rather than letting two of them start out crowded into the same true cluster (exactly the situation this chapter's worked example began in), which sharply reduces the chance of a bad local minimum. In practice, running k-means several times with different k-means++ initializations and keeping the run with the lowest final WCSS is standard.

Where k-means breaks: scale and shape

Two practical failures are worth understanding precisely, because both come directly from the distance formula derived earlier.

Scale. Recall that Euclidean distance sums squared differences across all features equally. Suppose you are clustering UPI transactions using two features: transaction amount in rupees (ranging from ₹10 to ₹50,000) and number of transactions that day (ranging from 1 to 20). A difference of ₹500 between two amounts contributes 500² = 250,000 to the squared-distance sum; a difference of even 15 in transaction count contributes only 15² = 225. The amount feature would completely swamp the count feature — the algorithm would effectively cluster on rupee amount alone and ignore the count feature entirely, not because count is unimportant but because its numbers are smaller. The standard fix is to standardize each feature before clustering: subtract its mean and divide by its standard deviation, so every feature contributes on a comparable scale.

Shape. k-means implicitly assumes clusters are roughly ball-shaped (convex) regions, because it groups every point with its nearest centroid — geometrically, this always partitions the plane into convex regions. It fails on shapes that aren't convex. A classic failure case: two concentric circles of points, one ring inside another. The "true" grouping (inner ring vs. outer ring) cannot be reproduced with a straight-line boundary from any pair of centroids, since both centroids would naturally sit near the middle and end up splitting each ring in half instead of separating the two rings. Density-based methods such as DBSCAN, which group points by how densely packed they are rather than by distance to a mean, handle such shapes correctly, though they lie outside the scope of this chapter.

A different family of methods sidesteps the "choose k in advance" requirement altogether: hierarchical (agglomerative) clustering starts with every point as its own cluster and repeatedly merges the two closest clusters — where "closest" might mean smallest minimum distance between any pair of points (single linkage), largest maximum distance (complete linkage), or average pairwise distance — until only one cluster remains. The full sequence of merges is recorded in a tree called a dendrogram, and cutting the dendrogram at any height yields a valid clustering for however many groups that height corresponds to — letting you choose k after seeing the structure, rather than before.

Where this fits in your exams

Being precise here matters more than sounding impressive: clustering is not part of the IIT-JEE or BITSAT syllabus, since both are physics–chemistry–mathematics examinations with no data-science component. Where it genuinely appears: it sits inside CBSE's Artificial Intelligence curriculum under exactly the "data has structure worth discovering without labels" theme this chapter opened with, and it is an explicit topic in GATE's Data Science and Artificial Intelligence paper, which lists clustering algorithms including k-means and hierarchical methods directly in its syllabus. If your competitive-exam track runs through GATE DA or a computer-science-with-data-science stream later, the derivation of the centroid-as-mean result and the mechanics of Lloyd's algorithm in this chapter are exactly the kind of first-principles question that gets asked — not just "name the algorithm," but "prove why the update step uses the mean."

Check yourself

• Run k-means by hand with k = 2 on the marks {30, 35, 80, 85, 90}, starting from centroids 30 and 35. (Following the same method as the worked example: iteration 1 gives clusters {30} and {35, 80, 85, 90} with means 30.0 and 72.5; iteration 2 reassigns 35 into the first cluster, giving {30, 35} and {80, 85, 90} with means 32.5 and 85; iteration 3 confirms no further change.)
• Why does standardizing features before clustering matter for a dataset combining UPI transaction amount (rupees) and transaction count (a small integer)? Answer using the squared-distance argument above, not just "because it's good practice."
• Explain, using the convex-region argument, why k-means with k = 2 cannot correctly separate two concentric rings of points even if you run it from many different initializations.
• A classmate says, "I'll just keep increasing k until WCSS is as small as possible, then I'll know I've found the best clustering." What is wrong with this reasoning, and what does WCSS equal when k is set equal to the number of data points?

Summary

Clustering groups data using only the data itself, with no labels to check against — the defining difference from classification. Similarity is made precise with Euclidean distance, derived from the Pythagorean theorem and generalized to any number of features. k-means minimizes the within-cluster sum of squared distances (WCSS); the centroid that minimizes this quantity for a fixed set of points is provably their mean, found by setting the derivative of the squared-error objective to zero. Lloyd's algorithm alternates assigning points to their nearest centroid and recomputing centroids as means, and is guaranteed to converge because WCSS never increases — but only to a local minimum, which is why initialization (and k-means++) matters. The elbow method compares WCSS across values of k to choose a reasonable cluster count, while remembering that WCSS trivially reaches zero when every point is its own cluster, which is not a meaningful clustering. k-means further assumes features are comparably scaled and clusters are roughly convex in shape; hierarchical clustering offers an alternative that builds a full dendrogram of merges instead of committing to one k upfront.