K-Nearest Neighbors

Difficulty:Intermediate

Reading Time:20 min

Track:

Practitioner

A simple algorithm that makes predictions for a new data point by finding the closest, most similar historical examples.

ML PractitionerModule 6 of 17

K-Nearest Neighbors

35%

TL;DR

KNN is a lazy, non-parametric classifier: it stores the training set and defers all work to prediction time, where it finds the $k$ closest points and takes a majority vote (or an average for regression).
The choice of $k$ is a bias-variance dial: small $k$ means low bias but high variance (jagged, noise-chasing boundaries), large $k$ means high bias but low variance (smooth, possibly underfit boundaries).
Predictions hinge on a distance metric, usually Euclidean $d(x, x') = \sqrt{\sum_i (x_i - x_i')^2}$ or Manhattan $d_1 = \sum_i |x_i - x_i'|$ .
Because distance mixes all features, feature scaling is mandatory — an unscaled large-range feature will dominate the metric and silently ignore the others.
KNN shines on small, low-dimensional datasets but degrades badly in high dimensions (the curse of dimensionality) and is slow at prediction time, costing $O(n \cdot p)$ per query with a brute-force search.

Learning Objectives

Explain the non-parametric nature of the K-Nearest Neighbors algorithm
Compute distances between data points using Euclidean and Manhattan distance metrics
Compare the behavior of the model for small versus large values of $K$ (overfitting vs underfitting)
Describe why feature scaling is critical for distance-based algorithms

Intuition

How to think conceptually about this topic

Imagine you move to a new city and want to know if a specific neighborhood is safe. You don't need a complex mathematical formula; you just ask the 5 people who live closest to that neighborhood. If 4 out of 5 say it's safe, you assume it's safe. That's exactly how KNN works.

Interactive Diagram

Test the intuition above by changing the model parameters

In Depth

Detailed explanations, contexts, and details

K-Nearest Neighbors (KNN) is one of the simplest and most intuitive algorithms in machine learning. It is a non-parametric method, meaning it does not assume any underlying mathematical shape for the data. Instead of training a model to find mathematical equations, KNN literally just memorizes the entire training dataset.

When you ask it to make a prediction for a new, unseen data point, it looks at the entire dataset, finds the $k$ data points that are geometrically closest (most similar) to the new point, and takes a vote. For classification, it returns the most common label among its neighbors; for regression, it returns the average value of its neighbors.

Where is it used?

KNN is used in basic recommendation systems (finding users with similar movie tastes), anomaly detection (flagging transactions that are geometrically far from a user's normal spending clusters), and as a quick baseline algorithm before trying more complex models.

How It Compares

KNN vs Logistic Regression vs Decision Tree

Dimension	KNN	Logistic Regression	Decision Tree
Model type	Non-parametric (instance-based)	Parametric (learns fixed weights $w, b$ )	Non-parametric (learns a tree structure)
Training cost	Effectively $O(1)$ — just stores the data (lazy)	Iterative optimization of the weights	Recursive splitting, roughly $O(n p \log n)$
Prediction cost	Expensive: $O(n p)$ per query (brute force)	Cheap: one dot product $O(p)$	Cheap: a root-to-leaf walk $O(\text{depth})$
Interpretability	Low — no global rule, only neighbor lookups	High — signed coefficients per feature	High — human-readable if/else splits
Handling of nonlinearity	Naturally nonlinear, arbitrary boundaries	Linear boundary unless features are engineered	Naturally nonlinear via axis-aligned splits
Feature scaling needed	Yes — distance is scale-sensitive	Helpful for convergence, not strictly required	No — splits are scale-invariant

TakeawayReach for KNN when boundaries are irregular and the dataset is small and low-dimensional; prefer logistic regression for a fast, interpretable linear baseline, and a decision tree when you want nonlinearity plus human-readable rules without worrying about scaling.

When to Use It

Reach for this when

The dataset is small to medium and low-dimensional, so brute-force neighbor search stays cheap and distances remain meaningful.
The decision boundary is irregular or highly non-linear and you want a method that adapts locally without assuming a functional form.
You need a quick, assumption-light baseline or a simple similarity engine (e.g. "find the most similar items/users").

Avoid it when

The feature space is high-dimensional — under the curse of dimensionality all points become roughly equidistant and neighbor votes lose meaning.
You have a large training set with tight latency requirements — every prediction scans the whole dataset, which is slow and memory-heavy.
You need an interpretable, global explanation of the model — KNN offers no coefficients or rules, only per-query neighbor lists.

Rules of thumb

Always scale features (standardize or min-max) before computing distances.
Start with $k \approx \sqrt{n}$ and tune $k$ by cross-validation; prefer an odd $k$ in binary classification to avoid ties.
For large datasets, replace brute-force search with an approximate index (KD-tree, ball tree, or HNSW) to cut prediction cost.

Implementation

Reference code implementation

Python

model_fitting.py

1import numpy as np
2from sklearn.neighbors import KNeighborsClassifier
3
4# Two-dimensional feature coordinates
5X = np.array([[0, 0], [1, 1.5], [1.5, 1], [8, 8], [8.5, 7.5], [9, 9]])
6# Binary Labels
7y = np.array([0, 0, 0, 1, 1, 1])
8
9# Initialize and fit KNN
10knn = KNeighborsClassifier(n_neighbors=2)
11knn.fit(X, y)
12print(f"KNN Class for coordinate [2, 2]: {knn.predict([[2, 2]])[0]}")

Strengths & Advantages

Extremely simple to understand and implement.
No training phase whatsoever; adding new data is instant.
Can easily handle complex, non-linear decision boundaries.

Limitations & Drawbacks

Extremely slow at prediction time on large datasets, because it must compute the distance to every single point.
Requires keeping the entire dataset in memory.
Sensitive to the scale of features; features with larger ranges will dominate the distance calculation.

Real-World Case Studies

Handwritten digit recognition on MNIST

Computer vision / OCR

Scenario

The MNIST benchmark contains 70,000 grayscale images of handwritten digits (60,000 train, 10,000 test), each a $28 \times 28$ image flattened into a 784-dimensional pixel vector. The task is to classify each image as one of the ten digits $0$ through $9$ .

Approach

Treat each image as a point in $\mathbb{R}^{784}$ and classify a test image by the majority label among its $k$ nearest training images under Euclidean (L2) distance. No model is trained — the algorithm simply searches the 60,000 stored examples for the closest matches at prediction time.

Outcome

A plain KNN classifier with $k = 3$ and Euclidean distance reaches roughly 97% test accuracy (about a 3% error rate) on MNIST — a strong result for such a simple, training-free method, and competitive with early neural networks. The main cost is at prediction time, since each of the 10,000 test queries is compared against all 60,000 training points.

Source: The MNIST Database of Handwritten Digits (benchmark results table) — LeCun, Y., Cortes, C. and Burges, C.J.C.

Common Misconceptions

MisconceptionKNN actually trains a model during the .fit() step.

CorrectionIn standard KNN, .fit() is a lazy step that just stores the training data in memory. All computation (finding neighbors and voting) happens during the prediction phase.

MisconceptionYou should always set

K

as large as possible to get a smooth boundary.

CorrectionIf

K

is too large (approaching the dataset size

N

), the model will just predict the majority class of the entire dataset, leading to underfitting. If

K=1

, the model will overfit to individual noise points.

References & Further Reading

Classification and Regression Treestextbook
By Breiman, L., Friedman, J., Stone, C.J. and Olshen, R.A
View Resource →
Machine Learning with Random Forests and Decision Treestextbook
By Scott, S
View Resource →

← Previous Topic

Model Evaluation & Validation

Next Topic →

Naive Bayes