在上一节我们将了ID3算法，和ID3算法的改进版C4.5算法。对于C4.5算法，我们也提到了它的不足，特别是不能处理连续数据等。而目前最常见的CART既可以做回归，也可以做分类，在skleran包中的决策树也采用此种方法。

特征选择方法

前面无论是ID3或者C4.5算法，我们都是使用的“熵”这一度量单位来选取特征。但计算熵需要大量的对数运算，有没有其他的特征选取方法呢？答案是肯定的，这里使用了统计学中的基尼系数，其基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

假设在分类问题中有$K$个类别，第$k$个类别的概率为$p_k$，则基尼系数表示为：

$Gini(p) =\sum\limits_{k=1}^K\sum\limits_{j\ne k}^Kp_kp_j= \sum\limits_{k=1}^Kp_k(1-p_k) = 1 - \sum\limits_{k=1}^Kp_k^2$

从直观上，我们可以认为基尼系数是某种属性分类错误的概率度量。

对于给定的样本$D$,假设有$K$个类别, 第$k$个类别的数量为$C_k$,则样本$D$的基尼系数表达式为：

$Gini(D) = 1 - \sum\limits _{k =1 }^{K}(\frac{|C_k|}{|D|})^2$

我们后面会构造二叉树，因此当只有两个节点时，其公式可以表示为：

$Gini(D) = \frac{|C_1|}{|D|}Gini(D_1)+\frac{|C_2|}{|D|}Gini(D_2)$

二叉树

在CART算法中，生成的决策树始终是二叉树。

离散值处理

对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。

若某个特征$A$被选择建立决策树点，有 A1、A2、A3 三种分类，CART分类树会考虑把 A 分成 {A1} 和 {A2,A3} {A1}，{A2} 和 {A1,A3}， {A3} 和 {A1,A2} 三种情况，找到基尼系数最小的组合，比如 {A2} 和 {A1,A3} {A2},然后建立二叉树节点，一个节点是 A2 对应的样本，另一个节点是 {A1,A3} 对应的节点。

同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征 $A$ 来划分 $A1$ 和 $A3$。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。

连续值处理

CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为：

$\min\limits_{A,s} [\min\limits_{c_1} \sum\limits_{x_i\in D_1(A,s) }(y_i-c_1)^2 + \min\limits_{c_2} \sum\limits_{x_i\in D_2(A,s) }(y_i-c_2)^2 ]$

对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

剪枝

由于决策时算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，即类似于线性回归的正则化，来增加决策树的返回能力。但是，有很多的剪枝方法，我们应该这么选择呢？

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

因此，CART树的剪枝算法可以概括为两步：

1. 第一步是从原始决策树生成各种剪枝效果的决策树，
2. 第二步是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

损失函数

首先对于是否对一个节点进行剪枝，我们需要一个度量标准，也就是剪枝前后的损失谁更大。

• 在剪枝的过程中，对于任意的一刻子树$T_t$,其损失函数为：

  $C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|$

  其中，$\alpha$为正则化参数，这和线性回归的正则化一样。

  $C(T_t)$为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量。

  $|T_t|$是子树$T_t$的叶子节点的数量。

• 当$\alpha=0$时，即没有正则化，原始的生成的CART树即为最优子树。当$\alpha=\infty$时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然，这是两种极端情况。一般来说，$\alpha$ 越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的$\alpha$，一定存在使损失函数$C_{\alpha}(T)$最小的唯一子树。

• 若将节点全部剪掉，只保留根节点，则根节点损失是：

  $C_{\alpha}(T) = C(T) + \alpha$

• 当$\alpha = 0$或者$\alpha$很小时，很容易得到：

  $C_{\alpha}(T_t) \le C_{\alpha}(T)$

  这表示根节点损失大于叶节点损失。

• 而我们需要得到根节点损失小于等于叶节点损失，这样我们才能合理的将其剪枝，即：

  $C_{\alpha}(T_t) = C_{\alpha}(T)\Rightarrow C(T) + \alpha = C(T_t) + \alpha|T_t|$

  $\alpha = \frac{C(T) - C(T_t)}{|T_t | -1}$

• 此时，$T_t$和$T$有相同的损失函数，但是$T$节点更少，因此可以对子树进行剪枝，也就是将它的子节点全部剪掉，变为一个叶子节点$T$。

交叉验证

我们可以计算出每个子树是否剪枝的阈值$α$，然后分别针对不同的$α$所对应的剪枝后的最优子树做交叉验证。

这样就可以选择一个最好的$α$，有了这个$α$，我们就可以用对应的最优子树作为最终结果。

算法小结

优点

1. 简单直观，生成的决策树很直观。
2. 基本不需要预处理，不需要提前归一化，处理缺失值。
3. 使用决策树预测的代价是 $\mathcal{O}(\log{2m})\mathcal{O}(\log{2m})$。 m为样本数。
4. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
5. 可以处理多维度输出的分类问题。
6. 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
7. 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
8. 对于异常点的容错能力好，健壮性高。

缺点

1. 决策树算法非常容易过拟合，导致泛化能力不强。
2. 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考资料

1. 决策树算法原理