分类预测-决策树方法33886.pptx

《分类预测-决策树方法33886.pptx》由会员分享，可在线阅读，更多相关《分类预测-决策树方法33886.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/30数据库新技术(数据挖掘)1/344.建立模型之决策树1.分类预测的概念2.什么是决策树什么是决策树3.决策树的核心问题决策树的核心问题决策树的生长，模型建立决策树的生长，模型建立决策树的修剪决策树的修剪4.C5.0算法及其应用实例算法及其应用实例n信息熵和信息增益信息熵和信息增益n修剪算法修剪算法2023/3/30数据库新技术(数据挖掘)2/344.1 分类预测概念n目的（通用）目的（通用）n学习模型建立的算法学习模型建立的算法n了解该算法在相应数据挖掘问题中的应用了解该算法在相应数据挖掘问题中的应用n分类预测的含义分类预测的含义n分类预测算法的类型分类预测算法的类型2023

2、/3/30数据库新技术(数据挖掘)3/344.1 分类预测概念n目的（通用）目的（通用）n分类预测的含义分类预测的含义1.通过对现有数据的学习通过对现有数据的学习建立起拟合数据的模型建立起拟合数据的模型2.利用该模型对未来新数据进行分类，具备预测能力利用该模型对未来新数据进行分类，具备预测能力n分类预测算法的类型分类预测算法的类型2023/3/30数据库新技术(数据挖掘)4/344.1 分类预测概念n目的（通用）目的（通用）n分类预测的含义分类预测的含义n分类预测算法的类型分类预测算法的类型n分析新数据在离散型输出变量上的取值分析新数据在离散型输出变量上的取值分类决策树分类决策树n分析新数据在

3、数值型（连续）输出变量上的取值分析新数据在数值型（连续）输出变量上的取值回归决策树回归决策树2023/3/30数据库新技术(数据挖掘)5/34聚类、分类和模式识别n聚类聚类n子集划分，把一个集合分割为无交集的子集；子集划分，把一个集合分割为无交集的子集；n模式分类模式分类n标识出样本归属的子集（标签）标识出样本归属的子集（标签）n模式识别模式识别n标识出样本对应的个体（样例）本身，或标识出标识出样本对应的个体（样例）本身，或标识出样本所属子集本身（如考古、物种鉴别等）样本所属子集本身（如考古、物种鉴别等）n【注注】样本，只需是个体或集合的特征表示样本，只需是个体或集合的特征表示2023/3/3

4、0数据库新技术(数据挖掘)6/34从二分类问题开始n很多问题可以归结为很多问题可以归结为1.上课、习题，以及考试都不是目的，只是为一个上课、习题，以及考试都不是目的，只是为一个结果：及格？通过？优秀结果：及格？通过？优秀2.看电影：这是好人还是坏人看电影：这是好人还是坏人3.求职：多项测试之后，决定求职：多项测试之后，决定喜欢还是不喜欢？满意还是不满意？喜欢还是不喜欢？满意还是不满意？4.研究方向：研究方向：Major in or out在上述选择过程中，涉及到多个因素，如何在上述选择过程中，涉及到多个因素，如何比较比较不同因素重要性不同因素重要性的差别的差别？2023/3/30数据库新技术(

5、数据挖掘)7/34在“虚度的日子”的判别中最关键的是哪一个因素？n睡眠时间睡眠时间：6/7/8/9/10n成功事例数目成功事例数目：1/2/3n开心指数开心指数：快乐、忧伤、愤怒、平淡、无聊n人际交往人际交往：有成效、封闭n健康指数健康指数：生病、恢复、亚健康、正常n学思比数学思比数：10：1，3：1，2：1，1：22023/3/30数据库新技术(数据挖掘)8/34基于树型结构的排序算法n树中节点的位置的确定和调整是通过对每一个节点中某个特定域的属性值排序决定，n通常，树中节点都具有该属性n二叉排序树二叉排序树n堆排序堆排序n如果树中节点没有现成的公共属性，无法据以比较节点以安排其在生成树中位

6、置，怎么办？2023/3/30数据库新技术(数据挖掘)9/342.什么是决策树n决策树来自决策论,由多个决策分支和可能的结果 （包括资源成本和风险）组成，用来创建到达目标的规划；nA Decision tree is a tree with branching nodes with a choice between two or more choices.n也可以用来表示算法。n分类预测：决策树表示n决策树学习结果：表示为决策树形式的离散值离散值（布尔）函数；nNode,test attributesnBranches,valuesnRoot Node,first attributenLeaf

7、 Nodes,discrete valuesn决策树的表示？2023/3/30数据库新技术(数据挖掘)10/34两类问题两类问题,右图右图IF(Outlook=Sunny)(Humidity=High)THEN PlayTennis=?IF(Outlook=Sunny)(Humidity=Normal)THEN PlayTennis=?两步骤求解过程：两步骤求解过程：Training examples:Day Outlook Temp.Humidity Wind Play TennisD1 Sunny Hot High Weak NoD2 Overcast Hot High Strong Ye

8、s 1.归纳推理求得一般性结论（决策树生成决策树生成学习学习）2.由决策树演绎推理得到新样例对应的结果演绎推理得到新样例对应的结果；OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo2.1 决策树学习决策树学习 和分类预测和分类预测2023/3/30数据库新技术(数据挖掘)11/34决策树生成算法有指导学习n样本数据中既包含输入字段、也包含输出字段n学习阶段，生成决策树模型n基于特定属性值比较，放置样本在生成树上n修剪生成树的特定算法n分类预测阶段，判断分类结果n基于逻辑，即通过对输入字段取值的布尔逻辑比较

9、实现对输出变量的(分类)值的预测2023/3/30数据库新技术(数据挖掘)12/34决策树分类算法基于逻辑n样本数据中既包含输入字段、也包含输出字段n学习阶段，生成决策树模型n分类预测阶段，判断分类结果n基于逻辑，即通过对输入字段取值的布尔逻辑比较基于逻辑，即通过对输入字段取值的布尔逻辑比较实现对输出变量的实现对输出变量的(分类分类)值的预测值的预测n每个叶子节点对应一条推理规则，作为对新的数据每个叶子节点对应一条推理规则，作为对新的数据对象进行分类预测的依据。对象进行分类预测的依据。2023/3/30数据库新技术(数据挖掘)13/343.决策树的核心问题n决策树的生成决策树的生成对训练样本进

10、行分组对训练样本进行分组n关键，确定树根节点和分支准则关键，确定树根节点和分支准则n停止生长时机停止生长时机n决策树的修剪决策树的修剪解决过度拟合问题解决过度拟合问题n预先修剪，限值决策树的充分生长，如：限制树的高度预先修剪，限值决策树的充分生长，如：限制树的高度n滞后修剪，待决策树充分生长完毕后再进行修剪滞后修剪，待决策树充分生长完毕后再进行修剪n当节点和分支数较多时，显然不合适当节点和分支数较多时，显然不合适2023/3/30数据库新技术(数据挖掘)14/343.1 决策树表示法n决策树决策树n通过把样本从根节点排列到通过把样本从根节点排列到某个叶某个叶子节点子节点来分类样本来分类样本n叶

11、子节点即为样本所属的分类n树上每个节点说明了对样本的某个树上每个节点说明了对样本的某个属性的测试属性的测试,如：湿度如：湿度n节点的每个后继分支对应于该属性节点的每个后继分支对应于该属性的一个可能值的一个可能值，Highn决策树代表样本的属性值约束的决策树代表样本的属性值约束的合取的析取式合取的析取式OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo2023/3/30数据库新技术(数据挖掘)15/34OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNo

12、StrongWeakYesNo决策树例图的逻辑表达式n决策树代表实例属性值约束的合取的析取式。n从树根到树叶的每一条路径对应一组属性测试的合取从树根到树叶的每一条路径对应一组属性测试的合取n树本身对应这些合取的析取。树本身对应这些合取的析取。n(Outlook=Sunny Humidity=High)(Outlook=Sunny Humidity=Normal)(Outlook=Overcast)(Outlook=Rain Wind=Weak)(Outlook=Rain Wind=Strong)注意注意：右面的决策树中没有Temperature（温度）属性；而Outlook的属性值有三个。20

13、23/3/30数据库新技术(数据挖掘)16/343.2 决策树学习的适用问题n适用问题的特征适用问题的特征n实例由实例由“属性属性-值值”对表示对表示（传统的数据库记录属性数据库记录属性）n目标函数具有离散的输出值n可能需要析取的描述可能需要析取的描述n训练数据可以包含错误/训练数据可以包含缺少属性值的实例训练数据可以包含缺少属性值的实例n问题举例问题举例n分类问题分类问题n核心任务是把新核心任务是把新(旧旧)样例分派到各可能的离散值对应的类别样例分派到各可能的离散值对应的类别2023/3/30数据库新技术(数据挖掘)17/343.2 决策树方法的适用问题n适用问题的特征适用问题的特征n问题举

14、例问题举例n根据疾病分类患者根据疾病分类患者/根据起因分类设备故障根据起因分类设备故障n根据拖欠支付的可能性根据拖欠支付的可能性分类贷款申请分类贷款申请(是否拒绝是否拒绝)n根据人员分类情形更新数据库记录数据根据人员分类情形更新数据库记录数据创新点？大型稀疏库创新点？大型稀疏库n分类问题分类问题n核心任务是把新核心任务是把新(旧旧)样例分派到各可能的离散值对应的类别样例分派到各可能的离散值对应的类别2023/3/30数据库新技术(数据挖掘)18/344.C5.0算法n大多数决策树学习算法是一种核心算法的变体n采用自顶向下的贪婪搜索采用自顶向下的贪婪搜索 遍历遍历 可能的决策树空间可能的决策树空

15、间nID3 Iterative Dichotomiser 3是这种算法的代表是这种算法的代表,ID3C4.5C5.0n如何安排节点在树中的顺序n树（堆）结构排序，需要树中节点具有相同属性，比较其属性值大小；而后移动节点n如何定义这个可以在决策树中进行比较的属性？换言之，该属性测度如何计算以便于比较？2023/3/30数据库新技术(数据挖掘)19/344.1 ID3算法n算法思想：如何安排节点在树中的顺序如何安排节点在树中的顺序n自顶向下构造决策树n从“哪一个属性将在树的根节点被测试哪一个属性将在树的根节点被测试”开始？使用统计测试统计测试来确定每一个实例属性单独单独分类 训练样例的能力nID3

16、的算法执行过程对样例集合对样例集合S 分类能力分类能力最好的属性属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支训练样例排列到适当的分支n重复上面的过程，直到训练样例被安排到适当的叶子上确定对应的分类2023/3/30数据库新技术(数据挖掘)20/344.1.1 最佳分类属性n信息增益信息增益n用来衡量给定的属性区分训练样例的能力，用来衡量给定的属性区分训练样例的能力，中间（间接）中间（间接）中间（间接）中间（间接）表示属性表示属性表示属性表示属性nID3算法在生成算法在生成 树树 的每一步使用的每一步使用信息增益信息增益从候选属性中从候选属性中选择属性选择属性n用熵

17、度量样例的均一性用熵度量样例的均一性 2023/3/30数据库新技术(数据挖掘)21/344.1.1 最佳分类属性n信息增益信息增益n用熵度量样例的均一性用熵度量样例的均一性n熵刻画了任意样例集合熵刻画了任意样例集合 S 的纯度的纯度n给定包含关于某个目标概念的正反样例的样例集给定包含关于某个目标概念的正反样例的样例集S，那么，那么 S 相对这个布尔型分类（函数）的熵为相对这个布尔型分类（函数）的熵为 n信息论中对熵的一种解释：信息论中对熵的一种解释：熵熵确定了确定了要编码集合要编码集合S中任意中任意成员的分类所需要的最少二进制位数；熵值越大，需要的成员的分类所需要的最少二进制位数；熵值越大，

18、需要的位数越多位数越多。n更一般地，如果目标属性具有更一般地，如果目标属性具有c个不同的值，那么个不同的值，那么 S 相对相对于于c个状态的分类的熵定义为个状态的分类的熵定义为 2023/3/30数据库新技术(数据挖掘)22/344.1.1 最佳分类属性（2）n用信息增益度量熵的降低程度熵的降低程度n属性A 的信息增益，使用属性A分割样例集合S 而导致的熵的降低程度 nGain(S,A)是在知道属性在知道属性A的值后可以节省的二进制位数的值后可以节省的二进制位数n例子，注意是对当前样例集合计算上式2023/3/30数据库新技术(数据挖掘)23/34PlayTennis的14个训练样例DayOu

19、tlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12

20、OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo2023/3/30数据库新技术(数据挖掘)24/34当前样例集合中的最佳分类属性Gain(S,Outlook)=0.246Gain(S,Temperature)=0.0292023/3/30数据库新技术(数据挖掘)25/34然后呢？n类别值较多的输入变量更容易成为当前最佳nGainsR(U,V)=Gains(U,V)/Entropy(V)n是不是再比较剩余的几个信息增益值？n应该怎么办？n注意决策树每个分支上属性间的关系2023/3/30数据库新

21、技术(数据挖掘)26/34根节点的左右孩子顺序全正例、全负例2023/3/30数据库新技术(数据挖掘)27/34用于学习布尔函数的ID3算法概要nID3(Examples,Target_attribute,Attributes)n创建树的root节点，整棵树的指针n如果Examples都为正,返回label=+的单节点树root;%原因在例子中说明n如果Examples都为反,返回label=-的单节点树rootn如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值n否则开始nAAttributes中分类分类exampl

22、es能力最好的属性能力最好的属性nroot的决策属性An对于A的每个可能值vi（当前子树，根节点的每一个孩子节点）（当前子树，根节点的每一个孩子节点）n在root下加一个新的分支对应测试A=vin令Examplesvi为Examples中满足A属性值为vi的子集n如果Examplesvi为空n在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）n结束n返回root2023/3/30数据库新技术(数据挖掘)28/34ID3算法举

23、例nn继续这个过程，直到满足以下两个条件中的任一个n所有的属性已经被这条路经包括n与这个节点关联的所有训练样例都具有相同的目标属性值2023/3/30数据库新技术(数据挖掘)29/34Entropy and Information Gainn这个信息增益到底怎么来的？n在信息论中信息增益是什么含义？n二者存在确定的关系吗？譬如：等价；提示：不是从Y到X的信息增益而是从p(x)p(y)到p(x,y)的信息增益Pattern recognition and machine learningpp:48582023/3/30数据库新技术(数据挖掘)30/34决策树学习中的假设空间搜索n观察ID3的搜索

24、空间和搜索策略，认识到这个算法的优势和不足在假设空间中搜索一个拟合训练样例的最优假设在假设空间中搜索一个拟合训练样例的最优假设假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间，避免（有偏的）不完备假设空间不含目标假设的问题维护单一的当前假设，不顾其它假设，维护单一的当前假设，不顾其它假设，前向策略前向策略不进行回溯，可能收敛到局部最优每一步使用所有的训练样例每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强2023/3/30数据库新技术(数据挖掘)31/34决策树学习的深入话题n决策树学习的实际问题n确定决策树增长的深（确定决策树增长的深（高高）

25、度）度n处理连续值的属性n选择一个适当的属性筛选度量标准选择一个适当的属性筛选度量标准n处理属性值不完整的训练数据n处理不同代价的属性处理不同代价的属性n提高计算效率 http:/ C4.5的修剪算法n滞后修剪滞后修剪n将生成树转换成规则再修剪，自己阅读将生成树转换成规则再修剪，自己阅读n从叶子节点向上逐层修剪从叶子节点向上逐层修剪n误差估计，在训练样本集上估计误差误差估计，在训练样本集上估计误差n通常，估计生成的决策树在测试集上的预测误差通常，估计生成的决策树在测试集上的预测误差n修剪标准修剪标准n修剪示例修剪示例2023/3/30数据库新技术(数据挖掘)33/344.2.1 避免过度拟合数

26、据n过度拟合过度拟合n对于一个假设对于一个假设h，如果存在其他的假设对训练样例的拟合，如果存在其他的假设对训练样例的拟合比它差，但在实例的整个分布上却表现得更好时，我们说比它差，但在实例的整个分布上却表现得更好时，我们说这个假设这个假设h过度拟合训练样例过度拟合训练样例n定义：给定一个假设空间定义：给定一个假设空间H，一个假设，一个假设h H，如果存在其，如果存在其他的假设他的假设h H，使得在训练样例上，使得在训练样例上h的错误率比的错误率比h小，但小，但在整个实例分布上在整个实例分布上h的错误率比的错误率比h小，那么就说假设小，那么就说假设h过度过度拟合训练数据。拟合训练数据。n图图3-6

27、的例子的例子，说明树的尺寸，说明树的尺寸(节点数节点数)对测试精度和训练对测试精度和训练精度的影响精度的影响避免过度拟合必须控制树尺寸避免过度拟合必须控制树尺寸!2023/3/30数据库新技术(数据挖掘)34/34Overfitting2023/3/30数据库新技术(数据挖掘)35/34避免过度拟合必须控制树尺寸nHigh accuracy,small errornLow accuracy,big error2023/3/30数据库新技术(数据挖掘)36/34避免过度拟合数据（2）n导致过度拟合的原因n一种可能原因是训练样例含有随机噪声一种可能原因是训练样例含有随机噪声n当训练数据没有噪声时，

28、过度拟合也有可能发生，当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。好地分割样例，但却与实际的目标函数并无关系。2023/3/30数据库新技术(数据挖掘)37/34避免过度拟合数据（3）n避免过度拟合的方法n及早停止树增长n后修剪法n两种方法的特点n第一种方法更直观，但是精确地估计何时停止树增长很困难n第二种方法被证明在实践中更成功2023/3/30数据库新技术(数据挖掘)38/34避免

29、过度拟合数据（4）n避免过度拟合的关键n使用什么样的准则来计算最终决策树的尺寸n解决方法1.使用与训练样例不同的一套分离的样例来评估通过后修剪方法从树上修剪节点的效用。2.使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。3.使用一个显式的标准来测度训练样例和决策树的编码复杂度，当这个测度最小时停止树增长。2023/3/30数据库新技术(数据挖掘)39/34避免过度拟合数据（5）n方法评述n第一种方法是最普通的，常被称为训练和验证集法n可用的数据分成两个样例集合：n训练集合，形成学习到的假设n验证集合，评估这个假设在后续数据上的

30、精度n方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动n验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。n常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。2023/3/30数据库新技术(数据挖掘)40/344.2.1 C5.0决策树的误差估计1.针对决策树的每个节点，以输出变量的众数类别为预测类别；2.设第i个节点包含Ni个观测样本值，有Ei个预测错误的观测，错误率，即误差3.在误差近似正态分布的假设下，对第i个节点的真实误差 进行区间估计，置信度定位1-，有悲观估计：2023/3/30数据库新技术(数据挖掘)41/344.2.2 C5

31、.0决策树的修剪标准n在误差估计的基础上，依据“减少误差”法判断是否修剪节点；1.计算待剪子树中叶子节点的加权误差2.与父节点的误差进行比较1.父节点的误差较小，则剪掉该子树2.父节点的误差较大，保留该子树2023/3/30数据库新技术(数据挖掘)42/34修剪节点、降低错误率n将树上的每一个节点作为修剪的候选对象将树上的每一个节点作为修剪的候选对象n修剪步骤n删除以此节点为根的子树，使它成为叶结点n把和该节点关联的训练样例的最常见分类赋给它n反复修剪节点，每次总是选取那些删除后可以那些删除后可以最大程度提高决策树在验证集合上的精度的最大程度提高决策树在验证集合上的精度的节点n继续修剪，直到进

32、一步的修剪是有害的为止n数据分成3个子集n训练样例，形成决策树n验证样例，修剪决策树n测试样例，精度的无偏估计n如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪2023/3/30数据库新技术(数据挖掘)43/34（C4.5）规则后修剪n从训练集合生成决策树，尽可能好地拟合训练数据，允许过度拟合发生n将决策树转化为等价的规则集合，对每一条从根节点到叶节点的路径创建一条规则n通过删除（泛化）前件来修剪每一条规则，前提是该删除（泛化）能提高规则的估计精度n按照修剪后的规则的估计精度对规则排序，并按这样的顺序应用这些规则来分类新实例2023/3/30数据库新技术(数据挖掘)44/34(C4.

33、5)规则后修剪n例子n右图的最左一条路径nif(outlook=sunny)(Humidity=High)then PlayTennis=Non考虑删除前件(outlook=sunny)和(Humidity=High)n选择使估计精度有最大提升的步骤n考虑修剪第二个前件2023/3/30数据库新技术(数据挖掘)45/34规则后修剪n规则精度估计方法规则精度估计方法n使用与训练集不相交的验证集使用与训练集不相交的验证集n基于训练集合本身基于训练集合本身n被被C4.5使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置n过程过程n

34、先计算规则在它应用的训练样例上的精度先计算规则在它应用的训练样例上的精度n然后假定此估计精度为二项式分布，并计算它的标准差然后假定此估计精度为二项式分布，并计算它的标准差n对于一个给定的置信区间，采用下界估计作为规则性能的度量对于一个给定的置信区间，采用下界估计作为规则性能的度量n评论评论n对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远越来越远n不是统计有效，但是实践中发现有效不是统计有效，但是实践中发现有效2023/3/30数据库新技术(数据挖掘)46/34规则后修剪n把决策树转化成规则集的好处n可以区分决策节点使用的不同上下文n消除了根节点附近的属性测试和叶节点附近的属性测试的区别n提高了可读性