第四章:决策树
第四章：决策树
大纲 口基本流程 口划分选择 口剪枝处理 口连续与缺失值 多变量决策树
大纲 基本流程 划分选择 剪枝处理 连续与缺失值 多变量决策树
基本流程 决策树基于树结构来进行预测 色泽=? 青绿 根蒂= 蜷缩 敲声 浊响 好瓜
基本流程 决策树基于树结构来进行预测 色泽=? 根蒂=? 敲声=? 好瓜 青绿 蜷缩 浊响 …... … …... … …... …
基本流程 口决策过程中提出的每个判定问题都是对某个属性的“测试” 口决策过程的最终结论对应了我们所希望的判定结果 口每个测试的结果或是导出最终结论,或者导出进一步的判定问题, 其考虑范围是在上次决策结果的限定范围之内 口从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强, 即处理未见示例能力强的决策树
基本流程 决策过程中提出的每个判定问题都是对某个属性的“测试” 决策过程的最终结论对应了我们所希望的判定结果 每个测试的结果或是导出最终结论，或者导出进一步的判定问题， 其考虑范围是在上次决策结果的限定范围之内 从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强， 即处理未见示例能力强的决策树
基本流程 Algorithn1决策树学习基本算法 输入: 训练集D={(x1,v1),…,(xm,ym)} 属性集A={a1,…,a} 过程:函数 TreeGenerate(D,A) 1:生成结点node (1)当前结点包含的 2:ifD中样本全属于同一类别 C then 样本全部属于同一类 3将mode标记为C类叶结点; return 别 5:ifA=0ORD中样本在A上取值相同then 6将node标记叶结点,其类别标记为D中样本数最多的类 return (2)当前属性集为空, 7: end if 或所有样本在所有属 8:从A中选择最优划分属性an; 性上取值相同 9:fora,的每一个值ado 10:为node生成每一个分枝;令D,表示D中在a,上取值为a"的样本子集; 11ifD,为空then 12将分枝结点标记为叶结点,其类别标记为D中样本最多的类: return 3)当前结点包含的 13. else 样本集合为空 14:以 TreeGeneratel(D,A-{a})为分枝结点 15: end if 16: end for 输出:以node为根结点的一棵决策树
基本流程 （1）当前结点包含的 样本全部属于同一类 别 （2）当前属性集为空， 或所有样本在所有属 性上取值相同 （3）当前结点包含的 样本集合为空