K-Nearest Neighbors

Classifying or predicting by looking at the k closest training points — the simplest non-parametric method, intuitive yet powerful.

k-NN classifies a new point by asking its nearest neighbors to vote

Current vote

Class 1

1 votes for C0
2 votes for C1

The amber circle grows until it reaches the kth nearest point. Only points inside that radius vote.

k=3Move across the chart

Definition

k-Nearest Neighbors (k-NN) is a simple non-parametric algorithm: to classify a new point, find the $k$ training points closest to it and take the majority class.

Algorithm:

Choose $k$ (number of neighbors)
For a new point $\mathbf{x}$ , compute the distance to every training point
Find the $k$ training points with smallest distance
Predict the majority class among those $k$ neighbors

Distance: usually Euclidean distance $\|\mathbf{x} - \mathbf{x}_i\|$ , but any distance function works.

$k=1$ : assign the class of the single nearest neighbor. Large $k$ : smoother boundary, more robust to noise.

Key properties

Non-parametric: makes no assumption about the underlying data distribution
"Lazy" learning: no training phase — all the work happens at prediction time
Naturally handles multi-class problems via simple majority vote
Decision boundary complexity adapts to the data, with no fixed functional form

Common mistakes

Forgetting to scale features: distance-based methods let large-scale features dominate unless every feature is standardized first
Using an even $k$ for binary classification: ties become possible and need a tie-breaking rule, which an odd $k$ avoids
Ignoring the curse of dimensionality: in high dimensions, "nearest" stops being meaningful as distances between all points converge

Iris flower classification

Given measurements (petal length, petal width) of a new flower: find the 3 nearest flowers in the training set. If 2 are Setosa and 1 is Versicolor, predict Setosa. Simple, no training required — just store all training examples.

Try it

What is the computational cost of classifying a single test point using k-NN with $n$ training points and $d$ features? How does this compare to training a logistic regression model?

Solution

For k-NN: computing distances to all $n$ training points costs $O(nd)$ . Finding the $k$ smallest costs $O(n)$ (or $O(n \log n)$ for exact sort). Total per prediction: $O(nd)$ . Training cost: $O(1)$ (just store the data).

For logistic regression: training costs $O(ndi)$ (gradient descent, $i$ iterations). Prediction costs $O(d)$ (dot product + sigmoid). k-NN is free to "train" but expensive to predict; logistic regression is the opposite.

Approximate nearest neighbor methods (KD-tree, ball tree, FAISS) can reduce query time to $O(d \log n)$ or $O(d)$ approximately.

Related concepts

Needs first

Norms Probability

Cross-Validation Geometry of Decision Boundaries Dimensionality Reduction K-Means Clustering Model Evaluation Support Vector Machines

View in full concept graph →