K-Nearest Neighbors

KNN operates in two conceptual phases: storage and lookup. During storage, you simply keep the entire training dataset in memory. During lookup (prediction), you measure the distance from the query point to every stored point, find the K closest, and aggregate their labels.

Distance Metric

The most common distance metric is Euclidean distance:

Explanation: The straight-line distance between two points A and B across all n features — the familiar ruler distance extended into many dimensions.

Symbols:

• $d(A, B)$: distance between points A and B
• $A_i$, $B_i$: the value of the i-th feature for points A and B respectively
• $n$: total number of features (dimensions)
• $\sum$: sum over all features

Another common choice is Manhattan distance, which adds absolute differences instead of squaring them:

Explanation: The "city block" distance — how far you'd travel if you could only move along grid lines, never diagonally.

Classification Decision

Once K neighbors are found, the predicted class is determined by majority vote:

Explanation: Pick whichever class label c appears most often among the K neighbors — literally count the votes and choose the winner.

Symbols:

• $\hat{y}$: the predicted class label
• $\arg\max_c$: the class c that maximizes the expression
• $\mathbb{1}(y_i = c)$: an indicator that equals 1 if neighbor i has class c, else 0
• K: the number of neighbors to consider

Python Implementation

Here's KNN from scratch, and then using scikit-learn: ```python import numpy as np from collections import Counter from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics import accuracy_score

# ── KNN from scratch ───────────────────────────────────────── class SimpleKNN: def __init__(self, k=3): self.k = k def fit(self, X, y):

# "Training" is just storing the data — that's it! self.X_train = X self.y_train = y def predict(self, X): return np.array([self._predict_one(x) for x in X]) def _predict_one(self, x):

# Step 1: compute distances to ALL training points distances = np.sqrt(np.sum((self.X_train - x) ** 2, axis=1))

# Step 2: find the K nearest indices k_indices = np.argsort(distances)[: self.k]

# Step 3: majority vote k_labels = self.y_train[k_indices] most_common = Counter(k_labels).most_common(1) return most_common[0][0]

# ── Load and split data ─────────────────────────────────────── 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 )

# ── IMPORTANT: scale features before KNN ───────────────────── scaler = StandardScaler() X_train_scaled = scaler.fit_transform(X_train) X_test_scaled = scaler.transform(X_test)

# ── From-scratch model ──────────────────────────────────────── knn_scratch = SimpleKNN(k=3) knn_scratch.fit(X_train_scaled, y_train) scratch_preds = knn_scratch.predict(X_test_scaled) print(f"Scratch accuracy: {accuracy_score(y_test, scratch_preds):.3f}")

# ── Scikit-learn model ──────────────────────────────────────── knn_sklearn = KNeighborsClassifier(n_neighbors=3, metric="euclidean") knn_sklearn.fit(X_train_scaled, y_train) sklearn_preds = knn_sklearn.predict(X_test_scaled) print(f"Sklearn accuracy: {accuracy_score(y_test, sklearn_preds):.3f}")

# ── Tune K with cross-validation ───────────────────────────── from sklearn.model_selection import cross_val_score for k in [1, 3, 5, 7, 11, 15]: scores = cross_val_score( KNeighborsClassifier(n_neighbors=k), X_train_scaled, y_train, cv=5 ) print(f"K={k:2d} CV accuracy: {scores.mean():.3f} ± {scores.std():.3f}") ``` ``` Scratch accuracy: 1.000 Sklearn accuracy: 1.000 K= 1 CV accuracy: 0.942 ± 0.026 K= 3 CV accuracy: 0.958 ± 0.033 K= 5 CV accuracy: 0.958 ± 0.033 K= 7 CV accuracy: 0.967 ± 0.021 K=11 CV accuracy: 0.950 ± 0.038 K=15 CV accuracy: 0.942 ± 0.026 ``` Notice that K=7 wins on this dataset — neither the smallest nor the largest K.

Feature Scaling Is Mandatory

KNN uses raw distances, so a feature measured in kilometres will dominate a feature measured in metres even if the metres feature is more informative. Always scale: ```python

# Without scaling — feature with large range dominates distance

# With StandardScaler — each feature has mean=0, std=1

# With MinMaxScaler — each feature is in [0, 1] from sklearn.preprocessing import MinMaxScaler

# Demonstrate the danger of not scaling X_bad = np.column_stack([ np.random.randn(100) 1000, # feature 1: huge range np.random.randn(100) 0.01, # feature 2: tiny range ])

# Distance will be almost entirely determined by feature 1!

# Feature 2 is effectively invisible to KNN. print("Always scale your features before using KNN.") ```

Decision Trees · Naive Bayes · Logistic Regression · Principal Component Analysis · DBSCAN Clustering