👥 k-Nearest Neighbors (kNN)

Part 1: What is k-Nearest Neighbors?

k-Nearest Neighbors (kNN) is a classification (and sometimes regression) algorithm. To predict the class of a new point, it looks at the K closest training points and lets them vote. Majority wins!

👶 In One Sentence (Like You're 5)

kNN means: "When someone new moves into the neighborhood, we don't ask them who they are—we look at their K closest neighbors. If 4 out of 5 neighbors have a dog, we guess they probably have a dog too."

Where kNN Is Used

Part 2: How kNN Works (Step by Step)

kNN is lazy: it doesn't "train" in the usual sense. At prediction time it does all the work.

Part 3: Distance Metrics

"Nearest" means we need a way to measure distance between two points. The choice of distance changes who the "neighbors" are.

Euclidean Distance (Default)

Straight-line distance. For two points \((x_1, y_1)\) and \((x_2, y_2)\) in 2D:

distance = √[(x₂ − x₁)² + (y₂ − y₁)²]

With more features, you add more squared differences under the square root. This is the default in sklearn and works well when features are on similar scales.

Manhattan Distance

Sum of absolute differences along each axis—like walking on a grid (city blocks):

distance = |x₂ − x₁| + |y₂ − y₁| + …

Useful when movement is along axes (e.g. streets) or when outliers should matter less than in Euclidean.

Hamming Distance

Hamming distance counts how many positions are different between two vectors of the same length. Each position is compared: if they match, add 0; if they differ, add 1. It's the number of "flips" needed to turn one into the other.

distance = (number of positions where value₁ ≠ value₂)

Often we use the normalized Hamming distance: (number of differing positions) / (total number of positions), so the result is between 0 (identical) and 1 (all different).

Part 4: Choosing K

K is the only main hyperparameter: how many neighbors get to vote?

Part 5: Weighted kNN

So far we assumed every one of the K neighbors gets one vote. In weighted kNN, closer neighbors get more influence than farther ones. A neighbor right next to the new point should matter more than one that barely made it into the "top K."

👶 In One Sentence

Weighted kNN means: "Not all neighbors are equal. The closer a neighbor is, the more we trust their vote." We assign a weight to each neighbor (usually based on distance) and use those weights when voting or averaging.

How the Weights Work

The most common choice is inverse distance: weight = 1 / distance. So:

• Neighbor at distance 1 → weight = 1
• Neighbor at distance 2 → weight = 0.5
• Neighbor at distance 4 → weight = 0.25

Closer neighbors get a larger weight and therefore more say in the vote. For classification we sum the weights per class (instead of counting votes) and pick the class with the highest total weight. For regression we take the weighted average of the neighbors' target values.

# Weighted kNN: closer neighbors count more
knn_weighted = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_weighted.fit(X_train_scaled, y_train)
y_pred = knn_weighted.predict(X_test_scaled)

Part 6: Anomaly Detection with kNN

Anomaly detection means finding points that don't "belong"—they're unusual compared to the rest. Fraudulent transactions, faulty sensors, rare diseases, or defective products are examples. kNN is a natural fit: points that are far from their neighbors are potential anomalies.

👶 In One Sentence

kNN for anomaly detection means: "If a point has no close neighbors, it's suspicious. Normal points sit near others; anomalies sit alone." We use the distance to the Kth nearest neighbor (or the average distance to K neighbors) as an anomaly score: the larger the distance, the more likely the point is an anomaly.

How It Works

1. For each point, find its K nearest neighbors and get their distances.
2. Use the distance to the Kth neighbor (or the mean distance to all K neighbors) as that point's anomaly score.
3. Points with a high score are far from others → flag them as anomalies. You can set a threshold (e.g. "score > 10") or use a percentile (e.g. top 5% of scores are anomalies).

from sklearn.neighbors import NearestNeighbors
from sklearn.preprocessing import StandardScaler
import numpy as np

# Scale the data
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Fit KNN: we only need distances, not labels
K = 5
nn = NearestNeighbors(n_neighbors=K)
nn.fit(X_scaled)

# Distance to Kth neighbor for each point (anomaly score)
distances, indices = nn.kneighbors(X_scaled)
# distances[:, -1] = distance to the Kth (last) neighbor
anomaly_score = distances[:, -1]

# Flag top 5% as anomalies (e.g. threshold = 95th percentile)
threshold = np.percentile(anomaly_score, 95)
is_anomaly = anomaly_score > threshold
print(f"Number of anomalies: {is_anomaly.sum()}")

Alternative: scikit-learn's LocalOutlierFactor (LOF) is a kNN-based anomaly detector that compares each point's local density to its neighbors'. Use from sklearn.neighbors import LocalOutlierFactor and fit_predict(X) for a -1 (anomaly) / 1 (normal) label per point.

Part 7: Why Scaling Matters

kNN uses distance. If one feature is in thousands (e.g. income) and another is 0–10 (e.g. satisfaction score), the big numbers will dominate and the small feature will barely matter.

Part 8: kNN in Python

Using scikit-learn: load data, split, scale, fit, predict, and (optionally) find the best K.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler

# 1. Split data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 2. Scale (important for kNN!)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# 3. Create and fit kNN with K=5
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 4. Predict and score
y_pred = knn.predict(X_test_scaled)
print("Accuracy:", knn.score(X_test_scaled, y_test))

Finding the Best K with Cross-Validation

from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt

scores = []
k_range = range(1, 25)

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    cv_scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)
    scores.append(cv_scores.mean())

# Plot: often best K is in the middle
plt.plot(k_range, scores)
plt.xlabel('K')
plt.ylabel('CV Accuracy')
plt.title('Finding Optimal K')
plt.show()

Weighted kNN: Use weights='distance' so closer neighbors count more (see Part 5: Weighted kNN). Default is weights='uniform' (one vote per neighbor).

Using Hamming Distance (Binary / Categorical Data)

When your features are binary (0/1) or one-hot encoded, use metric='hamming' so "nearest" means "fewest disagreeing positions":

# For binary or one-hot encoded features
knn_hamming = KNeighborsClassifier(n_neighbors=5, metric='hamming')
knn_hamming.fit(X_binary_train, y_train)
y_pred = knn_hamming.predict(X_binary_test)

Part 9: When to Use kNN — Pros & Cons

Part 10: Summary

• kNN = for a new point, find the K nearest training points and let them vote; majority class (or average for regression) wins.
• No real "training"—just store the data; all work happens at prediction time.
• Use a distance metric (Euclidean, Manhattan, or Hamming for binary/categorical data).
• Weighted kNN: use weights='distance' so closer neighbors have more influence (inverse distance); default is uniform (one vote each).
• Anomaly detection: points far from their K nearest neighbors get a high anomaly score; use NearestNeighbors and the distance to the Kth neighbor (or LocalOutlierFactor) to flag outliers.
• Always scale features so no single feature dominates distance.
• Choose K with cross-validation; avoid K=1 (noisy) and very large K (too smooth).
• Good for small–medium data and as a baseline; watch out for speed and curse of dimensionality on large or high-dimensional data.

Next, learn about Support Vector Machines (SVM) - the maximum margin classifier with the kernel trick! Or jump to Decision Trees & Random Forests.