决策树的剪枝理论

《决策树的剪枝理论》由会员分享，可在线阅读，更多相关《决策树的剪枝理论（33页珍藏版）》请在金锄头文库上搜索。

1、决策树的剪枝理论(2013-11-19 16:39:21)转 载标签： 数据挖掘决策树剪枝it分类： 数据挖掘剪枝理论，决策树的剪枝在上一节中没有仔细讲，趁这个机会学习了剪枝 的基础理论，这里会详细学习。决策树为什么(WHY)要剪枝？原因是避免决策树过拟合(Overfitting)样本。 前面的算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑， 决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训 练样本进行分类的话，你会发现对于训练样本而言，这个树表现完好，误差率 极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也 会被决策树学习，成为决策树的部

2、分，但是对于测试数据的表现就没有想象的 那么好，或者极差，这就是所谓的过拟合(Overfitting)问题。Quinlan 教授试 验，在数据集中，过拟合的决策树的错误率比经过简化的决策树的错误率要高。现在问题就在于，如何(HOW)在原生的过拟合决策树的基础上，生成简化版 的决策树？可以通过剪枝的方法来简化过拟合的决策树。剪枝可以分为两种： 预剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我们来详细学习下这两种 方法：PrePrune：预剪枝，及早的停止树增长，方法可以参考见上面树停止增长 的方法。PostPrune：后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简

3、化版 的剪枝决策树。其实剪枝的准则是如何确定决策树的规模，可以参考的剪枝思路有以下几 个：1：使用训练集合(Training Set）和验证集合(Validation Set)，来评估 剪枝方法在修剪结点上的效用2：使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是 否会改善训练集合外的数据的评估性能，如使用 Chi- Square（Quinlan，1986）测试来进一步扩展结点是否能改善整个分类数据的性 能，还是仅仅改善了当前训练集合数据上的性能。3：使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时， 停止树增长，如 MDL(Minimum Description

4、Length)准则。我们先看下使用思路一来解决问题的集中后剪枝方法：Reduced-Error Pruning(REP,错误率降低剪枝）该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这 个结点有如下步骤组成：1：删除以此结点为根的子树2：使其成为叶子结点3：赋予该结点关联的训练数据的最常见分类4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该 结点因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行 上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的 精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)REP 是最

5、简单的后剪枝方法之一，不过在数据量比较少的情况下，REP 方法 趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略， 所以在验证数据集合比训练数据集合小的多时，要注意这个问题。尽管 REP 有这个缺点，不过 REP 仍然作为一种基准来评价其它剪枝算法的 性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思 路。由于验证集合没有参与决策树的创建，所以用 REP 剪枝后的决策树对于测 试样例的偏差要好很多，能够解决一定程度的过拟合问题。Pessimistic Error Pruning(PEP，悲观剪枝）先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二

6、项式 分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能 的度量。这样做的结果，是对于大的数据集合，该剪枝策略能够非常接近观察 精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计 有效的，但是在实践中有效。PEP 为了提高对测试集合的预测可靠性，PEP 对误差估计增加了连续性校正 (Continuity Correction)。PEP 方法认为，如果：成立，则 Tt 应该被剪枝，上式中： 其中，e(t)为结点 t 出的误差；i 为覆盖 Tt 的叶子结点；Nt 为子树 Tt 的 叶子树；n(t)为在结点 t 处的训练集合数量。PEP 采用自顶向下的方式，如果

7、某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当 前决策树后剪枝算法中经度比较高的算法之一，但是饿存在有缺陷。首先，PEP 算法是唯一使用 Top-Down 剪枝策略，这种策略会导致与先剪枝出现同样的问题， 将该结点的某子节点不需要被剪枝时被剪掉；另外 PEP 方法会有剪枝失败的情 况出现。虽然 PEP 方法存在一些局限性，但是在实际应用中表现出了较高的精度,。 两外 PEP 方法不需要分离训练集合和验证机和，对于数据量比较少的情况比较 有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程 中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂

8、 度也只和非剪枝树的非叶子节点数目成线性关系。可能有同学会对上面的那个不等式有疑问，可以参考这篇文章 http:/ 中关于 PEP 剪枝部 分内容。PEP 方法实际上是将结点误差数目看做二项式分布，根据期望和方差 得到的结果。Cost-Complexity Pruning(CCP、代价复杂度)CCP 方法包含两个步骤：1：从原始决策树 T0 开始生成一个子树序列T0、T1、T2、.、Tn,其中 Ti+1 是从 Ti 总产生，Tn 为根节点2：从子树序列中，根据树的真实误差估计选择最佳决策树。在步骤一中，生成子树序列T0、T1、T2、.、Tn的基本思想是从 T0 开 始，裁剪 Ti 中关于训练数

9、据集合误差增加最小的分支来得到 Ti+1。实际上当 一棵树 T 在结点 t 出剪枝时，它的误差增加直观上认为是:其中 R(t)为在结点 t 的子树被裁剪后结点 t 的误差，R(Tt)为在结点 t 的子 树没被裁剪时子树 T 的误差。不过剪枝后 T 的叶子树减少了|L(Ti)|-1，其中 |L(Ti)|为子树 Ti 的叶子树，也就是说 T 的复杂性降低。因此考虑到树的复杂 性因素，树分支被裁剪后误差增加率可以由下式决定：Ti+1 就是选择 Ti 中具有最小alpha 值所对应的剪枝树如何从第一步骤产生的子树序列T0、T1、T2、.、Tn中选择出最佳决策 树是 CCP 方法的第二步骤的关键。通常可

10、以采用 V-交叉验证(V-fold Cross- Validation)和基于独立剪枝数据集两种方法，这两种方法可以参考 (Classification And Regression Trees,Breiman et.al)。当使用基于独立数 据集剪枝时，和 REP 方法相比，CCP 选择出来的最有决策树，不是从原始决策 树 T 的所有可能子树中得到，所以有可能会找到到最有决策树。其它如 Minimum Error Pruning(MEP)，Critical Value Pruning(CVP)， Optimal Pruning(OPP)，Cost-Sensitive Decision Tre

11、e Pruning(CSDTP)等方 法，这些剪枝方法各有利弊，关注不同的优化点，感兴趣的同学可以学习下。剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究 表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成 的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不 大。反而是剪枝方法对于最优树的生成更为关键。重点理解这些剪枝方法的理 论，对于最终最优树的生成是有好处的，其中上篇文章 http:/ 中 C4.5 使用了 PEP 剪枝方法，本文 的 CART 使用了 CCP 的剪枝方法，实际上，不应该对于算法使用的剪枝方法过于 追根究底，

12、而是应该对于剪枝过程理解透彻，对于在何种场景下对于不同的数 据类型使用何种的剪枝方法能够获得最优树的选择，才是真正理解了剪枝的理 论和重要性。背包问题(Knapsack problem)是在 1978 年由 Merkel 和 Hellman 提出的，是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过 W 的前提下，总

13、价值是否能达到 V？背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而引人注目。但是，大多数一次背包体制均被破译了，因此很少有人使用它。目目录录1 基本介绍2 背包问题题目基本思路空间复杂示例程序递归实现程序测试数据总结3 完全背包题目基本思路简单有效转为问题实现总结4 三种背包问题背包混合小结5 多重问题题目基本算法转为问题算法小结6 二维费用问题算法限制小结7 分组背包问题算法小结8 依赖问题简化问题算法一般问题小结9 泛化物品定义泛化物品问题泛化小结10 问法变化输出方案求方案总最优方案小结1 基本介绍它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品

14、并将它们放到背包中并加密消息。背包中的物品总重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而引人注目。但是，大多数一次背包体制均被破译了，因此很少有人使用它。2 背包问题题目题目有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 ci，价值是 wi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。基本思路基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即 fiv表示

15、前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi。可以压缩空间，fv=maxfv,fv-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i-1 件物品的问题。如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入容量为 v 的背包中”，价值为 fi-1v；如果放第 i 件物品，那么问题就转化为“前 i-1 件物品放入剩下的容量为 v-ci的背包中”，此时能获得的最大价值就是 fi-1v-ci再加上通过放入第 i 件物品获得的价值 wi。注意 fv有意义当且仅当存在一个前 i 件物品的子集，其费用总和为 v。所以按照这个方程递推完毕后，最终的答案并不一定是 fNV，而是 fN0.V的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项 fv-1，这样就可以保证 fNV就是最后的答案。至于为什么这样就可以，由你自己来体会了。空间复杂空间复杂以上方法的时间和空间复杂度均为 O(N*V），其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到 O(N）。先考虑上面讲的基本思