在kd tree的页面上引用维基百科:
kd树不适合在高维空间中有效地找到最近邻居.作为一般规则,如果维度为k,则数据中的点数N应为N >> 2k.否则,当kd树与高维数据一起使用时,树中的大多数点将被评估,并且效率不会比穷举搜索更好,[11]应该使用近似最近邻方法.
我不明白维度(k)和数据中的点数(N)之间的区别以及为什么关于何时kd树不方便的陈述是正确的.
小智 9
k是您的数据的维度,而n就是在你的数据集的点数.因此,如果您的数据集包含1000万个点,并且每个点有3个维度,k则为3并且n为1000万.
kd树不适合在高维度上找到最近邻居的原因与所谓的维度诅咒有关.kd树反复使用沿着单个维度的分割,但是当处理高维数据时,在一个维度上知道关于(欧几里德)距离的某些东西对于整个空间中的距离几乎没有说明.
想要超过2 k的数据集的原因非常直观:我们将数据集沿着每个维度分成两半大小相等的数据集.如果我们的数据点少于2 k,过了一段时间就没有更多的数据需要拆分了!例如,如果你有3个维度中的4个点,我们可以在x上拆分,给出两组两个点.我们将其拆分为y,给出四组一点.但是现在我们不能再拆分z了!