决策树后剪枝算法二错误率降低剪枝REP
决策树后剪枝算法(一)代价复杂度剪枝CPP
决策树后剪枝算法(二)错误率降低剪枝REP
决策树后剪枝算法(三)悲观错误剪枝PEP
决策树后剪枝算法(四)最小错误剪枝MEP
剪枝,是一个“用准确性换取简单性”的思想。它允许决策树对训练集过拟合,再通过删除对泛化精度无贡献的子分支,从而修剪出一颗较小的树。以下列出几种较常见的后剪枝算法,及其机制对比:
CCP | REP | PEP | MEP | |
---|---|---|---|---|
剪枝方式 | 自底向上 | 自底向上 | 自顶向下 | 自底向上 |
计算复杂度 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) |
误差估计 | 标准误差 | 剪枝集上误差 | 连续性矫正 | 概率估计 |
是否需要额外剪枝集 | 否 | 是 | 否 | 否 |
(2)错误率剪枝(REP)
错误率剪枝算法相对较简单朴素,同时也具备速度快的优点,但容易过度修剪。主要思路为划分训练集 - 验证集:训练集用形成学习到的决策树;验证集用来评估修剪决策树。大致流程可描述为:对于训练集上构建的过拟合决策树,自底向上遍历所有子树进行剪枝,直到针对交叉验证数据集无法进一步降低错误率为止。
(2.1)数学推导
评价标准:
R t e s t ( T t ) v s R t e s t ( t ) R t e s t ( T ) = e t e s t ( T ) n t e s t ( T ) R_{test}(T_t)~~vs~~R_{test}(t)\\ R_{test}(T)=\frac{e_{test}(T)}{n_{test}(T)} Rtest(Tt) vs Rtest(t)Rtest(T)=ntest(T)etest(T)
解读:
- R t e s t ( T ) R_{test}(T) Rtest(T)表示错误率,用来比较剪枝前后好坏。
- n t e s t ( T ) n_{test}(T) ntest(T)为 T T T节点分到的测试集样本数, e t e s t ( T ) e_{test}(T) etest(T)为 T T T节点对测试集分类错误样本数。
- 因测试集固定, n t e s t ( T ) n_{test}(T) ntest(T)为定值,评价标准可简化为 e t e s t ( T ) e_{test}(T) etest(T)。
补充说明,每个节点的类别确定方法,为多数表决。即在训练决策树时,对每个节点分到的训练样本进行多数表决,为每个节点贴上类别标签。以便后续验证集评估剪枝前后,错误样本数进行比较。
(2.2)算法流程
考虑决策树上每个分支节点作为剪枝候选对象,自底向上遍历,判断是否剪枝步骤如下:
- (1)删除以此节点为根的子树,使其成为叶子结点。
- (2)根据多数表决法,赋予该节点关联的训练数据类别。
- (3)比较删除前后错误样本数,判断是否剪枝该节点。
(2.3)例题计算
需注意的是,该例题为突出剪枝过程,巧妙设计为每个内部节点均可剪枝。实际应用中根据比较结果判断。
数据集
训练集生成决策树
进行多数表决类别打标签
基于测试集剪枝
(1)第四层 纹理
剪枝前:错误2 / 剪枝后:错误1
剪枝后错误数下降,故剪枝替换为单节点。
(2)第三层 色泽
剪枝前:错误1 / 剪枝后:错误1
剪枝后错误率未下降,根据奥卡姆剃刀原则,等错误率选复杂度低的树,故剪枝替换为单节点。
(3)第二层 色泽
剪枝前:错误2 / 剪枝后:错误1
剪枝后错误数下降,故剪枝替换为单节点。
(4)第二层 根蒂
剪枝前:错误1 / 剪枝后:错误1
剪枝后错误率未下降,根据奥卡姆剃刀原则,等错误率选复杂度低的树,故剪枝替换为单节点。
(5)第一层 脐部
剪枝前:错误2 / 剪枝后:错误4
剪枝后,错误数明显上升,故不能剪枝。
(6)最终结果
(1.4)代码实现
C4.5算法及REP剪枝手写实现
链接:https://pan.百度.com/s/1gl4TzGfVQWbqgKTZwQqXeQ?pwd=uof6
提取码:uof6
代码参考:http://www.hzcourse.com/web/refbook/detail/9970/226
————————————————————————————————————————————————————————————
参考资料:
[1] 现代决策树模型及其编程实践 黄智濒 编著
[2] 统计学习方法(第二版) 李航 著
[3] https://zhuanlan.zhihu.com/p/548186344
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggceac
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13