python决策树之CART分类回归树详解

决策树之CART（分类回归树）详解，具体内容如下

1、CART分类回归树简介

CART分类回归树是一种典型的二叉决策树，可以处理连续型变量和离散型变量。如果待预测分类是离散型数据，则CART生成分类决策树；如果待预测分类是连续型数据，则CART生成回归决策树。数据对象的条件属性为离散型或连续型，并不是区别分类树与回归树的标准，例如表1中，数据对象xi的属性A、B为离散型或连续型，并是不区别分类树与回归树的标准。

表1

2、CART分类回归树分裂属性的选择

2.1 CART分类树——待预测分类为离散型数据

选择具有最小Gain_GINI的属性及其属性值，作为最优分裂属性以及最优分裂属性值。Gain_GINI值越小，说明二分之后的子样本的“纯净度”越高，即说明选择该属性（值）作为分裂属性（值）的效果越好。
  对于样本集S，GINI计算如下：

其中，在样本集S中，Pk表示分类结果中第k个类别出现的频率。

对于含有N个样本的样本集S，根据属性A的第i个属性值，将数据集S划分成两部分，则划分成两部分之后，Gain_GINI计算如下：

其中，n1、n2分别为样本子集S1、S2的样本个数。

对于属性A，分别计算任意属性值将数据集划分成两部分之后的Gain_GINI，选取其中的最小值，作为属性A得到的最优二分方案：

对于样本集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本集S的最优二分方案：

所得到的属性A及其第i属性值，即为样本集S的最优分裂属性以及最优分裂属性值。

2.2 CART回归树——待预测分类为连续型数据

区别于分类树，回归树的待预测分类为连续型数据。同时，区别于分类树选取Gain_GINI为评价分裂属性的指标，回归树选取Gain_σ为评价分裂属性的指标。选择具有最小Gain_σ的属性及其属性值，作为最优分裂属性以及最优分裂属性值。Gain_σ值越小，说明二分之后的子样本的“差异性”越小，说明选择该属性（值）作为分裂属性（值）的效果越好。

针对含有连续型分类结果的样本集S，总方差计算如下：

其中，μ表示样本集S中分类结果的均值，Ck表示第k个分类结果。

对于含有N个样本的样本集S，根据属性A的第i个属性值，将数据集S划分成两部分，则划分成两部分之后，Gain_σ计算如下：

对于属性A，分别计算任意属性值将数据集划分成两部分之后的Gain_σ，选取其中的最小值，作为属性A得到的最优二分方案：

对于样本集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本集S的最优二分方案：

所得到的属性A及其第i属性值，即为样本集S的最优分裂属性以及最优分裂属性值。

3、CART分类回归树的剪枝

由于决策树的建立完全是依赖于训练样本，因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树对于测试样本来说过于庞大而复杂，可能产生较高的分类错误率。这种现象就称为过拟合。因此需要将复杂的决策树进行简化，即去掉一些节点解决过拟合问题，这个过程称为剪枝。

剪枝方法分为预剪枝和后剪枝两大类。预剪枝是在构建决策树的过程中，提前终止决策树的生长，从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强，因为很难精确的判断何时终止树的生长。后剪枝是在决策树构建完成之后，对那些置信度不达标的节点子树用叶子结点代替，该叶子结点的类标号用该节点子树中频率最高的类标记。后剪枝方法又分为两种，一类是把训练数据集分成树的生长集和剪枝集；另一类算法则是使用同一数据集进行决策树生长和剪枝。常见的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。其中，悲观错误剪枝法PEP(Pessimistic Error Pruning)在“决策树之C4.5算法详解”中有详细介绍，感兴趣的小童鞋可以了解学习。这里我们详细介绍CART分类回归树中应用最广泛的剪枝算法——代价复杂性剪枝法CCP(Cost Complexity Pruning)。

代价复杂性剪枝法CCP(Cost Complexity Pruning)主要包含两个步骤：（1）从原始决策树T0开始生成一个子树序列{T0,T1,...,Tn}，其中，Ti+1从Ti产生，Tn为根节点。（2）从第1步产生的子树序列中，根据树的真实误差估计选择最佳决策树。

CCP剪枝法步骤（1）

生成子树序列{T0,T1,...,Tn}的基本思想是从T0开始，裁剪Ti中关于训练数据集误差增加最小的分枝来得到Ti+1。实际上，当1棵树T在节点t处剪枝时，它的误差增加直观上认为是R(t)−R(Tt)，其中，R(t)为在节点t的子树被裁剪后节点t的误差，R(Tt)为在节点t的子树没被裁剪时子树Tt的误差。然而，剪枝后，T的叶子数减少了L(Tt)−1，其中，L(Tt)为子树Tt的叶子数，也就是说，T的复杂性减少了。因此，考虑树的复杂性因素，树分枝被裁剪后误差增加率由下式决定：

其中，R(t)表示节点t的子树被裁剪后节点t的误差，R(t)=r(t)∗p(t)，r(t)是节点t的误差率，p(t)是节点t上的样本个数与训练集中样本个数的比例。R(Tt)表示节点t的子树没被裁剪时子树Tt的误差，即子树Tt上所有叶子节点的误差之和。

Ti+1就是选择Ti中具有最小α值所对应的剪枝树。

例如：图1中ti表示决策树中第i个节点，A、B表示训练集中的两个类别，A、B之后的数据表示落入该节点分别属于A类、B类的样本个数。

图1，决策树中训练样本总个数为80。对于节点t4，其中，A类样本46个，B类样本4个，根据大多数原则，则节点t4中样本为A类，故节点t4的子树（t8、t9）被裁剪之后t4的误差为：450∗5080=480。节点t4的子树（t8、t9）被裁剪之前t4的误差为：145∗4580+25∗580=380。故α(t4)=480−3802−1=0.0125。类似过程，依次得到所有节点的误差增加率，如表2：

表2

从表2可以看出，在原始树T0行，4个非叶节点中t4的α值最小，因此，裁剪T0的t4节点的分枝得到T1；在T1行，虽然t2和t3的α值相同，但裁剪t2的分枝可以得到更小的决策树，因此，T2是裁剪T1中的t2分枝得到的。

CCP剪枝法步骤（2）

如何根据第1步产生的子树序列{T0,T1,...,Tn}，选择出1棵最佳决策树是CCP剪枝法步骤（2）的关键。通常采用的方法有两种，一种是V番交叉验证(V-fold cross-validation)，另一种是基于独立剪枝数据集。此处不在过分赘述，感兴趣的小童鞋，可以阅读参考文献[1][2][3]等。