文档介绍：决策树算法
第1页，本讲稿共89页
主要内容
决策树基本概念
决策树算法
决策树研究问题
主要参考文献
第2页，本讲稿共89页
主要内容
决策树基本概念
决策树算法
决策树研究问题
主要参考文献
第3页角和等于180度；等于180度
已知三角形ABC，A角等于76度，
B角等于89度，则其C角等于15度
第12页，本讲稿共89页
归纳学****由于依赖于检验数据，因此又称为检验学****归纳学****存在一个基本的假设：
任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学****的有效性的前提条件。
第6章决策树
决策树基本概念
关于归纳学****3)
第13页，本讲稿共89页
第6章决策树
决策树基本概念
关于归纳学****4)
归纳过程就是在描述空间中进行搜索的过程。归纳可分为自
顶向下，自底向上和双向搜索三种方式。
自底向上法一次处理一个输入对象。将描述逐步一般化。直
到最终的一般化描述。
自顶向下法对可能的一般性描述集进行搜索，试图找到一些
满足一定要求的最优的描述。
第14页，本讲稿共89页
第6章决策树
决策树基本概念
从机器学****看分类及归纳推理等问题（1）
从特殊的训练样例中归纳出一般函数是机器学****的中心问题；
从训练样例中进行学****通常被视为归纳推理。每个例子都是一个
对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。
学****过程将产生对目标函数f的不同逼近。F的每一个逼近都
叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过
调整假设的表示，学****过程将产生出假设的不同变形。在表示中
通常需要修改参数（如a, b）。
第15页，本讲稿共89页
第6章决策树
决策树基本概念
从机器学****看分类及归纳推理等问题（2）
从这些不同的变形中选择最佳的假设（或者说权值集合）。
一般方法如定义为使训练值与假设值预测出的值之间的误差平方
和E最小为最佳。
学****是在假设空间上的一个搜索。概念学****也可以看作是一
个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与
训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以
利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。
第16页，本讲稿共89页
第6章决策树
决策树基本概念
从机器学****看分类及归纳推理等问题（3）
分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数
进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，二元
分类问题混淆矩阵如下：
实际
的类
类1
f11
类0
f01
f10
f00
类1
类0
预测的类
准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00)
差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00)
第17页，本讲稿共89页
归纳学****假设
机器学****的任务是在整个实例集合X上确定与目标概念c相同
的假设。一般H表示所有可能假设。H中每个假设h表
示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上
的值，因此归纳学****最多只能保证输出的假设能与训练样例相拟
合。若没有更多的信息，只能假定对于未见实例最好的假设就是
训练数据最佳拟合的假设。
定义归纳学****假设：任一假设如果在足够大的训练样例中很
好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。
（Function Approximation）。
第6章决策树
决策树基本概念
从机器学****看分类及归纳推理等问题（4）
第18页，本讲稿共89页
主要内容
决策树基本概念
决策树算法
决策树研究问题
主要参考文献
第19页，本讲稿共89页
第6章决策树
决策树算法
与决策树相关的重要算法
1、Hunt,Marin和Stone 于1966年研制的CLS学****系统，用于学****单个概念。
2、1979年, . Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学****算法的典型。
3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。
4、1988年，Utgoff 在ID4基础上提出了ID5学****算法，进一步提高了效率。