大数据经典算法讲解.ppt

《大数据经典算法讲解.ppt》由会员分享，可在线阅读，更多相关《大数据经典算法讲解.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、大数据经典算法讲解大数据经典算法讲解现在学习的是第1页，共22页分类与回归分类与回归分类分类 划分离散变量划分离散变量回归回归划分连续变量划分连续变量现在学习的是第2页，共22页什么是什么是CARTwelcome to use these PowerPoint templates,New Content design,10 years experience分类与回归树分类与回归树CART采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成的决策树是结构简洁的二叉树。现在学习的是第3页，共22页摘要摘要递归划分自变量空间递归划

2、分自变量空间验证数据进行剪枝验证数据进行剪枝模型评价模型评价现在学习的是第4页，共22页Hunt算法算法设Dt是与节点t相关联的训练记录集，y=y1,y2,yc是类标号。Hunt算法的递归定义如下：(1)如果Dt中所有记录都属于同一个类yt，则t是 叶子节点。(2)如果Dt中包含属于多个类的记录，则选择一选择一 个属性测试条件个属性测试条件，将记录划分成较小的子集。对于测试条件的每一个输出创建一个子女结 点，并根据测试结果将Dt中的记录分布到子 女结点中。然后，对于每个子女结点，递归 调用该算法。现在学习的是第5页，共22页一递归划分自变量空间一递归划分自变量空间tid有房者有房者 婚姻状况婚

3、姻状况 年收入年收入 拖欠贷款者拖欠贷款者 1 2 3 4 5 6 7 8 910 是 否 否 是 否 否 是 否 否 否 单身 已婚 单身 已婚 离异 已婚 离异 单身 已婚 单身 125K 100K 70K 120K 95K 60K 220K 85K 75K 90K 否 否 否 否 是 否 否 是 否 是训练集 如何以递归方式建立决策树？如何以递归方式建立决策树？现在学习的是第6页，共22页决策树决策树如何划分训练记录？如何表示属性测试条件？如何确定最佳划分？如何构建测试条件效果最好的树？现在学习的是第7页，共22页如何确定最佳划分如何确定最佳划分贪婪法：根据子女结点类分布的一致性程度来

4、选择最佳划分度量结点的不纯度Gini熵误分类误差 现在学习的是第8页，共22页对于一个给定的结点t：是结点t中类j的相对频率最大值：(1-1/nc)，记录在所有类中等分布最小值：0，所有记录属于同一个类不纯度度量不纯度度量GINI现在学习的是第9页，共22页如何划分训练记录如何划分训练记录根据属性类型的不同：标称属性 序数属性 连续属性根据分割的数量 二元划分 多元化分 如何表示测试条件现在学习的是第10页，共22页选择最佳分割点选择最佳分割点数值型变量数值型变量 对记录的值从小到大排序，计算每个值作为临界点产生对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质

5、性减小程度最大的的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。临界值便是最佳的划分点。分类型变量分类型变量 列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。现在学习的是第11页，共22页有房有房无房无房否否 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.34

6、3现在学习的是第12页，共22页单身单身 已婚已婚离异离异否否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/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.4Gin

7、i(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(t2)=1-(2/4)-(2/4)=0.5Gini=6/100.2778+4/100.5=0.3667现在学习的是第13页，共22页60707585909510012012522055657280879297110122172230030303031221303030303007162534343434435261700.420 0.400 0.375 0.343 0.417 0.400 0

8、.300 0.343 0.375 0.400 0.420是是否否Gini现在学习的是第14页，共22页测试条件效果测试条件效果为确定测试条件划分，比较父节点（划分前）的不纯度和子女结点的不纯度，差越大测试效果就越好 不变值现在学习的是第15页，共22页决策树停止生长条件决策树停止生长条件节点达到完全纯度节点达到完全纯度树的深度达到用户所要的深度树的深度达到用户所要的深度异质性指标下降的最大幅度小于用户指定的幅度异质性指标下降的最大幅度小于用户指定的幅度节点中样本个数少于用户指定个数节点中样本个数少于用户指定个数现在学习的是第16页，共22页决策树决策树(Hunt算法算法)拖欠贷款者=否拖欠贷款

9、者=是拖欠贷款者=否拖欠贷款者=否拖欠贷款者=是有房者婚姻状况拖欠贷款者=否拖欠贷款者=否有房者年收入是是否否单身离异已婚80K80K拖欠贷款者=是拖欠贷款者=否拖欠贷款者=否有房者婚姻状况是否单身离异已婚现在学习的是第17页，共22页剪枝剪枝前剪枝前剪枝：停止生长策略：停止生长策略后剪枝后剪枝：在允许决策树得到最充分生长的基础上，再根据：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。一定的规则，自下而上逐层进行剪枝。当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决现在学习的是第18页，共22页剪枝方法剪枝方法231最小误差剪枝最小误差剪枝代价复杂性代价复杂性 悲观误差剪枝悲观误差剪枝现在学习的是第19页，共22页代价复杂性剪枝代价复杂性剪枝现在学习的是第20页，共22页模型评价模型评价 减少在冒险因素或损失因素方面的不确定性。减少在冒险因素或损失因素方面的不确定性。不仅包括不同模型的比较，而且还要对模型产生不仅包括不同模型的比较，而且还要对模型产生结果的商业价值进行比较。模型评价的角度有：结果的商业价值进行比较。模型评价的角度有：分险分险 收益收益 利润利润现在学习的是第21页，共22页Thank you!现在学习的是第22页，共22页