🔍 KNN Core Philosophy

🎯 Lazy Learning & Instance-Based

K-Nearest Neighbors (KNN) is a non-parametric, lazy learning algorithm. It stores all training instances and makes predictions based on the k closest neighbors. No explicit training phase — all computation happens during inference.

Why "Lazy"?

No model is built during training — KNN simply memorizes the dataset. Prediction involves computing distances between the query point and all training points, then aggregating the labels of the k nearest neighbors. This makes it highly interpretable but computationally expensive at scale.

📌 Lazy Learning📌 Non-Parametric📌 Distance-Based📌 Interpretable

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=100, n_features=4, random_state=42)
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X, y)  # nothing really happens here
print(f"Predictions: {knn.predict(X[:3])}")
print(f"Neighbors indices: {knn.kneighbors(X[:1], return_distance=False)}")

📏 Distance Metrics

🎯 Measuring Proximity

Euclidean (L2), Manhattan (L1), Minkowski, Chebyshev, Mahalanobis.

Choosing the Right Metric

Euclidean works well for continuous features. Manhattan is robust to outliers. Minkowski generalizes both with p parameter. Mahalanobis accounts for feature correlations.

📐 L2 Norm📏 L1 Norm🔄 Minkowski

from sklearn.neighbors import DistanceMetric
dist = DistanceMetric.get_metric('euclidean')
X_sample = [[0, 0], [3, 4]]
print(f"Euclidean: {dist.pairwise(X_sample)}")
# Minkowski p=3
dist_p3 = DistanceMetric.get_metric('minkowski', p=3)
print(f"Minkowski p=3: {dist_p3.pairwise(X_sample)}")

🎯 Choosing the Optimal K

🎯 Bias-Variance Tradeoff

Small K → high variance, overfitting. Large K → high bias, underfitting.

Hyperparameter Tuning

Use cross-validation to select K. Typically, K = √N is a good starting point. Odd K avoids ties in binary classification.

📊 Cross-Validation⚖️ Bias-Variance

from sklearn.model_selection import cross_val_score
import numpy as np
k_range = range(1, 31)
cv_scores = []
for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5)
    cv_scores.append(scores.mean())
best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k}")

⚖️ Weighted Voting & Distance Weighting

🎯 Closer Neighbors = More Influence

Weight votes by inverse distance or uniform.

Distance-Weighted KNN

Closer neighbors contribute more to the decision. Reduces impact of distant outliers.

📉 Inverse Distance⚖️ Uniform vs Weighted

knn_weighted = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_weighted.fit(X, y)
print(f"Weighted predictions: {knn_weighted.predict(X[:3])}")

🌀 Curse of Dimensionality

🎯 Distance Becomes Meaningless in High D

As dimensions increase, all points become equidistant.

Mitigation Strategies

Feature selection, PCA, or use distance metrics that handle high dimensions (e.g., cosine).

📉 Dimensionality Reduction🔍 Feature Selection

# Demonstrate curse: increasing dimensions -> distances converge
import numpy as np
for d in [2, 10, 100]:
    points = np.random.rand(1000, d)
    dists = np.linalg.norm(points - points.mean(axis=0), axis=1)
    print(f"Dim {d}: mean distance {dists.mean():.3f}, std {dists.std():.3f}")

📐 Feature Scaling & Normalization

🎯 Scale Matters for Distance

StandardScaler, MinMaxScaler, RobustScaler.

Why Scaling is Critical

Features with larger ranges dominate distance calculations. Always scale before KNN.

📊 Standardization📏 Normalization

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
knn_scaled = KNeighborsClassifier().fit(X_scaled, y)
print(f"Scaled accuracy: {knn_scaled.score(X_scaled, y):.3f}")

⚙️ Brute-Force vs KD-Tree vs Ball-Tree

🎯 Efficient Nearest Neighbor Search

Brute-force O(N), KD-Tree O(log N) for low D, Ball-Tree for high D.

Algorithm Selection

KD-Tree works well for D < 20. Ball-Tree handles higher dimensions. Auto selects based on data.

🌲 KD-Tree⚽ Ball-Tree

knn_auto = KNeighborsClassifier(algorithm='auto')
knn_ball = KNeighborsClassifier(algorithm='ball_tree')
knn_kd = KNeighborsClassifier(algorithm='kd_tree')

🏷️ Classification with KNN

🎯 Majority Vote

Assign class based on majority vote of k neighbors.

Decision Boundaries

KNN creates non-linear, complex decision boundaries that adapt to local data structure.

🗳️ Majority Vote📊 Decision Boundary

from sklearn.datasets import load_iris
iris = load_iris()
knn_clf = KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(iris.data, iris.target)
print(f"Accuracy: {knn_clf.score(iris.data, iris.target):.3f}")

📈 Regression with KNN

🎯 Average of Neighbors

Predict continuous value as average (or weighted average) of target values of k neighbors.

KNN Regressor

Works well for low-dimensional, smooth functions. Not extrapolative.

📊 Average📈 Weighted Average

from sklearn.neighbors import KNeighborsRegressor
from sklearn.datasets import make_regression
X_reg, y_reg = make_regression(n_samples=100, n_features=1, noise=0.1)
knn_reg = KNeighborsRegressor(n_neighbors=3)
knn_reg.fit(X_reg, y_reg)
print(f"R²: {knn_reg.score(X_reg, y_reg):.3f}")

🛡️ Outliers & Noise Robustness

🎯 Sensitivity to Noise

Outliers can distort predictions, especially with small K.

Mitigation

Use larger K, distance weighting, or robust preprocessing.

🛡️ Larger K⚖️ Weighted Voting

# Adding outliers
X_out = np.vstack([X, [[100, 100, 100, 100]]])
y_out = np.hstack([y, [1]])
knn_out = KNeighborsClassifier(n_neighbors=5).fit(X_out, y_out)
# Outlier might affect local neighborhoods

🧩 Missing Value Imputation

🎯 KNN Imputer

Fill missing values using average of k nearest neighbors.

Multivariate Imputation

KNN imputer leverages correlations between features to estimate missing values.

🔍 KNN Imputer📊 Multivariate

from sklearn.impute import KNNImputer
imputer = KNNImputer(n_neighbors=3)
X_missing = X.copy()
X_missing[0, 0] = np.nan
X_imputed = imputer.fit_transform(X_missing)
print(f"Imputed value: {X_imputed[0, 0]:.3f}")

📉 Dimensionality Reduction & KNN

🎯 PCA, t-SNE, UMAP

Reduce dimensions before KNN to mitigate curse of dimensionality.

When to Reduce

For high-dimensional datasets (D > 20), PCA or autoencoders can improve KNN performance.

📉 PCA🌀 t-SNE

from sklearn.decomposition import PCA
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)
knn_pca = KNeighborsClassifier().fit(X_pca, y)
print(f"Accuracy after PCA: {knn_pca.score(X_pca, y):.3f}")

⚙️ sklearn KNN API & Pipelines

🎯 KNeighborsClassifier, KNeighborsRegressor

Unified API, GridSearchCV, Pipelines.

Production Setup

Combine scaling and KNN in a Pipeline with hyperparameter tuning.

🔧 Pipeline🔎 GridSearch

from sklearn.pipeline import Pipeline
pipe = Pipeline([('scaler', StandardScaler()), ('knn', KNeighborsClassifier())])
params = {'knn__n_neighbors': [3,5,7,9]}
grid = GridSearchCV(pipe, params, cv=5)
grid.fit(X, y)
print(f"Best K: {grid.best_params_}")

🚀 Deployment & Performance

🎯 Scalability & Serving

KNN is memory-heavy and slow for large datasets. Use approximate methods (ANN).

Production Strategies

Use Faiss, Annoy, or HNSW for approximate nearest neighbors. Store model as pickle.

📦 Pickle⚡ ANN

import joblib
joblib.dump(knn, 'knn_model.joblib')
loaded_knn = joblib.load('knn_model.joblib')
print(loaded_knn.predict(X[:1]))