了解 scipy.spatial.KDTree 中的 `leafsize`
Understanding `leafsize` in scipy.spatial.KDTree
问题陈述：
我在 3D space 中有 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
函数 query_ball_point 将为任何版本的搜索树 return 正确的点集。 leafsize 参数不影响查询结果，只影响结果的性能。
想象一下下面显示的两棵树，用于相同的数据（但不同的 leafsize 参数）和搜索红色圆圈内所有点的查询。
在这两种情况下，代码只会 return 红圈内的两个点。这是通过检查与圆相交的树的所有框中的所有点来完成的。在每种情况下，这会导致不同的工作量（即不同的性能）。对于左边的树（对应于更大的叶子尺寸），算法必须检查圆内是否有 13 个点（6 个在上部相交框中，7 个在下部相交框中）。在右边的树中（叶子尺寸较小），只处理了三个点（一个在上面的相交框中，两个在下面的相交框中）。
按照这个逻辑，您可能认为始终使用较小的叶子尺寸是有意义的：这将最大限度地减少算法结束时实际比较的次数（确定这些点是否确实位于查询区域中） ).但这并不是那么简单：较小的叶子尺寸会生成更深的树，从而增加构建时间和树遍历时间的成本。在树遍历性能与叶级比较之间取得正确的平衡实际上取决于进入树的数据类型以及您正在进行的特定叶级比较。这就是为什么 scipy 提供 leafsize 参数作为参数，以便您可以调整事物以在特定算法上表现最佳。
问题陈述：
我在 3D space 中有 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
函数 query_ball_point 将为任何版本的搜索树 return 正确的点集。 leafsize 参数不影响查询结果，只影响结果的性能。
想象一下下面显示的两棵树，用于相同的数据（但不同的 leafsize 参数）和搜索红色圆圈内所有点的查询。
在这两种情况下，代码只会 return 红圈内的两个点。这是通过检查与圆相交的树的所有框中的所有点来完成的。在每种情况下，这会导致不同的工作量（即不同的性能）。对于左边的树（对应于更大的叶子尺寸），算法必须检查圆内是否有 13 个点（6 个在上部相交框中，7 个在下部相交框中）。在右边的树中（叶子尺寸较小），只处理了三个点（一个在上面的相交框中，两个在下面的相交框中）。
按照这个逻辑，您可能认为始终使用较小的叶子尺寸是有意义的：这将最大限度地减少算法结束时实际比较的次数（确定这些点是否确实位于查询区域中） ).但这并不是那么简单：较小的叶子尺寸会生成更深的树，从而增加构建时间和树遍历时间的成本。在树遍历性能与叶级比较之间取得正确的平衡实际上取决于进入树的数据类型以及您正在进行的特定叶级比较。这就是为什么 scipy 提供 leafsize 参数作为参数，以便您可以调整事物以在特定算法上表现最佳。