k-Nearest Neighbors (k-NN)
Tune the neighborhood: a data point asks its k closest acquaintances - and they vote.
Interactive classification field. Use the left and right arrow keys to change k. Use the up and down arrow keys to step through the test rings one by one and hear each ring's neighbor vote. Escape clears the selection. With a mouse or touch you can paint points, erase, and grab test rings.
0 / 0 rings correct. k is 1
Two clean groups, but one stray red point flips a ring at k=1. Nudge k up a little (k=3) and the majority already smooths the boundary.
Each ring is a test point that wants to be classified correctly. Color the field so every ring glows green - using three tools: slide k, paint points, and grab a test point to see its neighbors.
What happens on the field
This demo sorts points by their neighbours. Here is what the picture shows — the spatial idea behind the numbers.
- What you see
- A square field full of known points in two colours, blue and red. The tinted background splits the field into a blue region and a red one, with a curved boundary running between them. Points drawn as rings are test points still waiting for their verdict.
- What happens
- Grab a ring and short lines reach out to its k nearest neighbours; the point takes on whichever colour is in the majority there. Push k up and the boundary between the coloured regions grows smoother; pull k down and it turns jagged, hugging single outliers.
- What you can do
- Pick a level, set k with the slider, paint new points in blue or red or erase them, grab a ring to inspect it, and switch the distance measure.
- What to watch for
- k-NN computes no formula. It simply looks at what lies nearby and takes a vote. The boundary between the colours is drawn by the neighbours alone — and k decides how calm or jittery it runs.
Definition
k-NN in one sentence
Analogy
You move to a new town and want to know whether your street is quiet or lively. You simply ask the k nearest neighbors - and go with whatever the majority says.
That is exactly how k-NN classifies: for a new point it finds the k most similar examples and lets them vote. No training, no formula - just the neighborhood.
Definition
k-NN is a lazy learner: it just stores the training data and decides only at prediction time. A point's class is the majority class among its k nearest neighbors under a distance metric.
A small k gives a jagged, noise-sensitive boundary (variance). A large k gives a smooth, sluggish boundary (bias). The sweet spot sits in between.
k-NN classifies a new point in four steps - with no training at all, purely by comparing it to the closest examples:
- Measure distances: compute the distance from the new point to every training point (e.g. Euclidean - straight line - or Manhattan - city-block path).
- Pick the k closest: sort by distance and keep the k nearest neighbors. k is the one true dial.
- Let them vote: count which class is most common among those k neighbors.
- Majority wins: the most common class becomes the prediction. An odd k avoids ties.
That is exactly what you see below: grab a ring and its k neighbors, their distance lines and the running vote light up. Slide k and the majority changes live.
Lazy learning
k-NN never trains. The colored boundary only appears the moment you classify - every point simply asks its nearest neighbors.
Majority vote
Grab a ring: its k nearest neighbors light up, the lines show the distances, and the majority wins. That is the entire decision.
The k lever = bias-variance
A small k smooths nothing and follows every outlier (variance). A large k smooths everything, even real structure (bias). You just felt it yourself: too small breaks here, too large breaks there.
Check
Quick quiz - does k-NN stick?
Why is k-NN called a "lazy learner"?
Select one answer
1. Why is k-NN called a "lazy learner"?
2. You raise k from 1 to a large value. What happens to the decision boundary?
3. A single outlier point sits in the middle of the wrong region. How do you best outvote it?
4. What determines which neighbors are even "the closest"?
5. Why is k often chosen odd (1, 3, 5, ...)?
The idea: ask your neighbors
k-Nearest-Neighbors (k-NN) is one of the simplest classification algorithms there is. A new, unknown point simply gets the class that is in the majority among its k nearest neighbors. There is no formula, no model, no weights to train. The algorithm relies solely on the assumption that points lying close together usually belong to the same class.
Lazy learning: no training
k-NN is a lazy learner: during the training phase, nothing happens except that all training points are stored. All the work is done only at prediction time. That is why training is extremely fast, but each individual prediction is comparatively expensive, because it requires computing the distance to every stored point.
How a prediction works
- Measure distances: Compute the distance from the new point to every stored point.
- Choose the k nearest: Sort by distance and take the k closest neighbors.
- Vote: Every neighbor casts a vote for its class; the majority wins.
The distance measure (metric)
What close means is determined by the metric. The Euclidean distance measures the straight-line distance (square root of the sum of squared differences), the Manhattan distance only the paths along the axes. The choice of metric visibly changes the shape of the decision boundary. Important: features should be brought to a similar scale beforehand, otherwise one axis with large numeric values dominates the distance.
The role of k
The parameter k controls how smooth the decision boundary becomes. A small k (say k=1) follows every detail and reacts sensitively to outliers and noise (high variance). A large k averages over many neighbors and smooths the boundary, but can blur fine structures (high bias). There is no universally best k; the right value depends on the data and is usually found by trial and error or cross-validation. An odd k avoids ties with two classes.
Properties
- Non-parametric: no assumption about the shape of the data
- Instance-based: the training data itself is the model
- Intuitive: the decision can be read directly off the neighbors
- Expensive at runtime: every prediction checks all stored points
Play with the demo! Grab a test ring and slide the k control: at k=1, a single outlier can tip the ring into the wrong class; at a larger k, the majority overrules the troublemaker. On the spiral plane you see the opposite — a k that is too large blurs the fine arms, and here only a medium k helps. Also switch between Euclidean and Manhattan and watch how the boundary changes shape.
1951: Fix and Hodges
The roots of k-NN go back to a technical report by Evelyn Fix and Joseph Hodges for the US Air Force. They investigated non-parametric discrimination between classes — that is, classification without assuming a fixed distribution — and thereby laid the formal foundation of the method.
1967: Cover and Hart
Thomas Cover and Peter Hart published the famous theoretical analysis in "Nearest Neighbor Pattern Classification". They proved that the error rate of the simple nearest-neighbor method (k=1), given unlimited data, is at most twice as high as that of the best possible (Bayes-optimal) classifier. A remarkably strong result for such a simple method.
Why k-NN still matters today
Despite its age, k-NN remains in use, often as a robust baseline and as the core of recommender systems and similarity search. Modern variants speed up the expensive neighbor search with spatial data structures like k-d trees, or with approximate methods that find only near-optimal nearest neighbors, but do so very fast.
1
# k-Nearest-Neighbors (k-NN) - classification
2
# Idea: a point inherits the class of its neighbors
3
# Lazy learning - there is NO real training phase
4
function train(training_data):
5
# adjust nothing, compute nothing ...
6
storage = training_data # just remember
7
return storage
8
9
# Prediction for a new, unknown point
10
function classify(point, k, metric):
11
# 1. Measure the distance to ALL stored points
12
for each neighbor in storage:
13
distance[neighbor] = distance(point, neighbor, metric)
14
15
# 2. Sort by distance, take the k nearest
16
sort storage by distance ascending
17
neighbors = the first k entries
18
19
# 3. Majority vote among the k neighbors
20
votes_A = count of neighbors with class A
21
votes_B = count of neighbors with class B
22
if votes_A >= votes_B:
23
return class A
24
else:
25
return class B
26
27
# Distance measure - how "close" is measured
28
function distance(a, b, metric):
29
if metric == euclidean:
30
# straight-line distance
31
return sqrt((a.x-b.x)^2 + (a.y-b.y)^2)
32
else:
33
# Manhattan - only along the axes
34
return |a.x-b.x| + |a.y-b.y|
35
36
# k small = fine, but noisy boundary
37
# odd k avoids ties with 2 classes
38
# careful: scale features beforehand (otherwise one axis dominates)
39
# cost: every prediction compares against all n points (O(n))
40
# theory: with lots of data, at most 2x Bayes error (Cover & Hart)
💾 Remembering instead of learning
k-NN does not train in the usual sense. It simply stores all training points along with their class. That's why it's called lazy learning: the actual work is deferred until prediction time.
function train(training_data):
# adjust nothing, compute nothing ...
storage = training_data # just remember
return storage
💾 Store
Remember all training points along with their class. No training, just storing.
↔️ Measure distances
Compute the distance from the new point to every stored point.
👥 Choose the k nearest
Sort by distance and select the k closest neighbors.
☑️ Vote
Each neighbor votes for its class, the majority wins.
🏷️ Assign class
The new point gets the class with the most votes.