Try first

A new fruit arrives. You have six labeled examples. What is the simplest possible way to guess its label?

You wrote this in lesson 3039 without calling it a classifier. Recall what nearest did, then say what would make it better.

The whole algorithm

Find the most similar labeled example. Copy its label. Done.

There is no training. There are no parameters. There is no loss, no gradient, and no update rule. The model is the dataset.

The improvement is to ask more than one neighbor, so a single odd example cannot decide the answer alone.

function knn(point, data, k = 3) {
  const ranked = data
    .map(r => ({ r, d: distance(point, r.x) }))
    .sort((a, b) => a.d - b.d)
    .slice(0, k);

  const votes = {};
  for (const { r } of ranked) votes[r.y] = (votes[r.y] || 0) + 1;

  let best = null, bestCount = -1;
  for (const label in votes) {
    if (votes[label] > bestCount) { bestCount = votes[label]; best = label; }
  }
  return { label: best, confidence: bestCount / k, neighbors: ranked };
}

Measure the distance to every row. Sort. Take the closest k. Count the labels among them and return the winner.

The fraction of votes the winner got is a rough confidence. With k = 5, three votes to two is a much weaker claim than five to zero.

Draw the boundary

function knnMap(data, k, xMin, xMax, yMin, yMax) {
  const wd = canvas.width, ht = canvas.height;
  const img = ctx.createImageData(wd, ht);
  for (let py = 0; py < ht; py += 2) {
    for (let px = 0; px < wd; px += 2) {
      const x0 = xMin + px / wd * (xMax - xMin);
      const x1 = yMax - py / ht * (yMax - yMin);
      const v = knn([x0, x1], data, k).label | 0;
      for (let dy = 0; dy < 2; dy++) for (let dx = 0; dx < 2; dx++) {
        const i = ((py + dy) * wd + px + dx) * 4;
        img.data[i] = v ? 240 : 90;
        img.data[i+1] = 150;
        img.data[i+2] = v ? 90 : 220;
        img.data[i+3] = 255;
      }
    }
  }
  ctx.putImageData(img, 0, 0);
  view.xMin = xMin; view.xMax = xMax; view.yMin = yMin; view.yMax = yMax;
}

knnMap(points, 1, 0, 10, 0, 10);
for (const p of points) dot(p.x[0], p.x[1], p.y ? "#402" : "#024", 4);

Every second pixel, because this is slow: each pixel compares against every row in the dataset.

With k = 1 the boundary is jagged, with small islands around individual points. That is a model with no smoothing at all, and it classifies every training point perfectly because each one is its own nearest neighbor. Training accuracy 100 percent, and it means nothing.

Raise k to 5, then 15, then 31. The boundary smooths out and the islands disappear. At very high k it flattens into almost nothing, because a majority of a large neighborhood is nearly the majority of the whole dataset.

So k is a capacity control, exactly like polynomial degree in lesson 3096. Small k overfits, large k underfits, and you choose it on the validation set.

What it costs

Training is free and prediction is expensive, which is the reverse of everything else in this course.

training     nothing, just keep the data
memory       the entire dataset, forever
prediction   one distance per row, then a sort

A million rows means a million distance calculations per prediction. Real implementations use spatial index structures to cut that down, and those structures stop helping once you have more than about twenty features.

Two things that will break it

Unscaled features. This is entirely built on distance, so lesson 3042 applies at full strength. Skip scaling and the widest column decides every prediction. Try it on the raw fruit data and watch it classify by weight alone.

Too many features. In high dimensions, distances between points become nearly all the same. The nearest neighbor out of a thousand is barely nearer than the furthest, so “nearest” stops meaning anything. This is called the curse of dimensionality and it makes plain k-nearest neighbors a poor choice for raw images.

What to watch

Because there is no training, there is nothing to inspect and nothing to explain except the data itself. That cuts both ways. You cannot ask what the model learned, and you can always show exactly which examples produced a given answer, which is a genuinely good explanation.

Exercises

1. Sweep k from 1 to 31 and plot training and validation accuracy. Where is the best value?
2. Run it on the fruit data unscaled and scaled. Compare the two.
3. Weight each neighbor’s vote by 1 / distance. Does it help at large k?
4. Add 20 columns of random noise to the two feature dataset. Measure how accuracy falls as you add them.