algorithm - 无意义 “Nearest Neighbor” 的数据集？

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!!!!

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