CART生成与剪枝算法

从基尼不纯度来看待样本的划分方式，直观上若集合D中存在样本数的类别越多，那么其对应的“不纯度”也就会越大，直观的说也就是该集合“不纯”，这也很类似于信息熵的性质。对于CART分类树的剪枝过程来说，第二步交叉验证倒是容易理解，但第一步的子序列到底是怎么来的？我什么要减去其中g(t)​最小的子树？

1 引言

在上一篇文章中，笔者分别介绍了用ID3和C4.5这两种算法来生成决策树。其中ID3算法每次用信息增益最大的特征来划分数据样本，而C4.5算法每次用信息增益比最大的特征来划分数据样本。接下来，再来看另外一种采用基尼不纯度（Gini Impurity）为标准的划分方法，CART算法。

2 CART算法

分类与回归树（Classification and Regression Tree, CART），是一种既可以用于分类也可以用于回归的决策树，同时它也是应用最为广泛的决策树学习方法之一。CART假设决策树是二叉树，内部节点特征的取值均为“是”和“否”，左分支取值为“是”，右分支取值为“否”。这样，决策树在构建过程中就等价于递归地二分每个特征，将整个特征空间划分为有限个单元[1]。

在本书中，笔者暂时只对其中的分类树进行介绍。总体来说，利用CART算法来构造一棵分类需要完成两步：①基于训练数据集生成决策树，并且生成的决策树要尽可能的大；②用验证集来对已生成的树进行剪枝并选择最优子树。

2.1 分类树生成算法

在介绍分类树的生成算法前，让我们先来看一看新引入划分标准基尼不纯度。在分类问题中，假设某数据集包含有$K$$K$个类别，样本点属于第$k$$k$类的概率为$p_k$${{p}_{k}}$，则概率分布的基尼不纯度定义为

因此，对于给定的样本集合$D$$D$，其基尼不纯度为

其中，$C_k$$C_k$是$D$$D$中属于第$k$$k$类的样本子集，$|C_k|$$|C_k|$表示类别$k$$k$中的样本数，$K$$K$是类别的个数。

从基尼不纯度的定义可以看出，若集合$D$$D$中存在样本数的类别越多，那么其对应的“不纯度”也就会越大，直观的说也就是该集合“不纯”，这也很类似于信息熵的性质。相反，若是该集合中只存在一个类别，那么其对应的基尼不纯度就会是0。因此，在通过CART算法构造决策树时，会选择使基尼不纯度达到最小值的特征取值进行样本划分。

同时，在决策树的生成过程中，如果样本集合$D$$D$根据特征$A$$A$是否取某一可能值$a$$a$被分割成$D_1,D_2$$D_1,D_2$两个部分，即

则在特征$A$$A$的条件下，集合$D$$D$的基尼不纯度定义为：

其中$\text{Gini}(D,A)$$\text{Gini}(D,A)$表示经$A=a$$A=a$分割后集合$D$$D$的不确定性。可以看出这类似于条件熵，$\text{Gini}(D,A)$$\text{Gini}(D,A)$越小则表示特征$A$$A$越能降低集合$D$$D$的不确定性。

在介绍完成基尼不纯度后，就能够列出CART分类树的生成步骤：

输入：训练数据集$D$$D$，停止计算条件；

输出：CART分类决策树。

根据训练集，从根节点开始，递归地对每个节点进行如下操作，并构建二叉决策树。

(1) 设训练集为$D$$D$，根据式$(2)$$(2)$计算现有特征对该数据集的基尼不纯度。接着，对于每一个特征$A$$A$，对其可能的每一个值$a$$a$，根据样本点对$A=a$$A=a$是否成立将$D$$D$划分成$D_1,D_2$$D_1,D_2$两个部分，然后再利用式$(4)$$(4)$计算$A=a$$A=a$时的基尼不纯度；

(2) 在所有可能的特征$A$$A$以及它们所有可能的切分点$a$$a$中，选择基尼不纯度最小的特征取值作为划分标准将原有数据集划分为两个部分，并分配到两个子节点中去；

(3) 对两个子节点递归的调用步骤(1)和(2)，直到满足停止条件；

(4) 生成CART决策树。

其中，算法停止计算的条通常是节点中的样本点个数小于设定阈值，或样本集合的基尼不纯度小于设定阈值，亦或是没有更多特征，这一点同ID3和C4.5算法的停止条件类似。

2.2 分类树生成示例

在介绍完上述理论性的内容后，这里我们同样还是拿之前的数据集来对具体的生成过程进行详细的示例。由表8-1中的数据可知，此时的其基尼不纯度为

进一步，对于特征$A_1$${{A}_{1}}$来说，根据其取值是否为1，可以将原始样本划分为$D_1$$D_1$和$D_2$$D_2$两个部分。由式$(4)$$(4)$得

同理，对于特征$A_2$${{A}_{2}}$来说，根据其取值是否为1，也可以将原始样本划分为$D_1$$D_1$和$D_2$$D_2$两个部分。此时有

进一步，对于特征$A_3$${{A}_{3}}$来说，根据其分别取值是否为$D,S,T$$D,S,T$,每一次也可将原始样本划分为$D_1$$D_1$和$D_2$$D_2$两个部分。此时有

注意：每次划分时都是将样本集合划分为两个部分，即$A_i=a$$A_i=a$和$A_i\ne a$$A_i\neq a$

由以上计算结果可知，使用$A_1=1$${{A}_{1}}=1$对样本集合进行划分所得到的基尼不纯度最小。故，根节点应该以$A_1=1$${{A}_{1}}=1$是否成立来进行分割，如图1所示。

经过这次划分后，原始的样本集合就被特征“有工作”分割成了左右两个部分。接下来，再对左右两个集合递归的进行上述步骤，最终便可以得到通过CART算法生成的分类决策树，如图2所示。

2.3 分类树剪枝步骤

在2.2节中，笔者介绍了CART中决策树的生成算法，接下来再来看看在CART中如何对生成后的决策树进行剪枝。根据第4章内容的介绍可知，总体上来说模型（决策树）越复杂，越容易产生过拟合现象，此时对应的代价函数值也相对较小。在决策树中，遇到这种情况时也就需要进行剪枝处理。CART剪枝算法由两部组成：

(1) 首先是从之前生成的决策树$T_0$$T_0$底端开始不断剪枝，直到$T_0$$T_0$的根节点，形成一个子序列$\{T_0,T_1,...,T_n\}$$\{T_0,T_1,...,T_n\}$

(2) 然后通过交叉验证对这一子序列进行测试，从中选择最优的子树。

从上面的两个步骤可以看出，第二步并没有什么难点，关键就在于如何通过剪枝来生成这样一个决策树子序列。

• 剪枝，形成一个子序列

  在剪枝过程中，计算子树的损失函数

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

  其中，$T$$T$为任意子树，$C(T)$$C(T)$为对训练集的预测误差，$|T|$$|T|$为子树的叶节点个数，$\alpha \ge 0$$\alpha\geq0$为参数。需要指出的是不同与之前ID3和C4.5中剪枝算法的$\alpha$$\alpha$，前者是人为设定，而此处则是通过计算得到。

  具体地，从整体树$T_0$$T_0$开始剪枝，如图3所示。

  

  图 3. CART剪枝图

  对于$T_0$$T_0$的任意内部节点$t$$t$，以$t$$t$为根节点的子树$T_t$$T_t$（可以看作是剪枝前）的损失函数为

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

  同时，以$t$$t$为单节点的子树（可以看作是剪枝后）的损失函数为

  $$C_{\alpha }(t)=C(t)+\alpha \cdot 1(13)$$

  ① 当$\alpha =0$$\alpha=0$或者极小的时候，有不等式

  $$C_{\alpha }(T_t)<C_{\alpha }(t)(14)$$

  不等式成立的原因是因为，当$\alpha =0$$\alpha=0$或者极小的时候，起决定作用的就是预测误差$C(t)$$C(t)$和$C(T_t)$$C(T_t)$，而模型越复杂其训练误差总是越小的，因此不等式成立。

  ② 当$\alpha$$\alpha$增大时，在某一$\alpha$$\alpha$有

  $$C_{\alpha }(T_t)=C_{\alpha }(t)(15)$$

  等式成立的原因是因为，当$\alpha$$\alpha$慢慢增大时，就不能忽略模型复杂度所带来的影响（也就是式$(11)$$(11)$第二项）。所以总会存在一个取值$\alpha$$\alpha$使得等式$(15)$$(15)$成立。

  ③ 当$\alpha$$\alpha$再增大时，不等式$(14)$$(14)$反向

  因此，当$C_{\alpha }(T_t)=C_{\alpha }(t)$$C_{\alpha}(T_t)=C_{\alpha}(t)$时，有$\alpha =\frac{C(t)-C(T_t)}{|T_t|-1}$$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，此时的子树$T_t$$T_t$和单节点树$t$$t$有相同的损失函数值，但$t$$t$的节点少模型更简单，因此$t$$t$比$T_t$$T_t$更可取，即对$T_t$$T_t$进行剪枝。

  为此，对决策树$T_0$$T_0$中每一个内部节点$t$$t$来说，都可以计算

  $$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}(16)$$

  它表示剪枝后整体损失函数减少的程度。因为每个$g(t)$$g(t)$背后都对应着一个决策树模型，而不同的$g(t)$$g(t)$则表示损失函数变化的不同程度。接着，在树$T_0$$T_0$中减去$g(t)$$g(t)$最小的子树$T_t$$T_t$，将得到的子树作为$T_1$$T_1$。如此剪枝下去，直到得到根节点。

  注意，此时得到的一系列$g(t)$$g(t)$即$\alpha$$\alpha$，都能使得在每种情况下剪枝前和剪枝后的损失值相等，因此按照上面第②种情况中的规则要进行剪枝。但为什么是减去其中$g(t)$$g(t)$最小的呢？

  对于树$T$$T$来说，其内部可能的节点$t$$t$有$t_0,t_1,t_2,t_3$$t_0,t_1,t_2,t_3$；$t_i$$t_i$表示其中任意一个, 如图4所示。

  

  图 4. CART剪枝过程图

  因此便可以计算得到$g(t_0),g(t_1),g(t_2),g(t_3)$$g(t_0),g(t_1),g(t_2),g(t_3)$，也即对应的${\alpha }_0,{\alpha }_1,{\alpha }_2,{\alpha }_3$$\alpha_0,\alpha_1,\alpha_2,\alpha_3$。从上面的第②种情况可以知道，$g(t)$$g(t)$是根据式$(16)$$(16)$所计算得到，因此这4种情况下$t_i$$t_i$比$T_{t_i}$$T_{t_i}$更可取，都满足剪枝。但是由于以$t_i$$t_i$为根节点的子树对应的复杂度各不相同，也就意味着${\alpha }_i\ne {\alpha }_j,(i,j=0,1,2,3;i\ne j)$$\alpha_i\neq\alpha_j,(i,j=0,1,2,3;i\neq j)$,即${\alpha }_i,{\alpha }_j$$\alpha_i,\alpha_j$存在着大小关系。又因为，当$\alpha$$\alpha$大的时候，最优子树$T_{\alpha }$$T_{\alpha}$偏小；当$\alpha$$\alpha$小的时候，最优子树$T_{\alpha }$$T_{\alpha}$偏大；并且由于在这4中情况下剪枝前和剪枝后损失值都相等（即都满足剪枝条件），因此选择减去其中$g(t)$$g(t)$最小的子树。

  接着，在得到子树$T_1$$T_1$后，再通过上述步骤对$T_1$$T_1$进行剪枝得到$T_2$$T_2$。如此剪枝下去直到得到根节点，此时便得到了子树序列$T_0,T_1,T_2,....T_n$$T_0,T_1,T_2,....T_n$。

• 交叉验证选择最优子树$T_{\alpha }$$T_{\alpha}$

  通过上一步步我们便可以得到一系列的子树序列$T_0,T_1,...,T_n$$T_0,T_1,...,T_n$，最后再通过交叉验证来选取最优决的策树$T_{\alpha }$$T_{\alpha}$。

进一步，CART分类树的剪枝步骤可以总结为[1]：

输入：CART算法生成的分类树$T_0$${{T}_{0}}$;

输出：最优决策树$T_{\alpha }$${{T}_{\alpha }}$.

(1) 设$k=0,T=T_0$$k=0,T=T_0$;

(2) 设$\alpha =+\mathrm{\infty }$$\alpha =+\infty$;

(3) 对于树$T$$T$来说，自下而上地对其每个内部节点$t$$t$计算$C(T_t),|T_t|$$C({{T}_{t}}),|{{T}_{t}}|$以及

其中，$T_t$$T_t$表示以$t$$t$为根节点的子树，$C(T_t)$$C(T_t)$是子树$T_t$$T_t$在训练集上的误差，$|T_t|$$|T_t|$是子树$T_t$$T_t$叶节点的个数。

(4) 对$g(t)=\alpha$$g(t)=\alpha$对应的内部节点$t$$t$进行剪枝，并对叶节点以多数表决法决定其类别得到树$T$$T$；

(5) 令$k=k+1$$k=k+1$，${\alpha }_k=\alpha$$\alpha_k=\alpha$，$T_k=T$$T_k=T$；

(6) 如果$T_k$$T_k$不是由根节点及两个叶节点构成的树，则继续执行步骤(3)；否则令$T_k=T_n$$T_k=T_n$；

(7) 采用交叉验证在子树序列$T_0,T_1,...,T_n$${{T}_{0}},{{T}_{1}},...,{{T}_{n}}$中选择最优子树$T_{\alpha }$$T_{\alpha}$。

当然，如果仅看这些步骤可能依旧会很模糊，下面笔者再通过一个简单的图示进行说明。

2.4 分类树剪枝示例

现在假设通过CART算法生成了一棵如图5所示的决策树。

从图5可以看出，可对树$T_0$$T_0$进行剪枝的内部节点有$t_0,t_1,t_2,t_3$$t_0,t_1,t_2,t_3$，因此根据剪枝步骤(3)可以分别算出$g(t_0),g(t_1),g(t_2),g(t_3)$$g(t_0),g(t_1),g(t_2),g(t_3)$。假设此时算出$g(t_3)$$g(t_3)$最小，那么根据剪枝步骤(4)便可以得到如图6所示的子树$T_1$$T_1$，且${\alpha }_1=g(t_3)$$\alpha_1=g(t_3)$。

从图可以看出，根据剪枝步骤(6)可知需要再次对$T_1$$T_1$进行剪枝，且此时可对树$T_1$${{T}_{1}}$进行剪枝的内部节点有$t_0,t_1,t_2$${{t}_{0}},{{t}_{1}},{{t}_{2}}$。进一步，根据剪枝步骤(3)可以分别算出$g(t_0),g(t_1),g(t_2)$$g({{t}_{0}}),g({{t}_{1}}),g({{t}_{2}})$。假设此时算出$g(t_1)$$g({{t}_{1}})$最小，那么根据剪枝步骤(4)便可以得到如图7所示的子树$T_2$${{T}_{2}}$，且${\alpha }_2=g(t_1)$${{\alpha }_{2}}=g({{t}_{1}})$。

从图7可以看出，根据剪枝步骤(6)可知需要再次对$T_2$${{T}_{2}}$进行剪枝，且此时可对树$T_2$${{T}_{2}}$进行剪枝的内部节点有$t_0,t_1$${{t}_{0}},{{t}_{1}}$。进一步，根据剪枝步骤(3)可以分别算出$g(t_0),g(t_1)$$g({{t}_{0}}),g({{t}_{1}})$。假设此时算出$g(t_0)$$g({{t}_{0}})$最小，那么根据剪枝步骤(4)便可以得到如图8所示的子树$T_3$${{T}_{3}}$，且${\alpha }_3=g(t_0)$${{\alpha }_{3}}=g({{t}_{0}})$。

从图8可以看出，根据剪枝步骤(6)可知满足停止条件不需要继续进行剪枝。到此，便得到了整个子树序列$T_0,T_1,T_2,T_3$${{T}_{0}},{{T}_{1}},{{T}_{2}},{{T}_{3}}$，接着采用交叉验证在子树序列中选择最优子树$T_{\alpha }$$T_{\alpha}$即可。

到此为止，对于CART决策树的整个生成与剪枝过程就介绍完了。最后，通过sklearn来完成对于CART分类树的使用也很容易，只需要将类DecisionTreeClassifier中的划分标准设置为criterion="gini"即可，其它地方依旧不变。

xxxxxxxxxx
14
1
if __name__ == '__main__':
2
    from sklearn.datasets import load_iris
3
    from sklearn.model_selection import train_test_split
4

5
    data = load_iris()
6
    x, y = data.data, data.target
7
    x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3)
8
    from sklearn.tree import DecisionTreeClassifier
9

10
    model = DecisionTreeClassifier(criterion='gini')
11
    model.fit(x_train, y_train)
12
    print(model.score(x_test, y_test))
13

14
# 0.9777777

3 小结

在本节中，笔者首先介绍了什么是CART算法；然后进一步介绍了CART分类树中的划分标准基尼不纯度；接着详细介绍了CART分类树的生成过程，并通过一个实际例子展示整个决策树生成的计算过程；最后介绍了CART分类树剪枝过程的基本原理，并且也通过一个简单的图示展示了整个剪枝过程。

本次内容就到此结束，感谢您的阅读！如果你觉得上述内容对你有所帮助，欢迎点赞分享！若有任何疑问与建议，请添加掌柜微信nulls8（备注来源）或加群进行交流。青山不改，绿水长流，我们月来客栈见！

引用

[1] 李航，统计机器学习，清华大学出版社