前面两篇文章分别介绍了用ID3和C4.5这两种算法来生成决策树。其中ID3算法每次用信息增益最大的特征来划分数据集，C4.5算法每次用信息增益比最大的特征来划分数据集。下面介绍另外一种采用基尼指数为标准的划分方法，CART算法。
1. CART算法
分类与回归算法(Classification and Regression Tree,CART)，即可以用于分类也可以用于回归，是应用广泛的决策树学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价与递归地二分每个特征，将输入空间即特征空间划分为有限个单元。
CART算法由以下两步组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量最大；
（2）决策树剪枝：用验证集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝标准。
2. 分类树
在介绍分类树的生成算法前，我们先介绍一下划分标准基尼指数。
2.1 基尼指数
分类问题中，假设由K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：
Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kp2k(2.1)
因此，对于给定的样本集合D，其基尼指数为：
Gini(D)=1−∑k=1K(|Ck||D|)2(2.2)
其中，Ck是D中属于地k类的样本子集，K是类的个数。
如果样本集合D根据特征A是否取某一可能值a被分割成D1,D2两个部分，即
D1={(x,y)∈D|A(x)=a},D2=D−D1
则在特征A的条件下，集合D的基尼指数定义为
Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)(2.3)
基尼指数Gini(D)表示集合D的不确定性，即表示经A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也就越大，这点与熵相似。
下图是基尼指数，熵之半12H(p)和分类误差率之间的关系。横坐标表示概率，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似的表示分类误差率。
2.2 生成算法
输入：训练数据集D，停止计算条件；
输出：CART决策树
根据训练集，从根节点开始，递归地对每个结点进行一下操作，构建二叉决策树：
（1）设结点的训练集为D，利用公式(2.2)计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能的每一个值a，根据样本点对A=a的测试值为“是”或“否”将D分割成D1,D2两个部分，利用公式(2.3)计算A=a时的基尼指数；
（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征最为划分标准将原有数据集划分为两个部分并分配到两个子结点中去。
（3）对两个子结点递归的调用(1),(2)，直到满足停止条件；
（4）生成CART决策树
其中，算法停止计算的条件是：结点中的样本点个数小于预定阈值，或样本集的基尼指数小于预定阈值（也就是说此时样本基本属于同一类），或者没有更多特征。
同样我们还是拿之前的数据集来走一遍生成流程：
ID123456789101112131415年龄青年青年青年青年青年中年中年中年中年中年老年老年老年老年老年有工作否否是是否否否是否否否否是是否有自己的房子否否否是否否否是是是是是否否否贷款情况一般好好一般一般一般好好非常好非常好非常好好好非常好一般类别否否是是否否否是是是是是是是否
用D表示整个数据集，A1,A2,A3,A4，分别依次表示四个特征，用Ai=1,2,3...，表示每个特征的可能取值；如A2=1,A2=2，表示有工作和无工作。
有公式(2.2)可知：
Gini(D)=1−∑k=1K(|Ck||D|)2=1−[(615)2+(915)2]=2×615×915=0.48
由公式(2.3)可知：
Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)
求特征
A1的基尼指数（注意，每次都是将其划分为两部分）：
Gini(D,A1=1)Gini(D,A1=2)Gini(D,A1=3)=515Gini(D1)+1015Gini(D2)=515[2⋅25⋅(1−25)]+1015[2⋅710⋅(1−710)]=0.44=515[2⋅25⋅35]+1015[2⋅410⋅610]=0.48=515[2⋅15⋅45]+1015[2⋅510⋅510]=0.44
求特征A2,A3的基尼指数:
Gini(D,A2=1)Gini(D,A3=1)=515[2⋅55⋅0]+1015[2⋅410⋅610]=0.32=915[2⋅69⋅39]+615[2⋅66⋅0]=0.27
求特征A4的基尼指数:
Gini(D,A4=1)Gini(D,A4=2)Gini(D,A4=3)=515[2⋅15⋅45]+1015[2⋅210⋅810]=0.32=615[2⋅26⋅46]+915[2⋅49⋅59]=0.47=415[2⋅44⋅0]+1115[2⋅511⋅611]=0.36
由以上计算结果我们可以知道，Gini(D,A3=1)=0.27为所有基尼指数中最小者，所有A3=1为最优划分点。于是根结点生成两个子结点，如下：
且我们发现对于“有房子”这个子结点来说，已经满足算法停止条件；所有只需对另外一个子结点继续递归计算每个特征取值情况下的基尼指数即可。并且，最终我们将得到与ID3算法所生成的决策树完全一致。
2.3 剪枝算法
我们知道总体上来说，模型（决策树）越复杂，越容易导致过拟合，此时对应的代价函数值也相对较小。 所以就要进行剪枝处理。CART剪枝算法由两部组成：（1）首先是从之前生成的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子序列{T0,T1,...,Tn}；（2）然后通过交叉验证对这一子序列进行测试，从中选择最优子树。
可以看出，第二步没有什么难点，关键就在于如何来剪枝生成这么一个子序列.
（1）剪枝，形成一个子序列
在剪枝过程中，计算子树的损失函数：
Cα(T)=C(T)+α|T|
其中，T为任意子树，C(T)为对训练集的预测误差，|T|为子树的叶结点个数，α≥0为参数。需要指出的是不同与之前ID3,C4.5中剪枝算法的α，前者是认为给定的，而此处则是算法生成的，具体见后面。
具体地，从整体树T0开始剪枝。对T0的任意内部结点t，以t为根结点子树Tt（也就是剪枝前）的损失函数是
Cα(Tt)=C(Tt)+α|Tt|
以t为单结点树（也就是剪枝后）的损失函数是
Cα(t)=C(t)+α⋅1
①当α=0或者极小的时候，有不等式
Cα(Tt)<Cα(t)
不等式成立的原因是因为，当α=0或者极小的时候，起决定作用的就是预测误差C(t),C(Tt)，而模型越复杂其预测误差总是越小的。
②当α增大时，在某一α有
Cα(Tt)=Cα(t)
等式成立的原因时因为，当α慢慢增大时，就不能忽略模型复杂度所带来的影响（也就是第二项）；但由于剪枝前的模型更为复杂，所以总有个时候，两者会相等。
③当α再增大时，不等式反向。因此，当Cα(Tt)=Cα(t)时，有α=C(t)−C(Tt)|Tt|−1，则Tt,t有相同的损失函数值，而t的结点少，模型更简单，因此t比Tt更可取，对Tt进行剪枝。(注：此时的α时通过Cα(Tt)=Cα(t)计算出来的)
为此，对T0中每一个内部结点t，计算
g(t)=C(t)−C(Tt)|Tt|−1
它表示剪枝后整体损失函数减少的程度。在T0中减去g(t)最小的Tt，将得到的子树作为T1。如此剪枝下去，直到得到根结点。
注意，此时得到的一系列g(t)即α，都能使得在每种情况下剪枝前和剪枝后的损失值相等，因此按照上面第③中情况的规则，肯定是要剪枝的，但为什么是减去其中g(t)最小的呢？如下图：
对于树T来说，其内部可能的结点t有t0,t1,t2,t3；ti表示其中任意一个。因此我们便可以计算得到g(t0),g(t1),g(t2),g(t3)，也即对应的α0,α1,α2,α3。从上面的第③种情况我们可以知道，g(t)是根据Cα(Tt)=Cα(t)推导出来的，因此这四种情况下ti比Tti更可取，都满足剪枝。但是由于以ti为根结点的子树对应的复杂度各不相同，也就意味着αi≠αj,(i,j=0,1,2,3;i≠j),即αi,αj存在这大小关系。又因为我们知道：当α大的时候，最优子树Tα偏小；当α小的时候，最优子树Tα偏大；且子树偏大意味着拟合程度更好。因此，在都满足剪枝的条件下，选择拟合程度更高的子树，当然是最好的选择。
（2）交叉验证选择最优子树Tα
通过第（1）步我们可以得到一系列的子树序列T0,T1,...,Tn,然后运用交叉验证来选取最优决策树Tα
参考：
