knn() — k-Nearest Neighbors

Label a new point by asking its nearest neighbours to vote.

knn(k, training_data)

Key idea

• To label a new point, find its k closest training examples (data you already have labels for) and take the most common label. (e.g. k = 5, 3 are class A -> predict A)
• Small k follows the data closely — a wiggly boundary that can overfit (memorise random noise). (e.g. k = 1 memorizes every point)
• Large k smooths the boundary — more bias (rigidity), less variance (jumpiness). (e.g. k = 30 averages a big neighbourhood)
• There is no training step: the model just stores the data and votes when you ask for a prediction.

Definition

$$\hat{y}(x_0)=\text{majority vote of }\{y_i:x_i\in N_k(x_0)\}$$

$x_0$

the new point to classify

$N_k(x_0)$

its k nearest training points

$k$

how many neighbours vote

$\hat{y}$

the predicted class

In plain words

New kid in class? Look at the 5 students sitting nearest and guess they like what most of them like.

Where you'd use it

• Recommending products by finding users whose past purchases are closest to yours and suggesting what they bought.
• Recognising handwritten digits by comparing a new image to the k most similar labelled images.
• Flagging anomalies — a point whose neighbours are all far away is likely unusual.

Frequently asked questions

Why scale features for KNN?

It uses distances, so an unscaled large-range feature dominates.

How do I pick k?

By cross-validation — small k overfits, large k underfits.