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