在Scikit-Learn KNN中调整leaf_size以减少时间消耗

Question

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

原始代码：

knn = KNeighborsClassifier(n_neighbors=3)

新代码：

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

我读了很少的有关KDtree / Balltree的leaf_size参数的文档和文章，但是找不到有关如何安全调整此参数而又没有任何准确性和信息丢失的足够好的参考。

如果有人可以就上述问题分享一些见解，那将是非常友善的。

我提到的相关文章：
1.）http://scikit-learn.org/stable/modules/genic/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

在如何安全调整此参数而又没有任何准确性和信息丢失的情况下，找不到足够好的参考。

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

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

当添加参数leaf_size值为400时，我观察到代码执行所需的时间显着减少。

这很有趣，因为leaf_size增加（默认值为30）通常会减少查询时间。但是有可能大部分时间都花在了构造上，在这种情况下，叶子的尺寸越大，该阶段完成的速度就越快。请记住，球树不能保证结果树是平衡的。当高度不平衡时，构造甚至可能需要O（N ^ 2）时间。在这种情况下，leaf_size增加是完全合理的。这篇文章包含有关此问题的非常有趣的实验。