K-Nearest Neighbors Explained: Distance Metrics, Choosing K, and Classification

K-nearest neighbors (k-NN) classifies a new point by looking at the $k$ closest training examples and taking a majority vote. There is no separate “training” phase that learns weights. The model is the stored dataset plus a distance function. That simplicity makes k-NN a powerful baseline — and a sharp lesson in scaling, feature choice, and the curse of dimensionality.

This article explains distance metrics, how to choose $k$, weighted votes, regression with k-NN, and the failure modes that show up the moment your table has more than a few dozen columns.

How the k-NN algorithm works

Given a query $\mathbf{x}$:

1. Compute a distance $d(\mathbf{x},\mathbf{x}_i)$ to every training point.
2. Select the $k$ smallest distances.
3. For classification, return the most common label among those neighbors.
4. For regression, return the mean (or median) of the neighbor targets.

Ties in classification can be broken by smaller $k$, by distance-weighted votes, or by a predetermined class order. Distance-weighted k-NN gives closer neighbors more influence:

$$\hat y(\mathbf{x})=\arg\max_c\sum_{i\in N_k(\mathbf{x})} w_i\mathbf{1}\{y_i=c\},\qquad w_i=\frac{1}{d(\mathbf{x},\mathbf{x}_i)+\varepsilon}.$$

Because prediction scans the training set, cost grows with $n$. Tree indexes (KD-trees, ball trees) help in low dimension; they degrade as dimension grows.

Distance metrics change the neighbors

The default is Euclidean (L2) distance. Manhattan (L1) is more robust to large coordinate outliers. Minkowski interpolates between them. Cosine distance ignores vector length and keeps orientation — standard for text TF-IDF vectors.

If income is in dollars and age is in years, Euclidean distance is dominated by income. Standardize features (zero mean, unit variance) before k-NN unless you have a principled reason not to. This is the same geometry discussed in the vector norms guide.

Open the KNN Calculator and switch Euclidean versus Manhattan on the same points. The neighbor set — and sometimes the predicted class — will change.

How to choose k

$k$ is the entire inductive bias.

• $k=1$: the classifier memorizes the training set. Training error can be ~0; test error is noisy and sensitive to mislabels.
• Small $k$: flexible boundary, high variance.
• Large $k$: smoother boundary, high bias; in the limit you predict the global majority class.

Odd $k$ reduces two-class vote ties. The right $k$ is chosen by k-fold cross-validation, not by training accuracy.

A practical search is $k\in\{1,3,5,7,11,15,\sqrt{n}\}$. Plot validation error against $k$; you typically see a U-shape.

Why k-NN needs feature engineering

Irrelevant features are not ignored. Every extra noisy column adds distance in a direction that does not help. In high dimension, pairwise distances concentrate: nearest and farthest points become similar, so “nearest neighbor” loses meaning.

Remedies:

• Drop or regularize useless columns.
• Use PCA or other dimensionality reduction before k-NN.
• Learn a metric (Mahalanobis, metric-learning) if you have enough data.
• Scale and encode categoricals carefully; one-hot columns of rare levels can dominate L2.

See the feature engineering guide for scaling and encoding choices that k-NN feels immediately.

k-NN versus parametric classifiers

k-NN is a strong baseline. If k-NN is already excellent, a neural net may be overkill. If k-NN is terrible after scaling, the classes may overlap or the features may not carry neighborhood structure.

Frequently asked questions

Is k-NN supervised or unsupervised?

The classification/regression form is supervised: it uses labels of neighbors. Related unsupervised ideas (nearest-neighbor graphs, outlier scores) use distances without labels.

What is lazy learning?

Lazy (instance-based) methods postpone work until prediction time. k-NN is the textbook example. Eager methods such as logistic regression spend compute during training.

Can I use k-NN with mixed numeric and categorical data?

Yes, but you must define a distance: one-hot plus scaling, Gower distance, or separate numeric/categorical metrics. Naive Euclidean on integer-coded categories treats “red=1, blue=2, green=3” as ordered, which is usually wrong.

Why does k-NN overfit even with large k?

If features are unscaled or the label is noisy in a small neighborhood of duplicates, large $k$ cannot save you. Duplicated rows also bias votes. Clean the table first.

Next steps

Pick a two-feature toy set, standardize it, and plot error versus $k$. Then add a third noise feature and watch accuracy drop — that is the curse of dimensionality in one experiment. Reproduce the neighbor geometry in the KNN Calculator. When neighborhoods are the wrong inductive bias, move to a linear model or a tree ensemble.