文档介绍：机器学****br/>第3讲决策树学****br/>内容
简介
决策树原理
决策树算法
决策树中的过拟合问题
决策树的其他问题
属性的其他度量
简介
决策树也称为判定树。在决策树方法中,首先从实例集中构造决策树,这是一种有指导学****的方法。该方法先根据训练集数据形成决策树。如果该数不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树性结构。最终结果是一棵树,其叶结点是类名,中间结点是带有分枝的属性,该分枝对应属性的某一可能值。
决策树学****是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法,对噪声数据有很好的健壮性且能够学****析取表达式。学****得到的决策树能够被再次表示为多个if-then的规则,提高可读性。这种学****算法是最流行的归纳推理算法之一,被成功的应用到从医学医疗诊断到学****评估贷款申请的信用风险的广阔领域。
决策树原理
决策树方法首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。
归纳学****br/> 决策树技术发现数据模式和规则的核心是归纳算法。归纳算法是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性或属性中,通过比较、总结、概括而得出一个规律性的结论。归纳推理视图从对象的一部分或整体的特定观察中得到一个完备且正确的描述,即从特殊事实得出普遍规律性的结论。归纳对于认识的发展完善具有重要的意义。
归纳学****的过程就是寻找一般化描述的过程。这种一般化描述能够解释给定的输入数据,并可以用来预测新的数据。归纳学****存在一个基本的假定:任一假设如果能够在足够大的训练样本集中很好的逼近目标函数,则他也能在未见样本中很好地逼近目标函数。这个假定是归纳学****的前提条件。
决策树的表示
决策树的基本组成部分:决策结点、分支和子叶。决策树最上面的结点称为跟结点,是整个决策树的开始。每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策,通常对应于待分类对象的属性。每一个叶结点代表一种可能的分类结果。在沿着决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个节点上问题的不同测试输出导致不同的分支,最后会到达一个叶子结点。这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。
决策树表示法
决策树
通过把实例从根节点排列到某个叶子节点来分类实例;
叶子节点即为实例所属的分类;
树上每个节点说明了对实例的某个属性的测试;
节点的每个后继分支对应于该属性的一个可能值。
7
图3-1 Play tennis决策树
此图为典型学****到的决策树,这棵树根据天气情况分类“星期六上午是否适合打网球”,上面的实例沿着这棵决策树的最左分支向下排列,因而被判定为反例(也就是这棵树预测这个实例Play tennis=no)。
8
图3-1对应于一下表达式
决策树代表实例属性值约束的合取的析取式从根结点到叶结点的每一条路径对应一组属性的合取,树本身对应这些合取的析取。
9
决策树学****的适用问题
适用问题的特征
实例由“属性-值”对表示
目标函数具有离散的输出值
可能需要析取的描述
训练数据可以包含错误
训练数据可以包含缺少属性值的实例
分类问题
核心任务是把样例分类到各可能的离散值对应的类别
10
决策树算法
大多数决策树学****算法是一种核心算法的变体
采用自顶向下的贪婪搜索遍历可能的决策树空间
贪心算法
算法代表: ID3