决策树算法在适合一棵树时不会计算所有可能的树。如果他们这样做了，他们将解决一个NP 难题问题。决策树拟合算法通常在拟合过程中做出贪婪决策——在每个阶段，它们优化子问题以找到与给定节点中的数据的最佳分割，并在拟合过程中继续前进。此外，随着您深入决策树，您将拥有一组较小的数据，这些数据已进入给定节点，因此您将针对较小的数据子集优化拆分规则。所有这些选择都是对给定节点中数据的线性扫描。这并不复杂，但如果您有大量的观测值或大量的协变量要拆分，则计算上可能会变得有些昂贵。但是，很多工作可以拆分并发送到不同的机器上进行处理，因此有多种方法可以构建您的计算架构以扩大规模。

用于构建决策树的 CART 和 C4.5 算法之间存在一些差异。例如，CART 使用 Gini Impurity 来挑选特征，而 C.4.5 使用 Shannon Entropy。我认为这些差异与答案无关，所以我不会区分它们。

使决策树比您想象的更快的原因是：

1. 正如其他人所说，这些算法是 1-lookahead 算法。他们执行局部优化。在每个分支，他们选择最大化/最小化他们使用的任何度量（基尼或熵）的规则。这意味着他们可能会错过使用逻辑运算符的规则，例如and会产生更好的树。这意味着您在进行特征工程时应该非常小心/聪明。例如，假设您试图预测人们喝了多少酒，您可能想要对诸如new_feature = hour > 22 & hour < 4 & (friday_night | saturday_night). 决策树可能会遗漏这些规则，或者赋予它们应有的重要性。
2. 更重要的是，决策树使用的指标可以增量计算。假设你有一个特征 $X_1 = \{3,1.5,2.5,2,1\}$。决策树不需要计算 的度量，然后再计算 的度量，然后再计算，等等。选择 Gini 和 Entropy 是因为它们可以增量计算。首先，对每个特征进行排序，得到 $X_1 = \{1,1.5,2,2.5,3\}$。其次，当您计算 时，您可以使用结果轻松计算。这就像做一个平均数。如果你有一个样本的平均值，$\bar x$，我给你另一个值 $v$，你可以很便宜地更新你的平均值，$\bar x \leftarrow \frac{n\bar x+v}{ n+1}$。基尼系数$X_1 = \{3,1.5,2.5,2,1\}$. The decision tree does not need to compute the metric for X <= 1X <= 1.5X <= 2$X_1 = \{1,1.5,2,2.5,3\}$. Secondly, when you compute X <= 1X <= 1.5$\bar x$, and I give you another value $v$, you can cheaply update your average doing, $\bar x \leftarrow \frac{n\bar x+v}{n+1}$. 被计算为总和的一部分，可以很容易地对样本进行增量计算。
3. 决策树可以并行化。每个节点由两个独立的分支组成。因此，在每个分支上，您都有机会并行创建树。此外，特征选择本身也可以并行化。这就是使包裹xgboost如此之快的原因。梯度提升是顺序的，不能并行化，但树本身可以。

只是为了丰富答案，

分层轴平行决策树速度很快（CART，C4.5），但还有其他替代方案，例如非分层决策树或执行不倾斜分区的决策树，尽管它们可能更准确。如果您有兴趣，请查看以下参考资料（它们不是详尽的选择）。

非分层：

Grubinger, T.、Zeileis, A. 和 Pfeiffer, K.-.，2014。Evtree：RJStat.Software 中全局最优分类和回归树的进化学习 61 (1), 1-29。

斜劈：

Murthy, SK, Kasif, S. 和 Salzberg, S., 1994。倾斜决策树的归纳系统。J.人工。英特尔。水库。2（1），1-32。http://dx.doi.org/doi:10.1613/jair.63。Cantú-Paz, E. 和 Kamath, C., 2003。用进化算法诱导倾斜决策树。IEEE Trans。进化。计算。7（1），54-68。http://dx.doi.org/10.1109/TEVC.2002.806857。Heath, D.、Kasif, S. 和 Salzberg, S.，1993 年。倾斜决策树的归纳。J.人工。英特尔。水库。2 (2), 1002-1007。

祝你好运！