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

Question

我在看维基百科关于KD树的页面。作为一个例子，我用Python实现了构建KD树的算法。

不过，关于用KD树进行KNN搜索的算法换了种语言，而且不是特别清楚。虽然英文的解释开始变得有点道理，但有些地方（比如他们提到的“展开递归”去检查其他叶子节点）我还是搞不懂。

这到底是怎么回事？我该如何在Python中用KD树进行KNN搜索？这不是一个想要别人给我代码的问题，我也不期待得到代码。只想要一个简单的解释，谢谢！:)

Answer 1

让我们考虑一个简单的例子，假设我们有两个维度（d=2），下面是Kd树的结果。

你的查询点是Q，你想找到k个最近邻居。

上面的树就是Kd树的表示。
我们会在树中搜索，直到找到某个区域。在Kd树中，每个区域都是由一个点来表示的。

接着，我们会计算这个点和查询点之间的距离。

然后，我们会画一个以这个距离为半径的圆，看看是否有其他点更靠近查询点。

最后，我们会查看那些落在这个圆内的轴，回溯到这些轴上，找到更近的点。

Answer 2

我刚花了一些时间研究了一下维基百科上关于这个算法的描述，写出了以下的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的那条线的距离时，我们才需要查看“远离”这一侧。如果是这样，我们就会检查在“远离”这一侧是否有更近的点。

因为我们把最佳匹配的节点传入了这个第二个测试，所以它不需要遍历整个分支，如果方向不对会很快停止（只会向下走“近”子节点，直到找到叶子节点）。

为了计算点p和通过节点n的那条线之间的距离，我们可以简单地把这个点“投影”到轴上，复制相应的坐标，因为这些轴都是正交的（水平或垂直）。

Answer 3

这本书的介绍在第3页提到：

在一个d维空间中，给定n个点，可以通过递归的方式构建一个kd树。首先，我们需要找到这些点在第i个坐标上的中位数（最开始，i = 1）。也就是说，我们计算一个值M，使得至少有50%的点在第i个坐标上大于或等于M，而至少有50%的点在第i个坐标上小于或等于M。然后把这个值M存起来，并把点的集合P分成两个部分：PL和PR。PL里只包含那些第i个坐标小于或等于M的点，而PR的数量要么和PL一样，要么比PL多1。接下来，我们对PL和PR分别重复这个过程，把i换成i + 1（如果i等于d，就换回1）。当某个节点里的点的数量只有1个时，递归就停止了。

接下来的段落讨论了kd树在解决最近邻问题中的应用。

另外，这里有Jon Bentley在1975年发表的原始论文。

补充一下，SciPy里有kd树的实现：

• scipy.spatial
• 另一个Stack Overflow的问题