A Question With No Labels
Suppose your school hands you an anonymised sheet of Math and Science internal-assessment marks (out of 10, scaled down) for six students, with no other information — no names, no "topper" tag, no "needs support" flag. Six pairs of numbers. Nothing tells you which students resemble each other. Your job: find natural groups in this data, if any exist, using only the numbers themselves.
This is a fundamentally different problem from anything in a typical classification chapter. When you build a classifier to predict whether a student will pass or fail, you train on examples that already carry the correct answer — pass/fail labels attached by a teacher. That is supervised learning: you have inputs and known outputs, and you learn the mapping between them. Here you have no known outputs at all. Nobody has told you there are two groups, or three, or what those groups should be called. You only have the raw coordinates. This is unsupervised learning — the algorithm has to discover structure that was never labelled for it.
K-Means is the most widely used algorithm for exactly this task: given a pile of unlabelled numeric data, partition it into k groups (clusters) such that points inside a group are close to each other and groups are separated from one another. The "k" is a number you choose in advance — k=2 means "find two groups," k=3 means "find three." What the algorithm decides for you is which points belong to which group and where the centre of each group sits.
Intuition Before Formalism: Sort, Find Center, Re-sort
Before writing a single formula, do this in your head. Imagine two students are appointed team captains and told to stand anywhere in the classroom. Every other student walks to whichever captain is physically nearest to them — that is the entire "assignment" rule, nothing more. Now each captain looks at everyone who walked toward them and moves to stand exactly at the average position of their team (if your team is scattered to the left, you shift left; if they're spread toward the back, you shift back). Once both captains have re-positioned, some students near the boundary between the two teams may now find the other captain is closer, so they switch sides. The captains reposition again. You repeat this — walk to nearest captain, captain moves to the average of its team — and after a few rounds, nobody switches sides any more and the captains stop moving. The classroom has settled into two stable teams.
That entire process — described here with people, no algebra yet — is K-Means. The captains are called centroids. "Walk to the nearest captain" is the assignment step. "Captain moves to the team's average position" is the update step. "Repeat until nobody switches" is convergence. Everything that follows is just making this precise enough to run on a computer with thousands of points instead of six students.
Lloyd's Algorithm, Precisely
The standard K-Means procedure (formally called Lloyd's algorithm, after Stuart Lloyd, who described it at Bell Labs in 1957 for a signal-processing problem) works on points in a coordinate space — in our example, each student is a point (Math mark, Science mark).
- Choose k, the number of clusters, and pick k initial centroids. A simple, common choice (used below) is to pick k of the actual data points at random as the starting centroids — this is called Forgy initialisation.
- Assignment step: for every data point, compute its distance to every centroid and assign the point to the nearest one. K-Means uses ordinary straight-line (Euclidean) distance, but in code you compare squared distances — since square-rooting is monotonic (bigger squared distance always means bigger distance), skipping the square root gives the identical nearest centroid while avoiding unnecessary computation.
- Update step: for each cluster just formed, recompute its centroid as the mean (average) of every point currently assigned to it, separately for each coordinate.
- Repeat steps 2 and 3 until the assignments stop changing (equivalently, the centroids stop moving).
What the algorithm is actually trying to minimise is a single number called the Within-Cluster Sum of Squares (WCSS): add up the squared distance from every point to its own cluster's centroid, across all clusters. Small WCSS means points sit tightly around their centroids; that is the definition of a "good" clustering that K-Means is chasing.
Worked Example: Two Groups From Six Points
Here are our six students' (Math, Science) marks:
- P1 = (0, 0)
- P2 = (1, 0)
- P3 = (0, 1)
- P4 = (4, 4)
- P5 = (5, 4)
- P6 = (4, 5)
Let k=2, and initialise (Forgy method) by picking two actual data points as starting centroids: C1 = P1 = (0,0) and C2 = P4 = (4,4).
Assignment step 1. Compute each point's distance to C1(0,0) and C2(4,4) and keep the nearer one. P1 is 0 from C1 and √32≈5.66 from C2 → joins C1. P2(1,0) is 1 from C1 and 5 from C2 → joins C1. P3(0,1) is 1 from C1 and 5 from C2 → joins C1. P4(4,4) is 0 from C2 → joins C2. P5(5,4) is 1 from C2 and √41≈6.40 from C1 → joins C2. P6(4,5) is 1 from C2 → joins C2. Result: Cluster 1 = {P1, P2, P3}, Cluster 2 = {P4, P5, P6}.
Update step 1. New C1 = mean of P1,P2,P3 = ((0+1+0)/3, (0+0+1)/3) = (1/3, 1/3). New C2 = mean of P4,P5,P6 = ((4+5+4)/3, (4+4+5)/3) = (13/3, 13/3).
Assignment step 2. Re-check every point against the new centroids. Every point is still dramatically closer to its current centroid than to the other one (P2 is at distance²=5/9≈0.56 from the new C1 versus a huge distance from C2 clear across the plane) — nobody switches sides. Since the assignment didn't change, the update step will recompute the identical centroids, and the algorithm has converged after just one real update.
Now compute the exact distances that make up the final WCSS, since this is worth doing carefully by hand once. For Cluster 1, centroid (1/3, 1/3): P1(0,0) is at horizontal and vertical gap (1/3, 1/3), so its straight-line distance is √(1/9+1/9) = √(2)/3 ≈ 0.471, squared distance = 2/9. P2(1,0) has gaps (2/3, 1/3), distance √(4/9+1/9) = √5/3 ≈ 0.745, squared distance = 5/9. P3(0,1) has gaps (1/3, 2/3) by symmetry with P2, squared distance = 5/9. Cluster 1's contribution to WCSS: 2/9 + 5/9 + 5/9 = 12/9 = 4/3. By the symmetric geometry of this example, Cluster 2 contributes an identical 4/3. Total WCSS at convergence = 4/3 + 4/3 = 8/3 ≈ 2.67.
Here is the same run as short, traceable Python — no library beyond the built-ins, so you can follow every line:
points = [(0, 0), (1, 0), (0, 1), (4, 4), (5, 4), (4, 5)] # P1..P6
def sq_dist(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def mean_point(pts):
n = len(pts)
return (sum(p[0] for p in pts) / n, sum(p[1] for p in pts) / n)
centroids = [points[0], points[3]] # Forgy init: start at P1, P4
for step in range(10):
clusters = [[], []]
for p in points:
d0, d1 = sq_dist(p, centroids[0]), sq_dist(p, centroids[1])
clusters[0 if d0 <= d1 else 1].append(p)
updated = [mean_point(c) for c in clusters]
if updated == centroids:
print(f"Converged after {step} assignment pass(es)")
break
centroids = updated
print("Final centroids:", centroids)
print("Cluster 1:", clusters[0])
print("Cluster 2:", clusters[1])
Tracing it: on step 0, centroids start at (0,0) and (4,4), the assignment produces {P1,P2,P3} and {P4,P5,P6}, and updated becomes (1/3,1/3) and (13/3,13/3) — not equal to the starting centroids, so the loop continues with centroids = updated. On step 1, the assignment against the new centroids reproduces the exact same two clusters, so updated comes out identical to centroids, the equality check fires, and it prints "Converged after 1 assignment pass(es)." The final printed centroids are approximately (0.333, 0.333) and (4.333, 4.333) — matching the hand computation exactly.
Why the Mean? Proving It With Algebra You Already Know
The update step says "move the centroid to the average of its cluster." This isn't a convenient guess — it is provably the single best possible location for a centroid, in the sense of minimising the sum of squared distances to its cluster's points. You can prove this using nothing more than completing the square, the same technique you already use to solve quadratic equations of the form ax² + bx + c = 0. We're not solving for a root here — we're reusing the identical algebraic move to find the lowest point of a quadratic expression instead.
Work in one coordinate first (say, just the Math-mark axis), with n points x₁, x₂, …, xₙ assigned to a cluster. We want the value m that minimises the sum of squared gaps:
f(m) = (x₁ − m)² + (x₂ − m)² + … + (xₙ − m)²
Expand every term: (xᵢ − m)² = xᵢ² − 2xᵢm + m². Summing across all n points:
f(m) = (x₁² + x₂² + … + xₙ²) − 2m(x₁ + x₂ + … + xₙ) + nm²
Write S = x₁+x₂+…+xₙ (the sum) and Q = x₁²+x₂²+…+xₙ² (the sum of squares). Then f(m) = nm² − 2Sm + Q — a quadratic in m, and because its leading coefficient n is always positive (n is a count of points, at least 1), this parabola opens upward and genuinely has a minimum, not a maximum. Now complete the square exactly as you would to solve nm² − 2Sm + Q = 0:
f(m) = n·(m² − (2S/n)m) + Q = n·[(m − S/n)² − (S/n)²] + Q = n·(m − S/n)² + (Q − S²/n)
The term n·(m − S/n)² can never be negative, whatever value m takes — it's n times a square. So the whole expression f(m) is smallest exactly when that term is zero, which happens only at m = S/n. That is precisely the mean of x₁,…,xₙ. The minimum value itself works out to Q − S²/n, the leftover constant once the squared term vanishes — remember this quantity, it resurfaces below. Since squared Euclidean distance in two dimensions is (xᵢ−mx)² + (yᵢ−my)², the x-terms and y-terms never mix, so this exact 1-D argument applies separately and independently to the Math-mark coordinate and the Science-mark coordinate. That is the complete, rigorous justification for "centroid = mean of the cluster," built entirely from Class 10 algebra, with no calculus anywhere in it.
As a check, apply the Q − S²/n formula to Cluster 1's Math-mark values {0,1,0}: S=1, Q=1, n=3, giving 1 − 1/9·3... more directly, 1 − (1²)/3 = 1 − 1/3 = 2/3. Doing the same for the Science-mark values {0,0,1} also gives 2/3. Add them: 2/3 + 2/3 = 4/3 — exactly the WCSS contribution of Cluster 1 computed by hand earlier. The algebra and the worked arithmetic agree.
Two Misconceptions Worth Killing Now
"The k in k-means is the same idea as the k in k-NN." It is not, and mixing them up is one of the most common errors CBSE students make when these two algorithms are taught back to back. In k-Nearest Neighbours (a supervised algorithm), k is the number of labelled neighbours you consult to vote on a new point's class — every training point already has a known label, and k just controls how many votes you count. In K-Means (unsupervised), k is the number of groups you are asking the algorithm to invent from scratch — there are no labels anywhere in the process. Same letter, two unrelated meanings: one counts votes among known answers, the other counts groups that don't exist yet.
"K-Means finds the best possible clustering." It doesn't — it only guarantees a locally best clustering. Here is why the algorithm is even guaranteed to stop at all: at every assignment step, WCSS cannot increase (each point only ever switches to a centroid that is at least as close as the one it had), and at every update step, WCSS cannot increase either (the proof above shows the mean is the unique minimiser for the current assignment). Since WCSS is non-increasing at every step and there are only finitely many ways to partition n points into k groups, the algorithm cannot cycle forever — it must stop. But "stops" only means it reached a partition that no single point-swap or centroid-move can improve; it says nothing about whether some completely different partition would have had lower WCSS overall. Different starting centroids can and do converge to different final clusters with different final WCSS values. This is precisely why smarter initialisation matters, which the Limitations section below addresses directly.
Choosing k: The Elbow Method
K-Means requires you to state k in advance, but real data rarely announces its own number of natural groups. The elbow method works by running K-Means for several values of k and plotting WCSS against k. Using the Q − S²/n formula from the algebra section, we can compute this exactly for our six points.
For k=1, all six points form one cluster; its centroid is the mean of all six points, (7/3, 7/3). Working through Q − S²/n on each axis (S=14, Q=58, n=6 for both Math and Science marks here) gives 58 − 196/6 = 25.33 per axis, so WCSS(k=1) = 50.67.
For k=2, we already computed WCSS(k=2) = 8/3 ≈ 2.67 above.
For k=3, suppose the algorithm converges to {P1}, {P2, P3}, {P4, P5, P6} — a plausible split for this k. {P1} alone contributes 0 (a single point sits exactly at its own centroid). {P2, P3} has centroid (0.5, 0.5), contributing (1−0.5)²+(0−0.5)² = 0.5 for P2 and the same 0.5 for P3, total 1.0. {P4, P5, P6} still contributes 4/3 as before. WCSS(k=3) ≈ 0 + 1.0 + 1.33 = 2.33.
Lay these three numbers out: 50.67 → 2.67 → 2.33. The drop from k=1 to k=2 is enormous (a fall of 48), while the drop from k=2 to k=3 is small (only about 0.33). That sharp bend — a steep fall followed by a near-flat continuation — is the "elbow," and it sits at k=2. This matches what you can already see geometrically: the six points genuinely form two tight groups, and asking for a third group only slices one existing group into two pieces that were never really separate, buying very little reduction in WCSS for the added complexity.
Where K-Means Breaks Down
K-Means is fast and easy to reason about, but it rests on assumptions worth stating explicitly rather than discovering the hard way. It assumes clusters are roughly round (technically, convex) blobs of comparable size and spread — it will badly mis-split two crescent-shaped or very differently sized clusters, because it can only ever draw straight-line boundaries between centroids. It is sensitive to outliers, since a single extreme point can pull a centroid's mean noticeably off-centre. It needs numeric features on comparable scales — if Math marks ran 0–10 while some other feature ran 0–10,000, that second feature would dominate every distance calculation and silently decide most assignments. And, as already covered, it is sensitive to initialisation: a poor starting placement of centroids can converge to a visibly worse local optimum than a good one.
That last problem has a well-known fix. David Arthur and Sergei Vassilvitskii's k-means++ (2007) replaces plain random initialisation with a smarter randomised scheme: pick the first centroid uniformly at random, then pick each subsequent centroid with probability proportional to its squared distance from the nearest centroid already chosen — spreading the starting centroids apart rather than letting them land close together by chance. This single change provably improves both the speed and the final quality of the clustering on average, and it's the default initialisation in most production K-Means implementations today. Separately, on the question of speed: in the worst case Lloyd's algorithm can theoretically take an exponential number of iterations to converge, but David Arthur, Bodo Manthey, and Heiko Röglin's smoothed-analysis result (2009) proved that under small random perturbations of the input — a reasonable model for real, noisy data — the expected number of iterations is only polynomial. That gap between a frightening worst case and fast real-world behaviour is exactly why K-Means remains practical at scale despite the pessimistic theory.
Where the Underlying Algebra Shows Up in Your Exams
K-Means itself is not a topic tested in IIT-JEE or BITSAT — those exams do not cover machine learning. But the specific algebraic move this chapter's derivation relies on — completing the square to locate the minimum (or maximum) of a quadratic expression, without any calculus — is a direct, frequently examined technique in JEE and BITSAT algebra, usually phrased as "find the minimum value of ax² + bx + c" or "find the range of a quadratic function." The derivation of centroid = mean above is that exact technique, applied to a machine-learning objective instead of a textbook quadratic. If you're taking CBSE's Artificial Intelligence skill subject, clustering and unsupervised learning appear directly in the syllabus and in the practical project work expected there — this chapter's worked example, done by hand on paper, is a reasonable model for how that practical work should be shown and justified.
Check Your Understanding
- Using the six points above, suppose instead you had initialised with C1 = P2 = (1,0) and C2 = P5 = (5,4). Work through one assignment and one update step. Do you land on the same final clusters as the worked example? (You should — the two groups are separated widely enough that this initialisation converges to the identical partition, though it's worth confirming by hand rather than assuming.)
- Compute the WCSS for the "wrong" clustering {P1, P2, P4} and {P3, P5, P6} (deliberately mixing the two natural groups). Confirm it comes out higher than 8/3, and explain in one sentence why K-Means, run from a reasonable starting point, would never settle on this partition.
- Explain, without redoing the full completing-the-square derivation, why the argument in the "Why the Mean?" section only works because we used squared distance and would not go through if we had instead tried to minimise the sum of plain (unsquared) distances.
- A classmate initialises both centroids at the exact same point. Trace what happens on the first assignment and update step, and explain why this initialisation is unrecoverable for K-Means.
Summary
K-Means is an unsupervised algorithm: given unlabelled numeric points and a chosen k, it alternates an assignment step (each point joins its nearest centroid, compared by squared Euclidean distance) and an update step (each centroid moves to the mean of its current cluster), repeating until nothing changes. That "move to the mean" rule is not arbitrary — completing the square on the sum of squared distances proves the mean is the unique point minimising that sum, using only Class 10 algebra. The algorithm is guaranteed to terminate, because WCSS never increases and only finitely many partitions exist, but it is only guaranteed to reach a local minimum of WCSS, not the global one, which is why initialisation strategies like k-means++ matter in practice. The elbow method — plotting WCSS against k and looking for where the steep drop flattens out — gives a principled way to choose k itself, as the 50.67 → 2.67 → 2.33 sequence on our six-point example demonstrates directly. And K-Means' core assumption — that clusters are round, comparably sized blobs on comparably scaled features — is exactly the condition to check before trusting its output on new data.