文档介绍：决策树的剪枝理论
决策树的剪枝理论
  (2022-11-19 16:39:21)
转载▼
标签： 
数据挖掘
 
决策树
 
剪枝
 
it
分类： 数据挖掘
剪枝理论，决策树的剪枝在上一节中没有仔细讲，况出现。
虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度,。两外PEP方法不需要别离训练集合和验证机和，对于数据量比拟少的情况比拟有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。
可能有同学会对上面的那个不等式有疑问，可以参考这篇文章 中关于PEP剪枝局部内容。PEP方法实际上是将结点误差数目看做二项式分布，根据期望和方差得到的结果。
 
Cost-Complexity Pruning(CCP、代价复杂度)
CCP方法包含两个步骤：
1：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点
2：从子树序列中，根据树的真实误差估计选择最正确决策树。
在步骤一中，生成子树序列{T0、T1、T2、...、Tn}的根本思想是从T0开始，裁剪Ti中关于训练数据集合误差增加最小的分支来得到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方法的第二步骤的关键。通常可以采用V-交叉验证(V-fold Cross-Validation)和基于独立剪枝数据集两种方法，这两种方法可以参考(Classification And Regression Trees,Breiman )。当使用基于独立数据集剪枝时，和REP方法相比，CCP选择出来的最有决策树，不是从原始决策树T的所有可能子树中得到，所以有可能会找到到最有决策树。
 
其它如Minimum Error Pruning(MEP)，Critical Value Pruning(CVP)，Optimal Pruning(OPP)，Cost-Sensitive Decision Tree Pruning(CSDTP)等方法，这些剪枝方法各有利弊，关注不同的优化点，感兴趣的同学可以学****下。
 
剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究说明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保存最重要的属性划分，差异不大。反而是剪枝方法对于最优树的生成更为关键。重点理解这些剪枝方法的理论，对于最终最优树的生成是有好处的，其中上篇文章，本文的CART使用了CCP的剪枝方法，实际上，不应该对于算法使用的剪枝方法过于追根究底，而是应该对于剪枝过程理解透彻，对于在何种场景下对于不同的数据类型使用何种的剪枝方法能够获得最优树的选择，才是真正理解了剪枝的理论和重要性。
 
背包问题(Knapsack problem)是在1978年由Merkel和Hellman提出的，是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最适宜的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能到达V？背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而引人注目。但是，大多数一次背包体制均被破译了，因此很少有人使用它。
目
录
1根本介绍
2背包问题
题目
根本思路
空间复杂
例如程序
递归实现
程序
测试数据
总结
3完全背包
题目
根本思路
简单有效
转为问题
实现
总结
4三种背包