分类预测-决策树方法

2019/8/29数据库新技术(数据挖掘)1/344.建立模型之决策树1.分类预测的概念2.什么是决策树3.决策树的核心问题①决策树的生长，模型建立②决策树的修剪4.C5.0算法及其应用实例信息熵和信息增益修剪算法2019/8/29数据库新技术(数据挖掘)2/344.1分类预测概念目的（通用）学习模型建立的算法了解该算法在相应数据挖掘问题中的应用分类预测的含义分类预测算法的类型2019/8/29数据库新技术(数据挖掘)3/344.1分类预测概念目的（通用）分类预测的含义1.通过对现有数据的学习建立起拟合数据的模型2.利用该模型对未来新数据进行分类，具备预测能力分类预测算法的类型2019/8/29数据库新技术(数据挖掘)4/344.1分类预测概念目的（通用）分类预测的含义分类预测算法的类型分析新数据在离散型输出变量上的取值分类决策树分析新数据在数值型（连续）输出变量上的取值回归决策树2019/8/29数据库新技术(数据挖掘)5/34聚类、分类和模式识别聚类子集划分，把一个集合分割为无交集的子集；模式分类标识出样本归属的子集（标签）模式识别标识出样本对应的个体（样例）本身，或标识出样本所属子集本身（如考古、物种鉴别等）【注】样本，只需是个体或集合的特征表示2019/8/29数据库新技术(数据挖掘)6/34从二分类问题开始很多问题可以归结为1.上课、习题，以及考试都不是目的，只是为一个结果：及格？通过？优秀2.看电影：这是好人还是坏人3.求职：多项测试之后，决定喜欢还是不喜欢？满意还是不满意？4.研究方向：Majorinorout–在上述选择过程中，涉及到多个因素，如何比较不同因素重要性的差别？2019/8/29数据库新技术(数据挖掘)7/34在“虚度的日子”的判别中最关键的是哪一个因素？睡眠时间：6/7/8/9/10成功事例数目：1/2/3开心指数：快乐、忧伤、愤怒、平淡、无聊人际交往：有成效、封闭健康指数：生病、恢复、亚健康、正常学思比数：10：1，3：1，2：1，1：22019/8/29数据库新技术(数据挖掘)8/34基于树型结构的排序算法树中节点的位置的确定和调整是通过对每一个节点中某个特定域的属性值排序决定，通常，树中节点都具有该属性二叉排序树堆排序如果树中节点没有现成的公共属性，无法据以比较节点以安排其在生成树中位置，怎么办？2019/8/29数据库新技术(数据挖掘)9/342.什么是决策树决策树来自决策论,由多个决策分支和可能的结果（包括资源成本和风险）组成，用来创建到达目标的规划；ADecisiontreeisatreewithbranchingnodeswithachoicebetweentwoormorechoices.也可以用来表示算法。分类预测：决策树表示决策树学习结果：表示为决策树形式的离散值（布尔）函数；Node,testattributesBranches,valuesRootNode,firstattributeLeafNodes,discretevalues决策树的表示？2019/8/29数据库新技术(数据挖掘)10/34•两类问题,右图IF(Outlook=Sunny)^(Humidity=High)THENPlayTennis=?IF(Outlook=Sunny)^(Humidity=Normal)THENPlayTennis=?两步骤求解过程：Trainingexamples:DayOutlookTemp.HumidityWindPlayTennisD1SunnyHotHighWeakNoD2OvercastHotHighStrongYes1.归纳推理求得一般性结论（决策树生成学习）2.由决策树演绎推理得到新样例对应的结果；OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo2.1决策树学习和分类预测2019/8/29数据库新技术(数据挖掘)11/34决策树生成算法——有指导学习样本数据中既包含输入字段、也包含输出字段学习阶段，生成决策树模型基于特定属性值比较，放置样本在生成树上修剪生成树的特定算法分类预测阶段，判断分类结果基于逻辑，即通过对输入字段取值的布尔逻辑比较实现对输出变量的(分类)值的预测2019/8/29数据库新技术(数据挖掘)12/34决策树分类算法——基于逻辑样本数据中既包含输入字段、也包含输出字段学习阶段，生成决策树模型分类预测阶段，判断分类结果基于逻辑，即通过对输入字段取值的布尔逻辑比较实现对输出变量的(分类)值的预测每个叶子节点对应一条推理规则，作为对新的数据对象进行分类预测的依据。2019/8/29数据库新技术(数据挖掘)13/343.决策树的核心问题决策树的生成对训练样本进行分组关键，确定树根节点和分支准则停止生长时机决策树的修剪解决过度拟合问题预先修剪，限值决策树的充分生长，如：限制树的高度滞后修剪，待决策树充分生长完毕后再进行修剪当节点和分支数较多时，显然不合适2019/8/29数据库新技术(数据挖掘)14/343.1决策树表示法决策树通过把样本从根节点排列到某个叶子节点来分类样本叶子节点即为样本所属的分类树上每个节点说明了对样本的某个属性的测试,如：湿度节点的每个后继分支对应于该属性的一个可能值，High决策树代表样本的属性值约束的合取的析取式OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo2019/8/29数据库新技术(数据挖掘)15/34OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo决策树例图的逻辑表达式决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取树本身对应这些合取的析取。(Outlook=Sunny∧Humidity=High)∨(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)∨(Outlook=Rain∧Wind=Strong)注意：右面的决策树中没有Temperature（温度）属性；而Outlook的属性值有三个。2019/8/29数据库新技术(数据挖掘)16/343.2决策树学习的适用问题适用问题的特征实例由“属性-值”对表示（传统的数据库记录属性）目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误/训练数据可以包含缺少属性值的实例问题举例分类问题核心任务是把新(旧)样例分派到各可能的离散值对应的类别2019/8/29数据库新技术(数据挖掘)17/343.2决策树方法的适用问题适用问题的特征问题举例根据疾病分类患者/根据起因分类设备故障根据拖欠支付的可能性分类贷款申请(是否拒绝)根据人员分类情形更新数据库记录数据创新点？大型稀疏库分类问题核心任务是把新(旧)样例分派到各可能的离散值对应的类别2019/8/29数据库新技术(数据挖掘)18/344.C5.0算法大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3IterativeDichotomiser3是这种算法的代表,ID3C4.5C5.0如何安排节点在树中的顺序树（堆）结构排序，需要树中节点具有相同属性，比较其属性值大小；而后移动节点如何定义这个可以在决策树中进行比较的属性？换言之，该属性测度如何计算以便于比较？2019/8/29数据库新技术(数据挖掘)19/344.1ID3算法算法思想：如何安排节点在树中的顺序自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始？使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的算法执行过程①对样例集合S分类能力最好的属性被选作树的根节点②根节点的每个可能值产生一个分支③训练样例排列到适当的分支重复上面的过程，直到训练样例被安排到适当的叶子上确定对应的分类2019/8/29数据库新技术(数据挖掘)20/344.1.1最佳分类属性信息增益用来衡量给定的属性区分训练样例的能力，中间（间接）表示属性ID3算法在生成树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性2019/8/29数据库新技术(数据挖掘)21/344.1.1最佳分类属性信息增益用熵度量样例的均一性熵刻画了任意样例集合S的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类（函数）的熵为信息论中对熵的一种解释：熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数；熵值越大，需要的位数越多。更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为2019/8/29数据库新技术(数据挖掘)22/344.1.1最佳分类属性（2）用信息增益度量熵的降低程度属性A的信息增益，使用属性A分割样例集合S而导致的熵的降低程度Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子，注意是对当前样例集合计算上式()(,)()()vvvValuesASGainSAEntropySEntropySS2019/8/29数据库新技术(数据挖掘)23/34PlayTennis的14个训练样例DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo2019/8/29数据库新技术(数据挖掘)24/34当前样例集合中的最佳分类属性Gain(S,Outlook)=0.246Gain(S,Temperature)=0.0292019/8/29数据库新技术(数据挖掘)25/34然后呢？类别值较多的输入变量更容易成为当前最佳GainsR(U,V)=Gains(U,V)/Entropy(V)是不是再比较剩余的几个信息增益值？应该怎么办？注意决策树每个分支上属性间的关系2019/8/29数据库新技术(数据挖掘)26/34根节点的左右孩子顺序全正例、全负例2019/8/29数据库新技术(数据挖掘)27/34用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点，整棵树的指针如果Examples都为正,返回label=+的单节点树root;%原因在例子中说明如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi（当前子树，根节点的每一个孩子节点）在root下加一个新的分支对应测试A=vi令Examplesvi