决策树简介课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,决策树,组：,郭浩韩学成何珺,何军黄安迪,决策树组：,1,决策树简介课件,2,决策树简介课件,3,4.1,数据分类介绍,分类,是,数据挖掘,的一个重要课题,它的目的是：,构造一个分类函数或分类模型,该模型能把数据库中的数据项映射到给定类别中的某一个。,数据分类的过程一般来说主要包含两个步骤,第一步,建立一个描述已知数据集类别或概念的模型,第二步,利用所获得的模型进行分类操作,4.1 数据分类介绍分类是数据挖掘的一个重要课题, 它,4,4.1,数据分类介绍,-2,第一步,建立一个描述已知数据集类别或概念的模型,该模型是通过对数据库中各数据进行内容的分析而获得的。,分类学习方法所使用的数据集称为,训练样本集合,，每一数据行都属于一个确定的数据类别，其类别值是由一个属性来描述的,(,被称为,类别标记属性,),。,因此分类学习又可称为,监督学习,，它是在,已知训练样本类别,情况下，通过学习建立相应模型。而,无监督学习,则是在训练样本的类别与类别个数均未知的情况下进行的，如聚类分析。,4.1 数据分类介绍-2第一步, 建立一个描述已知数据集,5,4.1,数据分类介绍,-2,第二步,利用所获得的模型进行分类操作,首先对模型分类准确率进行估计。,模型的准确性可以通过由该模型所正确分类的测试样本个数所占总测试样本的比例得到。即对于每一个测试样本，比较其已知的类别与学习所获模型的预测类别。,如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未来数据行或对象,(,其类别未知,),进行分类，即利用学习所获得的模型,进行预测,，对未知类别的数据行或对象判断其类别,(,属性,),取值。,4.1 数据分类介绍-2第二步, 利用所获得的模型进行分,6,由训练数据产生分类规则,由训练数据产生分类规则,7,由分类规则对新的样本数据进行分类,由分类规则对新的样本数据进行分类,8,4.1,决策树介绍,-2,常用的分类预测算法：,决策树归纳分类,贝叶斯分类,基于规则的分类,用后向传播分类,遗传算法、粗糙集方法、模糊集方法,4.1 决策树介绍-2常用的分类预测算法：,9,4.1,决策树介绍,-2,4.1.1,决策树的基本知识,决策树方法最早产生于,20,世纪,60,年代，是由,Hunt,等人研究人类概念建模时建立的学习系统,CLS,(concept learning system),。到了,70,年代末，,J. Ross Quinlan,提出,ID3,算法，引进信息论中的有关思想，提出用信息增益,(information gain),作为特征判别能力的度量，来选择属性作为决策树的节点，并将建树的方法嵌在一个迭代的程序之中。当时他的主要目的在于减少树的深度，却忽略了叶子数目的研究。,1975,年和,1984,年，分别有人提出了,CHAID,和,CART,算法。,1986,年，,J. C. Schlinner,提出,ID4,算法。,1988,年，,P. E. Utgoff,提出,ID5R,算法。,1993,年，,Quinlan,本人以,ID3,算法为基础研究出,C4.5,算法。新算法在对预测变量的缺失值处理、剪枝技术、派生规则等方面作了较大的改进，,C5.0,是,C4.5,的商业改进版。,4.1 决策树介绍-24.1.1 决策树的基本知识,10,例子,关于上,mooc,的例子,例子关于上mooc的例子,11,例子,例子,12,决策树简介课件,13,4.1.1,决策树的基本知识,决策树技术发现数据模式和规则的核心是,归纳算法,。,归纳是从特殊到一般的过程。,归纳推理从若干个事实表征出的特征、特性或属性中,通过比较、总结、概括而得出一个规律性的结论。,归纳学习的过程就是寻找一般化描述,(,归纳断言,),的过程。这种一般化描述能够解释给定的输入数据，并可以用来,预测,新的数据。,归纳学习由于依赖于经验数据，因此又称作,经验学习,。,4.1.1 决策树的基本知识决策树技术发现数据模式和规则的,14,4.1.1,决策树的基本知识,-2,归纳学习存在一个基本假定,:,任一模型如果能在足够大的,训练样本集,中很好地逼近目标函数，则它也能在,未见样本,中很好地逼近目标函数。这个假定是归纳学习,有效性的前提条件,。,4.1.1 决策树的基本知识-2归纳学习存在一个基本假定:,15,4.1.1,决策树的基本知识,-2,归纳可以分为自下而上、自上而下和双向搜索三种方式,自下而上法一次处理一个输入对象，将描述逐步一般化，直到最终的一般化描述。,自上而下法则对可能的一般化描述集进行搜索，试图找到一些满足一定要求的最优的描述。,双向搜索方式则是这两者的结合。,4.1.1 决策树的基本知识-2归纳可以分为自下而上、自上,16,4.1.1,决策树的基本知识,-2,先根据,训练子集,形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集中，重复该过程一直到形成正确的决策集。,最终结果是“一棵树”，各分枝对应某种属性的某一可能值。,4.1.1 决策树的基本知识-2先根据训练子集形成决策树，,17,4.1.1,决策树的基本知识,决策树通常有两大类型，分别为,分类决策树,和,回归决策树,。,分类决策树用来实现对定类或定序目标变量的分类，回归决策树则完成对定距目标变量取值的预测。,根据决策树各种不同的属性，可分为以下几类,:,决策树内节点的测试属性可能是单变量的，即每个内节点只包含一个 属性,;,也可能是多变量的，既存在包含多个属性的内节点。,测试属性的不同属性值的个数，可能使得每个内节点有两个或多个 分枝。如果一棵决策树每个内节点只有两个分枝则称之为二叉 决策树，如由,CART,算法生成的决策树。,每个属性可能是值类型,(,连续值,),，也可能是枚举类型,(,离散值,),。,分类结果既可能是两类也有可能是多类，如果二叉决策树的结果只有 两类，则称之为布尔决策树。,4.1.1 决策树的基本知识决策树通常有两大类型，分别为分,18,4.1.1,决策树的基本知识,决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散函数值的方法，分类精度高，操作简单，并且对,噪声数据,有很好的稳健性，因而成为比较实用且比较流行的数据挖掘算法。,它的最大优点是，在学习过程中不需要使用者了解很多背景知识，只要训练样本集能够用,“属性,-,值”,的方式表达出来就能使用决策树学习算法来分类。,4.1.1 决策树的基本知识决策树学习是应用最广的归纳推理,19,4.1.1,决策树的基本知识,4.2.4,属性选择,属性选择的统计度量,(,又称为,分枝指标,splitting index,，,SI ),的计算是决策树构建算法的,关键,。,不同的决策树算法采用不同的统计度量，主要有,:,信息增益,Information Gain ( ID3,和,C4.5,算法使用,),， 所有属性假设都是,种类字段,，经过修改之后可以适用于 数值字段,;,基尼指数,Gini index(,即,Gini,指标,) CART,算法、,CHAID,算法和,SLIQ,算法使用 适用于种类和数值字段等等。,4.1.1 决策树的基本知识4.2.4 属性选择,20,4.1.1,决策树的基本知识,-2,决策树方法的,(,相对,),优点,:,可以生成可理解的规则数据挖掘产生的模式的可理解度是判别数据挖掘算法的主要指标之一，相比于一些数据挖掘算法，决策树算法产生的规则比较容易理解，并且决策树模型的建立过程也很直观。,计算量较小。,可以处理连续和集合属性。,决策树的输出包含属性的排序生成决策树时，按照最大信息增益选择测试属性，因此，在决策树中可以大致判断属性的相对重要性。,4.1.1 决策树的基本知识-2决策树方法的(相对)优点:,21,4.1.1,决策树的基本知识,-2,决策树方法的缺点,:,对于具有连续值的属性预测比较困难。,-,对于顺序相关的数据，需要很多预处理的工作。,当类别太多时，通常会增加误差,分枝间的拆分不够平滑，进行拆分时，不考虑其对将来拆分的影响。,缺值数据处理问题,:,因为决策树进行分类预测时，完全基于数据的测试属性，所以对于测试属性缺失的数据，决策树将无法处理。,通常仅根据单个属性来分类,:,决策树方法根据单个属性对数据进行分类，而在实际的分类系统中，类的划分不仅仅与单个属性有关，往往与一个属性集有关。因此，将决策树算法推广到考虑多属性是一个有待研究的课题。,4.1.1 决策树的基本知识-2决策树方法的缺点:,22,4.1.1,决策树的基本知识,-2,决策树学习算法适用的问题,:,样本可以用“属性,-,值”的方式来描述,目标函数的输出值为离散值,训练数据中允许包含有错误,:,样本的分类错误或属性值错误都允许,训练数据中有样本属性值缺失,4.1.1 决策树的基本知识-2决策树学习算法适用的问题:,23,4.1,决策树介绍,-2,4.1.2,决策树的应用和发展趋势,决策树由于结构简单、效率高等优点而获得了广泛的应用。决策树在,商业、工业、天文、医学、风险分析、社会科学和分类学,等领域的应用已经取得了很好的经济和社会效益。国内目前有关决策树的研究多是围绕算法的改进以及决策树在商业、工业等领域的运用。,在商业领域，决策树方法所能解决的典型商业问题有,:,客户关系 管理、数据库营销、客户群体划分、交叉销售等市场分析 行为，以及客户流失分析、客户信用计分及欺诈发现，等等。,在工业领域，决策树可以用于故障诊断、工业生产过程控制等。,在医学领域，决策树方法可用于疾病诊断治疔、 基因与高分子序列分析、医院信息系统挖掘及医疗政策分析等。,4.1 决策树介绍-24.1.2 决策树的应用和发展趋势,24,4.2,树的建模过程,4.2 树的建模过程,25,决策树简介课件,26,4.2,树的建模过程,决策树算法通过构造决策树来发现数据中蕴涵的分类规则，包含许多种不同的算法，主要可以分为三类,:,(1),基于,统计学理论,的方法，以,CART,为代表，在这类算法中，对于非终端节点来说，有两个分枝,;,(2),基于,信息理论,的方法，以,ID3,算法为代表，此类算法中，非终端的节点的分枝由样本类别个数决定,;,(3),以,AID,，,CHAD,为代表的算法，在此类算法中，非终端节点的分枝数在,2,至样本类别个数范围内分布。,这些算法在分类中应用的过程与思想基本上是一致的。,如何构造,精度高、规模小的决策树,是决策树算法的,核心内容,4.2 树的建模过程决策树算法通过构造决策树来发现数据,27,4.2,树的建模过程,总体步骤,决策树的构造基本可以分为如下两步,:,决策树的生成,决策树的生成是指由,训练样本数据集,生成决策树的过程。一般情况下，训练样本数据集是根据实际需要由实际的历史数据生成的、有一定综合程度的、用于数据分析处理的数据集。,决策树的剪枝,决策树剪枝是对上一阶段所生成的决策树进行检验、校正和修正的过程，主要是采用新的样本数据集,(,测试数据集,),中的数据检验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。一般情况下，根据测试数据集中的每一元组对生成的规则进行预测准确性的检验，如果预测准确性过低，则将该分枝剪除。,4.2 树的建模过程总体步骤决策树的构造基本可以分为如,28,4.2,树的建模过程,4.2.1,数据要求,(,数据准备,),在进行分类和预测挖掘之前，首先必须准备好有关挖掘数据。一般需要对数据进行以下预处理，以帮助提高分类和预测过程的准确性、有效性和可伸缩性。主要的工作包括：,数据清洗,相关分析,数据转换,4.2 树的建模过程4.2.1 数据要求(数据准备),29,4.2.1,数据准备,数据清洗,这一数据预处理步骤，主要是帮助除去数据中的噪声，并妥善解决缺失数据问题，尽管大多数分类算法都包含一些处理噪声和缺失数据的方法，但这一预处理步骤可以有效减少学习过程可能出现相互矛盾情况的问题。,4.2.1 数据准备数据清洗,30,4.2.1,数据准备,相关分析,由于数据集中的许多属性与挖掘任务本身可能是无关的，例如记录银行贷款申请,(,单,),填写时的星期数,(,属性,),，就可能与申请成功与否的描述无关。此外，有些属性也可能是冗余的。因此需要对数据进行相关分析，以使在学习阶段之前就消除无关或冗余属性。在机器学习中，这一相关分析步骤被称为,属性选择,(feature selection),，包含与挖掘任务无关的属性可能会减缓甚至误导整个学习过程。,4.2.1 数据准备相关分析,31,4.2.1,数据准备,数据转换,利用概念层次树，数据能够被泛化到更高的层次。概念层次树对连续数值的转换非常有效。例如，属性“收入”的数值就可以被泛化为若干离散区间，诸如低、中和高。由于泛化操作压缩了原来的数据集，从而可以帮助有效减少学习过程所涉及的输入输出操作。,4.2.1 数据准备数据转换,32,4.2,树的建模过程,4.2.2,树的生长,决策树算法是一种常用的数据挖掘算法，它是从机器学习领域中逐渐发展起来的一种分类函数逼近方法。决策树学习的基本算法是,贪心算法,，采用自上而下的递归方式构造决策树。,Hunt,等人于,1966,年提出的概念学习系统,(concept learning system,，,CLS),是最早的决策树算法，以后的许多决策树算法都是对,CLS,算法的改进或由,CLS,衍生而来。目前，利用决策树进行数据分类的方法已经被深入研究，并且形成了许多决策树算法。,4.2 树的建模过程4.2.2 树的生长,33,4.2.2,树的生长,决策树是“一棵树”，它的根节点是整个数据集合空间，每个分节点是对一个,单一变量,(,属性,),的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于,单一类别,的记录。,4.2.2 树的生长决策树是“一棵树”，它的根节点是整个数,34,4.2.2,树的生长,通常,通过,自上而下递归分割,的过程来构建决策树,分为三个步骤,:,(1),寻找初始分裂。整个,训练集,作为产生决策树的集合， 训练集每个记录必须是已经分好类的。决定哪个属性,(field),域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。,(2),树增长到一棵完整的树。重复第一步，直至每个叶节点 内的记录都属于同一类，或达到其他停止准则。,(3),数据的修剪。去掉一些可能是噪音或者异常的数据或节点,4.2.2 树的生长通常, 通过自上而下递归分割的过程来构,35,4.2.2,树的生长,其通用的基本算法,(,贪心算法,),为,:,以自上而下分而治之的方法，开始时，所有的数据都在根节点,;,属性都是种类字段,(,如果是连续的，将其离散化,);,所有记录用所选属性递归地进行分割,;,属性的选择是基于一个启发式规则或者一个统计的度量,(,如,information gain,),。,停止分割的条件,:,一个节点上的数据都是属于同一个类别或没有属性可以再用于对数据进行分割。,4.2.2 树的生长其通用的基本算法(贪心算法)为:,36,4.2.2,树的生长,算法的形式描述,Procedure BuildTree(S),用数据集,S,初始化根节点,R,用根节点,R,初始化队列,Q,Whi1e Q is not Empty, do,取出队列,Q,中的第一个节点,N,if N,不纯,(impure),for,每一个属性,A,估计该节点在,A,上的信息增益,选出最佳的属性,将,N,分裂为,N1,N2,4.2.2 树的生长算法的形式描述Procedure Bu,37,4.2,树的建模过程,-3,4.2.3,有效性和风险性,基本的决策树算法没有考虑噪声,生成的决策树完全与训练例子拟合。,这样虽然能降低算法的时间复杂度，但也使算法在较深层次的样本划分中，专注于训练样本集某个子集的统计信息，而忽视各类样本的整体分布情况，造成了对噪声敏感。,所以，虽然一棵完整的决策树能够非常准确地反映,训练样本集,中数据的特征，但因失去了一般代表性而无法对新数据进行准确的分类或预测，出现了过,匹配现象,。,4.2 树的建模过程-34.2.3 有效性和风险性,38,4.2.3,树的剪枝,过匹配,指的是模型由于过度训练，导致其记住的不是训练数据的一般特性，而是训练集的局部特性。,当将这个模型应用到新的测试集上时就导致预测结果的不准确。,因此，一个完整的决策树构造过程将包含,决策树的创建,和,决策树的剪枝,这两方面。,剪枝是一种克服噪声的技术，用于解决过匹配问题，同时它也能使树得到简化而变得更容易理解。,4.2.3 树的剪枝过匹配指的是模型由于过度训练，导致其记,39,4.2.3,树的剪枝,剪枝的原则包括,:,奥卡姆剃刀原则,“,如无必要，勿增实体”。即在与观察相容的情况下，应当选择最简单的一棵决策树。,决策树越小就越容易理解，其存储与传输的代价也就越小。,决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点的假设的样本个数就越少，可能导致决策树在测试集上的,分类错误率就会增大,。但决策树过小也会导致错误率较大。因此，,需要在树的大小与正确率之间寻找均衡点,4.2.3 树的剪枝剪枝的原则包括:,40,4.2.3,树的剪枝,常用的剪枝技术有预剪枝,(pre-pruning),和后剪枝,(post-pruning),两种。,预剪枝,：在构造决策树时，决定不再对,不纯的训练子集,进行进一步划分的剪枝方法 预剪枝技术限制了决策树的过度生长 如,CHAID, ID3,系列的,ID3,、,C4.5,算法等,后剪枝,：在树完全生成之后的剪枝策略 如,CART,算法等,剪枝的目的就是删除由于噪声数据而引起的分枝，从而避免决策树的过匹配。,4.2.3 树的剪枝常用的剪枝技术有预剪枝(pre-pru,41,4.2.3,树的剪枝,预剪枝中最直接而简单的方法是事先指定决策树生长的,最大深度,，使决策树不能得到充分生长。这种停止标准一般能够取得比较好的效果。不过指定树的高度的方法要求用户对数据的取值分布有较为清晰的把握，而且须对参数值进行反复尝试，否则无法给出一个较为合理的树高度阈值。,4.2.3 树的剪枝预剪枝中最直接而简单的方法是事先指定决,42,4.2.3,树的剪枝,后剪枝技术允许决策树过度生长，然后根据一定的规则，剪去决策树中那些不具有,一般代表性,的叶节点或分枝。,后剪枝算法有,自上而下,和,自下而上,两种剪枝策略。,自下而上的算法首先从最底层的内节点开始，剪去满足一定条件的内节点，在生成的新决策树上递归调用这个算法，直到没有可以剪枝的节点为止。,自上而下的算法是从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就进行剪枝。,4.2.3 树的剪枝后剪枝技术允许决策树过度生长，然后根据,43,4.2.3,树的剪枝,目前，决策树修剪策略主要有三种,:,悲观修剪,(pessimistic pruning),，,代价复杂度修剪,(cost-complexity pruning),和,基于最小描述长度,(minimum description length,，,MDL),原理的修剪,。,4.2.3 树的剪枝目前，决策树修剪策略主要有三种: 悲观,44,TO BE CONTINUED,决策树简介课件,45,1,、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你努力的不够多。,2,、孤单一人的时间使自己变得优秀，给来的人一个惊喜，也给自己一个好的交代。,3,、命运给你一个比别人低的起点是想告诉你，让你用你的一生去奋斗出一个绝地反击的故事，所以有什么理由不努力,!,4,、心中没有过分的贪求，自然苦就少。口里不说多余的话，自然祸就少。腹内的食物能减少，自然病就少。思绪中没有过分欲，自然忧就少。大悲是无泪的，同样大悟无言。缘来尽量要惜，缘尽就放。人生本来就空，对人家笑笑，对自己笑笑，笑着看天下，看日出日落，花谢花开，岂不自在，哪里来的尘埃,!,5,、心情就像衣服，脏了就拿去洗洗，晒晒，阳光自然就会蔓延开来。阳光那么好，何必自寻烦恼，过好每一个当下，一万个美丽的未来抵不过一个温暖的现在。,6,、无论你正遭遇着什么，你都要从落魄中站起来重振旗鼓，要继续保持热忱，要继续保持微笑，就像从未受伤过一样。,7,、生命的美丽，永远展现在她的进取之中,;,就像大树的美丽，是展现在它负势向上高耸入云的蓬勃生机中,;,像雄鹰的美丽，是展现在它搏风击雨如苍天之魂的翱翔中,;,像江河的美丽，是展现在它波涛汹涌一泻千里的奔流中。,8,、有些事，不可避免地发生，阴晴圆缺皆有规律，我们只能坦然地接受,;,有些事，只要你愿意努力，矢志不渝地付出，就能慢慢改变它的轨迹。,9,、与其埋怨世界，不如改变自己。管好自己的心，做好自己的事，比什么都强。人生无完美，曲折亦风景。别把失去看得过重，放弃是另一种拥有,;,不要经常艳羡他人，人做到了，心悟到了，相信属于你的风景就在下一个拐弯处。,10,、有些事想开了，你就会明白，在世上，你就是你，你痛痛你自己，你累累你自己，就算有人同情你，那又怎样，最后收拾残局的还是要靠你自己。,11,、人生的某些障碍，你是逃不掉的。与其费尽周折绕过去，不如勇敢地攀登，或许这会铸就你人生的高点。,12,、有些压力总是得自己扛过去，说出来就成了充满负能量的抱怨。寻求安慰也无济于事，还徒增了别人的烦恼。,13,、认识到我们的所见所闻都是假象，认识到此生都是虚幻，我们才能真正认识到佛法的真相。钱多了会压死你，你承受得了吗,?,带，带不走，放，放不下。时时刻刻发悲心，饶益众生为他人。,14,、梦想总是跑在我的前面。努力追寻它们，为了那一瞬间的同步，这就是动人的生命奇迹。,15,、懒惰不会让你一下子跌倒，但会在不知不觉中减少你的收获,;,勤奋也不会让你一夜成功，但会在不知不觉中积累你的成果。人生需要挑战，更需要坚持和勤奋,!,16,、人生在世：可以缺钱，但不能缺德,;,可以失言，但不能失信,;,可以倒下，但不能跪下,;,可以求名，但不能盗名,;,可以低落，但不能堕落,;,可以放松，但不能放纵,;,可以虚荣，但不能虚伪,;,可以平凡，但不能平庸,;,可以浪漫，但不能浪荡,;,可以生气，但不能生事。,17,、人生没有笔直路，当你感到迷茫、失落时，找几部这种充满正能量的电影，坐下来静静欣赏，去发现生命中真正重要的东西。,18,、在人生的舞台上，当有人愿意在台下陪你度过无数个没有未来的夜时，你就更想展现精彩绝伦的自己。但愿每个被努力支撑的灵魂能吸引更多的人同行。,1、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你,46,