k-means Clustering

Imagine you scatter a thousand customers on a map and want to open k stores so that, on average, everyone is as close as possible to their nearest store. Or you have a heap of photos and want to sort them into k piles of "similar" ones. Both are the same task: clustering — split points into k groups so that each group is tight and the groups are well separated.

The standard tool for this is k-means. Its goal is crisp: choose k centers and assign every point to its nearest center so that the total within-cluster variance — the sum of squared distances from each point to its center — is as small as possible.

It sounds like the kind of thing a computer should just solve. It runs in the blink of an eye, after all. But run it twice and you may get two different answers. That wobble is not a bug — it is a fingerprint of a genuinely hard problem.

Below are points and k = 3 centers. Press Step to run one round of Lloyd's algorithm: each point joins its nearest center, then each center hops to the average of its points. Repeat until nothing moves — that's convergence.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="360" height="300"></canvas>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="seed" type="button">{{btn_seed}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fbfdff; width: 100%; max-width: 360px; height: auto; display: block; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Now press New seeds and run it again. The points never changed, yet the clusters — and the final score (the total within-cluster variance) — often do. Some starts land on a tidy, low-score grouping; others get stuck in a worse one. Checking a clustering's score is instant. Finding the start that leads to the truly best score is the hard part — which is exactly why k-means++ exists: it picks smarter starting centers to dodge the bad local optima.

Here is the twist most people miss: k-means the algorithm is easy, but k-means the problem is not.

• Checking a clustering is trivial: assign each point to its nearest center and add up the squared distances. That's the score.
• Lloyd's algorithm (1957, the assign-then-update loop you just ran) is fast and always converges — but only to a local optimum. Where it lands depends entirely on the initial centers.
• The exact problem is NP-hard. Minimizing within-cluster sum of squares is NP-hard even for just k = 2 clusters in general dimension (Aloise, Deshpande, Hansen, Popat, 2009), and also NP-hard in the plane when k is part of the input (Mahajan, Nimbhorkar, Varadarajan, 2009). So no known algorithm finds the guaranteed best clustering in polynomial time.
• k-means++ (Arthur and Vassilvitskii, 2007) doesn't make it easy — but by seeding centers far apart with a clever random rule, it guarantees the result is, on average, within an $O(\log k)$ factor of the optimum, and in practice converges faster and better.

So the gap you felt in the demo — "this run looks great, that one looks bad" — is the same gap behind every hard optimization problem: a great checker and no efficient solver. It is the practical face of P vs NP.

"Group similar things together" is one of the most common tasks in all of data, and k-means is its workhorse:

• Customer and market segmentation: split users by behavior to target each group differently.
• Image compression (color quantization): cluster millions of pixel colors into k representative colors, then store only those — a direct cousin of vector quantization.
• Document and topic grouping: bucket articles or search results into themes without labels.
• Anomaly detection: points far from every center are suspicious — useful for fraud and fault monitoring.
• Feature learning: cluster centers can serve as a compact, learned vocabulary for images or signals.

Because the exact problem is hard, real systems lean on the practical recipe — run Lloyd's algorithm many times from k-means++ seeds and keep the best score. The same "many restarts, keep the best" strategy shows up across hard optimization, from the traveling salesman problem to graph coloring.

k-means is a beautiful illustration of a deep idea: an algorithm that always finishes quickly is not the same as a problem that is easy to solve. Lloyd's loop converges in moments, yet it only ever promises a local optimum, and the truly best clustering is NP-hard to find.

So when your clusters shift between runs, you're not doing anything wrong — you've bumped into intractability wearing a friendly face. The honest fix isn't a magic exact solver; it's humility plus good engineering: seed well with k-means++, restart often, keep the best, and remember that behind this everyday tool sits the same wall as P vs NP.