KNN: Classification and Regression Intuition

Most classifiers learn parameters during training — weights, thresholds, tree splits — and use those parameters to make predictions. KNN does neither. There is no training phase beyond memorizing the dataset. Every prediction computes distances to all stored examples on the fly and returns the consensus of the nearest ones. Simple to state, surprisingly effective, and reveals exactly what "local similarity" means in machine learning.

Anchor dataset: House classification and price prediction. Two features so distances can be computed by hand.

import numpy as np

# [sq_ft, bedrooms], neighborhood, price ($k)
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])

x_new = np.array([1250, 3])  # unknown house — classify neighborhood and predict price

The KNN Algorithm

At prediction time for a query point $x$:

1. Compute the distance from $x$ to every training sample
2. Sort training samples by distance, take the $k$ nearest
3. Classification: return the majority label among the $k$ neighbors
4. Regression: return the average $y$ value among the $k$ neighbors

No model, no parameters. The "decision boundary" is implicit — it shifts with every query point.

Step 1: Computing Euclidean Distance

$d(a,b)=\sqrt{{\sum }_j(a_j-b_j{)}^2}$

Distance from $x_{\text{new}}=[1250,3]$ to each training sample:

Ranked by distance: Sample 3 (150), Sample 4 (150), Sample 5 (350), Sample 2 (400), Sample 8 (450), Sample 1 (600), Sample 6 (650), Sample 7 (950).

Samples 3 and 4 are tied at $d=150$ — $x_{\text{new}}$ is exactly equidistant from sq_ft=1100 and sq_ft=1400. Tie-breaking is by index in sklearn (lower index first).

Step 2: k=3 Classification

The 3 nearest neighbors: Sample 3 (Suburban, $d=150$), Sample 4 (Urban, $d=150$), Sample 5 (Urban, $d=350$).

Vote count: Suburban = 1, Urban = 2 → Urban wins.

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

Step 3: k=3 Regression

Same 3 neighbors: Samples 3, 4, 5 with prices $y=[280,340,370]$.

$\hat{y}=\frac{280+340+370}{3}=\frac{990}{3}=\$330k$

Compare with $k=5$: neighbors are Samples 3, 4, 5, 2, 8 with $y=[280,340,370,220,210]$.

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

The $k$ value matters — increasing $k$ includes cheaper suburban houses (Samples 2 and 8), pulling the prediction down by $46k.

The k=1 circle (green) captures only Sample 3 (Suburban). Expanding to k=3 (blue) adds Sample 4 (Urban) and Sample 5 (Urban). Expanding to k=5 (amber) pulls in Samples 2 and 8 (both Suburban).

The Role of k

At $k=1$: the single nearest neighbor is Suburban, giving an incorrect classification for this ambiguous point. At $k=3$: the two Urban neighbors outvote the one Suburban neighbor. The prediction flips. This instability — where one vote changes the outcome — is characteristic of small $k$.

Distance Metric Matters

Same query point $x_{\text{new}}=[1250,3]$, comparing Euclidean vs Manhattan distance for the top 3 candidates:

$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 bedroom differences are tiny compared to sq_ft differences. The metrics diverge when feature scales are similar — Manhattan penalizes large differences in any one dimension more heavily than Euclidean, which distributes the penalty across all dimensions.

Feature Scaling Is Critical

Current raw distances are dominated by sq_ft (range 650–2200) and barely influenced by bedrooms (range 2–5). With raw features, adding a bedroom matters $10,000\times$ less than adding 1 sq_ft.

After StandardScaler (mean≈1312.5, std≈534 for sq_ft; mean≈3.1, std≈1.05 for bedrooms):

$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, bedrooms and sq_ft contribute proportionally. Skipping scaling is the most common KNN mistake.

sklearn Implementation

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
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
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 neighbors
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]]}")

kneighbors() is the key diagnostic tool — it returns which training samples are the actual neighbors for any query, letting you verify and debug predictions.

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 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?