数据挖掘算法CART

1、1.数据挖掘算法-CART分类与回归树(ClassificationandRegressionTrees,CART)是由四人帮LeoBreiman,JeromeFriedman,RichardOlshen与CharlesStone于1984年提出，既可用于分类也可用于回归。本文将主要介绍用于分类的CART。CART被称为数据挖掘领域内里程碑式的算法。不同于C4.5,CART本质是对特征空间进行二元划分(即CART生成的决策树是一棵二叉树)，并能够对标量属性(nominalattribute)与连续属性(continuousattribute)进行分裂。前一篇提到过决策树生成涉及到两个问题：如何

2、选择最优特征属性进行分裂，以及停止分裂的条件是什么。CART对特征属性进行二元分裂。特别地，当特征属性为标量或连续时，可选择如下方式分裂:AninstancegoesleftifCONDITION,andgoesrightotherwise即样本记录满足CONDITION则分裂给左子树，否则则分裂给右子树。标量属性，二元分裂与多路分裂如下:进行分裂的CONDITION可置为；比如，标量属性取值空间为F&tni忙LuKUty-CdCarTypeSports,LuxuryF&mily卜g1Cl73Gini(CarType)Sports,JLuxuryCarTVpieSportsFflmily,Lu

3、xuiryCD2C1010Gini0.167CarTypeFaniltySportsLunjryCD181Cl307Gini0J3连续属性CONDITION可置为不大于;比如，连续属性AnnualIncomd,取属性相邻值的平均值，其二元分裂结果如下：接下来，需要解决的问题：应该选择哪种特征属性及定义CONDITION，才能分类效果比较好。CART采用Gini指数来度量分裂时的不纯度，之所以采用Gini指数，是因为较于熵而言其计算速度更快一些。对决策树的节点t,Gini指数计算公式如下：Gmi(t)-1-为風站尸Gini(t)=1-Ikp(ck|t)2(1)Gini指数即为1与类别ck的概率平

4、方之和的差值，反映了样本集合的不确定性程度。Gini指数越大，样本集合的不确定性程度越高。分类学习过程的本质是样本不确定性程度的减少(即熵减过程)，故应选择最小Gini指数的特征分裂。父节点对应的样本集合为D,CART选择特征A分裂为两个子节点，对应集合为DL与Dr;分裂后的Gini指数定义如下：A)=惜忘诫氐)+G(D,A)=|Dl|D|Gini(DL)+|Dr|D|Gini(Dr)(2)其中，|表示样本集合的记录数量。CART算法流程与C45算法相类似:若满足停止分裂条件(样本个数小于预定阈值，或Gini指数小于预定阈值(样本基本属于同一类，或没有特征可供分裂)，则停止分裂；否则，选择最小

5、Gini指数进行分裂；递归执行1-2步骤，直至停止分裂。CART剪枝与C4.5的剪枝策略相似，均以极小化整体损失函数实现。同理，定义决策树T的损失函数为：2(f)=cm+o|T|(3)L(T)=C(T)+a|T|(3)a其中，C(T)表示决策树的训练误差，a为调节参数，|T|为模型的复杂度。CART算法采用递归的方法进行剪枝，具体办法：将a递增0=a0a1a2-an,计算得到对应于区间%5+1)的最优子树为T；从最优子树序列T,T2,TJ选出最优的(即损失函数最小的)。如何计算最优子树为Ti呢？首先，定义以t为单节点的损失函数为La(t)=C(t)+a以t为根节点的子树Tt的损失函数为La(T

6、t)=C(Tt)+a|Tt|令La(t)=La(Tt)，则得到理)-g),11-1a=C(t)-C(Tt)|Tt|-1此时，单节点t与子树Tt有相同的损失函数，而单节点t的模型复杂度更小，故更为可取；同时也说明对节点t的剪枝为有效剪枝。由此，定义对节点t的剪枝后整体损失函数减少程度为g(t)=C(t)-C(Tt)|Tt|-1N-i剪枝流程如下:对输入决策树T0,自上而下计算内部节点的g(t);选择最小的g(t)作为a1，并进行剪枝得到树匚，其为区间a1,a2)对应的最优子树。对树T1，再次自上而下计算内部节点的g(t)；.a2.T2.如此递归地得到最优子树序列，采用交叉验证选取最优子树。关于CART剪枝算法的具体描述请参看1，其中关于剪枝算法的描述有误：回到步骤(3)|(6)如果T不是由根节点单独构成的树，则回至I步骤(4)应改为回到步骤，要不然所有a均一样了。4.参考资料李航，统计学习方法.Pang-NingTa