KD树：`leafsize`参数的含义

Question

我在查看SciPy的KD Tree实现。我对leafsize参数感到困惑，它被描述为：

算法切换到暴力搜索的点数。默认值：16。

这是BST中叶子节点的数量吗？如果是这样，那么默认情况下，KD树将不超过32个点。这看起来太小了，特别是对于我的k=2的用例。我是否错误地解释了此参数？

- rishai

Answer 1

参数leafsize并不控制树中最大叶子节点的数量（它没有上限），而是控制与树中单个叶子节点相关联的输入点数。假设有64个点被添加到树中。如果每个点都与一个单独的叶子节点相关联，那么你将得到一棵完整的树，它有七层深度，并且任何需要使用某个点的处理都需要下降这七层来查找它。相反，如果leafsize为16，则会得到一棵只有3层深度的树，树中的每个叶子节点都与16个点相关联。处理一个点涉及到遍历树的三层，然后测试叶子节点中的每个点（因为它们是无序的）。这个值可以调整以提高性能，实际上，最佳值取决于树的具体用途。

从概念上讲，以下是针对不同leafsize值构建的树的示例。

您可以看到，在scipy源代码中，leafsize参数如何使树构建过程短路。这将导致在树的叶子节点中留下leafsize/2至leafsize个点无序。

- Alex

---

嗨，Alex，非常感谢你。我猜你得深入源代码才能找出这个问题？或者leafsize是kd树文献中的标准术语？ - rishai

我想我终于明白文档所说的“算法切换到暴力方法的点数”。对于叶大小为16，查询需要扫描16个点（在最坏情况下），这就是暴力方法所做的。 - rishai

我认为这是一种相当标准的技术。可以查看YouTube视频（此处或此处）以查看使用多个叶子节点构建kd树的示例。通常，这被称为树构建过程的“停止准则”，而不是叶子大小，特别是从机器学习的角度来看。 - Alex

谢谢Alex；正如你所看到的，我刚开始学习这个算法。 - rishai

@Alex，你能帮忙解决这个问题吗：https://dev59.com/nr7pa4cB1Zd3GeqPwVQd？ - seralouk

使用 query_ball_point 函数时，似乎 leafsize 参数没有任何效果。参见：https://dev59.com/nr7pa4cB1Zd3GeqPwVQd - seralouk