6.4 CART训练算法

Scikit-Learn使用分类和回归树（Classification and Regresssion Tree, CART）算法来训练决策树（也称为“增长树”）。该算法的工作原理是：首先使用单个特征\(k\)和阈值\(t_k\)将训练集分为两个子集。如何选择\(k\)和\(t_k\)呢? 它搜索产生最纯子集（按其大小加权）的一对\((k, t_k)\)。公式6-2给出了试图最小化的成本函数。

公式6-2：CART分类成本函数

\[J(k, t_k) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_{right} \tag{6-2} \\ \text{其中} \begin{cases} G_{left/right}\text{测量左右子集的不纯度} \\ n_{left/right}\text{测量左右子集的实例数} \end{cases}\]

一旦CART算法成功地将训练集分为两部分，它就会使用相同的逻辑将子集进行分割，然后再分割子集，以此类推。一旦达到最大深度（由超参数max_depth定义），或者找不到可减少不纯度的分割，它将停止递归。其他一些超参数可以控制其他一些停止条件（min_samples_split、min_samples_leaf、min_weight_fraction_leaf和max_leaf_nodes）。

如你所见，CART是一种贪婪算法：从顶层开始搜索最优分裂，然后每层重复这个过程。几层分裂之后，它并不会检视这个分裂的不纯度是否为可能的最低值。贪婪算法通常会产生一个相当不错的解，但是不能保证是最优解。

而不幸的是，寻找最优树是一个已知的NP完全问题：需要的时间是O（exp（m）），所以即使是很小的训练集，也相当棘手。这就是为什么我们必须接受一个“相当不错”的解。

P是可以在多项式时间内解决的一组问题。NP是可以在多项式时间内验证其解的一组问题。NP难问题是可以在多项式时间内将任何NP问题减少的问题。一个NP完全问题是NP和NP难。一个主要的开放数学问题是P=NP是否相等。如果P≠NP（这似乎是可能的），那么不会找到针对任何NP完全问题的多项式算法（也许在量子计算机上除外）