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

Question

在 k-d 树的页面上引用维基百科:

k-d trees are not suitable for efficiently finding the nearest neighbour in high-dimensional spaces. As a general rule, if the dimensionality is k, the number of points in the data, N, should be N>> 2k. Otherwise, when k-d trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search,[11] and approximate nearest-neighbour methods should be used instead.

我不明白维度 (k) 和数据中的点数 (N) 之间的区别，以及为什么关于 k-d 树何时不方便的说法是正确的。

Answer 1

k 是数据的维数，而n 是数据集中的点数 .因此，如果您的数据集包含 1000 万个点，并且每个点有 3 个维度，则 k 为 3，n 为 1000 万。

k-d 树不适合在高维度上寻找最近​​邻的原因与所谓的curse of dimensionality有关。 . k-d 树重复使用沿单个维度的拆分，但在处理高维数据时，了解一维中的(欧几里得)距离对整个空间中的距离知之甚少。

想要超过 2^k 的数据集的原因非常直观:我们将数据集沿每个维度分成大小相等的两半。如果我们的数据点少于 2^k，过一会儿就没有更多的数据可以拆分了!例如，如果您在 3 个维度上有 4 个点，我们可以在 x 上拆分，给出两组两点。我们将其拆分为 y，给出四组一个点。但是现在我们不能再在 z 上 split 了!