k-Nearest Neighbors: Convergence and Curse of Dimensionality

Module: Machine Learning | Difficulty: Advanced

1-NN Bayes Error Bound

k-NN Consistency

As , , :

Curse of Dimensionality

Volume of hypersphere:

Ratio of annulus to ball:

Distance Concentration

import numpy as np
from scipy.spatial.distance import cdist

class KNNClassifier:
    def __init__(self, k=5, metric='euclidean'):
        self.k = k; self.metric = metric
    def fit(self, X, y):
        self.X_train = X; self.y_train = y
    def predict(self, X):
        dists = cdist(X, self.X_train, self.metric)
        idx = np.argpartition(dists, self.k, axis=1)[:, :self.k]
        votes = self.y_train[idx]
        return np.array([np.bincount(v).argmax() for v in votes])

| Dimension | Nearest Dist / Farthest Dist | Accuracy | |-----------|------------------------------|----------| | 2 | 0.23 | 92% | | 10 | 0.68 | 78% | | 100 | 0.93 | 55% | | 1000 | 0.99 | 42% |

Research Insight: The curse of dimensionality makes k-NN impractical for high dimensions. Solutions include: dimensionality reduction (PCA), feature selection, and distance metric learning (LMNN, ITML).