K-Means Clustering: Centroids, Voronoi Cells and Inertia

Partition first, ask questions never

K-means is the simplest widely used unsupervised learning algorithm: given a set of points and a chosen number of clusters k, it partitions the points into k groups so that each point is closer to its own cluster's centre (its centroid) than to any other cluster's centre. There are no labels to learn from — the algorithm discovers structure purely from how the points are distributed in space.

The algorithm alternates two simple steps until nothing changes, a special case of a broader technique called Lloyd's algorithm: assignment — give every point to its nearest centroid — and update — move every centroid to the mean position of the points now assigned to it. Because reassigning points can never increase the total squared distance from points to their assigned centroid, and recomputing centroids as means can only decrease it further, the objective is guaranteed to be monotonically non-increasing at every step, which is why the loop always terminates rather than oscillating forever.

1. pick k initial centroids
2. repeat until assignments stop changing:
     assign each point to its nearest centroid   (Voronoi partition)
     move each centroid to the mean of its assigned points
3. done — clusters are the final Voronoi regions

What K-means is actually minimising

The formal objective is within-cluster sum of squares (WCSS), also called inertia: the total squared Euclidean distance from every point to its own cluster's centroid, summed over all clusters. Every iteration of assignment-then-update is provably non-increasing in this quantity, which is why watching inertia drop, level off, and eventually flatten out is the standard way to watch convergence happen live — a flat inertia curve means the assignment has stopped changing and the algorithm has reached a local optimum of WCSS.

Geometrically, fixing the centroids and asking 'which centroid is each point closest to' is exactly the definition of a Voronoi diagram: the k centroids partition the plane into k convex regions, each the set of points closer to that centroid than to any other. K-means is, in this sense, iteratively refitting a Voronoi diagram to the data — moving each generating point to the centre of mass of its own cell, then recomputing the cells for the new points, and repeating.

Local optima and why initialisation matters

K-means is only guaranteed to find a local minimum of WCSS, not the global one — starting from different initial centroids can converge to different, sometimes visibly worse, final clusterings, especially with clusters of very different sizes or densities. Plain random initialisation is notoriously prone to picking two initial centroids close together inside what should be one cluster, leaving another cluster with no nearby centroid at all. K-means++ fixes this by choosing initial centroids sequentially with probability proportional to squared distance from already-chosen centroids, which strongly biases the starting positions toward being spread out — in practice it converges faster and to noticeably better local optima than uniform random starts, and is the default initialisation in essentially every modern implementation.

Choosing k: the elbow and silhouette methods

K-means needs k specified in advance, and the algorithm has no way to tell you the 'right' one — inertia strictly decreases as k grows (more clusters can only fit the data at least as well, and k equal to the number of points drives WCSS to zero trivially), so you cannot simply pick the k that minimises WCSS. The elbow method plots WCSS against k and looks for the point where the rate of decrease sharply flattens — a visual, somewhat subjective heuristic based on diminishing returns. The silhouette score is more principled: for each point it compares average distance to points in its own cluster against average distance to points in the nearest other cluster, producing a score from -1 to 1 that rewards tight, well-separated clusters, and the k that maximises the average silhouette score across all points is a common, more quantitative choice.

Frequently asked questions

Try it live

Everything above runs in your browser — open K-Means Clustering and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.