FIG. 13 · ATLAS K-Means
Lloyd's algorithm,
drawn live.
Partition n points into k clusters by alternating: assign each point to the nearest centroid, recompute centroids as the mean of their members. Fast, simple, sensitive to k — and the engine behind almost every customer-segmentation deck you've ever seen.
Click Run to watch the algorithm converge. Click Step to advance one iteration at a time. Try the rings preset to feel where the model breaks — centroid-distance is not the right way to cluster a doughnut. For a real-world case study, see the Customer Segmentation lab where this engine drives a campaign-ROI model.
§ I The algorithm, animated
Centroids are seeded with k-means++ for stability. On Run, the algorithm alternates assignment and update until the centroids stop moving. The faint shading is the Voronoi partition — the region of the canvas closest to each centroid.
§ II How it works
Pick k starting centroids. For every point, find the nearest centroid by Euclidean distance and assign it to that cluster. Recompute each centroid as the mean of its assigned points. Repeat until no point changes cluster (or a max-iteration cap is reached).
The objective being minimized is the within-cluster sum of squared distances — the "inertia" readout in the panel. Each iteration either lowers it or leaves it unchanged. The algorithm is monotonic, fast, and beautifully simple. Its weaknesses come from the simplicity, not despite it.
The math
For points x_1, …, x_n and clusters C_1, …, C_k:
argmin_C Σ_i Σ_(x ∈ C_i) ‖x − μ_i‖²where μ_i is the centroid of cluster C_i. The two-step iteration is:
Assign: C_i = { x : i = argmin_j ‖x − μ_j‖ }Update: μ_i = (1 / |C_i|) Σ_(x ∈ C_i) x
K-means++ initializes the first centroid at random and each subsequent one with probability proportional to squared distance from existing centroids. It converges to better local minima than uniform random seeding, with the same iteration cost.
§ III Where it shines, where it breaks
Spherical clusters with similar size
When clusters are roughly round, roughly equal in count, and well-separated, k-means converges fast and finds them reliably. That covers a surprising fraction of real customer segmentation and topic-grouping problems.
Speed at scale
Mini-batch k-means scales to billions of points. Each iteration is O(nk), and the algorithm typically converges in under fifty iterations. It is the cluster-method-of-choice for production pipelines because it gets out of the way fast.
Non-convex shapes
Try the rings preset. K-means slices the plane with straight Voronoi boundaries; it cannot recognize that the inner ring and outer ring are different. DBSCAN handles this case by following density rather than centroid distance.
k is your guess
Move the k slider through 2-3-4-5. Each value gives a perfectly valid k-means solution. The algorithm has no opinion about which is right. The elbow method, silhouette score, and gap statistic try to answer that, none perfectly. DBSCAN's eps + minPts is a different (also imperfect) framing of the same problem.
§ IV Trade-off scorecard
Directional, not exact. Mini-batch variants make k-means even faster on large data.
- Inference0.85
- Accuracy0.55
- Training0.80
- Small size0.85
§ V In production
The Customer Segmentation lab on this site. K-Means at k=4 on log-transformed RFM features partitions a one-million-transaction UK retail dataset into segments where the top 21% of customers generate 64% of revenue. Same Lloyd's iteration you see above — just on a wider feature space and more interesting points.
§ VI Compare to
DBSCAN
Density-based clustering · phase 3
Segmentation Lab
K-Means on real RFM data · FIG. 02
Isolation Forest
For outliers, not clusters · phase 3