如何解决决策树过拟合.ppt

1、,构造决策树 如何解决过度拟合数据问题,2,怎么去认识并去解决这个问题？,概念,原因,解决,什么是过度拟合数据,过度拟合数据是怎么产生的,怎么去解决这个问题,2,一.什么是过度拟合数据？,过度拟合（overfitting）的标准定义：给定一个假设空间H，一个假设h属于H，如果存在其他的假设h属于H,使得在训练样例上h的错误率比h小，但在整个实例分布上h比h的错误率小，那么就说假设h过度拟合训练数据。 overfittingt是这样一种现象：一个假设在训练数据上能够获得比其他假设更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据。此时我们就叫这个假设出现了overfitting的现象。,

2、3,二.产生过度拟合数据问题的原因有哪些？,原因1：样本问题 （1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？） （2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景； （3）建模时使用了样本中太多无关的输入变量。 原因2：构建决策树的方法问题 在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（

3、拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。,4,上面的原因都是现象，但是其本质只有一个，那就是“业务逻辑理解错误造成的”，无论是抽样，还是噪音，还是决策树等等，如果我们对于业务背景和业务知识非常了解，非常透彻的话，一定是可以避免绝大多数过拟合现象产生的。因为在模型从确定需求，到思路讨论，到搭建，到业务应用验证，各个环节都是可以用业务敏感来防止过拟合于未然的。,5,三.如何解决过度拟合数据问题的发生？,针对原因1的解决方法： 合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树； 针对原因2的解决方法（主要）： 剪枝：提前停止树的增长或者对已经生成的树按照一定的规

4、则进行后剪枝。,6,剪枝,剪枝是一个简化过拟合决策树的过程。有两种常用的剪枝方法： 先剪枝（prepruning）：通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类； 有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法： 1.定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法； 2.达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效；,7,剪枝,8,3.定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策

5、树的生长； 4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。 先剪枝方法不但相对简单，效率很高，而且不需要生成整个决策树，适合于解决大规模问题。该方法看起来很直接，但要精确地估计决策树生长的停止时间并不容易，即选取一个恰当的阈值是非常困难的。高阈值可能导致过分简化的树，而低阈值可能使得树的简化太少。,剪枝,后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估

6、计何时停止树增长很困难。,9,A1？,A2？,A3？,A4？,A5？,A1？,A2？,A4？,类A,类B,类A,类B,类A,类B,类A,类B,类A,类B,yes,no,yes,no,no,no,no,no,no,no,yes,yes,yes,yes,yes,yes,剪枝后,剪枝的思路,无论是通过及早停止还是后修剪来得到正确规模的树，一个关键的问题是使用什么样的准则来确定最终正确树的规模： 1.使用训练集合(Training Set）和验证集合(Validation Set)，来评估剪枝方法在修剪结点上的效用。 2.使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外

7、的数据的评估性能。测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。 3.使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则。,10,Reduced-Error Pruning(REP,错误率降低剪枝）,REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。 这个方法的动机是：即使学习器可能会被训练集中的随机

8、错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。,11,REP,该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成： 1：删除以此结点为根的子树 2：使其成为叶子结点 3：赋予该结点关联的训练数据的最常见分类 4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点 因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。,12

9、,REP,REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过如果训练集较小，通常不考虑采用REP算法。 尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。,13,Pesimistic-Error Pruning(PEP,悲观错误剪枝）,14,悲观错误剪枝法是根据剪

10、枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。,PEP,15,把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为 这样的话，我们可以看到一颗子树虽然具有多个子节点，但由

11、于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在,PEP,16,的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。 那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过 统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：,17,把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概

12、率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为 使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝： 这个条件就是剪枝的标准。当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。,PEP,PEP例子,18,类1 类1 类2 T4这棵子树的误差率： 子树误判次数的标准误差： 子树替换为一个叶节点后，其误判个数为：7+0.5=7.5 因为8.5+1.9967.5，所以决定将子树T4替换这一个叶子节点。,T4 9 7,

13、T6 3 4,T7 6 3,T8 3 2,T9 0 2,T4 9 7,T6 3 4,T7 6 3,T8 3 2,PEP,19,悲观错误剪枝方法的优点： 1.得到的决策树是关于测试数据集的具有高精度的子树，并且是规模最小的树； 2.它的计算复杂度是线性的。因为决策树中的每个非叶子结点只需要访问一次就可以评估其子树被修剪的概率； 3.由于使用独立的测试数据集，和原始决策树相比，修剪后的决策树对未来新事例的预测偏差较小。,PEP,20,悲观错误剪枝方法的缺点： 1.PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉； 2.PEP

14、方法会有剪枝失败的情况出现。,Cost-Complexity Pruning（CCP，代价复杂度剪枝),21,该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，则表示剪枝后树的复杂度降低程度与代价间的关系，定义为 其中， |N1|：子树Tt中的叶节点数； R（t）：结点t的错误代价，计算公式为R（t）=r（t）*p（t）， r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本 的比例； R（Tt）：子树

15、Tt错误代价，计算公式为R（Tt）=R(i)，i为子树Tt的叶节点。,CCP,22,类1 类1 类2 我们以非叶结点T4为例，假设已有的数据有60条，那么 R(t)=r(t)*p(t)=(7/16)*(16/60)=7/60 R（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,T9 2 0,T4 9 7,T6 3 4,T7 6 3,T8 3 2,CCP,23,CCP剪枝算法分为两个步骤： 1.对于完全决策树T的每个非叶结点计算值，循环剪掉具有最小值的子树，直到剩下根节点。在该步可得

16、到一系列的剪枝树T0，T1，T2.Tm,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果； 2.从子树序列中，根据真实的误差估计选择最佳决策树。,CCP,24,通常使用1-SE（1 standard error of minimum error）规则从步骤1产生的一系列剪枝树中选择一棵最佳的剪枝决策树。方法为，假定一个含有N个样本的剪枝集，分别用在步骤1中产生的剪枝树Ti对该剪枝集进行分类，记Ti所有叶结点上长生的错分样本数为Ei，令E=minEi，定义E的标准错误为： ，所得的最佳剪枝树Tbest是满足条件EiE+SE（E）且包含的接点数最少的那棵剪枝树Ti。,其它的后剪枝方法,25,最小错误剪枝(Mini