The K-means algorithm is one of the simplest and most widely used clustering methods. It aims to find $K$ centroids that minimize the sum of squared distances from each data point to its nearest centroid.
K-means is iterative: assign points to the nearest centroid, update centroids to the mean of their points, repeat until convergence. Despite its simplicity, it is powerful for exploratory data analysis, image compression, and customer segmentation.
Part 1: Interactive 2D K-Means
The plot below shows synthetic data with three natural clusters. Use the slider to change $K$ – the algorithm re-runs instantly. Black crosses are centroids; inertia (SSE) is displayed.
Figure 1: K-means clustering. Each colour is a cluster; black crosses are centroids.
Part 2: When K-Means Fails – The Shape Limitation
K-means assumes spherical clusters. With concentric circles (below), K=2 produces a linear cut that fails.
Figure 2: K-means (K=2) on concentric circles – fails to capture the ring structure.
Part 3: The K-Means Algorithm – Step by Step
The algorithm iterates between two steps until convergence:
- Assignment step: For each point, assign it to the nearest centroid (using Euclidean distance).
- Update step: Recompute each centroid as the mean (average) of all points assigned to it.
But what does "nearest" mean, and what exactly is the algorithm trying to optimize? K‑means minimizes a quantity called the inertia (or within‑cluster sum of squares, WCSS). For a given set of cluster assignments, the inertia is defined as:
\[ J = \sum_{i=1}^{N} \| \mathbf{x}_i - \boldsymbol{\mu}_{c_i} \|^2 \]Let's break this down:
- \( N \) is the total number of data points.
- \( \mathbf{x}_i \) is the \(i\)-th data point (a vector in \(d\)-dimensional space).
- \( c_i \) is the index of the cluster to which point \(i\) is assigned.
- \( \boldsymbol{\mu}_{c_i} \) is the centroid (mean vector) of that cluster.
- \( \| \mathbf{x}_i - \boldsymbol{\mu}_{c_i} \|^2 \) is the squared Euclidean distance between the point and its cluster centroid.
In other words, for every point we measure how far it is from its cluster center, square that distance, and sum over all points. The result is a single number that quantifies how compact the clusters are. The smaller the inertia, the tighter the clusters – points are closer to their respective centroids.
K‑means tries to find cluster assignments and centroids that minimize this inertia. The assignment step fixes the centroids and assigns each point to the nearest one, which is exactly the action that locally reduces inertia. Then the update step recomputes the centroids as the mean of the assigned points – which, by definition, minimises the sum of squared distances for that cluster. By alternating these two steps, K‑means is guaranteed to converge to a local minimum of \( J \).
The inertia is also often called the Sum of Squared Errors (SSE), and it serves as a natural measure of clustering quality. That's why in the interactive plot above we display it – it gives you immediate feedback on how well the current \( K \) fits the data.
K-means is guaranteed to converge to a local minimum of \( J \), but the result depends on the initial centroids. A common improvement is K‑means++, which spreads out the initial centroids to get better and more consistent results.
How to Choose K?
The elbow method plots inertia vs. K; the elbow suggests a good K.
Figure 3: Inertia vs. K – elbow around K=3 matches the true number of clusters.
Why Is K-Means So Popular?
- Simplicity and speed.
- Interpretable centroids.
- Scales well.
Common Pitfalls
- Must choose K in advance.
- Sensitive to initialisation (use K-means++).
- Assumes spherical clusters.
- Outliers can distort centroids.
The Takeaway
K-means is a powerful clustering tool. Understanding its limitations helps you apply it effectively and know when to use more advanced methods.