让我们看看前几个维度。

• 对于，如果示例布置在规则网格上，这仅意味着它们在直线上的距离相等，例如，在整数处。我们可以假设我们的测试示例 位于原点。有两个距离相等的最近邻居，即和处的点。$d=1$$x_t$$x_t=0$$1$$1$$-1$

• 对于，我们有一个平面，规则网格可以由所有二维整数点组成。对于在原点的测试示例（不失一般性），有四个最近的邻居，同样都是距离：，，和。$d=2$$1$$(0,1)$$(-1,0)$$(0,-1)$$(1,0)$

• 对于，我们在三维空间中有一个规则网格。我们在原点的测试示例现在有六个最近的邻居，都在距离处。$d=3$$1$

一般来说，由于我们有维并且可以假设我们的规则网格仅由维整数点组成，我们可以在原点处进行测试示例，然后我们可以通过选择最近邻尺寸并将该坐标设置为或，并将所有其他坐标保留为。$d$$d$$2d$$d$$1$$-1$$0$

这说明的问题是，如果我们的问题中没有结构（即，我们的示例在规则网格上，没有集群，可能有一些噪声），那么选择固定数量最近邻居可能只是意味着在随机的，因为有这么多最近的邻居，可能只是因为噪声而被区分。$k$

特别是，如果网格是 d 维的，的 2d 最近的示例都在相同的距离$x_t$？谁能想象一下插图（如果可能的话）？

该示例涉及常规网格。

在常规网格中，每条网格线（在每个维度上）都有两个相邻节点，一个在 +1，一个在 -1。

对于非正则分布，2d 最近的邻居不再处于完全相同的距离，并且存在一些随机性。但是规则网格的例子表明，有很多方向可以找到最近的邻居（这使得噪声更容易超过信号）。

我认为@Stephan Kolassa 很好地解释了作者在那段中的意思。“在高维情况下，所有样本看起来都相似”的理论基础在本文的第 3.4 节“不稳定性结果”中进行了阐述。

基本上跳过第 6 页的证明

...所有点都收敛到距查询点相同的距离。因此在这些条件下，最近邻的概念不再有用。

我认为如果作者引用这篇论文而不是使用那个网格示例，演示文稿会更加清晰。更高维度的结果可能不直观，因为我们生活在一个 3D 世界中。

想象一下单位立方体。所有训练数据都在这个立方体内均匀采样，即，我们正在考虑这样一个测试点的最近邻。$[0,1]^d$$∀i,x_i∈[0,1]^d$$k=10$

设 ℓ 是包含测试点的所有 k 最近邻的最小超立方体的边长。然后和。如果 n=1000，ℓ 有多大？$ℓ^d≈\frac{k}{n}$$ℓ≈(\frac{k}{n})^{1/d}$

因此，当 d≫0 时，几乎需要整个空间来找到 10-NN。

为了模拟这种现象，我进行了以下实验（实现参考中的示例）：

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() 

并且这些图与参考中的图非常吻合。

参考：

1. 第 2 讲：k-最近邻