我在查看SciPy的KD Tree实现。我对
leafsize
参数感到困惑,它被描述为:
算法切换到暴力搜索的点数。默认值:16。
这是BST中叶子节点的数量吗?如果是这样,那么默认情况下,KD树将不超过32个点。这看起来太小了,特别是对于我的k=2的用例。我是否错误地解释了此参数?
leafsize
参数感到困惑,它被描述为:
算法切换到暴力搜索的点数。默认值:16。
这是BST中叶子节点的数量吗?如果是这样,那么默认情况下,KD树将不超过32个点。这看起来太小了,特别是对于我的k=2的用例。我是否错误地解释了此参数?
leafsize
并不控制树中最大叶子节点的数量(它没有上限),而是控制与树中单个叶子节点相关联的输入点数。假设有64个点被添加到树中。如果每个点都与一个单独的叶子节点相关联,那么你将得到一棵完整的树,它有七层深度,并且任何需要使用某个点的处理都需要下降这七层来查找它。相反,如果leafsize为16,则会得到一棵只有3层深度的树,树中的每个叶子节点都与16个点相关联。处理一个点涉及到遍历树的三层,然后测试叶子节点中的每个点(因为它们是无序的)。这个值可以调整以提高性能,实际上,最佳值取决于树的具体用途。leafsize
值构建的树的示例。
您可以看到,在scipy源代码中,leafsize
参数如何使树构建过程短路。这将导致在树的叶子节点中留下leafsize/2
至leafsize
个点无序。
leafsize
是kd树文献中的标准术语? - rishaiquery_ball_point
函数时,似乎leafsize
参数没有任何效果。参见:https://dev59.com/nr7pa4cB1Zd3GeqPwVQd - seralouk