scipy - 了解 scipy.spatial.KDTree 中的 `leafsize`

Question

问题陈述:
我在 3D 空间中有 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

Answer 1

函数query_ball_point将为任何版本的搜索树返回正确的点集。 leafsize参数不影响查询的结果，只影响结果的性能。
想象一下下面显示的两棵树的相同数据(但不同的叶子尺寸参数)和搜索红色圆圈内所有点的查询。

在这两种情况下，代码只会返回位于红色圆圈内的两个点。这是通过检查与圆相交的树的所有框中的所有点来完成的。在每种情况下，这会导致不同的工作量(即不同的性能)。对于左树(对应于更大的叶子尺寸)，算法必须检查圆内是否有 13 个点(6 个在上相交框中，7 个在下相交框中)。在右边的树(叶子尺寸较小)中，只有三个点得到处理(一个在上相交框中，两个在下相交框中)。
按照这个逻辑，您可能认为总是使用小叶尺寸是有意义的:这将最大限度地减少算法结束时的实际比较次数(确定点是否实际位于查询区域中)。但这并不是那么简单:较小的叶子尺寸将生成更深的树，从而增加了构建时间和树遍历时间的成本。通过叶级比较获得树遍历性能的正确平衡实际上取决于进入树的数据类型以及您正在执行的特定叶级比较。这就是 scipy 提供 Leafsize 参数作为参数的原因，以便您可以调整事物以在特定算法上表现最佳。