Introduction

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.

Cluster the Points

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">Three natural blobs of points, with <b>k = 3</b> centers (the big rings). Press <b>Step</b> to run one round of Lloyd’s algorithm: assign every point to its nearest center, then move each center to the average of its points. <b>Checking</b> a clustering’s score is instant — <b>finding</b> the start that reaches the best score is hard.</p>
<canvas id="cv" width="360" height="300"></canvas>
<div class="status" id="status">Press Step to begin.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to convergence</button>
  <button id="seed" type="button">New seeds</button>
  <button id="reset" type="button" class="ghost">Reset points</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// k-means clustering with Lloyd's algorithm. Goal: pick k centers and assign each point to its nearest center, minimizing the within-cluster sum of squared distances (the "score"). Lloyd's loop (assign -> update) always converges, but only to a LOCAL optimum: different seeds -> different scores. Finding the global best is NP-hard (Aloise et al. 2009). Checking a score is instant.
const W = 360, H = 300, K = 3;
const COLORS = ['#e63946', '#2a9d8f', '#457b9d'];
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
let points = [], centers = [], assign = [], iter = 0, converged = false;

function rnd(a, b) { return a + Math.random() * (b - a); }
function blob(cx, cy, n, spread) {
  for (let i = 0; i < n; i++) points.push({ x: cx + rnd(-spread, spread), y: cy + rnd(-spread, spread) });
}
function makePoints() {
  points = [];
  blob(95, 80, 18, 34);
  blob(265, 95, 18, 34);
  blob(170, 220, 18, 34);
}
function seed() {
  // random initial centers chosen from the data points (forgy init)
  centers = []; const used = new Set();
  while (centers.length < K) {
    const i = Math.floor(Math.random() * points.length);
    if (used.has(i)) continue; used.add(i);
    centers.push({ x: points[i].x, y: points[i].y });
  }
  assign = points.map(() => -1); iter = 0; converged = false;
}
const d2 = (p, c) => (p.x - c.x) * (p.x - c.x) + (p.y - c.y) * (p.y - c.y);

// ASSIGN: each point -> nearest center. Returns true if any assignment changed.
function assignStep() {
  let changed = false;
  for (let i = 0; i < points.length; i++) {
    let best = 0, bd = Infinity;
    for (let c = 0; c < centers.length; c++) {
      const dd = d2(points[i], centers[c]);
      if (dd < bd) { bd = dd; best = c; }
    }
    if (assign[i] !== best) { assign[i] = best; changed = true; }
  }
  return changed;
}
// UPDATE: each center -> mean of its assigned points.
function updateStep() {
  for (let c = 0; c < centers.length; c++) {
    let sx = 0, sy = 0, n = 0;
    for (let i = 0; i < points.length; i++) if (assign[i] === c) { sx += points[i].x; sy += points[i].y; n++; }
    if (n > 0) { centers[c].x = sx / n; centers[c].y = sy / n; }
  }
}
// SCORE: within-cluster sum of squared distances (lower is better).
function score() {
  let s = 0;
  for (let i = 0; i < points.length; i++) s += d2(points[i], centers[assign[i]]);
  return s;
}
function step() {
  if (converged) return;
  const changed = assignStep();
  updateStep();
  iter++;
  if (!changed && iter > 1) converged = true;
  draw();
  const s = Math.round(score());
  setStatus(fmt('%v% — score %s% (lower = tighter clusters).', { v: converged ? 'Converged' : fmt('Iteration %iter%', { iter: iter }), s: s }), converged);
}
function runAll() {
  let guard = 0;
  while (!converged && guard++ < 100) step();
}
function setStatus(t, done) { const el = document.getElementById('status'); el.textContent = t; el.className = 'status' + (done ? ' done' : ''); }
function draw() {
  ctx.clearRect(0, 0, W, H);
  for (let i = 0; i < points.length; i++) {
    const a = assign[i];
    ctx.fillStyle = a < 0 ? '#9aa5b1' : COLORS[a];
    ctx.beginPath(); ctx.arc(points[i].x, points[i].y, 4, 0, 7); ctx.fill();
  }
  for (let c = 0; c < centers.length; c++) {
    ctx.strokeStyle = COLORS[c]; ctx.lineWidth = 3;
    ctx.beginPath(); ctx.arc(centers[c].x, centers[c].y, 10, 0, 7); ctx.stroke();
    ctx.fillStyle = COLORS[c];
    ctx.beginPath(); ctx.arc(centers[c].x, centers[c].y, 3, 0, 7); ctx.fill();
  }
}
document.getElementById('step').addEventListener('click', step);
document.getElementById('run').addEventListener('click', runAll);
document.getElementById('seed').addEventListener('click', () => { seed(); draw(); setStatus('New random seeds — press Step.', false); });
document.getElementById('reset').addEventListener('click', () => { makePoints(); seed(); draw(); setStatus('Press Step to begin.', false); });
makePoints(); seed(); draw();
Result
Console

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.

The Real Complexity

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)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/k-means/Content licensed under CC BY-NC 4.0.