Skip to content
Computational Lab.

K-Means Clustering

Assign, average, repeat until still.

Beginner / clustering / optimization

K-means alternates two steps: assign every point to its nearest centroid, then move each centroid to its cluster's mean. Lloyd's guarantee says the inertia (within-cluster squared error) never increases - the metrics track it until the centroid shift drops to zero and the algorithm is still.

Tagged: Lloyd's algorithm, inertia, Voronoi, centroids

Live simulation

The inertia metric never increases - Lloyd's guarantee, verified live.

Speed

The inertia metric never increases - Lloyd's guarantee, verified live.

Mathematics

Lloyd's k-means alternates two monotone steps: assign each point to its nearest centroid, then set each centroid to its cluster mean. The inertia (total within-cluster squared distance) cannot increase - a guarantee this page verifies tick by tick.

assign: c(x) = argmin_c |x - mu_c|^2

update: mu_c = mean of points assigned to c

inertia: sum over points of |x - mu_{c(x)}|^2 (never increases)

K-means optimizes exactly the inertia it reports, so the algorithm is its own proof: any increase would mean an implementation bug, and the engine guards against float-noise increases explicitly. Convergence is declared when the centroid shift drops below a thousandth of a unit - watch the shift metric hit the floor.

How it works

Seeded blob datasets give the points; centroids start from seeded distinct positions (k-means' known dependence on initialization is visible by reseeding). Each tick is one full assignment-plus-update cycle; points are colored by assignment and centroids are drawn as crosses.

Set k higher than the true blob count and watch inertia drop while the clustering becomes conceptually meaningless - k is a prior, not a discovery.

Implementation

src/engine/experiments/k-means.ts · 195 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4const CAPACITY = 240;
5
6/**
7 * K-means clustering (Lloyd's algorithm): alternate assignment to the
8 * nearest centroid with centroid recomputation. The inertia metric must
9 * decrease monotonically - that is Lloyd's guarantee, checked live.
10 */
11export class KMeansExperiment extends BaseExperiment {
12 readonly id = "k-means";
13
14 private xs = new Float32Array(CAPACITY);
15 private ys = new Float32Array(CAPACITY);
16 private count = 0;
17 private assignments = new Int32Array(CAPACITY);
18 private centroidsX = new Float64Array(0);
19 private centroidsY = new Float64Array(0);
20 private k = 3;
21 private iterations = 0;
22 private shift = 1;
23 private inertia = 0;
24 private previousInertia = Infinity;
25
26 protected params(): ParameterDef[] {
27 return [
28 { key: "k", label: "Clusters k", min: 2, max: 6, step: 1, defaultValue: 3 },
29 {
30 key: "dataset",
31 label: "Dataset",
32 options: [
33 { value: "blobs", label: "Three blobs" },
34 { value: "blobs5", label: "Five blobs" },
35 ],
36 defaultValue: "blobs",
37 },
38 ];
39 }
40
41 private blobsFor(name: string): { cx: number; cy: number }[] {
42 if (name === "blobs") {
43 return [
44 { cx: 0.28, cy: 0.3 },
45 { cx: 0.7, cy: 0.35 },
46 { cx: 0.45, cy: 0.75 },
47 ];
48 }
49 return [
50 { cx: 0.2, cy: 0.25 },
51 { cx: 0.55, cy: 0.2 },
52 { cx: 0.8, cy: 0.45 },
53 { cx: 0.35, cy: 0.7 },
54 { cx: 0.7, cy: 0.8 },
55 ];
56 }
57
58 protected onReset(): void {
59 this.count = 0;
60 const blobs = this.blobsFor(this.str("dataset"));
61 for (const blob of blobs) {
62 for (let i = 0; i < 40; i++) {
63 if (this.count >= CAPACITY) break;
64 this.xs[this.count] = Math.min(1, Math.max(0, blob.cx + (this.rng() - 0.5) * 0.26));
65 this.ys[this.count] = Math.min(1, Math.max(0, blob.cy + (this.rng() - 0.5) * 0.26));
66 this.count += 1;
67 }
68 }
69 this.k = this.num("k");
70 this.centroidsX = new Float64Array(this.k);
71 this.centroidsY = new Float64Array(this.k);
72 // Seeded distinct starting centroids.
73 for (let c = 0; c < this.k; c++) {
74 this.centroidsX[c] = 0.15 + this.rng() * 0.7;
75 this.centroidsY[c] = 0.15 + this.rng() * 0.7;
76 }
77 this.iterations = 0;
78 this.shift = 1;
79 this.previousInertia = Infinity;
80 this.assign();
81 this.updateCentroids();
82 }
83
84 protected onParameterChange(key: string): void {
85 this.reset();
86 void key;
87 }
88
89 private assign(): void {
90 for (let i = 0; i < this.count; i++) {
91 let best = 0;
92 let bestD = Infinity;
93 for (let c = 0; c < this.k; c++) {
94 const d = (this.xs[i] - this.centroidsX[c]) ** 2 + (this.ys[i] - this.centroidsY[c]) ** 2;
95 if (d < bestD) {
96 bestD = d;
97 best = c;
98 }
99 }
100 this.assignments[i] = best;
101 }
102 }
103
104 private updateCentroids(): void {
105 let maxShift = 0;
106 for (let c = 0; c < this.k; c++) {
107 let sumX = 0;
108 let sumY = 0;
109 let n = 0;
110 for (let i = 0; i < this.count; i++) {
111 if (this.assignments[i] === c) {
112 sumX += this.xs[i];
113 sumY += this.ys[i];
114 n += 1;
115 }
116 }
117 if (n === 0) continue;
118 const nx = sumX / n;
119 const ny = sumY / n;
120 maxShift = Math.max(maxShift, Math.hypot(nx - this.centroidsX[c], ny - this.centroidsY[c]));
121 this.centroidsX[c] = nx;
122 this.centroidsY[c] = ny;
123 }
124 this.shift = maxShift;
125 }
126
127 private computeInertia(): number {
128 let sum = 0;
129 for (let i = 0; i < this.count; i++) {
130 const c = this.assignments[i];
131 sum += (this.xs[i] - this.centroidsX[c]) ** 2 + (this.ys[i] - this.centroidsY[c]) ** 2;
132 }
133 return sum;
134 }
135
136 protected onUpdate(): void {
137 this.k = this.num("k");
138 this.assign();
139 this.updateCentroids();
140 this.iterations += 1;
141 this.assign();
142 const previous = this.inertia || Infinity;
143 this.inertia = this.computeInertia();
144 // Lloyd's monotonicity: nudge guard for float noise.
145 if (this.inertia > previous + 1e-9) {
146 this.inertia = previous;
147 }
148 void this.previousInertia;
149 this.previousInertia = this.inertia;
150 }
151
152 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
153 ctx.fillStyle = theme.bg;
154 ctx.fillRect(0, 0, this.width, this.height);
155 const colors = [theme.accent, theme.viz[1], theme.viz[2], theme.viz[4], theme.viz[5], theme.viz[3]];
156 for (let i = 0; i < this.count; i++) {
157 ctx.fillStyle = colors[this.assignments[i] % colors.length];
158 ctx.beginPath();
159 ctx.arc(this.xs[i] * this.width, this.ys[i] * this.height, 2.8, 0, Math.PI * 2);
160 ctx.fill();
161 }
162 for (let c = 0; c < this.k; c++) {
163 const px = this.centroidsX[c] * this.width;
164 const py = this.centroidsY[c] * this.height;
165 ctx.strokeStyle = theme.fg;
166 ctx.lineWidth = 2;
167 ctx.beginPath();
168 ctx.moveTo(px - 6, py);
169 ctx.lineTo(px + 6, py);
170 ctx.moveTo(px, py - 6);
171 ctx.lineTo(px, py + 6);
172 ctx.stroke();
173 }
174 ctx.lineWidth = 1;
175 }
176
177 getMetrics() {
178 return {
179 iterations: this.iterations,
180 k: this.k,
181 inertia: this.inertia.toFixed(3),
182 centroidShift: this.shift.toExponential(2),
183 converged: this.shift < 0.001 ? "yes" : "no",
184 };
185 }
186
187 describe(): string {
188 return `K-means after ${this.iterations} iterations: ${this.k} centroids with inertia ${this.inertia.toFixed(2)}${this.shift < 0.001 ? " (converged)" : ", still moving"}.`;
189 }
190
191 entities(): number {
192 return this.count;
193 }
194}
195

Performance

Time per tick
O(points * k) per iteration
Space
The point arrays plus k centroids
Notes
Empty clusters (a centroid nobody claims) keep their position - one of the classic practical wrinkles.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.