为什么k-d树不适用于高维数据？

Question

引用维基百科关于k-d树页面的内容：

k-d树不适合在高维空间中高效地查找最近邻居。作为一般规则，如果维度为k，则数据中的点数N应大于2k。否则，当使用k-d树处理高维数据时，树中的大多数点将被评估，效率不比穷举搜索[11]更好，应改用近似最近邻居方法。

我不明白维度（k）和数据中的点数（N）之间的区别，以及为什么这个关于k-d树的声明是正确的。

- justHelloWorld

---

k是数据点的维数（向量分量）的数量。当k很大时，k-D树效率低下，因为切分不能有效地减少最小距离，搜索会退化为穷举。 - user1196549

64和4之间有什么关系？ - user1196549

抱歉，只是一个打字错误：k=64，但N是多少？ - justHelloWorld

向量的数量，还有什么？ - user1196549

为了有意义：当然不是。 - user1196549

Answer 1

k表示数据的维度，n表示数据集中的点数。因此，如果您的数据集包含1000万个点，每个点具有3个维度，则k为3，n为1000万。

k-d树不适用于在高维空间查找最近邻居，这与所谓的“维度灾难”有关。维度灾难。k-d树重复使用单个维度上的划分，但是在处理高维数据时，了解一个维度（欧几里得距离）的距离对整个空间的距离关系并没有多大作用。

想要一个包含超过2^k个数据集的原因很容易理解：我们沿着每个维度将数据集分成两个相等大小的半集。如果数据点少于2^k个，过一段时间后就没有更多数据可供分割！例如，如果您有3个维度中的4个点，我们可以在x轴上进行分割，得到两组两个点。我们再在y轴上分割，得到四个只有一个点的集合。但是现在我们不能再在z轴上进行分割了！

- Jordi Vermeulen

---

了解一维[欧几里得]距离并不能说明完整空间中的距离，它只提供了一个下限。因此，在不是所有维度上的接近并不意味着在完整空间中也是接近的，但是即使在一个维度上很远也会排除这种可能性。 - greybeard

kd-tree的工作速度慢还是准确率低？或者两者都有？构建高维数据的kd-tree需要O(nk)的时间。同时准确性可能会受到影响。 - canbax