这在提到维度灾难时经常被引用并且去
(右手公式称为相对对比度)
该定理的结果表明,到给定查询点的最大和最小距离之间的差异不会像到高维空间中任何点的最近距离一样快。这使得邻近查询变得毫无意义且不稳定,因为最近和最远邻居之间的区别很差。
然而,如果一个人真的尝试计算样本值的相对对比度,这意味着一个人采用一个包含非常小的值的向量并计算到零向量的距离,并对一个包含更大值的向量做同样的事情,然后一个人比较这些值3 的维度和倍大的维度,人们会看到,虽然比率确实降低了,但变化非常小,以至于与实际使用的维度数量无关(或者有人知道有人在工作吗?数据的尺寸与格雷厄姆数的大小相同——我猜这是描述论文实际相关的效果所需的大小——我认为不是)。
如前所述,这个定理经常被引用来支持这样一种说法,即在高维空间中基于欧几里得空间测量接近度是一种糟糕的策略,作者自己这么说,但所提出的行为实际上并没有发生,这让我认为这个定理被以一种误导的方式使用。
示例:带d
维度
a=np.ones((d,)) / 1e5
b=np.ones((d,)) * 1e5
dmin,dmax=norm(a), norm(b)
(dmax-dmin)/dmin
对于 d=3
9999999999.0
对于 d=1e8
9999999998.9996738
并且使用 1e1 而不是 1e5(假设数据是标准化的)
对于 d=3
99.0
对于 d=1e8
98.999999999989527