machine-learning - 调整 leaf_size 以减少 Scikit-Learn KNN 中的时间消耗

Question

我试图实现 KNN 来进行手写字符识别，但我发现代码的执行花费了很多时间。当添加值为 400 的参数 leaf_size 时，我观察到代码执行所花费的时间显着减少。

原始代码:

knn = KNeighborsClassifier(n_neighbors=3)

新代码:

knn = KNeighborsClassifier(n_neighbors=3,leaf_size=400)

我读过一些有关 KDtree/Balltree 的 leaf_size 参数的文档和文章，但找不到任何足够好的引用来说明如何安全地调整此参数，而不会造成任何准确性和信息丢失。

如果有人能分享有关上述问题的一些见解，那就太好了。

我引用的相关文章:
1.) http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html
2.)https://jakevdp.github.io/blog/2013/04/29/benchmarking-nearest-neighbor-searches-in-python/
3.)http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

Answer 1

couldn't find any good enough reference on how to safely tune this parameter without any accuracy and information loss.

一般来说，leaf_size 越大，算法选择的邻居就越近(请注意，这与更高的准确度不同)。这是因为该树的主要目的是减少邻居的候选者数量。 KD 树和 Ball Tree 都不能保证 split 将使真正的最近点保持在树中。从这个意义上说，树的使用意味着“信息丢失”，树越大，将真正的邻居放入错误分支的机会就越大。在极端情况下，根本没有树(称为暴力)，因此所有点都是邻居的候选点，因此算法保证找到精确的解决方案。

但是，至少在理论上，即使邻居选择错误，实际上也可能会导致更高的分类精度。但几乎不可能提前说明 leaf_size 的变化如何影响最终的精度。

When added parameter leaf_size with value 400, I observed that time taken by code to execute was significantly reduced.

这很有趣，因为leaf_size增加(默认为30)通常会导致查询时间减少。但可能大部分时间都花在了构建上，在这种情况下，叶子的尺寸越大，此阶段完成的速度就越快。请记住，球树不能保证结果树平衡。当高度不平衡时，构建甚至可能需要 O(N^2) 时间。在这种情况下，leaf_size 的增加非常有意义。 This post包含关于这个问题的非常有趣的实验。