决策树学习课件.ppt

《决策树学习课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、机器学习第3讲决策树学习内容简介决策树原理决策树算法决策树中的过拟合问题决策树的其他问题属性的其他度量简介决策树也称为判定树。在决策树方法中，首先从实例集中构造决策树，这是一种有指导学习的方法。该方法先根据训练集数据形成决策树。如果该数不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树性结构。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应属性的某一可能值。决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪声数据有很好的健壮性且能够学习析取表达

2、式。学习得到的决策树能够被再次表示为多个if-then的规则，提高可读性。这种学习算法是最流行的归纳推理算法之一，被成功的应用到从医学医疗诊断到学习评估贷款申请的信用风险的广阔领域。决策树原理决策树方法首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。归纳学习决策树技术发现数据模式和规则的核心是归纳算法。归纳算法是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性或属性中，通过比较、总结、概括而得出一个规律性的结论。归纳推理视图从对象的一部分或整体的特定观察中得到一个完备且正确的描述，即从特殊事实得出普遍规律性的结

3、论。归纳对于认识的发展完善具有重要的意义。归纳学习的过程就是寻找一般化描述的过程。这种一般化描述能够解释给定的输入数据，并可以用来预测新的数据。归纳学习存在一个基本的假定：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则他也能在未见样本中很好地逼近目标函数。这个假定是归纳学习的前提条件。决策树的表示决策树的基本组成部分：决策结点、分支和子叶。决策树最上面的结点称为跟结点，是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶结点代表一种可能的分类结果。在沿着决策树从上到下

4、遍历的过程中，在每个结点都会遇到一个测试，对每个节点上问题的不同测试输出导致不同的分支，最后会到达一个叶子结点。这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试；节点的每个后继分支对应于该属性的一个可能值。图3-1Playtennis决策树此图为典型学习到的决策树，这棵树根据天气情况分类“星期六上午是否适合打网球”，上面的实例沿着这棵决策树的最左分支向下排列，因而被判定为反例（也就是这棵树预测这个实例Pla

5、ytennis=no）。7图3-1对应于一下表达式决策树代表实例属性值约束的合取的析取式从根结点到叶结点的每一条路径对应一组属性的合取，树本身对应这些合取的析取。8决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例分类问题核心任务是把样例分类到各可能的离散值对应的类别9决策树算法大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间贪心算法算法代表：ID310基本的决策树学习算法（2）ID3的思想自顶向下构造决策树从“哪一个属性将在

6、树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程11熵:物理学概念?宏观上：热力学定律—体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，1865）?微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，1872）?结论：熵是描述事物无序性的参数，熵越大则无序性越强,在信息领域定义为“熵越大，不确定性越大”（香浓，1948年）12最佳分类属性信息增益用

7、来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为Entropy(S)=信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=13假设S是关于某布尔概念的有14个样例的集合，它包括9个正例和5个反例，（我们采用记号[9+,5-]来概括这样的数据样例）。那么S相对于这个布尔分类的

8、熵为：注：如果S的所有成员属于一类那么