8.7 CART生成与剪枝算法#
在8.4节中，我们分别介绍了利用ID3和C4.5这两种算法来生成决策树的过程，其中ID3算法每次用信息增益最大的特征来划分数据样本，而C4.5算法则每次用信息增益比最大的特征来划分数据样本。接下来，再来看另外一种采用基尼不纯度（Gini Impurity）为标准的划分方法，CART算法。
8.7.1 CART算法#
分类与回归树（Classification And Regression Tree, CART），是一种既可以用于分类也可以用于回归的决策树，同时它也是应用最为广泛的决策树学习方法之一。CART假设决策树是一棵二叉树，内部节点的特征取值均为“是”或“否”，即左分支取值为“是”，右分支取值为“否”。这样，决策树在构建过程中就等价于递归地二分每个特征，将整个特征空间划分为有限个单元[2]。
在本书中，我们暂时只对其中的分类树进行介绍。总体来讲，利用CART算法来构造一棵分类树需要完成两步： ①基于训练数据集生成决策树，并且生成的决策树要尽可能大。②用验证集对已生成的树进行剪枝并选择最优子树。
8.7.2 分类树生成算法#
在介绍分类树的生成算法前先来介绍新引入的划分标准——基尼不纯度。在分类问题中，假设某数据集包含$K$个类别，样本点属于第$k$类的概率为$p_k$，则此时的基尼不纯度定义为
$$ \text{Gini}(p)=\sum\limits_{k=1}^{K}{{{p}_{k}}(1-{{p}_{k}})}=1-\sum\limits_{k=1}^{K}{p_{k}^{2}}\tag{8-34} $$因此，对于给定的样本集合$D$，其基尼不纯度为
$$ \text{Gini}(D)=1-\sum\limits_{k=1}^{K}{{{\left( \frac{|{{C}_{k}}|}{|D|} \right)}^{2}}}\tag{8-35} $$其中，$C_k$是$D$中属于第k类的样本子集，$C_k$表示类别$k$中的样本数，$K$是类别的个数。
从基尼不纯度的定义可以看出，若集合$D$中存在样本数的类别越多，则其对应的“不纯度”也会越大，直观地说也就是该集合“不纯”，这也很类似于信息熵的性质。相反，若该集合中只存在一个类别，则其对应的基尼不纯度就会是0，因此，在通过CART算法构造决策树时，会选择使基尼不纯度达到最小值时的特征取值进行样本划分。
同时，在决策树的生成过程中，如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，即
$$ {{D}_{1}}=\{(x,y)\in D|A(x)=a\},{{D}_{2}}=D-{{D}_{1}}\tag{8-36} $$则在特征$A$的条件下，集合$D$的基尼不纯度定义为
$$ \text{Gini}(D,A)=\frac{|{{D}_{1}}|}{|D|}\text{Gini}({{D}_{1}})+\frac{|{{D}_{2}}|}{|D|}\text{Gini}({{D}_{2}})\tag{8-37} $$其中$\text{Gini}(D,A)$ 表示经$A=a$分割后集合$D$的不确定性。可以看出这类似于条件熵，$\text{Gini}(D,A)$越小则表示特征$A$越能降低集合$D$的不确定性。
在介绍完成基尼不纯度后，就能够列出CART分类树的生成步骤。
输入： 训练数据集$D$，停止计算条件。
输出： CART分类决策树。
根据训练集，从根节点开始，递归地对每个节点进行如下操作，并构建二叉决策树。
(1) 设训练集为$D$，根据式(8-35)计算现有特征对该数据集的基尼不纯度。接着，对于每个特征$A$，对其可能的每个值$a$，根据样本点对$A=a$是否成立将$D$划分成$D_1$和$D_2$两部分，然后利用式(8-37)计算$A=a$时的基尼不纯度。
(2) 在所有可能的特征$A$及它们所有可能的切分点$a$中，选择基尼不纯度最小的特征取值作为划分标准将原有数据集划分为两部分，并分配到两个子节点中去。
(3) 对两个子节点递归的调用步骤(1)和(2)，直到满足停止条件。
(4) 生成CART决策树。
其中，算法停止计算的条件通常是节点中的样本点个数小于设定阈值，或样本集合的基尼不纯度小于设定阈值，抑或没有更多的特征，这一点同8.3节中ID3和C4.5算法的停止条件类似。
8.7.3 分类树生成示例#
在介绍完上述理论性的内容后，这里同样还是采用之前的信用卡审批数据集来对具体的生成过程进行详细示例。由表8-1中的数据可知，此时整个数据集对应的基尼不纯度为
$$ \text{Gini}(D)=1-\sum\limits_{k=1}^{K}{{{\left( \frac{|{{C}_{k}}|}{|D|} \right)}^{2}}}=1-{{\left( \frac{5}{15} \right)}^{2}}-{{\left( \frac{10}{15} \right)}^{2}}\approx 0.444\tag{8-38} $$进一步，对于特征$A_1$来讲，根据其取值是否为1，可以将原始样本划分为$D_1$和$D_2$两部分。由式(8-37)得
$$ \text{Gini}(D,{{A}_{1}}=1)=\frac{7}{15}\text{Gini}({{D}_{1}})+\frac{8}{15}\text{Gini}({{D}_{2}})=\frac{7}{15}\times \frac{24}{49}+\frac{8}{15}\times \frac{14}{64}\approx 0.345\tag{8-39} $$同理，对于特征$A_2$来讲，根据其取值是否为1，也可以将原始样本划分为$D_1$和$D_2$两部分。此时有
$$ \text{Gini}(D,{{A}_{2}}=1)=\frac{8}{15}\text{Gini}({{D}_{1}})+\frac{7}{15}\text{Gini}({{D}_{2}})=\frac{8}{15}\times \frac{1}{2}+\frac{7}{15}\times \frac{12}{49}\approx 0.381\tag{8-40} $$进一步，对于特征$A_3$来讲，根据其分别取值是否为D、S和T，每一次也可将原始样本划分为$D_1$和$D_2$两部分。此时有
$$ \text{Gini}(D,{{A}_{3}}=D)=\frac{12}{15}\text{Gini}({{D}_{1}})+\frac{3}{15}\text{Gini}({{D}_{2}})=\frac{12}{15}\times \frac{4}{9}+\frac{3}{15}\times \frac{4}{9}\approx 0.444\tag{8-41} $$$$ \text{Gini}(D,{{A}_{3}}=S)=\frac{11}{15}\text{Gini}({{D}_{1}})+\frac{4}{15}\text{Gini}({{D}_{2}})=\frac{11}{15}\times \frac{56}{121}+\frac{4}{15}\times \frac{3}{8}\approx 0.439\tag{8-42} $$$$ \text{Gini}(D,{{A}_{3}}=T)=\frac{7}{15}\text{Gini}({{D}_{1}})+\frac{8}{15}\text{Gini}({{D}_{2}})=\frac{7}{15}\times \frac{20}{49}+\frac{8}{15}\times \frac{30}{64}\approx 0.440\tag{8-43} $$注意： 每次划分时都将样本集合划分为两部分，即$A_i=a$和$A_i\neq a$
由以上计算结果可知，使用$A_1=1$对样本集合进行划分所得到的基尼不纯度最小。故根节点应该以$A_1=1$是否成立进行分割，如图8-13所示。
经过这次划分后，原始的样本集合就被特征“有工作”分割成了左右两部分。接下来，再对左右两个集合递归地执行上述步骤，最终便可以得到通过CART算法生成的分类决 策树，如图8-14所示。
8.7.4 分类树剪枝步骤#
在8.7.3节中，我们介绍了CART中决策树的生成算法，接下来再来看一看在CART中如何对生成后的决策树进行剪枝。根据第4章内容的介绍可知，总体上来讲模型（决策树）越复杂，越容易产生过拟合现象，此时对应的代价函数值也相对较小。在决策树中，遇到这种情况时也就需要进行剪枝处理。CART剪枝算法由两部组成：
(1) 首先从之前生成的决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，这样便形成了一个子序列$\{T_0,T_1,...,T_n\}$。
(2) 然后通过交叉验证对这一子序列进行测试，从中选择最优的子树。
从上面的两个步骤可以看出，第(2)步并没有什么难点，关键就在于如何通过剪枝来生成这样一个决策树子序列。
1). 剪枝，形成一个子序列
在剪枝过程中，计算子树的损失函数
$$ C_{\alpha}(T)=C(T)+\alpha|T|\tag{8-44} $$其中，$T$为任意子树，$C(T)$为对训练集的预测误差，$|T|$ 为子树的叶节点个数，$\alpha\geq 0$ 为参数。需要指出的是，不同于之前ID3和C4.5中剪枝算法的$\alpha$，前者是人为设定的，而此处则是通过计算得到的。
具体地，从整体树$T_0$开始剪枝，如图8-15所示。
对于$T_0$的任意内部节点$t$，以$t$为根节点的子树$T_t$（可以看作剪枝前）的损失函数为
$$ {{C}_{\alpha }}({{T}_{t}})=C({{T}_{t}})+\alpha |{{T}_{t}}|\tag{8-45} $$同时，以$t$为单节点的子树（可以看作剪枝后）的损失函数为
$$ {{C}_{\alpha }}(t)=C(t)+\alpha \cdot 1\tag{8-46} $$(1)当$\alpha=0$或者极小的时候，有不等式
$$ {{C}_{\alpha }}({{T}_{t}})<{{C}_{\alpha }}(t)\tag{8-47} $$不等式成立的原因是因为，当$\alpha=0$或者极小时，起决定作用的是预测误差$C(t)$和$C(T_t)$，而模型越复杂其训练误差总是越小，因此不等式成立。
(2) 当$\alpha$增大时，在某一$\alpha$有
$$ {{C}_{\alpha }}({{T}_{t}})={{C}_{\alpha }}(t)\tag{8-48} $$等式成立的原因是因为，当$\alpha$慢慢增大时，就不能忽略模型复杂度所带来的影响（也就是式(8-45)第2项），所以总会存在一个取值$\alpha$使等式(8-48)成立。
(3) 当$\alpha$再增大时，不等式(8-47)反向。
因此，当$C_{\alpha}(T_t)=C_{\alpha}(t)$时，有$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，此时的子树$T_t$和单节点树$t$有相同的损失函数值，但$t$的节点少且模型更简单，因此$t$比$T_t$更可取，即对$T_t$进行剪枝。
为此，对于决策树$T_0$中每个内部节点$t$来讲，都可以计算
$$ g(t)=\frac{C(t)-C({{T}_{t}})}{|{{T}_{t}}|-1}\tag{8-49} $$它表示剪枝后整体损失函数减少的程度。因为每个$g(t)$背后都对应着一个决策树模型，而不同的$g(t)$则表示损失函数变化的不同程度。接着，在树$T_0$中减去$g(t)$最小的子树$T_t$，将得到的子树作为$T_1$。如此剪枝下去，直到得到根节点。
注意，此时得到的一系列$g(t)$，即$\alpha$，都能使在每种情况下剪枝前和剪枝后的损失值相等，因此按照上面第(2)种情况中的规则进行剪枝，但为什么要减去其中$g(t)$最小的子树呢？
对于树$T$来讲，其内部可能的节点$t$有$t_0$、$t_1$、$t_2$、$t_3$。$t_i$表示其中任意一个，如图8-16所示。
因此便可以计算得到$g(t_0)$、$g(t_1)$、$g(t_2)$、$g(t_3)$，即对应的$\alpha_0$、$\alpha_1$、$\alpha_2$、$\alpha_3$。从上面的第(2)种情况可以知道，$g(t)$是根据式(8-49)所计算得到的，因此这4种情况下$t_i$比$T_{t_i}$更可取，都满足剪枝，但是由于以$t_i$为根节点的子树对应的复杂度各不相同，意味着$\alpha_i\neq \alpha_j,(i,j=0,1,2,3;i\neq j)$，即$\alpha_i$和$\alpha_j$存在着大小关系。又因为，当$\alpha$大的时候，最优子树$T_\alpha$偏小，当$\alpha$小的时候，最优子树$T_\alpha$偏大，并且由于在这4种情况下剪枝前和剪枝后损失值都相等（都满足剪枝条件），因此选择减去其中$g(t)$最小的子树。
接着，在得到子树$T_1$后，再通过上述步骤对$T_1$进行剪枝便可得到$T_2$。如此剪枝下去直到得到根节点，此时便得到了子树序列$T_0$,$T_1$,$T_2$,…，$T_n$。
2). 交叉验证选择最优子树$T_\alpha$
通过上一步我们便可以得到一系列的子树序列$T_0$,$T_1$,…,$T_n$，最后通过交叉验证来选取最优的决策树$T_\alpha$。
进一步，CART分类树的剪枝步骤可以总结为[2]
输入： CART算法生成的分类树$T_0$。
输出： 最优决策树$T_\alpha$。
(1) 设$k=0,T=T_0$。
(2) 设$\alpha=+\infty$。
(3) 对于树$T$来讲，自下而上地对其每个内部节点$t$计算$C(T_t)$、$|T_t|$ 及
$$ g(t)=\frac{C(t)-C({{T}_{t}})}{|{{T}_{t}}|-1},\alpha =\min(\alpha ,g(t))\tag{8-50} $$其中，$T_t$表示以$t$为根节点的子树；$C(T_t)$是子树$T_t$在训练集上的误差；$|T_t|$是子树$T_t$叶节点的个数。
(4) 对$g(t)=\alpha$所对应的内部节点$t$进行剪枝，并对叶节点以多数表决法决定其类别得到树$T$。
(5) 令$k=k+1$，$\alpha_k=\alpha$，$T_k=T$。
(6) 如果$T_k$不是由根节点及两个叶节点构成的树，则继续执行步骤(3)，否则令$T_k=T_n$。
(7) 采用交叉验证在子树序列$T_0$,$T_1$,…,$T_n$中选择最优子树$T_\alpha$。
当然，如果仅看这些步骤可能依旧会很模糊，下面再通过一个简单的图示进行说明。
8.7.5 分类树剪枝示例#
现在假设通过CART算法生成了一棵如图8-17所示的决策树。
从图8-17可以看出，可对树$T_0$进行剪枝的内部节点有$t_0$、$t_1$、$t_2$、$t_3$，因此根据剪枝步骤(3)可以分别算出$g(t_0)$、$g(t_1)$、$g(t_2)$、$g(t_3)$。假设此时算出的$g(t_3)$最小，那么根据剪枝步骤(4)便可以得到如图8-18所示的子树$T_1$，并且$\alpha_1=g(t_3)$。
从图8-18可以看出，根据剪枝步骤(6)可知需要再次对$T_1$进行剪枝，并且此时可对树$T_1$进行剪枝的内部节点有$t_0$、$t_1$、$t_2$。进一步，根据剪枝步骤(3)可以分别算出$g(t_0)$、$g(t_1)$、$g(t_2)$。假设此时算出的$g(t_1)$最小，那么根据剪枝步骤(4)便可以得到如图8-19所示的子树$T_2$，并且$\alpha_2=g(t_1)$。
从图8-19可以看出，根据剪枝步骤(6)可知需要再次对$T_2$进行剪枝，并且此时可对树$T_2$进行剪枝的内部节点有$t_0$和$t_1$。进一步，根据剪枝步骤(3)可以分别算出$g(t_0)$和$g(t_1)$。假设此时算出的$g(t_0)$最小，那么根据剪枝步骤(4)便可以得到如图8-20所示的子树$T_3$，并且$\alpha_3=g(t_0)$。
从图8-20可以看出，根据剪枝步骤(6)可知满足停止条件，所以不需要继续进行剪枝。至此，便得到了整个子树序列$T_0$、$T_1$、$T_2$、$T_3$，接着采用交叉验证在子树序列中选择最优子树$T_\alpha$即可。
到此为止，对于CART决策树的整个生成与剪枝过程就介绍完了。最后，通过sklearn来完成对于CART分类树的使用也很容易，只需将类DecisionTreeClassifier中的划分标准设置为criterion="gini"，其它地方不变。
8.7.6 小结#
在本节中，我们首先介绍了什么是CART算法，然后进一步介绍了CART分类树中的划分标准——基尼不纯度，接着详细介绍了CART分类树的生成过程，并通过一个实际例子展示了整个决策树生成的计算过程，最后介绍了CART分类树剪枝过程的基本原理，并且通过一个简单的图示展示了整个剪枝过程。