文档介绍:Date: 2/25/2017 File: ML1. 1 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 第3章决策树学****Decision-Tree Algorithm) Date: 2/25/2017 File: ML1. 2 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 概论?决策树学****是应用最广的归纳推理算法之一?是一种逼近离散值函数的方法?很好的健壮性?能够学****析取表达式? ID3, Assistant, ?搜索一个完整表示的假设空间?归纳偏置是优先选择较小的树?决策树表示了多个 if-then 规则 Date: 2/25/2017 File: ML1. 3 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 提纲?决策树定义?适用问题特征?基本 ID3 算法?决策树学****的归纳偏置?训练数据的过度拟合?更深入的话题 Date: 2/25/2017 File: ML1. 4 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 决策树表示法?决策树–通过把实例从根节点排列到某个叶子节点来分类实例。–叶子节点即为实例所属的分类–树上每个节点说明了对实例的某个属性的测试–节点的每个后继分支对应于该属性的一个可能值?图 3-1 ?决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取, 树本身对应这些合取的析取。 Date: 2/25/2017 File: ML1. 5 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering (Outlook=Sunny ∧ Humidity= Normal) ∨(Outlook =Overcast) ∨ (Outlook=Rain ∧ Wind=Weak) Decision Tree for PlayTennis Date: 2/25/2017 File: ML1. 6 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 决策树学****的适用问题?适用问题的特征–实例由“属性-值”对表示–目标函数具有离散的输出值–可能需要析取的描述–训练数据可以包含错误–训练数据可以包含缺少属性值的实例?问题举例–根据疾病分类患者–根据起因分类设备故障–根据拖欠支付的可能性分类贷款申请?分类问题–核心任务是把样例分类到各可能的离散值对应的类别 Date: 2/25/2017 File: ML1. 7 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 基本的决策树学****算法?大多数决策树学****算法是一种核心算法的变体?采用自顶向下的贪婪搜索遍历可能的决策树空间? ID3 是这种算法的代表 Date: 2/25/2017 File: ML1. 8 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for Control Engineering 基本的决策树学****算法( 2) ? ID3 的思想–自顶向下构造决策树–从“哪一个属性将在树的根节点被测试”开始–使用统计测试来确定每一个实例属性单独分类训练样例的能力? ID3 的过程–分类能力最好的属性被选作树的根节点–根节点的每个可能值产生一个分支–训练样例排列到适当的分支–重复上面的过程 Date: 2/25/2017 File: ML1. 9 Machine Learning Peng Kaixiang 2011. All rights reserved. Machine Learning for