大数据经典算法讲解

大数据经典算法讲解第1页，共22页，2023年，2月20日，星期四分类与回归分类——划分离散变量回归——划分连续变量第2页，共22页，2023年，2月20日，星期四什么是CARTwelcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience分类与回归树CART采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成的决策树是结构简洁的二叉树。第3页，共22页，2023年，2月20日，星期四摘要递归划分自变量空间验证数据进行剪枝模型评价第4页，共22页，2023年，2月20日，星期四Hunt算法设Dt是与节点t相关联的训练记录集，y={y1,y2,…,yc}是类标号。Hunt算法的递归定义如下：(1)如果Dt中所有记录都属于同一个类yt，则t是叶子节点。(2)如果Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每一个输出创建一个子女结点，并根据测试结果将Dt中的记录分布到子女结点中。然后，对于每个子女结点，递归调用该算法。第5页，共22页，2023年，2月20日，星期四一递归划分自变量空间tid有房者婚姻状况年收入拖欠贷款者12345678910是否否是否否是否否否单身已婚单身已婚离异已婚离异单身已婚单身125K100K70K120K95K60K220K85K75K90K否否否否是否否是否是训练集

如何以递归方式建立决策树？第6页，共22页，2023年，2月20日，星期四决策树如何划分训练记录？

如何表示属性测试条件？

如何确定最佳划分？如何构建测试条件效果最好的树？第7页，共22页，2023年，2月20日，星期四如何确定最佳划分贪婪法：根据子女结点类分布的一致性程度来选择最佳划分度量结点的不纯度Gini熵误分类误差第8页，共22页，2023年，2月20日，星期四对于一个给定的结点t：是结点t中类j的相对频率最大值：(1-1/nc)，记录在所有类中等分布最小值：0，所有记录属于同一个类不纯度度量——GINI第9页，共22页，2023年，2月20日，星期四如何划分训练记录

根据属性类型的不同：

标称属性

序数属性

连续属性根据分割的数量

二元划分

多元化分如何表示测试条件第10页，共22页，2023年，2月20日，星期四选择最佳分割点数值型变量对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。分类型变量

列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。第11页，共22页，2023年，2月20日，星期四有房无房否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.343第12页，共22页，2023年，2月20日，星期四单身已婚离异否241是201单身或已婚离异否61是21单身或离异已婚否34是30离异或已婚单身否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/10×0.5+4/10×0+2/10×0.5=0.3Gini(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.3667第13页，共22页，2023年，2月20日，星期四60707585909510012012522055657280879297110122172230≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>030303031221303030303007162534343434435261700.4200.4000.3750.3430.4170.4000.3000.3430.3750.4000.420是否Gini第14页，共22页，2023年，2月20日，星期四测试条件效果为确定测试条件划分，比较父节点（划分前）的不纯度和子女结点的不纯度，差越大测试效果就越好

不变值第15页，共22页，2023年，2月20日，星期四决策树停止生长条件节点达到完全纯度树的深度达到用户所要的深度异质性指标下降的最大幅度小于用户指定的幅度节点中样本个数少于用户指定个数第16页，共22页，2023年，2月20日，星期四决策树(Hunt算法)拖欠贷款者=否拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否拖欠贷款者=是有房者婚姻状况拖欠贷款者=否拖欠贷款者=否有房者年收入是是否否单身离异已婚<80K≥80K拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否有房者婚姻状况是否单身离异已婚第17页，共22页，2023年，2月20日，星期四剪枝前剪枝：停止生长策略后剪枝：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决第18页，共22页，2023年，2月20日，星期四剪枝方法231最小误差剪枝代价复杂性

悲观误差剪枝第19页，共22页，2023年，2月20日，星期四代价复杂性剪枝第20页，共22页，2023年，2月20日，星期四模型评价

减少在冒险因素或损失因素方面的不确定性。不仅包括不同模型的比较，而且还