K-Nearest Neighbors

The Story That Explains KNN

How KNN Works — Four Steps

Distance Metrics — How "Closeness" Is Measured

The entire logic of KNN depends on a reliable measure of similarity. Different distance metrics lead to different neighbours — and different predictions. Choosing the right metric matters.

Step-by-Step Manual Calculation

Let us classify one new patient by hand using K=3 and Euclidean distance. We have five existing patients with two features: Age and Glucose Level, and a known diabetes label.

Classification vs Regression

Choosing K — The Most Critical Decision

Feature Scaling — Mandatory, Never Optional

KNN's core operation is measuring distance. Any feature with a larger numerical range will dominate all distance calculations, effectively making all other features invisible to the model.

The Curse of Dimensionality

Python Implementation

KNN Classification — Iris Dataset

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report, confusion_matrix

iris = load_iris()
X, y = iris.data, iris.target

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

# ⚠️ CRITICAL: Always put StandardScaler inside Pipeline
# This prevents data leakage from the test set into scaling
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(
        n_neighbors=5,          # K — tune with cross-validation
        metric='euclidean',     # distance function
        weights='uniform',      # all neighbours vote equally
        algorithm='auto',       # auto-selects ball_tree/kd_tree/brute
        n_jobs=-1               # use all CPU cores for search
    ))
])

pipe.fit(X_train, y_train)
y_pred = pipe.predict(X_test)

print(f"Accuracy: {pipe.score(X_test, y_test):.4f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

# Predict with class probabilities (fraction of K neighbours per class)
y_prob = pipe.predict_proba(X_test)
for i in range(3):
    cls   = iris.target_names[y_pred[i]]
    conf  = y_prob[i].max() * 100
    print(f"  Sample {i+1}: {cls:12s} ({conf:.0f}% of neighbours agree)")

Finding Optimal K with Cross-Validation

import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

k_range  = range(1, 32, 2)   # odd values 1, 3, 5 ... 31
k_scores = []

for k in k_range:
    pipe_k = Pipeline([
        ('scaler', StandardScaler()),
        ('knn',    KNeighborsClassifier(n_neighbors=k, n_jobs=-1))
    ])
    scores = cross_val_score(
        pipe_k, X_train, y_train,
        cv=5, scoring='accuracy'
    )
    k_scores.append((k, scores.mean(), scores.std()))

# Print table of K vs CV accuracy
print(f"{'K':>4} {'CV Accuracy':>12} {'Std Dev':>10}")
print("-" * 30)
for k, mean, std in k_scores:
    marker = " ← BEST" if mean == max(s[1] for s in k_scores) else ""
    print(f"{k:>4}   {mean:.4f}       ±{std:.4f}{marker}")

best_k = max(k_scores, key=lambda x: x[1])[0]
print(f"\nOptimal K = {best_k}")

KNN Regression — House Price Prediction

from sklearn.neighbors import KNeighborsRegressor
from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import r2_score, mean_absolute_error

housing = fetch_california_housing()
X, y    = housing.data, housing.target

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

# Uniform KNN regression — simple average of K neighbours
knn_reg = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsRegressor(
        n_neighbors=10,
        weights='distance',   # closer neighbours contribute more
        metric='euclidean',
        n_jobs=-1
    ))
])

knn_reg.fit(X_train, y_train)
y_pred = knn_reg.predict(X_test)

print(f"R² Score: {r2_score(y_test, y_pred):.4f}")
print(f"MAE:      ${mean_absolute_error(y_test, y_pred)*100_000:.0f}")

Implementing KNN from Scratch

import numpy as np
from collections import Counter

def euclidean_distance(x1, x2):
    """Straight-line distance between two points."""
    return np.sqrt(np.sum((x1 - x2) ** 2))

class KNNClassifier:
    def __init__(self, k=5):
        self.k = k

    def fit(self, X, y):
        """No training — just memorise the dataset."""
        self.X_train = X
        self.y_train = y
        return self

    def predict(self, X):
        """Predict class for each point in X."""
        return np.array([self._predict_one(x) for x in X])

    def _predict_one(self, x):
        # Step 1: compute distance to every training point
        distances = [euclidean_distance(x, x_tr)
                     for x_tr in self.X_train]
        # Step 2: find indices of K smallest distances
        k_idx = np.argsort(distances)[:self.k]
        # Step 3: get labels of K nearest neighbours
        k_labels = self.y_train[k_idx]
        # Step 4: return majority vote
        return Counter(k_labels).most_common(1)[0][0]

# ── Test against sklearn ─────────────────────────────────────
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

iris = load_iris()
X, y = iris.data, iris.target
sc   = StandardScaler()

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

X_train_sc = sc.fit_transform(X_train)
X_test_sc  = sc.transform(X_test)

knn_scratch = KNNClassifier(k=5)
knn_scratch.fit(X_train_sc, y_train)
y_pred = knn_scratch.predict(X_test_sc)

acc = np.mean(y_pred == y_test)
print(f"Scratch KNN accuracy: {acc:.4f}")  # matches sklearn

Weighted KNN — Closer Neighbours Vote Louder

Standard KNN gives every neighbour an equal vote regardless of distance. A neighbour at distance 0.01 has the same influence as one at distance 50. Weighted KNN fixes this by weighting each neighbour's vote inversely proportional to its distance — closer means more influential.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Full hyperparameter search — K, weights, metric, p
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('knn',    KNeighborsClassifier(n_jobs=-1))
])

param_grid = {
    'knn__n_neighbors': [3, 5, 7, 9, 11, 15, 21],
    'knn__weights':     ['uniform', 'distance'],
    'knn__metric':      ['euclidean', 'manhattan'],
}

grid = GridSearchCV(
    pipe, param_grid,
    cv=5, scoring='accuracy',
    n_jobs=-1, verbose=0
)
grid.fit(X_train, y_train)

print("Best parameters: ", grid.best_params_)
print(f"Best CV accuracy: {grid.best_score_:.4f}")
print(f"Test accuracy:    {grid.score(X_test, y_test):.4f}")

Search Algorithms — How sklearn Finds Neighbours Fast

Full Pipeline — Breast Cancer Diagnosis

import pandas as pd
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report, ConfusionMatrixDisplay
import matplotlib.pyplot as plt

cancer = load_breast_cancer()
X, y   = cancer.data, cancer.target   # 30 features, binary label

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

# 30 features → apply PCA first to fight the curse of dimensionality
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('pca',    PCA(n_components=10, random_state=42)),
    ('knn',    KNeighborsClassifier(
        n_neighbors=9,
        weights='distance',
        metric='euclidean',
        n_jobs=-1
    ))
])

pipe.fit(X_train, y_train)
y_pred = pipe.predict(X_test)

# Cross-validation score
cv_scores = cross_val_score(
    pipe, X_train, y_train, cv=5, scoring='f1'
)
print(f"5-Fold CV F1:  {cv_scores.mean():.4f} ± {cv_scores.std():.4f}")
print(f"Test Accuracy: {pipe.score(X_test, y_test):.4f}")

print(classification_report(
    y_test, y_pred,
    target_names=cancer.target_names
))

# Confusion matrix
ConfusionMatrixDisplay.from_predictions(
    y_test, y_pred,
    display_labels=cancer.target_names
)
plt.tight_layout()
plt.show()

When to Use KNN

KNN vs Other Classifiers

Strengths vs Weaknesses

Real-World Applications

Golden Rules