CART算法

Page1CARTClassificationandRegressionTreeVeyron2014/06/06Page2ID3算法（IterativeDichotomiser3---迭代二叉树3代）是一个由RossQuinlan发明的用于决策树的算法。Page3CART是1984年由Breiman,Friedman,Olshen,Stone提出的一个决策树算法随机森林是通过将很多的决策树组合而成的,随机森林采用CART算法Gini系数是Breiman于1984年提出来的，主要用在CART(ClassficationandRegressionTree)算法中Page4基尼指标在CART算法中,基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。假设y的可能取值为{1,2,...,m},令fi是样本被赋予i的概率，则基尼指数可以通过如下计算：Page5Gini指标(Giniindex)Gini指标用来度量数据集的不纯度：Gini越小，数据越纯CART中计算Gini指标考虑每个属性上的二元划分，根据训练数据集S中的属性F将S分成的S1和S2，则给定划分的Gini指标如下公式所示：最小化Gini指标21()1CiiiGiniSpSi其中，p是中类别的概率1212||||()()()FSSGiniSGiniSGiniSSSPage6选择最佳分割点数值型变量：对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。分类型变量：列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。最好的划分就是使得GINI最小的划分。Page7一递归划分自变量空间Num有房者婚姻状况年收入拖欠贷款者12345678910是否否是否否是否否否单身已婚单身已婚离异已婚离异单身已婚单身125K100K70K120K95K60K220K85K75K90K否否否否是否否是否是Page8有房无房否34是03Gini(t1)=1-(3/3)²-(0/3)²=0Gini(t2)=1-(4/7)²-(3/7)²=0.4849Gini=0.3×0+0.7×0.4898=0.343Page9对离散值如{x,y,z}，则在该属性上的划分有三种情况({{x,y},{z}},{{x,z},y},{{y,z},x})，空集和全集的划分除外Page10单身或已婚离异否61是21单身或离异已婚否34是30离异或已婚单身否52是12Gini(t1)=1-(6/8)²-(2/8)²=0.375Gini(t2)=1-(1/2)²-(1/2)²=0.5Gini=8/10×0.375+2/10×0.5=0.4Gini(t1)=1-(3/6)²-(3/6)²=0.5Gini(t2)=1-(4/4)²-(0/4)²=0Gini=6/10×0.5+4/10×0=0.3Gini(t1)=1-(5/6)²-(1/6)²=0.2778Gini(t2)=1-(2/4)²-(2/4)²=0.5Gini=6/10×0.2778+4/10×0.5=0.3667Page11607075859095100120125220657280879297110122172≤≤≤≤≤≤≤≤≤0303031221303030301625343434344352610.4000.3750.3430.4170.4000.3000.3430.3750.400是否Gini对于连续值处理引进“分裂点”的思想，假设样本集中某个属性共n个连续值，则有n-1个分裂点，每个“分裂点”为相邻两个连续值的均值(a[i]+a[i+1])/2。Page12决策树拖欠贷款者=否拖欠贷款者=否拖欠贷款者=是拖欠贷款者=是拖欠贷款者=否有房者婚姻状况拖欠贷款者=否拖欠贷款者=否有房者年收入是是否否单身离异已婚97K≥97K拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否有房者婚姻状况是否单身离异已婚Page13C4.5算法和CART算法的优缺点优点缺点C4.5算法1)用信息增益率来选择属性2)在树构造过程中进行剪枝3)能够完成对连续属性的离散化处理4)能够对不完整数据进行处理在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效CART算法1)对目标变量及预测变量概率分布上要求2)使用二元分支，充分运用全部的数据，尽可能发现全部树的结构3)能够处理孤立点4)能够对空缺值进行处理CART本身是一种大样本的统计分析方法,样本量较小时模型不稳定Page14