大数据经典算法CART 讲解PPT课件

.,(第四组)分类与回归树算法(CART),.,分类与回归,分类划分离散变量,回归划分连续变量,.,什么是CART,welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience,CART采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成的决策树是结构简洁的二叉树。,.,摘要,递归划分自变量空间,验证数据进行剪枝,模型评价,.,Hunt算法,设Dt是与节点t相关联的训练记录集，y=y1,y2,yc是类标号。Hunt算法的递归定义如下：(1)如果Dt中所有记录都属于同一个类yt，则t是叶子节点。(2)如果Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每一个输出创建一个子女结点，并根据测试结果将Dt中的记录分布到子女结点中。然后，对于每个子女结点，递归调用该算法。,.,一递归划分自变量空间,训练集,如何以递归方式建立决策树？,.,决策树,如何划分训练记录？如何表示属性测试条件？如何确定最佳划分？如何构建测试条件效果最好的树？,.,如何确定最佳划分,贪婪法：根据子女结点类分布的一致性程度来选择最佳划分度量结点的不纯度Gini熵误分类误差,.,对于一个给定的结点t：是结点t中类j的相对频率最大值：(1-1/nc)，记录在所有类中等分布最小值：0，所有记录属于同一个类,不纯度度量GINI,.,如何划分训练记录,根据属性类型的不同：标称属性序数属性连续属性根据分割的数量二元划分多元化分,如何表示测试条件,.,选择最佳分割点,数值型变量,对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。,分类型变量,列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。,.,Gini(t1)=1-(3/3)-(0/3)=0Gini(t2)=1-(4/7)-(3/7)=0.4849Gini=0.30+0.70.4898=0.343,.,Gini(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.3,Gini(t1)=1-(6/8)-(2/8)=0.375Gini(t2)=1-(1/2)-(1/2)=0.5Gini=8/100.375+2/100.5=0.4,Gini(t1)=1-(3/6)-(3/6)=0.5Gini(t2)=1-(4/4)-(0/4)=0Gini=6/100.5+4/100=0.3,Gini(t1)=1-(5/6)-(1/6)=0.2778Gini(t2)=1-(2/4)-(2/4)=0.5Gini=6/100.2778+4/100.5=0.3667,.,.,测试条件效果,为确定测试条件划分，比较父节点（划分前）的不纯度和子女结点的不纯度，差越大测试效果就越好不变值,.,决策树停止生长条件,节点达到完全纯度,树的深度达到用户所要的深度,异质性指标下降的最大幅度小于用户指定的幅度,节点中样本个数少于用户指定个数,.,决策树(Hunt算法),拖欠贷款者=否,拖欠贷款者=是,拖欠贷款者=否,拖欠贷款者=否,拖欠贷款者=是,有房者,婚姻状况,拖欠贷款者=否,拖欠贷款者=否,有房者,年收入,是,是,否,否,单身离异,已婚,80K,80K,拖欠贷款者=是,拖欠贷款者=否,拖欠贷款者=否,有房者,婚姻状况,是,否,单身离异,已婚,.,剪枝,前剪枝：停止生长策略,后剪枝：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。,当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决,.,剪枝方法,2,3,1,最小误差剪枝,代价复杂性,悲观误差剪枝,.,代价复杂性剪枝,.