Skip to content
Computational Lab.

K-Nearest Neighbors

No training - the dataset is the model.

Beginner / classification / instance-based

K-nearest neighbors classifies each query by majority vote among its k closest points - there is no training phase at all. The rendered boundary is a direct majority-vote survey of the space, which is why changing k redraws it and adding one point bends it instantly. Leave-one-out accuracy is measured live.

Tagged: majority vote, decision boundary, lazy learning, leave-one-out

Live simulation

There is no training: add one point and the boundary bends instantly.

Speed

There is no training: add one point and the boundary bends instantly.

Mathematics

K-nearest neighbors classifies a query by majority vote among its k closest labeled points. There is no training: the dataset is the model, the decision boundary is implicit, and every data edit changes the boundary immediately.

vote(x) = sign of the sum of labels among the k nearest points

boundary: the locus where the k-neighbor vote flips

leave-one-out: classify each point using the dataset without it

The boundary field is computed by literally voting on a 96x48 grid - no approximation of the boundary, just the estimator evaluated everywhere. The leave-one-out accuracy in the metrics is the honest generalization estimate: each point is classified by neighbors that exclude it, which is the only fair way to score a lazy learner.

How it works

Points come from a seeded multi-blob layout whose boundary is deliberately non-linear; the k slider (odd, 1 to 15) changes the vote size, and small k produces jagged island boundaries while large k smooths them into the global structure.

The tool selector adds or erases labeled points; the field recomputes on the next render because the data was the model all along.

Implementation

src/engine/experiments/k-nn.ts · 201 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, PointerState, ThemeColors } from "../core/types";
3
4const CAPACITY = 200;
5
6/**
7 * K-nearest-neighbor classification with the boundary rendered by majority
8 * vote on a grid. No training at all - the dataset IS the model, which is
9 * exactly why adding one point bends the boundary immediately.
10 */
11export class KnnExperiment extends BaseExperiment {
12 readonly id = "k-nn";
13
14 private xs = new Float32Array(CAPACITY);
15 private ys = new Float32Array(CAPACITY);
16 private labels = new Float32Array(CAPACITY);
17 private count = 0;
18 private field = new Uint8Array(96 * 48);
19 private fieldK = -1;
20 private pointer = { x: 0, y: 0, down: false, inside: false };
21 private lastCell = { x: -1, y: -1 };
22
23 protected params(): ParameterDef[] {
24 return [
25 { key: "k", label: "Neighbors k", min: 1, max: 15, step: 2, defaultValue: 3 },
26 {
27 key: "tool",
28 label: "Pointer tool",
29 options: [
30 { value: "classA", label: "Add class A (+)" },
31 { value: "classB", label: "Add class B (-)" },
32 { value: "erase", label: "Erase nearest" },
33 ],
34 defaultValue: "classA",
35 },
36 ];
37 }
38
39 protected onReset(): void {
40 this.count = 0;
41 // Two noisy spirals-in-a-blob mix: clearly non-linear boundary potential.
42 const blobs = [
43 { cx: 0.25, cy: 0.7, label: 1, n: 26 },
44 { cx: 0.45, cy: 0.3, label: 1, n: 14 },
45 { cx: 0.72, cy: 0.62, label: -1, n: 26 },
46 { cx: 0.52, cy: 0.85, label: -1, n: 14 },
47 ];
48 for (const blob of blobs) {
49 for (let i = 0; i < blob.n; i++) {
50 this.add(blob.cx + (this.rng() - 0.5) * 0.3, blob.cy + (this.rng() - 0.5) * 0.3, blob.label, true);
51 }
52 }
53 this.fieldK = -1;
54 }
55
56 private add(x: number, y: number, label: number, skipField = false): void {
57 if (this.count >= CAPACITY) return;
58 this.xs[this.count] = Math.min(1, Math.max(0, x));
59 this.ys[this.count] = Math.min(1, Math.max(0, y));
60 this.labels[this.count] = label;
61 this.count += 1;
62 if (!skipField) this.fieldK = -1;
63 }
64
65 protected onUpdate(): void {}
66
67 resize(width: number, height: number): void {
68 this.width = width;
69 this.height = height;
70 }
71
72 onPointer(state: PointerState): void {
73 this.pointer = state;
74 if (!state.inside || !state.down) {
75 this.lastCell = { x: -1, y: -1 };
76 return;
77 }
78 const x = state.x / Math.max(1, this.width);
79 const y = state.y / Math.max(1, this.height);
80 const cell = { x: Math.round(x * 50), y: Math.round(y * 50) };
81 if (cell.x === this.lastCell.x && cell.y === this.lastCell.y) return;
82 this.lastCell = cell;
83 const tool = this.str("tool");
84 if (tool === "erase") {
85 let best = -1;
86 let bestDist = 0.06;
87 for (let i = 0; i < this.count; i++) {
88 const d = Math.hypot(this.xs[i] - x, this.ys[i] - y);
89 if (d < bestDist) {
90 bestDist = d;
91 best = i;
92 }
93 }
94 if (best >= 0) {
95 this.count -= 1;
96 this.xs[best] = this.xs[this.count];
97 this.ys[best] = this.ys[this.count];
98 this.labels[best] = this.labels[this.count];
99 this.fieldK = -1;
100 }
101 } else {
102 this.add(x, y, tool === "classA" ? 1 : -1);
103 }
104 }
105
106 private vote(x: number, y: number, k: number): number {
107 // Partial selection over the k smallest distances.
108 const bestD = new Float64Array(k).fill(Infinity);
109 const bestL = new Float32Array(k);
110 for (let i = 0; i < this.count; i++) {
111 const d = (this.xs[i] - x) ** 2 + (this.ys[i] - y) ** 2;
112 let slot = k - 1;
113 if (d >= bestD[slot]) continue;
114 while (slot > 0 && bestD[slot - 1] > d) {
115 bestD[slot] = bestD[slot - 1];
116 bestL[slot] = bestL[slot - 1];
117 slot -= 1;
118 }
119 bestD[slot] = d;
120 bestL[slot] = this.labels[i];
121 }
122 let votes = 0;
123 for (let s = 0; s < k; s++) votes += bestL[s];
124 return votes >= 0 ? 1 : -1;
125 }
126
127 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
128 ctx.fillStyle = theme.bg;
129 ctx.fillRect(0, 0, this.width, this.height);
130 const k = this.num("k");
131 const fieldH = 48;
132 if (this.fieldK !== k || this.fieldK === -1) {
133 for (let gy = 0; gy < fieldH; gy++) {
134 for (let gx = 0; gx < 96; gx++) {
135 this.field[gy * 96 + gx] =
136 this.vote((gx + 0.5) / 96, (gy + 0.5) / fieldH, k) > 0 ? 1 : 0;
137 }
138 }
139 this.fieldK = k;
140 }
141 // Regions
142 const cw = this.width / 96;
143 const ch = this.height / fieldH;
144 for (let gy = 0; gy < fieldH; gy++) {
145 for (let gx = 0; gx < 96; gx++) {
146 ctx.fillStyle = this.field[gy * 96 + gx] > 0 ? theme.accent : theme.viz[1];
147 ctx.globalAlpha = 0.08;
148 ctx.fillRect(gx * cw, gy * ch, cw + 0.5, ch + 0.5);
149 }
150 }
151 ctx.globalAlpha = 1;
152 // Points
153 for (let i = 0; i < this.count; i++) {
154 ctx.fillStyle = this.labels[i] > 0 ? theme.accent : theme.viz[1];
155 ctx.beginPath();
156 ctx.arc(this.xs[i] * this.width, this.ys[i] * this.height, 3.4, 0, Math.PI * 2);
157 ctx.fill();
158 }
159 }
160
161 getMetrics() {
162 let trainingCorrect = 0;
163 for (let i = 0; i < this.count; i++) {
164 // Leave-one-out style: skip the point itself by checking k+1 neighbors.
165 const k = Math.min(this.num("k") + 1, this.count);
166 const bestD = new Float64Array(k).fill(Infinity);
167 const bestL = new Float32Array(k);
168 for (let j = 0; j < this.count; j++) {
169 if (j === i) continue;
170 const d = (this.xs[j] - this.xs[i]) ** 2 + (this.ys[j] - this.ys[i]) ** 2;
171 let slot = k - 1;
172 if (d >= bestD[slot]) continue;
173 while (slot > 0 && bestD[slot - 1] > d) {
174 bestD[slot] = bestD[slot - 1];
175 bestL[slot] = bestL[slot - 1];
176 slot -= 1;
177 }
178 bestD[slot] = d;
179 bestL[slot] = this.labels[j];
180 }
181 let votes = 0;
182 for (let s = 0; s < k - 1; s++) votes += bestL[s];
183 if ((votes >= 0 ? 1 : -1) === this.labels[i]) trainingCorrect += 1;
184 }
185 return {
186 points: this.count,
187 k: this.num("k"),
188 looAccuracy: this.count > 0 ? `${((trainingCorrect / this.count) * 100).toFixed(1)} %` : "n/a",
189 model: "the dataset itself",
190 };
191 }
192
193 describe(): string {
194 return `${this.count} labeled points classified by their ${this.num("k")} nearest neighbors - the boundary is recomputed from the data itself, so every added point bends it.`;
195 }
196
197 entities(): number {
198 return this.count;
199 }
200}
201

Performance

Time per tick
O(points) per query; O(grid * points) per field render
Space
The dataset
Notes
k = 1 memorizes (zero training error by construction); k = 15 smooths - the bias-variance trade-off as a slider.

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.