厦门网站建设网页设计,苏州网络推广seo服务,金华网站建设明细报价表,网页微信怎么登陆决策树的过拟合问题决策树是一种分类器#xff0c;通过ID3#xff0c;C4.5和CART等算法可以通过训练数据构建一个决策树。但是#xff0c;算法生成的决策树非常详细并且庞大#xff0c;每个属性都被详细地加以考虑#xff0c;决策树的树叶节点所覆盖的训练样本都是“纯”的…决策树的过拟合问题决策树是一种分类器通过ID3C4.5和CART等算法可以通过训练数据构建一个决策树。但是算法生成的决策树非常详细并且庞大每个属性都被详细地加以考虑决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话你会发现对于训练样本而言这个树表现完好误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习成为决策树的部分但是对于测试数据的表现就没有想象的那么好或者极差这就是所谓的过拟合(Overfitting)问题。决策树的剪枝决策树的剪枝有两种思路预剪枝Pre-Pruning和后剪枝Post-Pruning预剪枝Pre-Pruning在构造决策树的同时进行剪枝。所有决策树的构建方法都是在无法进一步降低熵的情况下才会停止创建分支的过程为了避免过拟合可以设定一个阈值熵减小的数量小于这个阈值即使还可以继续降低熵也停止继续创建分支。但是这种方法实际中的效果并不好。后剪枝Post-Pruning决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查判断如果将其合并熵的增加量是否小于某一阈值。如果确实小则这一组节点可以合并一个节点其中包含了所有可能的结果。后剪枝是目前最普遍的做法。后剪枝的剪枝过程是删除一些子树然后用其叶子节点代替这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类 称为majority class majority class 在很多英文文献中也多次出现。后剪枝算法后剪枝算法有很多种这里简要总结如下Reduced-Error Pruning (REP,错误率降低剪枝这个思路很直接完全的决策树不是过度拟合么我再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树我们尝试着把它替换成一个叶子节点该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替这样就产生了一个简化决策树然后比较这两个决策树在测试数据集中的表现如果简化决策树在测试数据集中的错误比较少那么该子树就可以替换成叶子节点。该算法以bottom-up的方式遍历所有的子树直至没有任何子树可以替换使得测试数据集的表现得以改进时算法就可以终止。Pessimistic Error Pruning (PEP悲观剪枝PEP剪枝算法是在C4.5决策树算法中提出的 把一颗子树具有多个叶子节点用一个叶子节点来替代我研究了很多文章貌似就是用子树的根来代替的话比起REP剪枝法它不需要一个单独的测试数据集。PEP算法首先确定这个叶子的经验错误率empirical为E0.5/N0.5为一个调整系数。对于一颗拥有L个叶子的子树则子树的错误数和实例数都是就应该是叶子的错误数和实例数求和的结果则子树的错误率为e这个e后面会用到子树的错误率然后用一个叶子节点替代子树该新叶子节点的类别为原来子树节点的最优叶子节点所决定这句话是从一片论文看到的但是论文没有讲什么是最优通过参考其他文章貌似都是把子树的根节点作为叶子也很形象就是剪掉所有根以下的部分J为这个替代的叶子节点的错判个数但是也要加上0.5即KJ0.5。最终是否应该替换的标准为被替换子树的错误数-标准差 新叶子错误数出现标准差是因为我们的子树的错误个数是一个随机变量经过验证可以近似看成是二项分布就可以根据二项分布的标准差公式算出标准差就可以确定是否应该剪掉这个树枝了。子树中有N的实例就是进行N次试验每次实验的错误的概率为e符合BNe的二项分布根据公式均值为Ne方差为Ne1-e标准差为方差开平方。二项分布的知识在文章最后网上找到这个案例来自西北工业大学的一份PPT我个人觉得PPT最后的结论有误PEP案例这个案例目的是看看T4为根的整个这颗子树是不是可以被剪掉。树中每个节点有两个数字左边的代表正确右边代表错误。比如T4这个节点说明覆盖了训练集的16条数据其中9条分类正确7条分类错误。我们先来计算替换标准不等式中关于子树的部分子树有3个叶子节点分别为T7、T8、T9因此L3子树中一共有16条数据根据刚才算法说明把三个叶子相加所以N16子树一共有7条错误判断所以E7那么根据e的公式e70.5×3/ 16 8.5 /16 0.53根据二项分布的标准差公式标准差为16×0.53×1-0.53^0.5 2.00子树的错误数为“所有叶子实际错误数0.5调整值” 7 0.5×3 8.5把子树剪枝后只剩下T4T4的错误数为70.57.5这样 8.5-2 7.5 因此不满足剪枝标准不能用T4替换整个子树。Cost-Complexity Pruning(CCP代价复杂度剪枝)CART决策树算法中用的就是CCP剪枝方法。也是不需要额外的测试数据集。Minimum Error Pruning(MEP)Critical Value Pruning(CVP)Optimal Pruning(OPP)Cost-Sensitive Decision Tree Pruning(CSDTP)。附录二项分布 Binomial Distribution考察由n次随机试验组成的随机现象它满足以下条件重复进行n次随机试验
n次试验相互独立
每次试验仅有两个可能结果
每次试验成功的概率为p失败的概率为1-p。
在上述四个条件下设X表示n次独立重复试验中成功出现的次数显然X是可以取01…n等n1个值的离散随机变量且它的概率函数为二项分布概率公式这个分布称为二项分布记为b(n,p)。二项分布的均值E(X)np
二项分布的方差Var(X)np(1-p)。
标准差就是方差开平方
举个例子比较好理解。扔好多次硬币就是一个典型的二项分布符合四项条件扔硬币看正反面是随机的我们重复进行好多次比如扔5次
每次扔的结果没有前后关联相互独立
每次扔要么正面要么反面
每次正面看作成功概率1/2, 反面看作失败概率1-1/2 1/2 即这里p0.5
于是这个实验就符合B50.5的二项分布。那么计算扔5次硬币出现2次正面的概率就可以带入公式来求PX2 C(52)×(0.5)2×(0.5)3 31.25%这个实验的的期望均值为np5×0.52.5意思是每扔5次都记录正面次数然后扔了好多好多的“5次”这样平均的正面次数为2.5次这个实验的方差为np(1-p)5×0.5×0.51.25表示与均值的误差平方和表示波动情况。多说一句二项分布在n很大时趋近于正态分布。作者程sir
链接http://www.jianshu.com/p/794d08199e5e
來源简书
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
