《决策树培训讲义(powerpoint 89页)》由会员分享，可在线阅读，更多相关《决策树培训讲义(powerpoint 89页)（91页珍藏版）》请在金锄头文库上搜索。
1、第第 6 6 章章 决策树决策树主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献第6章 决策树决策树基本概念决策树基本概念关于分类问题关于分类问题 分类（Classification）任务就是通过学习获得一个目标函数（Target Function）f, 将每个属性集x映射到一个预先定义好的类标号y。 分类任务的输入数据是纪录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个
2、特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）第6章 决策树决策树基本概念决策树基本概念关于分类问题关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类与回归分类目标属性分类目标属性y是离散的，回归目标属性是离散的，回归目标属性y是连续的是连续的第6章 决策树决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输
3、入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。 分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。第6章 决策树决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤： 1、模型构建（归纳） 通过对训练集合的归纳，建立分类模型。 2、预测应用（推论） 根据建立的分类模型，对测试集合进行测试。第6章 决
4、策树决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）训练集（类标号已知）检验集（类标号未知）检验集（类标号未知）归纳推论第6章 决策树决策树基本概念决策树基本概念决策树决策树 决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。第6章 决策树决策树基本概念决策
5、树基本概念决策树的优点决策树的优点1、推理过程容易理解，决策推理过程可以表示成If Then形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量的重要性，减少变量的数目提供参考。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(1) 决策树技术发现数据模式和规则的核心是归纳算法。 归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。 归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展
6、和完善具有重要的意义。人类知识的增长主要来源于归纳学习。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(2) 归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。 锐角三角形内角和等于180度； 钝角三角形内角和等于180度； 三角形内角和 直角三角形内角和等于180度； 等于180度 已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度 归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设： 任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函
7、数。该假定是归纳学习的有效性的前提条件。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(3)第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(4) 归纳过程就是在描述空间中进行搜索的过程。归纳可分为自顶向下，自底向上和双向搜索三种方式。 自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。 自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述。第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（1） 从特殊的训练样例中归纳出一般函数是机器学习的中心问题；从
8、训练样例中进行学习通常被视为归纳推理。每个例子都是一个对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。 学习过程将产生对目标函数f的不同逼近。F的每一个逼近都叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过调整假设的表示，学习过程将产生出假设的不同变形。在表示中通常需要修改参数（如a, b）。 第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（2） 从这些不同的变形中选择最佳的假设（或者说权值集合）。一般方法如定义为使训练值与假设值 预测出的值之间的误差平方和E最小为最佳。 学习是在假设空间上的一
9、个搜索。概念学习也可以看作是一个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。 第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（3） 分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数进行评估。这些计数存储在混同矩阵（进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，二元）的表格中，二元分类问题混淆矩阵如下：分类问题
10、混淆矩阵如下：实际实际的类的类类类1f11类类0f01f10f00类类1类类0预测的类预测的类准确率准确率=正确的预测数正确的预测数/预测总数预测总数=（f11+f00）/(f11+f01+f10+f00)差错率差错率=错误的预测数错误的预测数/预测总数预测总数=（f10+f01）/(f11+f01+f10+f00)归纳学习假设 机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设 。一般H表示所有可能假设。H中每个假设h表示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟合。若没有更多的信息，只能假定对于未见实例最好的假
11、设就是训练数据最佳拟合的假设。 定义 归纳学习假设：任一假设如果在足够大的训练样例中很好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。（Function Approximation）。 第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（4）主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献第6章 决策树决策树算法决策树算法与决策树相关的重要算法与决策树相关的重要算法1、Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。2、
12、1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。CLS, ID3，
13、C4.5，CART第6章 决策树决策树算法决策树算法计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买假定公司收集了左表数据，那么对假定公司收集了左表数据，那么对于任意给定的客人（测试样例），于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于即：你能预测这位客人是属于“买买”计算机的那一类，还是属于计算机的
14、那一类，还是属于“不不买买”计算机的那一类？计算机的那一类？又：你需要多少有关这位客人的信又：你需要多少有关这位客人的信息才能回答这个问题？息才能回答这个问题？决策树的用途决策树的用途第6章 决策树计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买谁在买计算机？谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树的用途决策树算法决策树算法第6章
15、决策树计数年龄收入学生信誉归类：买归类：买计算机？计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买谁在买计算机？谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树的用途决策树算法决策树算法第6章 决策树决策树算法决策树算法决策树的表示决策树的表示决策树的基本组成部分：决策结点、分支和叶子。决策树的基本组成部分：决策结点、分支和叶子。年龄？学生？信誉？买青中老否是优良不买买买不买决策树
16、中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果 在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别第6章 决策树决策树算法决策树算法CLS（Concept Learning System）算法）算法 CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。 CLS基本思想基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。第6章 决策树人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红
