K-NEAREST NEIGHBORS
No training equation — classify a point by asking its nearest neighbours to vote.
01 Overview
02 The Problem
A streaming service must tag a new article's topic — politics or sports — but it has no equation for "topic". What it has is thousands of already-tagged articles. The new one is a neighbour not in the dictionary. The problem is classification by similarity when no parametric model fits the boundary.
03 Why It Matters
KNN is the prototype of lazy, instance-based learning — the opposite of fitting equations. If similarity is a sound notion of closeness, it needs no training at all. That makes it a robust baseline and the seed of ideas that dominate recommendation and anomaly detection.
04 Intuition
Drop every training point on a map. To classify a new point, grow a circle around it until it contains exactly \(k\) residents; those residents vote, majority wins. For regression they average instead. The dial \(k\) is the smoothness: \(k=1\) memorises every quirk (jagged, overfit); large \(k\) washes everything toward the global majority (underfit).
05 Mathematical Foundation
A metric \(d\) defines geometry. Euclidean \(d(p,q)=\sqrt{\sum_i(p_i-q_i)^2}\), Manhattan \(d=\sum_i|p_i-q_i\), Minkowski as the family. The curse of dimensionality: as dimension \(d\) grows, all pairwise distances concentrate — nearest and farthest become indistinguishable. The majority vote is a \(k\)-NN estimate of the Bayes rule as \(k\to\infty\) with shrinking neighbourhoods.
06 The Equation
- \(q\) the query point being classified
- \(x_{(i)}\) the i-th closest training point to \(q\)
- \(d(x_{(i)},q)\) distance from query to that neighbour
- \(k\) how many neighbours get a vote
07 How It Learns
- “Training” = store the dataset verbatim (often standardised).
- At query time: compute \(d\) to every stored point — O(n) per prediction.
- Select \(k\) nearest: sort, keep the smallest distances.
- Decide by majority vote (mean for regression).
08 Algorithm
09 Visual Explanation
A quick visual summary of how this model sees data and makes its prediction.
10 Worked Example
Query at (5,4). Distances: A at 1.4, 2.0, 2.8; B at 2.2, 3.5, 3.6. \(k=3\) voters {A:1.4, A:2.0, B:2.2} → A wins 2–1. \(k=5\) adds A:2.8 → {A,A,A,B,B} → A wins 3–2. The verdict held, but a tiny noise flip near 2.8 could have changed everything — \(k\) guards against exactly that.