Understand the illustration of the curse of dimensionality? I understand how the curse of high dimensionality works when most features are irrelevant in this highly cited article: A Few Useful Things to Know About Machine Learning, but I get stuck in reading the following illustration:

This
is because in high dimensions all
examples look alike. Suppose, for
instance, that examples are laid out
on a regular grid, and consider a test
example $x_t$. If the grid is d-dimensional, $x_t$’s 2d nearest examples are
all at the same distance from it. So as
the dimensionality increases, more
and more examples become nearest
neighbors of $x_t$, until the choice of
nearest neighbor (and therefore of
class) is effectively random

The first sentence is unintuitive. Especially, why If the grid is d-dimensional, $x_t$’s 2d nearest examples are
all at the same distance from it?
To make it concrete, there are two coordinates(A and B) in a 2d plane:

Using geogebra
Suppose that (0, 0) is the test example, and we can see that A is closer to it than B. I wonder if B would be as close to the test example as A in any higher dimensional space? If so, how? If not, how would all samples look alike?


imagine the unit cube $[0,1]^d$. All training data is sampled uniformly within this cube, i.e. $∀i,x_i∈[0,1]^d$, and we are considering the $k=10$ nearest neighbors of such a test point.



Let ℓ be the edge length of the smallest hyper-cube that contains all k-nearest neighbor of a test point. Then $ℓ^d≈\frac{k}{n}$ and $ℓ≈(\frac{k}{n})^{1/d}$. If n=1000, how big is ℓ?



So as d≫0 almost the entire space is needed to find the 10-NN.

To simulate the phenomenon, I conducted the following experiment(implement the example in the reference):
import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams.update({'figure.figsize':(7,5), 'figure.dpi':100})
import numpy as np
np.random.seed(0) 
from scipy.spatial import distance_matrix
min_val = 0
max_val = 1
n = 1000

for d in (2, 3, 10, 100, 1000, 10000):
    a = np.random.rand(n, d)
    b = np.random.rand(n, d)
    distances = distance_matrix(a, b)
    distances = np.array(distances).flatten()
    plt.hist(distances, bins=100, weights=np.ones(len(distances)) / len(distances))
    # plt.gca().set(title='Frequency Histogram', ylabel='Frequency')
    plt.show() 

And the plots align very well with those in the reference.
References:

*

*Lecture 2: k-nearest neighbors
