经典算法CART

1、分类与回归分类与回归分类分类 划分离散变量划分离散变量回归回归划分连续变量划分连续变量welcome to use these PowerPoint templates, New Content design, 10 years experience分类与回归树分类与回归树CART采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成的决策树是结构简洁的二叉树。 分类回归树是一棵二叉树，且每个非叶子节点都有两个孩子，所以对于第一棵子树其叶子节点数比非叶子节点数多1。上例属性有上例属性有8个，每个属性又有多少离散的值可取。个，每

2、个属性又有多少离散的值可取。在决策树的每一个节点上我们可以按任一个属性在决策树的每一个节点上我们可以按任一个属性的任一个值进行划分。比如最开始我们按：的任一个值进行划分。比如最开始我们按： 1）表面覆盖为毛发和非毛发）表面覆盖为毛发和非毛发 2）表面覆盖为鳞片和非鳞片）表面覆盖为鳞片和非鳞片 3）体温为恒温和非恒温）体温为恒温和非恒温等等产生当前节点的左右两个孩子。等等产生当前节点的左右两个孩子。按哪种划分最好呢？按哪种划分最好呢？有有3个标准可以用来衡量划分的好坏：个标准可以用来衡量划分的好坏：GINI指数、双指数、双化指数、有序双化指数。化指数、有序双化指数。 体温为非恒温时包含爬行类3个

3、、鱼类3个、两栖类2个,则 体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个,则 所以如果按照“体温为恒温和非恒温”进行划分的话，我们得到GINI的增益（类比信息增益）： 最好的划分就是使得GINI_Gain最小的划分。终止条件终止条件 一个节点产生左右孩子后，递归地对左右孩子进行划分即可产生分类回归树。这里的终止条件是什么？什么时候节点就可以停止分裂了？直观的情况，当节点包含的数据记录都属于同一个类别时就可以终止分裂了。这只是一个特例，更一般的情况我们计算2值来判断分类条件和类别的相关程度，当2很小时说明分类条件和类别是独立的，即按照该分类条件进行分类是没有道理的，此时节点停止分裂。注意这

4、里的“分类条件”是指按照GINI_Gain最小原则得到的“分类条件”。如何确定叶子节点的类？如何确定叶子节点的类？ 前面提到Tree-Growth终止的方式有2种，对于第一种方式，叶子节点覆盖的样本都属于同一类，那么这种情况下叶子节点的类自然不必多言。对于第二种方式，叶子节点覆盖的样本未必属于同一类，直接一点的方法就是，该叶子节点所覆盖的样本哪个类占大多数，那么该叶子节点的类别就是那个占大多数的类。如何划分训练记录？ 如何表示属性测试条件？ 如何确定最佳划分？如何构建测试条件效果最好的树？贪婪法：根据子女结点类分布的一致性程度来 选择最佳划分度量结点的不纯度Gini熵误分类误差 对于一个给定的

5、结点t： 是结点t中样本输出取类别j的概率最大值：(1 - 1/nc)，记录在所有类中等分布最小值：0，所有记录属于同一个类2)(1)(jt jptGINI)( t jp如何划分训练记录根据属性类型的不同： 标称属性 序数属性 连续属性根据分割的数量 二元划分 多元化分 选择最佳分割点选择最佳分割点数值型变量数值型变量 对记录的值从小到大排序，计算每个值作为临界点对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。度最大的临界值便是最佳的划分点。分类型变量分类型变量 列出划分为两

6、个子集的所有可能组合，计算每种组合下列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。的组合作为最佳划分点。有房有房无房无房否否 3 4是是 0 3Gini(t1)=1-(3/3)-(0/3)=0Gini(t2)=1-(4/7)-(3/7)=0.4849Gini=0.30+0.70.4898=0.343单身单身 已婚已婚离异离异否否241是是201单身或已婚单身或已婚 离异离异否否 61是是 21单身或离异单身或离异 已婚已婚否否 34是是 30离异或已婚离异或已婚 单身单身

7、否否52是是12Gini(t1)=1-(2/4)-(2/4)=0.5Gini(t2)=1-(0/4)-(4/4)=0Gini(t3)=1-(1/2)-(1/2)=0.5Gini=4/100.5+4/100+2/100.5=0.3Gini(t1)=1-(6/8)-(2/8)=0.375Gini(t2)=1-(1/2)-(1/2)=0.5Gini=8/100.375+2/100.5=0.4Gini(t1)=1-(3/6)-(3/6)=0.5Gini(t2)=1-(4/4)-(0/4)=0Gini=6/100.5+4/100=0.3Gini(t1)=1-(5/6)-(1/6)=0.2778Gini(

8、t2)=1-(2/4)-(2/4)=0.5Gini=6/100.2778+4/100.5=0.366760707585909510012012522055657280879297110122172230030303031221303030303007162534343434435261700.420 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400 0.420是是否否Gini测试条件效果测试条件效果 为确定测试条件划分，比较父节点（划分前）的不纯度和子女结点的不纯度，差越大测试效果就越好 不变值决策树停止生长条件决策树停止生长条件节点达

9、到完全纯度节点达到完全纯度树的深度达到用户所要的深度树的深度达到用户所要的深度异质性指标下降的最大幅度小于用户指定的幅度异质性指标下降的最大幅度小于用户指定的幅度节点中样本个数少于用户指定个数节点中样本个数少于用户指定个数拖欠贷款者=否拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否拖欠贷款者=是有房者婚姻状况拖欠贷款者=否拖欠贷款者=否有房者年收入是是否否单身离异已婚80K80K拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否有房者婚姻状况是否单身离异已婚剪枝剪枝前剪枝前剪枝：停止生长策略：停止生长策略后剪枝后剪枝：在允许决策树得到最充分生长的基础上，：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。再根据一定的规则，自下而上逐层进行剪枝。当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决剪枝方法剪枝方法231最小误差剪枝最小误差剪枝代价复杂性代价复杂性 悲观误差剪枝悲观误差剪枝代价复杂性剪枝代价复杂性剪