K-Nearest Neighbors

You're house hunting. You find a 1,250 sq ft, 3-bedroom place — not too big, not too small — and you need to know two things fast: is this in a decent neighborhood, and what should I offer? You pull up recent sales in the area. A 1,100 sq ft 3-bedroom nearby sold for $280k.A1,400sqft3-bedroomtwostreetsoverwentfor$340k. A 1,600 sq ft 4-bedroom a bit further out sold for $370k. You don't have a formula. You just look at the houses most like yours and see what they're worth.

That's the entire idea of K-Nearest Neighbors. No equations trained in advance, no parameters learned from data. When a new question arrives, you find the most similar examples you've already seen and let them vote. It is the most intuitive algorithm in machine learning — and the hardest to fool yourself into thinking you understand until you trace the distances by hand.

What Is KNN?

K-Nearest Neighbors is a non-parametric, lazy algorithm. "Non-parametric" means it makes no assumption about the shape of the decision boundary — no line, no curve, no equation. "Lazy" means it does no work during training. It literally just stores the training data. All the computation happens at prediction time: you give it a new point, it finds the $k$ closest stored points, and returns their consensus.

This is NOT the same as parametric models like linear regression or logistic regression. Those learn a fixed set of weights during training, and prediction is a single dot product — fast and constant-time, but the model is committed to its parametric form. KNN makes no commitment. Its decision boundary is implicit, local, and changes shape with every query point. The flexibility is a strength until it isn't — we'll get to that in the limitations.

Anchor Dataset

Let's make this concrete. Eight houses, two features (square footage and bedrooms), a neighborhood label for classification, and a sale price for regression.

import numpy as np

X_train = np.array([
    [650,  2],  # Suburban
    [850,  2],  # Suburban
    [1100, 3],  # Suburban
    [1400, 3],  # Urban
    [1600, 4],  # Urban
    [1900, 4],  # Urban
    [2200, 5],  # Urban
    [800,  2],  # Suburban
])
y_clf = np.array(['Sub', 'Sub', 'Sub', 'Urb', 'Urb', 'Urb', 'Urb', 'Sub'])
y_reg = np.array([180, 220, 280, 340, 370, 430, 500, 210])

Our test house — the one we need to classify and price:

x_new = np.array([1250, 3])

The training houses are a mix of smaller suburban places (blue collar, lower price) and larger urban ones (higher price). Our test point at 1,250 sq ft and 3 bedrooms sits right in the middle — close to both a 1,100 sq ft Suburban ($280k)anda1,400sqftUrban($340k). Let's walk through exactly what KNN does with it.

The Plan — Four Phases to a KNN Prediction

We'll trace KNN in four phases. First we compute every distance, then rank them, then classify by majority vote, and finally regress by averaging. Each phase builds on the previous one.

Phase 1: Compute Euclidean Distances

Goal: Measure how far the query house is from every training house in feature space.

The most common distance metric is Euclidean distance — the straight-line distance between two points in $p$-dimensional space. For two houses $a$ and $b$ with $p$ features:

$d(a,b)=\sqrt{{\sum }_{j=1}^p(a_j-b_j{)}^2}$

Let's substitute our numbers. Our query is $x_{\text{new}}=[1250,3]$. For the first training house $[650,2]$:

$d=\sqrt{(1250-650{)}^2+(3-2{)}^2}=\sqrt{600^2+1^2}=\sqrt{360001}=600.0$

Here's the full trace for all eight houses, with each term expanded:

Notice that the squared difference in sq_ft is orders of magnitude larger than the squared difference in bedrooms — $360000$ vs $1$ for Sample 1. This imbalance will matter later when we talk about feature scaling. For now, let's verify the computation with numpy:

d = np.sqrt(np.sum((X_train - x_new)**2, axis=1))
print(d.round(1))

[600. 400. 150. 150. 350. 650. 950. 450.]

Matches the table. There is a tie: Samples 3 and 4 both have $d=150.0$ because 1,100 and 1,400 are equidistant from 1,250 (both are 150 away), and both have 3 bedrooms. sklearn breaks ties by index — lower index first.

✓ Phase 1 complete. We computed all eight distances. Sq_ft dominates the calculation. Samples 3 and 4 are tied for closest at 150.0.

Phase 2: Select the $k$ Nearest Neighbors

Goal: Rank the training houses by distance and keep only the $k$ closest.

Sorting the distances from Phase 1:

For $k=3$, we keep Samples 3, 4, and 5. For $k=5$, we keep Samples 3, 4, 5, 2, and 8. Let's visualize the neighborhoods:

The concentric circles show the decision radius for different $k$ values. The innermost circle ($k=1$) captures only Sample 3 (Suburban). The middle circle ($k=3$) adds Sample 4 (Urban) and Sample 5 (Urban). The outer circle ($k=5$) pulls in Samples 2 and 8 (both Suburban). The choice of $k$ fundamentally changes which houses get to vote.

✓ Phase 2 complete. At $k=3$, our neighbors are Samples 3, 4, and 5 — one Suburban, two Urban.

Phase 3: Classify by Majority Vote

Goal: Let the $k$ nearest neighbors vote; the majority label wins.

There is no formula to train here — just a count. For $k=3$:

• Sample 3: Suburban
• Sample 4: Urban
• Sample 5: Urban

Vote tally: Suburban = 1, Urban = 2. Urban wins.

Confidence: $P(\text{Urban})=2/3=0.667$, $P(\text{Suburban})=1/3=0.333$.

Let's verify with numpy:

from scipy.stats import mode
neighbors_3 = y_clf[[2, 3, 4]]  # indices 2, 3, 4 from phase 2
print(mode(neighbors_3))

ModeResult(mode=array(['Urb']), count=array([2]))

What matters here: at $k=1$, this same query would be classified Suburban (the single nearest neighbor is Sample 3). The prediction flips at $k=3$ because two Urban neighbors enter the circle. This flip is the signal that our query point sits near a decision boundary.

✓ Phase 3 complete. The query house $[1250,3]$ is classified Urban with 67% confidence.

Phase 4: Regress by Averaging

Goal: Predict a numeric value by averaging the $k$ nearest neighbors' targets.

Same $k=3$ neighbors, but now we look at their prices instead of their labels:

$\hat{y}=\frac{1}{k}{\sum }_{i=1}^k{y}_{(i)}=\frac{280+340+370}{3}=\frac{990}{3}=\$330k$

What if we use $k=5$ instead? The neighbors expand to Samples 3, 4, 5, 2, and 8:

${\hat{y}}_{k=5}=\frac{280+340+370+220+210}{5}=\frac{1420}{5}=\$284k$

The $k=5$ prediction is $46klowerbecauseitincludestwocheapersuburbanhouses(Samples2and8at$220k and $210k).Thisisthebias-variancetradeoffinaction—larger$k$ smooths the prediction but may dilute local signal.

print(y_reg[[2, 3, 4]].mean())       # k=3
print(y_reg[[2, 3, 4, 1, 7]].mean()) # k=5

330.0
284.0

✓ Phase 4 complete. Predicted price is $330kwith$k=3$,$284k with $k=5$. The choice of $k$ changes the result by $46k.

Summary Trace Table

Hyperparameter Sensitivity: The Role of $k$

The single most important hyperparameter in KNN is $k$ — how many neighbors get to vote. Let's see how it affects predictions on our anchor:

At $k=1$, the prediction flips from Urban to Suburban — the single nearest neighbor is Suburban, so the model overfits to that one point. This is the telltale sign of $k$ being too small: high variance, sensitive to noise in any individual training sample.

Let's measure it systematically with leave-one-out cross-validation on our 8-sample anchor:

from sklearn.model_selection import LeaveOneOut
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

X_train = np.array([[650,2],[850,2],[1100,3],[1400,3],[1600,4],[1900,4],[2200,5],[800,2]])
y_clf = np.array(['Sub','Sub','Sub','Urb','Urb','Urb','Urb','Sub'])

scaler = StandardScaler()
X_sc = scaler.fit_transform(X_train)
loo = LeaveOneOut()

for k in [1, 2, 3, 4, 5, 7]:
    correct = sum(
        KNeighborsClassifier(n_neighbors=k).fit(X_sc[tr], y_clf[tr]).predict(X_sc[te])[0] == y_clf[te][0]
        for tr, te in loo.split(X_sc)
    )
    print(f"k={k}: LOO accuracy = {correct}/8 = {correct/8:.3f}")

k=1: LOO accuracy = 7/8 = 0.875
k=2: LOO accuracy = 6/8 = 0.750
k=3: LOO accuracy = 7/8 = 0.875
k=4: LOO accuracy = 7/8 = 0.875
k=5: LOO accuracy = 6/8 = 0.750
k=7: LOO accuracy = 5/8 = 0.625

Here's the thing about $k$ — I learned this the hard way debugging a production classifier. At $k=1$, training accuracy is always 100% (every point's nearest neighbor is itself), so if you only look at training accuracy you'll think the model is perfect. Cross-validation reveals the truth: at $k=7$, the model can barely distinguish Urban from Suburban (62.5%) because it's averaging over most of the dataset and losing local signal. The sweet spot is $k=3$–$4$, where the model captures local structure without memorizing noise.

Distance Metric Matters

Euclidean distance is the default, but it is not the only option. Here's the same query with Manhattan distance:

$d_{\text{Euclidean}}(a,b)=\sqrt{{\sum }_j(a_j-b_j{)}^2},d_{\text{Manhattan}}(a,b)={\sum }_j|a_j-b_j|$

Same ranking here because the bedroom difference is tiny compared to sq_ft. The metrics diverge when features have similar scales — Manhattan penalizes large differences in any single dimension more linearly, while Euclidean squares them and amplifies outliers.

Feature Scaling Is Critical

Look back at the distance table. Sq_ft contributed terms like $360000$ while bedrooms contributed at most $4$. In raw units, adding one bedroom has $10,000\times$ less influence on distance than adding one sq_ft. The algorithm silently ignores bedrooms.

StandardScaler fixes this by transforming each feature to zero mean and unit variance:

• Sq_ft: mean $\approx 1312.5$, std $\approx 534$
• Bedrooms: mean $\approx 3.1$, std $\approx 1.05$

After scaling, all features contribute proportionally:

$x_{\text{new}}$ scaled: $[(1250-1312.5)/534,(3-3.1)/1.05]=[-0.117,-0.095]$

Sample 3 scaled: $[(1100-1312.5)/534,(3-3.1)/1.05]=[-0.398,-0.095]$

$d_{\text{scaled}}(\text{new},3)=\sqrt{(-0.117+0.398{)}^2+0^2}=\sqrt{0.079}=0.281$

After scaling, both features matter. StandardScaler is not optional for KNN — it is structurally part of the algorithm. Skipping it is the single most common mistake.

Putting It All Together: sklearn

Let's automate the full pipeline with sklearn, using scaling and verifying the neighbors:

from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_sc       = scaler.fit_transform(X_train)
x_new_sc   = scaler.transform(x_new.reshape(1, -1))

# Classification with k=3
knn_clf = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
knn_clf.fit(X_sc, y_clf)
print(f"Classification: {knn_clf.predict(x_new_sc)[0]}")
print(f"Probabilities:  {dict(zip(knn_clf.classes_, knn_clf.predict_proba(x_new_sc)[0]))}")

# Regression with k=3
knn_reg = KNeighborsRegressor(n_neighbors=3, metric='euclidean')
knn_reg.fit(X_sc, y_reg)
print(f"Regression ŷ: ${knn_reg.predict(x_new_sc)[0]:.1f}k")

# Inspect which neighbors were used
distances, indices = knn_clf.kneighbors(x_new_sc)
print(f"\n3 nearest neighbors (indices): {indices[0]}")
print(f"Distances (scaled):  {distances[0].round(3)}")
print(f"Labels: {y_clf[indices[0]]}")

Classification: Urb
Probabilities:  {'Sub': 0.333, 'Urb': 0.667}
Regression ŷ: $330.0k
3 nearest neighbors (indices): [2 3 4]
Distances (scaled): [0.281 0.281 0.655]
Labels: ['Sub' 'Urb' 'Urb']

The kneighbors() method is the diagnostic tool I use most — it tells you exactly which training points drove the prediction. If a prediction seems wrong, inspect the neighbors first.

When KNN Works and When It Doesn't

KNN works when the decision boundary is genuinely local — a house's price is better predicted by nearby houses than by a global formula, a tumor's malignancy is better predicted by similar histological examples than by a fixed threshold. The sign that KNN is the right tool is when domain knowledge says "things similar in these features tend to have similar outcomes."

Reach for KNN first when you need a quick, interpretable baseline with no training phase. It's unbeatable for rapid prototyping — you can have a model running in five lines of code with zero training time. The sign you chose the wrong tool is when prediction latency matters (KNN is slow at inference for large datasets) or when the decision boundary is known to follow a parametric form (linear relationships, threshold effects).

Related Concepts

KNN assumes you already understand Euclidean distance (geometry) and feature normalization (from the feature engineering section) — without both, the distance computation is meaningless. It unlocks spatial indexing methods (KD-trees, Ball trees, covered in the next post), which replace the $O(n)$ brute-force sweep with logarithmic query time. It also motivates the curse of dimensionality: as features grow, all pairwise distances converge and "nearest neighbor" loses meaning, which in turn motivates dimensionality reduction methods like PCA.

Honest Limitations

Here's the thing about KNN at scale — I ran into this on a recommendation system with 2 million users. Each KNN prediction requires computing distances to every training point. With $n=1,000,000$ and $p=100$ features, that's $10^8$ floating-point operations per query — roughly a second on commodity hardware. Use a Ball tree or approximate nearest neighbor index (FAISS, HNSW) before deploying at that scale, or the latency will surprise you.

A single unscaled high-range feature will silently dominate the distance calculation. I've seen a model where income in dollars (range 0–200k) shared space with age in years (range 20–80), and the income feature contributed 99.9% of every distance. The model had effectively one feature. StandardScaler is not optional — it is structurally required.

KNN cannot tell you which features drove a prediction. If a stakeholder asks why a house was classified Urban, you can show them the $k$ neighbors — "because it's most similar to these three houses" — but you cannot produce a coefficient or importance score. When the business requires explainability per prediction, use a decision tree or logistic regression instead.

Test Your Understanding

1. At $k=1$, Sample 3 (Suburban) is the nearest neighbor. At $k=3$, two Urban neighbors outvote it. What is the smallest perturbation to $x_{\text{new}}$ (in sq_ft) that would change the $k=3$ classification back to Suburban?

2. The table shows $k=1$ regression predicts $280kand$k=3$predicts$330k. If the true price for $x_{\text{new}}=[1250,3]$ is $310k,which$k$ismoreaccurate?Doesthisgeneralize—ishigherorlower$k$ better for regression accuracy?

3. Euclidean distance uses squared differences: $(a_j-b_j{)}^2$. For a dataset with one feature in $[0,1]$ and another in $[0,1000]$, the squared difference for the large feature is up to $10^6$ vs $1$ for the small feature. Compute how many times more influential the large feature is.

4. After StandardScaler, Sample 3 and Sample 4 both have scaled distance 0.281 from $x_{\text{new}}$. If you used MinMaxScaler (range $[0,1]$) instead, would the distances still be equal? Why or why not?

5. KNN has no training phase — fitting is $O(1)$ (just storing data). But prediction is $O(n\times p)$ per query. For $n=1,000,000$ and $p=100$, estimate the number of floating-point operations per prediction. How does this compare to logistic regression inference?