无意义的“最近邻”数据集？

Question

在论文“When Is 'Nearest Neighbor' Meaningful?”中我们读到，“我们表明，在某些广泛的条件下（在数据和查询分布或工作负载方面），随着维度的增加，到最近的距离 neighbor 接近最远邻居的距离。换句话说，到不同数据点的距离对比变得不存在。条件我们已经确定发生这种情况的范围比其他工作的独立同分布 (IID) 维度假设要广泛得多假定。

我的问题是我应该如何生成类似于此效果的数据集？我创建了三个点，每个点有 1000 个维度，每个维度的随机数在 0-255 之间，但是点创建不同的距离并且不会重现上面提到的内容。似乎改变维度（例如 10 或 100 或 1000 维度）和范围（例如 [0,1]）不会改变任何东西。我仍然有不同的距离，这应该不是任何问题，例如。聚类算法！

Answer 1

我之前也没有听说过这个，所以我有点防御，因为我 have seen that real and synthetic datasets in high dimensions 真的不支持相关论文的说法。

因此，作为第一个肮脏、笨拙且可能不太好的尝试，我的建议是在您选择的维度 (I do it like like this) 中生成一个球体，然后放置一个在球体中心查询。

在这种情况下，每个点与查询点的距离相同，因此最近邻点的距离等于最远邻点的距离。

当然，这与维度无关，但这是看了论文中的数字后想到的。它应该足以让你目瞪口呆，但可以肯定的是，如果有的话，可能会生成更好的数据集。

编辑关于：

distances for each point got bigger with more dimensions!!!!

这是预料之中的，因为维度越高space，space越稀疏，因此距离越大。此外，这是预料之中的，例如，如果您考虑欧几里德距离，它会随着维度的增长而变大。

Answer 2

我认为论文是对的。首先，您的测试：测试的一个问题可能是您使用的点数太少。我使用了 10000 点，下面是我的结果（在所有维度上 [0.0 ... 1.0] 中均匀分布的点）。对于 DIM=2，min/max 几乎相差 1000 倍，对于 DIM=1000，它们仅相差 1.6 倍，对于 DIM=10000 相差 1.248 。所以我想说这些结果证实了论文的假设。

DIM/N = 2 / 10000
min/avg/max= 1.0150906548224441E-5 / 0.019347838262624064 / 0.9993862941797146    
DIM/N = 10 / 10000.0
min/avg/max= 0.011363500131326938 / 0.9806472676701363 / 1.628460468042207
DIM/N = 100 / 10000
min/avg/max= 0.7701271349716637 / 1.3380320375218808 / 2.1878136533925328
DIM/N = 1000 / 10000
min/avg/max= 2.581913326565635 / 3.2871335447262178 / 4.177669393187736
DIM/N = 10000 / 10000
min/avg/max= 8.704666143050158 / 9.70540814778645 / 10.85760200249862

DIM/N = 100000 / 1000 (N=1000!)
min/avg/max= 30.448610133282717 / 31.14936583713578 / 31.99082677476165

我猜解释如下：让我们取三个随机生成的向量，A、B 和 C。总距离基于这些向量的每一行的距离之和。向量的维度越多，差异的总和就越接近一个共同的平均值。换句话说，向量 C 在所有元素中到 A 的距离都不太可能大于另一个向量 B 到 A 的距离。随着维度的增加，C 和 B 到 A（以及彼此）的距离将越来越相似。

我的测试数据集创建如下。数据集本质上是一个立方体，每个维度都在 0.0 到 1.0 之间。创建的坐标在 0.0 和 1.0 之间的每个维度上均匀分布。示例代码（N=10000，DIM=[2..10000]）：

public double[] generate(int N, int DIM) {
    double[] data = new double[N*DIM];
    for (int i = 0; i < N; i++) {
        int pos = DIM*i;
        for (int d = 0; d < DIM; d++) {
            data[pos+d] = R.nextDouble();
        }
    }
    return data;
}

根据已接受答案 here 底部给出的等式，我们得到：

d=2 -> 98460

d=10 -> 142.3

d=100 -> 1.84

d=1,000 -> 0.618

d=10,000 -> 0.247

d=100,000 -> 0.0506（使用 N=1000）

无意义的“最近邻”数据集？

Dataset for meaningless “Nearest Neighbor”?

algorithm

math

dataset

nearest-neighbor

dimensional-modeling