预排序会减慢大型决策树的训练吗？

Question

在 Scikit-Learn 的类文档中DecisionTreeClassifier，presort超参数是这样描述的：

预排序：bool，可选（默认=False）

是否对数据进行预排序以加快在拟合中找到最佳分割的速度。对于大型数据集上决策树的默认设置，将此设置为 true 可能会减慢训练过程。当使用较小的数据集或受限的深度时，这可能会加快训练速度。

我不明白为什么预排序会减慢对大型数据集的训练并加快对较小数据集的训练。我希望完全相反。事实上，关于决策树计算复杂度的文档指出，如果没有预排序，复杂度是 O(n_features * n_samples^2 * log(n_samples))，但是通过预排序它变成 O(n_features * n_samples * log(n_samples))。

因此，我预计预排序需要一点时间，这会稍微减慢训练速度，但如果训练集很大，这将在很大程度上得到补偿。

这只是 Scikit-Learn 文档中的一个错误还是我遗漏了什么？

编辑

我进行了一些测试，我发现预排序似乎确实会减慢大型训练集的训练速度。事实上，我观察到 O(n_features * n_samples^2 * log(n_samples)) 之类的东西，甚至更糟（即指数），带有预排序，而 O(n_features * n_samples * log(n_samples)) 没有预排序。当 n_samples 小于几千时，预排序的训练似乎会更快一些。

所以经验的答案是“是”，但我很想知道为什么。

Answer 1

似乎预排序可以加速找到拟合中的最佳分割，但需要额外的时间来对训练数据进行排序。

根据您提到的复杂性，如下：

with presort: O(n_features * n_samples^2 * log(n_samples))
without presort: O(n_features * n_samples * log(n_samples))

复杂度乘以是很有意义的，这是基于此链接的n_samples排序算法可以提供的最佳复杂度。

但是，我不太确定这个预排序对训练有多大帮助。我找不到任何关于 sklearn 如何实现它的资源。