What does each iteration of Lloyd's algorithm for k-means do?
answer
- two alternating steps per pass
- one step freezes centres, one freezes labels
- the total squared distance never goes up
- recentre on the group average
basics
~10 sEach Lloyd iteration does two things: assign every point to its nearest centroid, then move each centroid to the mean of the points assigned to it. The loop repeats until assignments stop changing.
solid answer
~50 sLloyd's algorithm is the standard way to fit k-means. You start from k initial centroids, then alternate two steps. The **assignment step** puts every point in the cluster whose centroid is closest by squared Euclidean distance, holding the centroids fixed. The **update step** replaces each centroid with the mean of the points now assigned to it, holding the labels fixed. Both steps minimise the same objective, the within-cluster sum of squares `WCSS = sum over clusters of sum over its points of ||x - centroid||^2`, so the objective can never increase from one pass to the next. Since there are only finitely many ways to label the points, the labels must stop changing after a finite number of passes, and that is convergence. One pass costs roughly `n * k * d` distance computations for n points, k clusters and d features.
code
python · 15 linespoints = [1.0, 2.0, 3.0, 10.0, 11.0, 12.0]
centroids = [1.0, 4.0] # a deliberately poor start
for step in range(1, 4):
groups = [[] for _ in centroids]
for x in points: # assignment step
best = min(range(len(centroids)), key=lambda i: (x - centroids[i]) ** 2)
groups[best].append(x)
centroids = [sum(g) / len(g) for g in groups] # update step
wcss = sum((x - centroids[i]) ** 2 for i, g in enumerate(groups) for x in g)
print(step, groups, centroids, round(wcss, 2))
# 1 [[1.0, 2.0], [3.0, 10.0, 11.0, 12.0]] [1.5, 9.0] 50.5
# 2 [[1.0, 2.0, 3.0], [10.0, 11.0, 12.0]] [2.0, 11.0] 4.0
# 3 [[1.0, 2.0, 3.0], [10.0, 11.0, 12.0]] [2.0, 11.0] 4.0go deeper
Be ready to name the two steps in order and say what stops the loop. Knowing that the centroid is an average of its members, not a real row from the table, is the detail juniors most often miss.
Explain why neither step can raise the within-cluster sum of squares, and why the update uses the mean specifically: the mean is the point minimising total squared distance. Mention the finite number of labellings as the termination argument.
Show the operational consequences: cost per pass grows with rows times clusters times features, empty clusters need a reseeding rule, and centroids presented to stakeholders are averages that may describe no real record. Say how you set the stopping tolerance.
Own the framing that k-means is an objective plus a heuristic, and that the choice of squared Euclidean distance is a modelling assumption about what 'similar' means for this data, not a neutral default. Be able to say when that assumption is not worth defending.
## What k-means is actually optimising k-means is defined by an objective, not by a procedure. Given n points and a chosen number of clusters k, it looks for an assignment of points to clusters and a set of k centre points that minimise the **within-cluster sum of squares (WCSS)**: ``` WCSS = sum over clusters c of sum over points x in c of ||x - mu_c||^2 ``` where `mu_c` is the centre (centroid) of cluster c and `||x - mu_c||^2` is squared Euclidean distance. Read plainly: every point pays a penalty equal to the square of its distance from its own cluster's centre, and we want the total penalty as small as possible. Nothing in this objective mentions density, connectivity or probability — it is pure squared distance to a centre. Finding the exact minimiser of WCSS is computationally hard in general, so in practice we use a heuristic that finds a good solution quickly. That heuristic is Lloyd's algorithm, and it is what almost everyone means when they say "k-means". ## The two steps Start with k initial centroids (chosen at random, or by a smarter seeding rule), then repeat: 1. **Assignment step.** Holding the centroids fixed, give each point the label of its nearest centroid, measured by squared Euclidean distance. Ties are broken arbitrarily. 2. **Update step.** Holding the labels fixed, replace each centroid with the arithmetic mean of the points currently carrying its label — the componentwise average across every feature. Stop when no point changes label between passes (or when the centroids move less than a small tolerance, or a maximum pass count is hit). ## Why each step can only help This is the part interviewers probe. Each step is an exact minimisation of the same objective over one block of variables while the other block is frozen — the pattern known as block coordinate descent. - In the assignment step the centroids are frozen. For a single point, its contribution to WCSS is its squared distance to whichever centre it is assigned to, so choosing the *nearest* centre is exactly the choice that minimises its contribution. Doing this for every point minimises WCSS over all possible labellings. - In the update step the labels are frozen. For a fixed set of points, the value m minimising `sum of ||x - m||^2` is the mean of those points — this is why the algorithm uses the mean and not the median, which would minimise a sum of absolute distances instead. So WCSS is non-increasing across passes. Combined with the fact that there are only finitely many ways to partition n points into k groups, the sequence of labellings cannot improve forever and cannot revisit a labelling with a strictly higher cost, so the algorithm terminates in a finite number of passes. Convergence is guaranteed; **optimality is not** — Lloyd's algorithm settles at a local minimum determined by where it started. ## A worked trace On the 1-D points 1, 2, 3, 10, 11, 12 started from centroids 1 and 4, the first pass groups {1, 2} and {3, 10, 11, 12} and recentres to 1.5 and 9.0, with WCSS 50.5. The second pass moves the 3 across, giving {1, 2, 3} and {10, 11, 12}, centres 2 and 11, WCSS 4.0. The third pass changes nothing, so it has converged. Notice the poor starting centre recovered here — it does not always. ## Practical points that follow from the mechanics - **A centroid is a mean, not a data point.** It usually sits at a location where no record exists — an average of averages. That matters when you present a cluster centre to a stakeholder as "a typical customer". - **Empty clusters can happen.** If a centroid attracts no points, its mean is undefined; implementations reseed it, typically at the point currently furthest from its own centre. - **The mean and squared Euclidean distance are a package.** The update step is only the exact minimiser because the objective is squared Euclidean. Swapping in a different distance breaks that guarantee. - **Feature units drive the result.** Because everything is distance, a feature measured on a large numeric range dominates the objective, so features are normally put on a comparable scale first. - **Cost.** One pass is about `n * k * d` distance evaluations, which is cheap and linear in the number of rows, and is a large part of why k-means stays popular on big tables. ## An application that makes the mechanics concrete Colour quantisation: treat every pixel of a photograph as a 3-D point in red-green-blue space and run k-means with k = 16. The assignment step groups pixels by colour similarity, the update step averages each group into one representative colour, and replacing every pixel with its centroid colour rewrites the image using just 16 colours. The 16 centroid colours are means, so most of them are not colours that appeared in the original photo.
- Why is Lloyd's algorithm guaranteed to stop rather than cycling forever?Each step minimises the within-cluster sum of squares over one block of variables with the other frozen, so the objective never increases. There are only finitely many ways to label n points into k groups, and a labelling with a strictly lower cost can never be revisited, so the labels must settle after finitely many passes.
- What happens if a centroid ends up with no points assigned to it?Its mean is undefined, so the update step has nothing to average. Implementations handle it rather than crash: the usual fix is to reseed that centroid at the data point currently furthest from its own centre, which both keeps k clusters alive and attacks the largest single contribution to the objective. Empty clusters are a symptom of poor initialisation or of k being larger than the structure supports.
- How would you use k-means to reduce a photograph to 16 colours?Treat every pixel as a 3-D point in red-green-blue space and run k-means with k = 16 over the pixels. Each centroid is the average colour of the pixels assigned to it, so replacing every pixel with its centroid rewrites the image in 16 colours. Most of those 16 are averages, so they need not appear in the original image.
It is like seating guests at k tables: everyone walks to the nearest table, then each table is wheeled to the middle of the people who sat down. Repeat until nobody moves.
saying these in an interview costs you the question
- Cannot say which quantity each step holds fixed
- Thinks a centroid must be one of the data points
- Believes a pass can increase the within-cluster sum of squares
- Says the algorithm just runs a fixed number of passes with no convergence test
- Confuses k-means' k with the k of k-nearest-neighbours