姓名：崔升 学号：14020120005
转载自：http://www.cnblogs.com/en-heng/p/5173704.html
【嵌牛导读】：
分类与回归树（Classification and Regression Trees, CART）是由四人帮Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone于1984年提出，既可用于分类也可用于回归。本文将主要介绍用于分类的CART。CART被称为数据挖掘领域内里程碑式的算法。
【嵌牛鼻子】：经典大数据算法之CART算法的简单介绍
【嵌牛提问】：CART是一种怎么的算法，其数学原理又是如何？
【嵌牛正文】：
1. 前言
不同于C4.5，CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树），并能够对标量属性（nominal attribute）与连续属性（continuous attribute）进行分裂。
2. CART生成
前一篇提到过决策树生成涉及到两个问题：如何选择最优特征属性进行分裂，以及停止分裂的条件是什么。
特征选择
CART对特征属性进行二元分裂。特别地，当特征属性为标量或连续时，可选择如下方式分裂：
An instance goes left if CONDITION, and goes right otherwise
即样本记录满足CONDITION则分裂给左子树，否则则分裂给右子树。
标量属性
进行分裂的CONDITION可置为不等于属性的某值；比如，标量属性Car Type取值空间为{Sports, Family, Luxury}，二元分裂与多路分裂如下：
连续属性
CONDITION可置为不大于εε；比如，连续属性Annual Income，εε取属性相邻值的平均值，其二元分裂结果如下：
接下来，需要解决的问题：应该选择哪种特征属性及定义CONDITION，才能分类效果比较好。CART采用Gini指数来度量分裂时的不纯度，之所以采用Gini指数，是因为较于熵而言其计算速度更快一些。对决策树的节点tt，Gini指数计算公式如下：
Gini(t)=1−∑k[p(ck|t)]2(1)(1)Gini(t)=1−∑k[p(ck|t)]2
Gini指数即为11与类别ckck的概率平方之和的差值，反映了样本集合的不确定性程度。Gini指数越大，样本集合的不确定性程度越高。分类学习过程的本质是样本不确定性程度的减少（即熵减过程），故应选择最小Gini指数的特征分裂。父节点对应的样本集合为DD，CART选择特征AA分裂为两个子节点，对应集合为DLDL与DRDR；分裂后的Gini指数定义如下：
G(D,A)=|DL||D|Gini(DL)+|DR||D|Gini(DR)(2)(2)G(D,A)=|DL||D|Gini(DL)+|DR||D|Gini(DR)
其中，|⋅||⋅|表示样本集合的记录数量。如上图中的表格所示，当Annual Income的分裂值取87时，则Gini指数计算如下：
410[1−(14)2−(34)2]+610[1−(26)2−(46)2]=0.417410[1−(14)2−(34)2]+610[1−(26)2−(46)2]=0.417
CART算法
CART算法流程与C4.5算法相类似：
若满足停止分裂条件（样本个数小于预定阈值，或Gini指数小于预定阈值（样本基本属于同一类，或没有特征可供分裂），则停止分裂；
否则，选择最小Gini指数进行分裂；
递归执行1-2步骤，直至停止分裂。
3. CART剪枝
CART剪枝与C4.5的剪枝策略相似，均以极小化整体损失函数实现。同理，定义决策树TT的损失函数为：
Lα(T)=C(T)+α|T|(3)(3)Lα(T)=C(T)+α|T|
其中，C(T)C(T)表示决策树的训练误差，αα为调节参数，|T||T|为模型的复杂度。
CART算法采用递归的方法进行剪枝，具体办法：
将αα递增0=α0<α1<α2<⋯<αn0=α0<α1<α2<⋯<αn，计算得到对应于区间[αi,αi+1)[αi,αi+1)的最优子树为TiTi；
从最优子树序列{T1,T2,⋯,Tn}{T1,T2,⋯,Tn}选出最优的（即损失函数最小的）。
如何计算最优子树为TiTi呢？首先，定义以tt为单节点的损失函数为
Lα(t)=C(t)+αLα(t)=C(t)+α
以tt为根节点的子树TtTt的损失函数为
Lα(Tt)=C(Tt)+α|Tt|Lα(Tt)=C(Tt)+α|Tt|
令Lα(t)=Lα(Tt)Lα(t)=Lα(Tt)，则得到
α=C(t)−C(Tt)|Tt|−1α=C(t)−C(Tt)|Tt|−1
此时，单节点tt与子树TtTt有相同的损失函数，而单节点tt的模型复杂度更小，故更为可取；同时也说明对节点tt的剪枝为有效剪枝。由此，定义对节点tt的剪枝后整体损失函数减少程度为
g(t)=C(t)−C(Tt)|Tt|−1g(t)=C(t)−C(Tt)|Tt|−1
剪枝流程如下：
对输入决策树T0T0，自上而下计算内部节点的g(t)g(t)；选择最小的g(t)g(t)作为α1α1，并进行剪枝得到树T1T1，其为区间[α1,α2)[α1,α2)对应的最优子树。
对树T1T1，再次自上而下计算内部节点的g(t)g(t)；……α2α2……T2T2……
如此递归地得到最优子树序列，采用交叉验证选取最优子树。
关于CART剪枝算法的具体描述请参看[1]，其中关于剪枝算法的描述有误：
(6)如果T不是由根节点单独构成的树，则回到步骤(4)
应改为回到步骤(3)，要不然所有αα均一样了。
4. 参考资料
[1] 李航，《统计学习方法》.
[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar,Introduction to Data Mining.
[3] Dan Steinberg, The Top Ten Algorithms in Data Mining.
网友评论