Unsupervised Machine Learning · Clustering

K-Means Clustering & Lloyd's Algorithm

Step-by-step frame-by-frame visualization of Voronoi point assignments and centroid convergence

Lloyd's Heuristic & Within-Cluster Sum of Squares (WCSS)

Given $n$ observations $\mathbf{x}_1, \dots, \mathbf{x}_n \in \mathbb{R}^d$, $K$-Means partitions the observations into $K$ sets $S = \{S_1, S_2, \dots, S_K\}$ to minimize the within-cluster sum of squares (also called inertia):

$$\arg\min_{S} \sum_{j=1}^{K} \sum_{\mathbf{x} \in S_j} \|\mathbf{x} - \boldsymbol{\mu}_j\|^2$$

Because finding the global minimum is NP-hard, Lloyd's algorithm alternates between two coordinate-descent steps:

Step 1 (Assignment): Assign each sample point $\mathbf{x}_i$ to its closest centroid in Euclidean space: $$S_j^{(t)} = \left\{ \mathbf{x}_p : \|\mathbf{x}_p - \boldsymbol{\mu}_j^{(t)}\|^2 \le \|\mathbf{x}_p - \boldsymbol{\mu}_{j^*}^{(t)}\|^2 \quad \forall j^* \right\}$$
Step 2 (Update): Recalculate centroids as the center of mass (arithmetic mean) of assigned points: $$\boldsymbol{\mu}_j^{(t+1)} = \frac{1}{|S_j^{(t)}|} \sum_{\mathbf{x}_i \in S_j^{(t)}} \mathbf{x}_i$$

Interactive Clustering Workbench

Ready

Model Parameters

Number of Clusters (K) 3

Direct input:

Dataset Distribution

Centroid Initialization

Step Delay 600ms

Optimization Metrics Live

Current Phase Ready

Iteration (t) 0

Active K 3

Inertia (WCSS) 0.0

Centroid Max Shift (Δ) 0.000

Cluster Membership

Tip: Click anywhere inside the canvas to add custom observations

Why Lloyd's Algorithm Guarantees Convergence
At each step, WCSS either strictly decreases or remains constant. Because there are only finitely many ($K^n$) possible cluster assignments, the algorithm cannot loop indefinitely and must converge to a local minimum in a finite number of iterations.

The Curse of Local Minima & K-Means++
Standard random initialization can get trapped in sub-optimal configurations (e.g. two centroids in one true cluster while another cluster is split). K-Means++ solves this by spreading out initial centroids proportional to squared distance $D(\mathbf{x})^2$, providing an $O(\log K)$ approximation guarantee!

Key Principles & Common Fallacies

1. Assumption of Spherical Clusters

K-Means implicitly assumes clusters are convex, isotropic (spherical), and equally sized. Try the Concentric Rings preset to see K-Means fail on non-linearly separable geometries where spectral clustering or DBSCAN is required.

2. Determining K (The Elbow Heuristic)

Inertia always decreases as $K$ increases (dropping to zero when $K=n$). The Elbow Method plots WCSS vs $K$ and picks the point where the marginal decrease suddenly flattens.

3. Feature Scaling Requirement

Because cluster assignments rely on Euclidean distance $\|\mathbf{x} - \boldsymbol{\mu}\|^2$, features with larger numeric scales dominate the metric. In practice, standardize data ($\mu=0, \sigma=1$) before running K-Means.