Why does K-Nearest Neighbors suffer from the curse of dimensionality, mathematically?

KNN relies on the assumption that nearby points in feature space share similar labels — its entire predictive power comes from local neighborhoods being meaningful. As the number of dimensions d increases, two related mathematical phenomena destroy this assumption.

First, the volume of a hypersphere relative to its bounding hypercube shrinks rapidly as d increases — most of the volume of a high-dimensional cube concentrates near its corners, far from the center. Second, and more critically, distances between randomly distributed points become increasingly similar to each other as d grows: the ratio of the distance to the nearest neighbor versus the farthest neighbor approaches 1. This means in high dimensions, the concept of 'nearest' neighbor becomes statistically meaningless — every point is approximately equidistant from every other point.

import numpy as np

def distance_ratio_demo(n_dims_list, n_points=1000):
    for d in n_dims_list:
        points = np.random.uniform(0, 1, size=(n_points, d))
        query = np.random.uniform(0, 1, size=d)
        dists = np.linalg.norm(points - query, axis=1)
        ratio = dists.min() / dists.max()
        print(f'd={d:4d}: nearest/farthest distance ratio = {ratio:.4f}')

distance_ratio_demo([2, 10, 50, 200, 1000])
# Output shows the ratio approaching 1.0 as d grows —
# nearest and farthest neighbors become almost equidistant!

# Mitigation: dimensionality reduction before KNN
from sklearn.decomposition import PCA
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline

pipe = make_pipeline(PCA(n_components=20), KNeighborsClassifier(n_neighbors=5))
pipe.fit(X_train, y_train)

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.