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

Question

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

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

这是如何工作的，如何在 python 中使用 KD 树进行 KNN 搜索？这不是一个 “请给我发送代码!” 类型的问题，我不希望这样。请做一个简短的解释:)

Answer 1

这book introduction , 第 3 页:

Given a set of n points in a d-dimensional space, the kd-tree is constructed recursively as follows. First, one finds a median of the values of the ith coordinates of the points (initially, i = 1). That is, a value M is computed, so that at least 50% of the points have their ith coordinate greater-or-equal to M, while at least 50% of the points have their ith coordinate smaller than or equal to M. The value of x is stored, and the set P is partitioned into PL and PR , where PL contains only the points with their ith coordinate smaller than or equal to M, and |PR | = |PL |±1. The process is then repeated recursively on both PL and PR , with i replaced by i + 1 (or 1, if i = d). When the set of points at a node has size 1, the recursion stops.

以下段落讨论了它在解决最近邻问题中的用途。

或者，这里是 original 1975 paper by Jon Bentley .

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

• scipy.spatial
• another Stack Overflow question