KD 树：`leafsize` 参数的含义
KD Tree: meaning of `leafsize` parameter
我正在查看 SciPy 的 KD Tree implementation。我被leafsize这个参数搞糊涂了，据说是
The number of points at which the algorithm switches over to brute-force. Default: 16.
这是BST的叶子数吗？如果是这样，这意味着默认情况下，KD 树将包含不超过 32 个点。这似乎小得不合理，尤其是对于我的 k=2 用例。我是否错误地解释了参数？
参数 leafsize 不控制树中叶子的最大数量（无界），而是控制与树中单个叶子相关联的输入点的数量。考虑将 64 个点添加到树中。如果每个点都与单个叶子相关联，您将得到一棵七层深的完整树，任何需要一个点的处理都会下降这七层以找到它。或者，如果 leafsize 为 16，您将得到一棵只有 3 层深的树，并且树中的每个叶子都与 16 个点相关联。处理一个点涉及降低树的三个级别，然后测试叶中的 16 个点中的每一个（因为它们是无序的）。这个值可以根据性能进行调整，根据经验，最佳值取决于树的使用方式。
从概念上讲，这是为不同 leafsize 值构建的树的示例。
您可以在scipy source code中看到leafsize参数short-circuits树的构建过程。这将使 leafsize/2 和 leafsize 之间的点在树的叶子中无序。
我正在查看 SciPy 的 KD Tree implementation。我被leafsize这个参数搞糊涂了，据说是
The number of points at which the algorithm switches over to brute-force. Default: 16.
这是BST的叶子数吗？如果是这样，这意味着默认情况下，KD 树将包含不超过 32 个点。这似乎小得不合理，尤其是对于我的 k=2 用例。我是否错误地解释了参数？
参数 leafsize 不控制树中叶子的最大数量（无界），而是控制与树中单个叶子相关联的输入点的数量。考虑将 64 个点添加到树中。如果每个点都与单个叶子相关联，您将得到一棵七层深的完整树，任何需要一个点的处理都会下降这七层以找到它。或者，如果 leafsize 为 16，您将得到一棵只有 3 层深的树，并且树中的每个叶子都与 16 个点相关联。处理一个点涉及降低树的三个级别，然后测试叶中的 16 个点中的每一个（因为它们是无序的）。这个值可以根据性能进行调整，根据经验，最佳值取决于树的使用方式。
从概念上讲，这是为不同 leafsize 值构建的树的示例。
您可以在scipy source code中看到leafsize参数short-circuits树的构建过程。这将使 leafsize/2 和 leafsize 之间的点在树的叶子中无序。