17

我正在查看 KD 树的 Wikipedia 页面。例如，我在 python 中实现了用于构建列出的 kd 树的算法。

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

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

4

3 回答 3

14

本书介绍，第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 实现：

于 2010-12-12T03:33:50.713 回答
9

我刚刚花了一些时间自己对算法的维基百科描述感到困惑，并提出了以下可能有帮助的 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，我们只需要查看“远离”侧。如果是，那么我们检查“远离”一侧是否有更接近的点。pbpn

因为我们的最佳匹配节点被传递到第二个测试中，所以它不必对分支进行完全遍历，如果它在错误的轨道上会很快停止（只沿着“近”子节点前进，直到它碰到叶子。）

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

于 2011-03-10T04:13:06.250 回答
0

让我们考虑一个例子，为简单起见考虑d = 2，Kd树的结果如下所示

在此处输入图像描述

您的查询点是 Q 并且您想找出 k 近邻 在此处输入图像描述

上面的树是 kd-tree 的表示，
我们将搜索整个树以落入其中一个区域。在 kd-tree 中，每个区域都由一个点表示。

然后我们将找出该点与查询点之间的距离

然后我们会以这个距离为半径画一个圆来确定是否有离查询点更近的点。

然后是落在那个圆圈区域的轴，我们回溯到那个轴并找到近点

于 2018-07-28T02:16:25.600 回答