理解scipy.spatial.KDTree中的“leafsize”

Question

理解scipy.spatial.KDTree中的“leafsize”

machine-learningscipytreenearest-neighborkdtree

6

问题陈述：

我在一个三维空间中有150k个点，它们的坐标存储在一个尺寸为[150k, 3]的矩阵中，以毫米为单位。

我想找到给定点p周围半径r内的所有邻居点，并以最准确的方式进行计算。

我应该如何选择leafsize参数？

from scipy.spatial import KDTree
import numpy as np

pts = np.random.rand(150000,3)

T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)

neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)

np.allclose(sorted(neighbors1), sorted(neighbors2))
True

- seralouk

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex · Accepted Answer

函数query_ball_point将为任何版本的搜索树返回正确的点集。 leafsize参数不会影响查询结果，只会影响结果的性能。

想象一下，对于相同数据（但叶大小参数不同）的两棵树，以及搜索所有位于红色圆圈内的点的查询所示如下。

在这两种情况下，代码只会返回位于红色圆圈内的两个点。这是通过检查树中所有框中的所有点是否与圆相交来完成的。这导致每种情况下的工作量（即不同的性能）不同。对于左侧的树（对应较大的叶大小），算法必须检查13个点是否在圆内（上部相交框中有6个，在下部相交框中有7个）。在右侧的树中（具有较小的叶大小），仅处理了三个点（上部相交框中有一个，在下部相交框中有两个）。

按照这种逻辑，您可能认为始终使用较小的叶大小是有意义的：这将最小化算法末尾实际比较的数量（以确定点是否实际位于查询区域内）。但事情并非那么简单：较小的叶大小会生成更深的树，增加构建时间和树遍历时间的成本。获得树遍历性能和叶级比较的正确平衡实际上取决于输入树的数据类型和您正在执行的特定叶级比较。这就是为什么scipy提供叶大小参数作为参数，以便您可以调整它们以在特定算法上表现最佳。