k-Nearest Neighbors

k-Nearest Neighbors (KNN) is the simplest classifier in this library: it stores all the training cases and classifies each new case by a majority vote of its neighbors. There is no training phase and no fitted equation — the data itself is the model, which is why KNN is called a non-parametric, instance-based method. It has been used in statistical estimation and pattern recognition since the early 1970s (Cover & Hart formalized its properties in 1967).

If $k = 1$, a case is simply assigned the class of its single nearest neighbor. Larger $k$ smooths the vote across more evidence.

Distance: what “nearest” means

Everything hinges on the distance function. For continuous predictors, the default is Euclidean distance:

$D(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$

Close relatives are Manhattan distance, $\sum_i |x_i - y_i|$, and their generalization, the Minkowski distance $(\sum_i |x_i - y_i|^p)^{1/p}$, which reduces to Manhattan at $p = 1$ and Euclidean at $p = 2$.

These measures only make sense for numbers. For categorical variables, use the Hamming distance — the count of positions at which two cases differ:

$D_H(x, y) = \sum_{i=1}^{n} \mathbf{1}\left[ x_i \neq y_i \right]$

With a mixture of numerical and categorical predictors, standardize the numerical ones (e.g. to $[0, 1]$) so both kinds of difference live on comparable scales.

Worked example: credit default

The training set below records Age and Loan amount for eleven clients, with Default as the target. Should a new applicant with Age = 48, Loan = $142,000 be classified as a defaulter?

Age	Loan	Default	Distance to query
25	$40,000	N	102,002.6
35	$60,000	N	82,001.0
45	$80,000	N	62,000.1
20	$20,000	N	122,003.2
35	$120,000	N	22,003.8
52	$18,000	N	124,000.1
23	$95,000	Y	47,006.6
40	$62,000	Y	80,000.4
60	$100,000	Y	42,001.7
48	$220,000	Y	78,000.0
33	$150,000	Y	8,000.01

With $k = 1$, the nearest case is the last row:

$D = \sqrt{(48 - 33)^2 + (142{,}000 - 150{,}000)^2} = \sqrt{15^2 + 8{,}000^2} = 8{,}000.01 \;\Rightarrow\; \text{Default} = Y$

With $k = 3$, the three closest cases are Y, N, and Y — two Y votes against one N — so the prediction is again Default = Y.

Choosing k

• Small $k$ (1–3) fits noise; large $k$ oversmooths and can wash out local structure.
• Historically, the sweet spot for most datasets is between 3 and 10, and almost anything in that range beats 1NN.
• Pick $k$ by cross-validation: score candidate values on held-out folds and keep the winner.
• With two classes, prefer an odd $k$ to avoid tied votes.

Try it

Interactive playground: a two-class scatter plot where you place a query point and sweep k from 1 to 15, watching distance rings and the majority vote. A typical readout for a query point placed near the boundary of the two clusters:

k	Votes (A / B)	Prediction
1	1 / 0	A
3	2 / 1	A
5	2 / 3	B
7	3 / 4	B
9	4 / 5	B

Notice how the prediction flips as k grows — small k tracks local structure, large k tracks the global majority.

In practice

sklearn.neighbors.KNeighborsClassifier is the standard implementation; always wrap it in a Pipeline with StandardScaler so distances are meaningful. KNN is a strong baseline for small, low-dimensional datasets and for recommendation-style similarity lookups, but exact search gets slow in high dimensions — production systems switch to approximate nearest-neighbor indexes (FAISS, Annoy, HNSW). Distance-weighted voting (weights='distance') lets nearer neighbors count more and often beats uniform voting at larger $k$.

Common pitfalls

• Skipping normalization. The largest-scale feature silently controls every distance — as the credit example shows, the answer can flip completely.
• High-dimensional data. In many dimensions all points become roughly equidistant (the curse of dimensionality), and “nearest” stops meaning “similar.”
• Choosing k on the training set. 1NN scores 100% on its own training data; only held-out validation reveals the right $k$.
• Ignoring ties and class imbalance. A majority class dominates large $k$; use distance weighting or class balancing.
• Treating KNN as cheap at prediction time. Every prediction compares against the whole training set — budget for it.

Summary

KNN classifies by majority vote among the $k$ closest training cases under a distance function — Euclidean for numbers, Hamming for categories. Normalize predictors first, choose $k$ (typically 3–10) by cross-validation, and remember that the model is only as good as its distance metric. Simple, transparent, and surprisingly competitive on the right data.