KD树最近邻搜索如何工作？

Question

我正在查看KD树木的维基百科页面。作为一个例子，我在python中实现了构建kd树的算法。

但是，使用KD树进行KNN搜索的算法会切换语言，但并不完全清楚。英文解释开始有意义，但其中的部分内容（例如，“解开递归”来检查其他叶节点的区域）对我来说并没有任何意义。

这是如何工作，以及如何使用python中的KD树进行KNN搜索？这不意味着是一个"send me the code!"类型的问题，我不期望。只是简单的解释，请:)

Answer 1

这book introduction，第3页：

鉴于d维空间中一组的n个点，KD树构造 递归如下。首先，找到点的坐标值（最初，i = 1）的中值。也就是说，计算M值，使得至少50％的点的第i个坐标大于或等于 到M，而至少50％的点的第i个坐标小于或等于 M.存储x的值，并且集合P被分割成PL和PR，其中PL仅包含其第i个坐标 小于或等于M的点，并且| PR | = | PL |±1。这个过程然后在PL和PR上递归地重复 ，我用i + 1（或1，如果i = d）替换。 当节点上的一组点的大小为1时，递归停止。

以下段落讨论了它在求解最近邻中的用法。或者，这里是original 1975 paper by Jon Bentley。

编辑：我要补充一点，SciPy的有kdtree实现：

• scipy.spatial
• another Stack Overflow question

Answer 2

我刚刚花了一些时间令人费解了算法的Wikipedia描述自己，并提出了以下可能有所帮助的Python实现：https://gist.github.com/863301

closest_point的第一阶段是一个简单的深度优先搜索，以找到最匹配的叶节点。

而不是简单地返回发现备份调用堆栈的最佳节点，第二阶段检查，看是否有可能是“离开”侧上的更接近节点：（ASCII艺术图）

  n  current node 
b   |  best match so far 
|  p |  point we're looking for 
|< >| |  error 
     |< >|  distance to "away" side 
     |< | >| error "sphere" extends to "away" side 
      | x possible better match on the "away" side 

当前节点n沿着一条线分割空间，所以如果点p与最佳匹配b之间的“误差”大于从点p和线n之间的距离，我们只需要看“离开”侧。如果是，那么我们检查一下，看看“离开”方面是否有任何点更接近。

因为我们最好的匹配节点被传递到了第二个测试中，所以它不必完全遍历分支，并且如果它位于错误的轨道上，它会很快停下来（只能沿着“near”子节点直到它碰到一片叶子。）

要计算点p和通过节点n分割空间的线之间的距离，我们可以简单地将点“投影”到轴上，方法是将相应坐标复制为轴都是正交的（水平或垂直）。