决策树课件(共66张)

决策树根据李峰等人的PPT改编课件主要依据李航编写的《统计学习方法》编制，清华大学出版社另一本参考书：《数据挖掘与数学建模》国防工业出版社第1页，共66页。决策树1.1决策树模型与学习1.2特征选择1.3决策树的生成1.4决策树的剪枝1.5CART算法第2页，共66页。1.1决策树模型与学习1.1.1决策树模型1.1.2决策树与if-then规则1.1.3决策树与条件概率分布1.1.4决策树学习第3页，共66页。1.1.1决策树模型什么是决策树？定义1.1（决策树）分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。第4页，共66页。决策树学习算法的特点决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。显然，它属于有监督学习。从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。第5页，共66页。决策树学习的主要算法

建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。ID3

（J.RossQuinlan-1975）核心：信息熵C4.5—ID3的改进，核心：信息增益比CART（Breiman-1984），核心：基尼指数第6页，共66页。例1.找对象决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？(年龄)

母亲：26。

女儿：长的帅不帅？(长相)

母亲：挺帅的。

女儿：收入高不？(收入情况)

母亲：不算很高，中等情况。

女儿：是公务员不？(是否公务员)

母亲：是，在税务局上班呢。

女儿：那好，我去见见。第7页，共66页。1.1.2决策树与if-then规则由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。If-then规则集合的一重要性质：互斥并且完备第8页，共66页。1.1.3决策树与条件概率分布将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。

第9页，共66页。1.1.4决策树学习

第10页，共66页。1.1.4决策树学习目标：我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。决策树学习的损失函数：（通常是）正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题。现实中决策树学习通常采用启发式方法，即局部最优。具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。第11页，共66页。1.2特征选择

特征选择问题特征选择在于选取对训练数据具有分类能力的特征。如何判断一个特征对于当前数据集的分类效果？

也即确定选择特征的准则。第12页，共66页。ID年龄有工作有自己的房子信贷情况类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例1.2右表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的四个特征。表的最后一列是类别，是否同意贷款，取2个值：是、否。希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类。特征选择是决定用哪个特征来划分特征空间。第13页，共66页。1.2.2信息增益

第14页，共66页。熵-就分类而言，所有成员都属于一类，熵为零；不同类别

数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。

第15页，共66页。条件熵

第16页，共66页。信息增益

第17页，共66页。信息增益的具体公式

第18页，共66页。信息增益算法

第19页，共66页。例1.3对表1.1所给的训练数据集D,

根据信息增益准则选择最优特征。ID年龄有工作有自己的房子信贷情况类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否

第20页，共66页。1.2.3信息增益比

第21页，共66页。1.3决策树的生成

1.3.1ID3算法

第22页，共66页。例1.4对表1.1的训练数据集，利用ID3算法建立决策树ID年龄有工作信贷情况类别1青年否一般否2青年否好否3青年是好是5青年否一般否6中年否一般否7中年否好否13老年是好是14老年是非常好是15老年否一般否有自己的房子(A3)ID年龄有工作信贷情况类别4青年是一般是8中年是好是9中年否非常好是10中年否非常好是11老年否非常好是12老年都好是是否表1表2第23页，共66页。

第24页，共66页。有自己的房子是否是是否有工作ID年龄信贷情况类别3青年好是13老年好是14老年非常好是表3ID年龄信贷情况类别1青年一般否2青年好否5青年一般否6中年一般否7中年好否15老年一般否表4

这里生成的决策树只用到两个特征（两个内节点），ID3算法容易存在过拟合问题。第25页，共66页。补充：如何解决决策树的过拟合问题概念原因解决什么是过度拟合数据过度拟合数据是怎么产生的怎么去解决这个问题第26页，共66页。补充：如何解决决策树的过拟合问题——概念

过度拟合（overfitting）：如果决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合”。

定义：给定一个假设H，如果在假设空间上存在另一个假设H'，使得在训练集上H的错误率差比H'小，而在测试集上H的错误率却比H'要大，那么称假设H过度拟合训练数据。第27页，共66页。二.产生过度拟合数据问题的原因有哪些？原因1：样本问题（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？）（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；（3）建模时使用了样本中太多无关的输入变量。原因2：构建决策树的方法问题在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。第28页，共66页。三.如何解决过度拟合数据问题？针对原因1的解决方法：合理、有效地抽样，用相对能够反映业务逻辑的训练

集去产生决策树；针对原因2的主要解决方法：剪枝：提前停止树的增长或者对已经生成的树按照一

定的规则进行后剪枝。第29页，共66页。1.3.2C4.5的生成算法C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征。第30页，共66页。1.4决策树的剪枝

第31页，共66页。算法1.4树的剪枝算法

第32页，共66页。关于剪枝的补充——先剪枝剪枝是一个简化过拟合决策树的过程。有两种常用的剪枝方法：

先剪枝（prepruning）：通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类；有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：

1.定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；

2.达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效；第33页，共66页。补充：关于剪枝——先剪枝3.定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。

先剪枝方法不但相对简单，效率很高，而且不需要生成整个决策树，适合于解决大规模问题。该方法看起来很直接，但要精确地估计决策树生长的停止时间并不容易，即选取一个恰当的阈值是非常困难的。高阈值可能导致过分简化的树，而低阈值可能使得树的简化太少。第34页，共66页。解决决策树过拟合的另一种方法——随机森林根据总投票人数，250可能有所调整定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；女儿：长的帅不帅？(长相)

母亲：挺帅的。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。补充：如何解决决策树的过拟合问题CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。2特征选择

特征选择问题1所给的训练数据集D,

根据信息增益准则选择最优特征。C4.现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：决策树由结点和有向边组成。那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过关于剪枝的补充——后剪枝

后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。第35页，共66页。补充：关于剪枝的准则无论是通过及早停止还是后修剪来得到正确规模的树，一个关键的问题是使用什么样的准则来确定最终正确树的规模：1.使用训练集合(TrainingSet）和验证集合(ValidationSet)，来评估剪枝方法在修剪结点上的效用。2.使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能。测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。3.使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(MinimumDescriptionLength)准则。第36页，共66页。补充：关于剪枝的准则Reduced-ErrorPruning(REP,错误率降低剪枝）

REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。第37页，共66页。REP——错误率降低剪枝

该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点由如下步骤组成：1：删除以此结点为根的子树2：使其成为叶子结点3：赋予该结点关联的训练数据的最常见分类4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点训练集合可能过拟合，使用验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。第38页，共66页。Pesimistic-ErrorPruning(PEP,悲观错误剪枝）悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。第39页，共66页。PEP——悲观错误剪枝对于一个叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一棵子树，它有L个叶子节点，那么该子树的误判率估计为这样的话，我们可以看到一棵子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在第40页，共66页。PEP续的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：第41页，共66页。PEP续把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：这个条件就是剪枝的标准。当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。第42页，共66页。PEP——小例题T4这棵子树的误差率：子树误判次数的标准误差：子树替换为一个叶节点后，其误判个数为：7+0.5=7.5因为8.5+1.996>7.5，所以决定将子树T4替换这一个叶子节点。第43页，共66页。Cost-ComplexityPruning（CCP，代价复杂度剪枝)该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数α，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为其中，|N1|：子树Tt中的叶节点数；R（t）：结点t的错误代价，计算公式为R（t）=r（t）*p（t），r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；R（Tt）：子树Tt错误代价，计算公式为R（Tt）=∑R(i)，i为子树Tt的叶节点。第44页，共66页。例子我们以非叶结点T4为例，假设已有的数据有60条，那么R(t)=r(t)*p(t)=(7/16)*(16/60)=7/60R（Tt）=∑R(i)=(2/5)*(5/60)+(0/2)*(2/60)+(3/9)*(9/60)=5/60α=（R(t)-R（Tt）)/(|N1|-1)=1/60第45页，共66页。CCP续CCP剪枝算法分为两个步骤：1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列的剪枝树｛T0，T1，T2......Tm｝,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果；2.从子树序列中，根据真实的误差估计选择最佳决策树。第46页，共66页。CCP续通常使用1-SE（1standarderrorofminimumerror）规则从步骤1产生的一系列剪枝树中选择一棵最佳的剪枝决策树。方法为，假定一个含有N＇个样本的剪枝集，分别用在步骤1中产生的剪枝树Ti对该剪枝集进行分类，记Ti所有叶结点上长生的错分样本数为Ei，令E＇=min｛Ei｝，定义E＇的标准错误为：，所得的最佳剪枝树Tbest是满足条件Ei≤E＇+SE（E＇）且包含的接点数最少的那棵剪枝树Ti。第47页，共66页。几种后剪枝方法的比较REPPEPCCP剪枝方式自底向上自顶向下自底向上是否需要独立剪枝集需要不需要不需要误差估计剪枝集上的误差估计使用连续校正标准误差计算复杂度O(n)O(n)O(n2)第48页，共66页。1.5CART（分类与回归树）算法CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。这样的决策树等价于递归地二分每个特征。步骤：（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。第49页，共66页。1.5.1CART生成决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数(Giniindex)最小化准则，进行特征选择，生成二叉树。最开始我们可以按：表面覆盖为毛发与非毛发表面覆盖为鳞片与非鳞片恒温与非恒温来产生当前结点的左右两个孩子。我们将Gini指数来作为准则判别哪种划分比较好。第50页，共66页。GINI指数

第51页，共66页。1.5.2CART剪枝

第52页，共66页。记原始数据为D，长度为N(即图中有N个离散点)解决决策树过拟合的另一种方法——随机森林*当然可以使用决策树作为基本分类器本质仍然是分类问题：对于某个电影，有N个决策树，每个决策树对该电影有1个分类(1、2、3、4、5类)，求这个电影应该属于哪一类(可以是小数：分类问题变成了回归问题)*在所有属性上，对这n个样本建立分类器(ID3、C4.T4这棵子树的误差率：但是基于损失函数找到全局最优决策树是NP-完全问题。有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：*从所有属性中随机选择k个属性，选择最佳分割属性R：该电影的用户投票的平均得分(Rating)把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。这些分类器组成的“总分类器”，仍然叫做随机森林。*将数据放在这m个分类器上，最后根据这m个分类器不同类别

数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：实验结果第53页，共66页。UCI\method\precisioniriswineBreast-cancer感知机100%--KNN88%73.33%-朴素贝叶斯97.8%95.62%95.614%决策树100%96.4286%98.5507%第54页，共66页。解决决策树过拟合的另一种方法——随机森林BootstrapingBootstraping的名称来自成语“pullupbyyourownbootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。注：Bootstrap本义是指高靴子口后面的悬挂物、小环、带子，是穿靴子时用手向上拉的工具。“pullupbyyourownbootstraps”即“通过拉靴子让自己上升”，意思是“不可能发生的事情”。后来意思发生了转变，隐喻“不需要外界帮助，仅依靠自身力量让自己变得更好”第55页，共66页。解决决策树过拟合的另一种方法——随机森林组合模型——Bagging的策略（三个臭皮匠顶个诸葛亮的意思）

*

bootstrapaggregation

*

从样本集中重采样(有重复的)选出n个样本*在所有属性上，对这n个样本建立分类器(ID3、C4.5、

CART、SVM、Logistic回归等)*重复以上两步m次，即获得了m个分类器*将数据放在这m个分类器上，最后根据这m个分类器

的投票结果，决定数据属于哪一类第56页，共66页。解决决策树过拟合的另一种方法——随机森林第57页，共66页。解决决策树过拟合的另一种方法——随机森林随机森林应用非常广泛，根据目标变量的取值类型大致可分为两类一种是分类：当目标变量取值为离散型时（属性变量、种类变量、有序变量、多级变量等），采用该法可进行分类；

当目标变量为连续型，则可做回归，对应的预测结果是目标变量的分布。优点：可以产生高准确度的分类器第58页，共66页。解决决策树过拟合的另一种方法——随机森林随机森林在bagging基础上做了修改。*从样本集中用Bootstra