KD树最近邻居搜索如何工作? [英] How does the KD-tree nearest neighbor search work?
问题描述
我正在查看Wikipedia页面上的KD树.例如，我在python中实现了构建列出的kd树的算法.
I am looking at the Wikipedia page for KD trees. As an example, I implemented, in python, the algorithm for building a kd tree listed.
但是，使用KD树进行KNN搜索的算法会切换语言，并且尚不完全清楚.英文解释开始很有意义，但是其中的一部分(例如它们展开递归"以检查其他叶节点的区域)对我而言实际上没有任何意义.
The algorithm for doing KNN search with a KD tree, however, switches languages and isn't totally clear. The English explanation starts making sense, but parts of it (such as the area where they "unwind recursion" to check other leaf nodes) don't really make any sense to me.
这是如何工作的，如何用python中的KD树进行KNN搜索?这并不意味着要成为"send me the code!"类型的问题，而且我也不希望这样.请给我一个简短的解释:)
How does this work, and how can one do a KNN search with a KD tree in python? This isn't meant to be a "send me the code!" type question, and I don't expect that. Just a brief explanation please :)
推荐答案
此书籍简介，第3页:
给定d维空间中的一组n个点，就构造了kd树 递归如下.首先，找到第ith个值的中位数 点的坐标(最初，i = 1).即，计算出值M， 这样至少有50％的点的第i个坐标大于或等于 到M，而至少50％的点的ith坐标更小 等于或等于M.存储x的值，并对集合P进行分区 到PL和PR中，其中PL仅包含其第i个坐标的点 小于或等于M，并且| PR | = | PL |±1.然后重复该过程 在PL和PR上递归地将i替换为i + 1(如果i = d，则替换为1). 当节点上的点集的大小为1时，递归将停止.
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.
以下段落讨论了它在解决最近邻居中的用途.
The following paragraphs discuss its use in solving nearest neighbor.
或者，这是乔恩·本特利(Jon Bentley)1975年的原始论文 .
Or, here is the original 1975 paper by Jon Bentley.
我应该补充一点，SciPy具有一个kdtree实现:
I should add that SciPy has a kdtree implementation:
- scipy.spatial
- another Stack Overflow question
这篇关于KD树最近邻居搜索如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
