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

Question

我正在查看KD树的维基百科页面.作为一个例子,我在python中实现了用于构建列出的kd树的算法.

然而,使用KD树进行KNN搜索的算法切换语言并不完全清楚.英语解释开始有意义,但它的一部分(例如它们"展开递归"以检查其他叶节点的区域)对我来说并没有任何意义.

这是如何工作的,如何在python中使用KD树进行KNN搜索？这不是一个"send me the code!"类型问题,我不期望这样.请简单解释一下:)

Answer 1

这本书介绍,第3页:

给定d维空间中的一组n个点,如下递归地构造kd树.首先,找到点的第i个坐标值的中值(最初,i = 1).也就是说,计算值M,使得至少50%的点的第i个坐标大于或等于M,而至少50%的点的第i个坐标小于或等于M.存储x的值,并将集合P划分为PL和PR,其中PL仅包含第i个坐标小于或等于M的点,并且| PR | = | PL |±1.然后在PL和PR上递归地重复该过程,其中i由i + 1(或1,如果i = d)代替.当节点上的点集具有大小1时,递归停止.

以下段落讨论了它在解决最近邻居中的用法.

或者,这是Jon Bentley最初的1975年论文.

编辑:我应该补充一点,SciPy有一个kdtree实现:

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

Answer 2

我自己花了一些时间来解释维基百科对算法的描述,并提出了以下可能有用的Python实现:https://gist.github.com/863301

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

第二阶段不是简单地返回找到备份调用堆栈的最佳节点,而是检查"离开"端是否有更近的节点:( ASCII art diagram)

            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,我们可以通过复制适当的坐标简单地将点"投影"到轴上,因为轴都是正交的(水平或垂直).