KNN Implementation

You know how KNN works by hand and how spatial indexing makes it fast at scale. Now the question is: how do you actually tune it for a real dataset? What $k$ should you pick? Does distance-based weighting help? And when does KNN outperform a simple parametric model like linear regression?

We will answer all three by running KNN on two real-world datasets — Wine Quality (classification, 13 features) and California Housing (regression, 8 features). The house anchor from the first post will appear for a manual trace of weighted voting.

Anchor Datasets

Two datasets this time — one for classification, one for regression — because tuning KNN looks different for each task.

import numpy as np
from sklearn.datasets import load_wine, fetch_california_housing
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, mean_squared_error, r2_score

The Plan — Six Steps to a Tuned KNN Model

We will run KNN classifier on Wine Quality, find the optimal $k$, evaluate, then do the same for regression on California Housing, and finally compare against linear regression.

Step 1: KNN Classifier on Wine Quality — With and Without Scaling

Goal: Quantify the impact of feature scaling on a real multi-class dataset.

The Wine dataset has 178 samples, 13 features (alcohol, proline, color intensity, etc.), and 3 cultivar classes. The features are on wildly different scales — alcohol ranges 11–15, proline ranges 290–1680.

wine = load_wine()
X, y = wine.data, wine.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# Baseline — without scaling
knn_raw = KNeighborsClassifier(n_neighbors=5)
knn_raw.fit(X_train, y_train)
print(f"Without scaling — Test Accuracy: {knn_raw.score(X_test, y_test):.4f}")

# Proper — with scaling
scaler = StandardScaler()
X_train_sc = scaler.fit_transform(X_train)
X_test_sc  = scaler.transform(X_test)

knn_sc = KNeighborsClassifier(n_neighbors=5)
knn_sc.fit(X_train_sc, y_train)
print(f"With scaling    — Test Accuracy: {knn_sc.score(X_test_sc, y_test):.4f}")

Without scaling — Test Accuracy: 0.7222
With scaling    — Test Accuracy: 0.9444

A 22-point improvement from scaling alone. Here is why: the Wine dataset includes proline (range 290–1680) and color intensity (range 1–13). Without scaling, proline's squared differences are roughly $(1400{)}^2\approx 2\times 10^6$ while color intensity's are $(12{)}^2\approx 144$. Proline contributes $10,000\times$ more to every distance computation even though color intensity may be equally important for distinguishing wine cultivars. I used random_state=42 to get a reproducible train-test split — without it, the 22-point gap would vary every run and we could not trust the comparison.

✓ Step 1 complete. Scaling improves accuracy from 72.2% to 94.4% — a 22-point jump. Scaling is not optional for KNN.

Step 2: Finding the Optimal $k$

Goal: Find the $k$ value that maximizes cross-validation accuracy.

We sweep $k$ from 1 to 30, using 10-fold cross-validation on the scaled training set:

k_range = range(1, 31)
cv_scores = []
for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_train_sc, y_train, cv=10, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]
print(f"Best k: {best_k}, CV Accuracy: {max(cv_scores):.4f}")

Best k: 7, CV Accuracy: 0.9648

The curve tells the story of bias-variance tradeoff. At $k=1$, training accuracy is always 100% (every point's nearest neighbor is itself), but CV accuracy is around 0.88 — the model memorizes noise. The peak is at $k=7$. As $k$ grows beyond 15, accuracy steadily declines because neighbors from other classes are being included. The default $k=5$ in sklearn is a reasonable starting point, but it is almost never optimal — you should always tune this.

✓ Step 2 complete. Optimal $k$ is 7 with CV accuracy of 96.5%. The $k=1$ overfitting signal is visible in the gap between perfect training accuracy and degraded CV accuracy.

Step 3: Final Model Evaluation

Goal: Train the best model and evaluate on the held-out test set.

best_knn = KNeighborsClassifier(n_neighbors=best_k)
best_knn.fit(X_train_sc, y_train)

print(f"Test Accuracy: {best_knn.score(X_test_sc, y_test):.4f}")
print(classification_report(y_test, y_pred, target_names=wine.target_names))

Test Accuracy: 0.9722

              precision  recall  f1-score  support
    class_0       1.00    0.93     0.97       14
    class_1       0.93    1.00     0.96       14
    class_2       1.00    1.00     1.00        8
    accuracy                       0.97       36

97.2% accuracy. One misclassification: a class_0 wine predicted as class_1. Class 2 is perfectly separated — it likely has a distinct enough chemical signature that its 8 test samples all fell closest to other class 2 wines.

✓ Step 3 complete. The final model misclassifies 1 of 36 test samples. Precision and recall are above 0.93 for all classes.

Step 4: Weighted KNN — Does Distance-Based Voting Help?

Goal: Compare uniform voting (all neighbors count equally) with distance-weighted voting (closer neighbors count more).

The distance-weighted vote formula weights each neighbor by the inverse of its distance:

$\hat{y}=\arg {\max }_c{\sum }_{i\in \text{kNN}}1[y_i=c]\cdot w_i,w_i=\frac{1}{d(q,x_i)}$

for weights in ['uniform', 'distance']:
    knn = KNeighborsClassifier(n_neighbors=best_k, weights=weights)
    knn.fit(X_train_sc, y_train)
    acc = knn.score(X_test_sc, y_test)
    cv  = cross_val_score(knn, X_train_sc, y_train, cv=10, scoring='accuracy').mean()
    print(f"weights={weights:8s}: Test={acc:.4f}, CV={cv:.4f}")

weights=uniform : Test=0.9722, CV=0.9648
weights=distance: Test=0.9722, CV=0.9648

Identical performance on this dataset — the wine classes are well-separated enough that neighbor distances do not change the vote outcome. Distance weighting matters most when: (1) some neighbors are much closer than others, or (2) the decision boundary is noisy and the nearest neighbor is far more informative than the $k$-th.

Let's trace it on our house anchor from post 1 to see the mechanism. For the query $q=(3.0,3)$ with $k=3$:

• Neighbor C ($d=0.5$, Suburban): $w_C=1/0.5=2.0$
• Neighbor D ($d=0.5$, Urban): $w_D=1/0.5=2.0$
• Neighbor E ($d=1.41$, Urban): $w_E=1/1.41=0.71$

Uniform vote: Suburban = 1, Urban = 2 → Urban (67% confidence). Distance-weighted: Suburban weight = 2.0, Urban weight = $2.0+0.71=2.71$ → Urban (58% confidence).

Both predict Urban, but weighting reduces the confidence — D and E partially cancel out relative to C's proximity.

✓ Step 4 complete. Distance weighting has no effect on well-separated classes but matters when neighbors are at varying distances from the query.

Step 5: KNN Regressor on California Housing

Goal: Apply KNN to a regression task and observe the $k$ sensitivity.

The California Housing dataset tracks median house prices in California districts. We use the first 5000 samples (computational speed) with 8 features.

data = fetch_california_housing()
X, y = data.data[:5000], data.target[:5000]

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)
scaler = StandardScaler()
X_train_sc = scaler.fit_transform(X_train)
X_test_sc  = scaler.transform(X_test)

print(f"{'k':>4} | {'RMSE':>8} | {'R²':>8}")
for k in [1, 3, 5, 10, 20, 50]:
    knn_reg = KNeighborsRegressor(n_neighbors=k, weights='distance')
    knn_reg.fit(X_train_sc, y_train)
    y_pred  = knn_reg.predict(X_test_sc)
    rmse = np.sqrt(mean_squared_error(y_test, y_pred))
    r2   = r2_score(y_test, y_pred)
    print(f"{k:>4} | {rmse:>8.4f} | {r2:>8.4f}")

k |     RMSE |       R²
   1 |   0.6321 |   0.6789
   3 |   0.5812 |   0.7234
   5 |   0.5641 |   0.7389
  10 |   0.5823 |   0.7231
  20 |   0.6234 |   0.6891
  50 |   0.7012 |   0.6231

Peak at $k=5$ with R² of 0.739. At $k=1$, the model overfits — each prediction is the price of a single training house, which is noisy. At $k=50$, the model underfits — it averages over too broad a geographic area, losing local price patterns. I use random_state=42 again to ensure the train-test split is fixed so the $k$ sweep comparison is valid.

✓ Step 5 complete. Optimal $k$ for regression is 5. The $k=50$ underfit shows the same pattern as $k=1$ overfit — both extremes hurt generalization.

Step 6: KNN vs Linear Regression

Goal: Compare KNN to a global parametric model on the same regression task.

from sklearn.linear_model import LinearRegression

lr = LinearRegression()
lr.fit(X_train_sc, y_train)
y_pred_lr = lr.predict(X_test_sc)

knn_best = KNeighborsRegressor(n_neighbors=5, weights='distance')
knn_best.fit(X_train_sc, y_train)
y_pred_knn = knn_best.predict(X_test_sc)

print(f"Linear Regression: RMSE={np.sqrt(mean_squared_error(y_test, y_pred_lr)):.4f}, "
      f"R²={r2_score(y_test, y_pred_lr):.4f}")
print(f"KNN (k=5):         RMSE={np.sqrt(mean_squared_error(y_test, y_pred_knn)):.4f}, "
      f"R²={r2_score(y_test, y_pred_knn):.4f}")

Linear Regression: RMSE=0.7321, R²=0.6134
KNN (k=5):         RMSE=0.5641, R²=0.7389

KNN beats linear regression by 12.6 R² points. The reason is structural: housing prices have strong local structure. A district's price is better predicted by its nearest geographic neighbors than by a single global formula applied to all of California. Linear regression imposes a flat plane over the entire state; KNN adapts locally.

This is NOT the same as saying KNN is always better — KNN has no interpretable coefficients, is much slower at inference, and its $O(n)$ prediction cost scales with the dataset. Linear regression gives you a clear formula and $O(p)$ inference regardless of $n$. The choice depends on whether you need the local structure (KNN) or the global interpretability and speed (linear regression).

✓ Step 6 complete. KNN outperforms linear regression by 12.6 R² points on California Housing due to local price structure.

Summary Trace Table

When KNN Implementation Details Matter

The sign that you chose the right implementation approach is when cross-validation gives a clear $k$ peak and scaling changes the result dramatically — that means the algorithm is working and the data has genuine local structure. The sign of trouble is when CV accuracy is flat across all $k$ values — that suggests the local-smoothness assumption is violated and a global model or kernel method would perform better.

Common KNN Pitfalls

Here are the mistakes I have made (and seen others make) with KNN in practice:

KNN Hyperparameter Guide

Related Concepts

This post assumes you understand the KNN algorithm (distance computation, voting, $k$ selection) from post 1 and the KD-tree/Ball tree indexing from post 2. KNN is the canonical non-parametric baseline — it makes no distributional assumption — which makes it the natural comparison point when evaluating parametric models. The local-smoothness idea that KNN formalizes reappears in kernel regression and locally weighted regression. Moving from KNN to ensemble methods (random forest, gradient boosting) is a natural next step: those methods also exploit local structure, but learn it from data rather than computing it at query time, removing the $O(n)$ inference cost.

Honest Limitations

Here is the thing about KNN for debugging — I once spent two days trying to understand why a customer-churn KNN model was making wrong predictions. There is no coefficient or split criterion to inspect. No "feature 3 drove this prediction." Only the $k$ neighbors. If a prediction is wrong, you have to look at which neighbors were chosen and reason backward about why. That works for a few hundred samples but becomes impractical at scale.

Inference cost is the other hard limit. Linear regression inference is $O(p)$ — two dot products, always constant time. KNN inference is $O(n\times p)$ per query, and there is no caching across queries. At $n=10^6$ and $p=100$, each KNN prediction is roughly $10^4\times$ more expensive than linear regression, even with a Ball tree. I had to replace KNN with gradient boosting for a real-time fraud detection system precisely because the latency budget was 10ms and KNN could not meet it.

KNN assumes the data is locally smooth — nearby points share the same label. This fails for problems where the decision boundary is global or follows a non-local pattern (XOR, checkerboard). If your CV accuracy is low at every value of $k$, the local-smoothness assumption is violated. Do not try to fix this with more tuning — switch to a kernel method or ensemble model.

Test Your Understanding

1. Without scaling, KNN test accuracy is 72.2%; with scaling, 94.4%. The Wine dataset has 13 features including proline (range ~290–1680) and color_intensity (range ~1–13). Estimate how much more proline contributes to Euclidean distance vs color_intensity before scaling. What ratio does this give?

2. The CV accuracy curve peaks at $k=7$ and declines for larger $k$. If you plotted training accuracy (not CV) on the same chart, what would it look like? Where does training accuracy equal 1.0?

3. Distance-weighted KNN uses $w_i=1/d_i$. What happens if $d_i=0$ (query is identical to a training sample)? How should this edge case be handled, and what does sklearn do?

4. KNN Regressor with $k=1$ gives RMSE=0.632. On the training set, $k=1$ gives perfect RMSE=0.0. The gap between training RMSE (0) and test RMSE (0.632) is the generalization gap. Is this gap larger or smaller than for linear regression? What does the size of the gap tell you?

5. KNN has no explicit model — it cannot tell you "which features matter most." If a domain expert asks you why house A is predicted to cost $400k, what can you show them from the KNN model that serves as an explanation?