k-Nearest Neighbours

Last lesson left logistic regression boxed in by its own strength: one straight boundary, fixed once, helpless against classes that coil around each other. So swing to the opposite extreme — a classifier that learns no boundary at all, and instead decides each new case by simply asking its neighbours.

To label a new point, look at the points nearest to it and copy the majority. If your five nearest neighbours are three cats and two dogs, you call it a cat. That is the whole algorithm: you are like your neighbours.

What makes it strange is that there is no training. A linear model fits weights; a tree builds splits; this one does nothing up front — it just stores the training data and does all the work at prediction time, measuring distances to find who is near.

For that it is called a lazy learner: flexible enough to trace any curvy boundary the data demands, at the price of slow predictions on big datasets.

Find the neighbours, take a vote

Two ingredients, and only two: a distance to decide who counts as near, and a vote to combine their labels.

Distance. The usual choices are Euclidean (straight-line, √Σ(aᵢ − bᵢ)²) and Manhattan (sum of absolute coordinate differences, Σ|aᵢ − bᵢ|). For two 2-D points a and b:

Euclidean:  d = √[ (a₁−b₁)² + (a₂−b₂)² ]
Manhattan:  d = |a₁−b₁| + |a₂−b₂|

Vote. For classification, take the majority label among the k neighbours. For regression, average their values instead.

k controls the bias–variance trade-off

The only real knob is k. Picking up exactly the dial the last lesson promised, it sets how wiggly the decision boundary is, sliding the model right along the bias-variance curve.

Two words to keep straight as you read: bias is the error left over because the model is too rigid to trace the true pattern. Variance is how much the fitted boundary would lurch about if you re-drew the training set from scratch.

• Small k (say k = 1): the prediction follows the single nearest point, so the boundary is jagged and chases noise — low bias, high variance.
• Large k: the vote averages over many points, smoothing the boundary — higher bias, lower variance. Push k to the size of the dataset and every query just returns the overall majority class.

Those labels read backwards to almost everyone the first time, so here is the objection stated properly: surely k = 1 is the simplest rule in the world — find one point, copy its label — so why is it the low-bias, high-variance end rather than the other way round?

Because bias and variance describe the boundary the rule produces, not how short the rule is to write down. With k = 1 the boundary is free to bend around every individual training point, so it can match almost any true shape (little bias). But swap in a fresh training sample and it redraws itself completely (large variance).

With large k every prediction is a consensus of many points, so the boundary is stiff: it cannot follow fine structure (large bias), yet it barely twitches when the data changes (little variance). Flexibility is the thing being dialled, and small k is the flexible end.

How GATE asks this

Typical MCQ or MSQ questions on the properties ask you to:

• identify kNN as a lazy (instance-based, non-parametric — it learns no fixed set of weights, it just keeps the data) learner with no training phase
• state the effect of increasing k (smoother boundary, more bias, less variance)
• choose the right distance metric

NAT versions hand you a tiny labelled set and a query point and ask you to compute a distance or name the predicted class.

Worked example — classify by the 3 nearest neighbours

Training points: A = (1, 2) is class +, B = (2, 3) is class +, C = (5, 5) is class −, D = (6, 4) is class −. Classify the query q = (3, 3) using k = 3 and Euclidean distance.

Compute each distance from q = (3, 3). We can compare squared distances — the ordering is identical, and it spares us the square roots:

d(q,A)² = (3−1)² + (3−2)² = 4 + 1 = 5     → d ≈ 2.24
d(q,B)² = (3−2)² + (3−3)² = 1 + 0 = 1     → d = 1.00
d(q,C)² = (3−5)² + (3−5)² = 4 + 4 = 8     → d ≈ 2.83
d(q,D)² = (3−6)² + (3−4)² = 9 + 1 = 10    → d ≈ 3.16

Sort by distance: B (1.00) < A (2.24) < C (2.83) < D (3.16). The 3 nearest are B(+), A(+), C(−). Vote: 2 (+) vs 1 (−) → predict +.

q did indeed sit nearer the lower-left + cluster, just as the eyeball suggested.

(Sanity check: with k = 1 we would use only B, also +. With k = 5 we would be forced to look beyond the four points we have — k must never exceed the dataset size.)

In one breath

k-Nearest Neighbours is a lazy classifier that does no training — it just stores the data, then labels a new point by the majority vote of its k closest neighbours under a distance (Euclidean √Σ(aᵢ−bᵢ)² or Manhattan Σ|aᵢ−bᵢ|).

The single knob k is the smoothing dial on the bias-variance curve (small k → jagged, low bias / high variance; large k → smooth, high bias / low variance). Because everything rides on distance, you must scale your features first and prefer an odd k in two-class problems to avoid tied votes.

Practice

A question to carry forward

kNN decides everything by geometry — who sits closest — and pays for it twice: it must hoard every training point forever, and it offers no sense of how sure it is, only a raw vote. Two cats and a dog says “cat,” but with what confidence? It cannot say.

So picture a wholly different way to classify, one that speaks in probabilities from the start. Instead of measuring distance, ask of each class a question: if the true class were this, how likely is the evidence I’m seeing?

Score every class by that likelihood times how common the class is, and pick the winner. That is Bayes’ rule turned into a classifier — compact, fast, no points to store.

Here is the thread onward: when the evidence is many features at once, computing their joint likelihood exactly is hopeless. So what single bold shortcut makes the probabilities cheap, and how badly does the shortcut have to be wrong before the answers go wrong with it?