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.空间
• 另一个堆栈溢出问题

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

。如果是，那么我们检查“客队”一侧是否有更接近的点。

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

要计算点

p

与通过节点

n

分割空间的线之间的距离，我们可以简单地将点向下“投影”到轴上，方法是复制适当的坐标，因为轴都是正交的（水平或垂直）垂直）。

Answer 3

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

你的查询点是Q，你想找出k个近邻

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

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

然后我们以该距离为半径画一个圆，以确保是否有任何点距离查询点更近。

然后落在该圆区域内的轴，我们回溯到这些轴并找到附近点

Answer 4

1. 第一次遍历的结束点约为 0.1、0.52，搜索点为 0.38、0.6（所有数字均为估计值）。 所以误差约为 0.29。

2. 然后我们必须回溯到前一个节点，看看该超平面是否比误差更近。
   距离是 0.04，所以我们也必须检查它，我们找到点 0.42、0.641，距离只有 0.08。

3. 我们现在到达超平面距离 0.15 的根，因此那一侧没有任何东西可以更接近。

如果您想知道最好和最坏的情况使用 KD 树（即平衡二叉树）进行 1-NN（最近邻）搜索的时间复杂度在什么范围内？.