资源描述：
《6.3-决策树学习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章机器学习6.1机器学习概述6.2归纳学习6.3决策树学习6.4其它机器学习方法2014-4-16人工智能丁世飞第六章机器学习6.1机器学习概述6.2归纳学习6.3决策树学习6.4其它机器学习方法2014-4-16人工智能丁世飞6.3决策树学习决策树学习是离散函数的一种树形表示，表达能力强，可以表示任意的离散函数，是一种重要的归纳学习方法。决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。2014-4-16人工智能丁世飞6.3.1决策树的组成及分类1.
2、决策树的组成：通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类。树上每个节点说明了对实例的某个属性的测试。节点的每个后继分支对应于该属性的一个可能值。2014-4-16人工智能丁世飞6.3.1决策树的组成及分类2.决策树的分类：依据每个节点所测试的属性个数，决策树可分为单变量树和多变量树。单变量树：每个节点的测试值都使用一个输入维，也就是只测试一个属性。如图6.6所示数据集与单变量树。2014-4-16人工智能丁世飞6.3.1决策树的组成及分类x>w110CYesNo2x2x>w
3、220w20YesNoC1C1wx101C2C2C1图6.6数据集与单变量树2014-4-16人工智能丁世飞6.3.1决策树的组成及分类2.决策树的分类：依据每个节点所测试的属性个数，决策树可分为单变量树和多变量树。多变量树：每个节点的测试值都使用多个输入维，也就是选择多个属性的组合进行测试。如图6.7所示数据集与线性多变量树。2014-4-16人工智能丁世飞6.3.1决策树的组成及分类wx+wx+w>011112210X2C2YesNoC1C2C1X1图6.7数据集与线性多变量树2014-4-16人工智能丁世飞
4、6.3.1决策树的组成及分类3.决策树的分类：适用问题的特征：实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例分类问题：核心任务是把样例分类到各可能的离散值对应的类别2014-4-16人工智能丁世飞6.3.2决策树的构造算法CLS:亨特(Hunt)于1966年研制了一个概念学习系统(ConceptLearningSystem,CLS)，可以学习单个概念，并用此学到的概念分类新的实例。这是一种早期的基于决策树的归纳学习系统。昆兰(Qui
5、nlan)于1983年此进行了发展，研制了ID3算法。该算法不仅能方便地表示概念属性-值信息的结构，而且能从大量实例数据中有效地生成相应的决策树模型。2014-4-16人工智能丁世飞6.3.2决策树的构造算法CLS:在CLS决策树中:节点对应于待分类对象的属性;由某一节点引出的弧对应于这一属性可能取的值;叶节点对应于分类的结果。2014-4-16人工智能丁世飞6.3.2决策树的构造算法CLS:为构造CLS算法，现假设如下：给定训练集TR，TR的元素由特征向量及其分类结果表示，分类对象的属性表AttrList为{A
6、,A,…A}，全部分类结果12n构成的集合Class为{C,C,…C]，一般n≥1和m≥2。12m对每一属性Ai，其值域为Value-Type(Ai)。值域可以是离散的，也可以是连续的。这样，TR的元素就可表示成的形式，其中X=(a,a,…a)，a对应于实例第i个属性的取值，C∈Class为实12ni例X的分类结果。记V(X,Ai)为特征向量X属性Ai的值，则决策树的构造算法CLS可递归地描述为:2014-4-16人工智能丁世飞6.3.2决策树的构造算法CLS:算法6.2决策树构造算法CLS:(1)如
7、果TR中所有实例分类结果均为Ci,则返回Ci;(2)从属性表中选择某一属性Ai作为检测属性;(3)不妨假设
8、ValueType(Ai)
9、=k,根据Ai取值的不同,将TR划分为k个训练集TR,TR,…TR,其中:12kTR={
10、∈TR且V(X,A)为属性A的第i个值}i(4)从属性表中去掉已做检测的属性Ai;(5)对每一个i(1≤i≤k),用TRi和新的属性表递归调用CLS生成Tri的决策树DTR;i(6)返回以属性Ai为根,DTR1,…,DTRk为子树的决策树。2014-4-16人工智能丁
11、世飞现考虑鸟是否能飞的实例，见表6.1：InstancesNo.ofBrokenLivingarea/weightFlyWingsWingsstatus120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.
