机器学习---预剪枝、后剪枝(REP、CCP、PEP、)

这篇具有很好参考价值的文章主要介绍了机器学习---预剪枝、后剪枝(REP、CCP、PEP、)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 为什么要进行剪枝

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

横轴表示在决策树创建过程中树的结点总数,纵轴表示决策树的预测精度。 实线显示的是决策树

在训练集上的精度,虚线显示的则是在⼀个独⽴的测试集上测量出来的精度。 随着树的增⻓,在

训练样集上的精度是单调上升的, 然⽽在独⽴的测试样例上测出的精度先上升后下降。 

出现这种情况的原因:

噪声、样本冲突,即错误的样本数据;特征即属性不能完全作为分类标准;巧合的规律性,数据量

不够⼤。

剪枝 (pruning)是决策树学习算法对付"过拟合"的主要⼿段。 在决策树学习中,为了尽可能正确分

类训练样本,结点划分过程将不断重复,有时会造成决策树分⽀过多,这时就可能因训练样本学

得"太好"了,以致于把训练集⾃身的⼀些特点当作所有数据都具有的⼀般性质⽽导致过拟合。因

此,可通过主动去掉⼀些分⽀来降低过拟合的⻛险。

如何判断决策树泛化性能是否提升呢? 可使⽤留出法,即预留⼀部分数据⽤作"验证集"以进⾏性

能评估。例如对下表的⻄⽠数据集,将其随机划分为两部分,其中编号为 {1,2,3,6, 7, 10,

14, 15, 16, 17} 的样例组成训练集,编号为 {4, 5, 8, 9, 11, 12, 13} 的样例组成验证

集。

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

假定采⽤信息增益准则来划分属性选择,则上表中训练集将会⽣成⼀棵下⾯决策树。 

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

接下来,将对这⼀棵树进⾏剪枝。 

2. 预剪枝

决策树剪枝的基本策略有"预剪枝" (pre-pruning)和"后剪枝"(post- pruning) 。

预剪枝是指在决策树⽣成过程中,对每个结点在划分前先进⾏估计,若当前结点的划分不能带来决

策树泛化性能提升,则停⽌划分并将当前结点标记为叶结点;后剪枝则是先从训练集⽣成⼀棵完

整的决策树,然后⾃底向上地对⾮叶结点进⾏考察,若将该结点对应的⼦树替换为叶结点能带来决

策树泛化性能提升,则将该⼦树替换为叶结点。

有多种不同的方式可以让决策树停止生长,下面介绍几种停止决策树生长的方法:

①定义一个高度,当决策树达到该高度时就可以停止决策树的生长 ,这是一种最为简单的方法;

②达到某个结点的实例具有相同的特征向量,即使这些实例不属于同一类,也可以停止决策树的生

长。这种方法对于处理数据中的数据冲突问题非常有效;

③定义一个阈值,当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长;

④定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值的大小来决定是否

停止决策树的生长。

预剪枝方法不但相对简单,效率很高,而且不需要生成整个决策树 ,适合于解决大规模问题。该

方法看起来很直接,但要精确地估计决策树生长的停止时间并不容易,即选取一个恰当的阈值是非

常困难的。高阈值可能导致过分简化的树,而低阈值可能使得树的简化太少。

在测试集上定义损失函数C,目标是通过剪枝使得在测试集上C的值下降。 例如通过剪枝使在测试

集上误差率降低。 首先,自底向上的遍历每一个非叶节点(除了根节点),将当前的非叶节点从树

中剪去,其下所有的叶节点合并成一个节点,代替原来被剪掉的节点。 然后,计算剪去节点前后

的损失函数,如果剪去节点之后损失函数变小了,则说明该节点是可以剪去的,并将其剪去;如果

发现损失函数并没有减少, 说明该节点不可剪去,则将树还原成未剪去之前的状态。 最后,重复

上述过程,直到所有的非叶节点(除了根节点)都被尝试了。

对于上例,⾸先,基于信息增益准则,会选取属性"脐部"来对训练集进⾏划分,并产⽣ 3 个分⽀,

如下图所示。然⽽,是否应该进⾏这个划分呢?预剪枝要对划分前后的泛化性能进⾏估计。在划分

之前,所有样例集中在根结点。

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

若不进⾏划分,该结点将被标记为叶结点,其类别标记为训练样例数最多的类别,假设将这个叶结

点标记 为"好⽠"。 ⽤前⾯表的验证集对这个单结点决策树进⾏评估。则编号为 {4,5,8} 的样例

被分类正确。另外 4个样例分类错误,于是验证集精度为3 / 7 ∗ 100% = 42.9%。 

在⽤属性"脐部"划分之后,上图中的结点2、3、4分别包含编号为 {1,2,3, 14}、 {6,7, 15,

17}、 {10, 16} 的训练样例,因此这 3 个结点分别被标记为叶结点"好⽠"、 "好⽠"、 "坏⽠"。

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

此时,验证集中编号为 {4, 5, 8,11, 12} 的样例被分类正确,验证集精度为5 / 7 ∗ 100% =

71.4% > 42.9%。于是,⽤"脐部"进⾏划分得以确定。

然后,决策树算法应该对结点2进⾏划分,基于信息增益准则将挑选出划分属性"⾊泽"。然⽽,在

使⽤"⾊泽"划分后,编号为 {5} 的验证集样本分类结果会由正确转为错误,使得验证集精度下降为

57.1%。于是,预剪枝策略将禁⽌结点2被划分。 对结点3,最优划分属性为"根蒂",划分后验证集

精度仍为 71.4%. 这个划分不能提升验证集精度,于是,预剪枝策略禁⽌结点3被划分。 对结点4,

其所含训练样例已属于同⼀类,不再进⾏划分。于是,基于预剪枝策略从上表数据所⽣成的决策树

如上图所示,其验证集精度为 71.4%。这是⼀棵仅有⼀层划分的决策树,也称"决策树桩" (decision

stump)。

3. 后剪枝

后剪枝先从训练集⽣成⼀棵完整决策树,继续使⽤上⾯的案例,从前⾯计算,了解到前⾯构造的决

策树的验证集精度为 42.9%。

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

后剪枝⾸先考察结点6,若将其领衔的分⽀剪除则相当于把6替换为叶结点。替换后的叶结点包含编

号为 {7, 15} 的训练样本,于是该叶结点的类别标记为"好⽠",此时决策树的验证集精度提高至 

57.1%。于是,后剪枝策略决定剪枝,如下图所示。

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

然后考察结点5,若将其领衔的⼦树替换为叶结点,则替换后的叶结点包含编号为 {6,7,15}的训

练样例,叶结点类别标记为"好⽠";此时决策树验证集精度仍为 57.1%. 于是,可以不进⾏剪枝。

对结点2,若将其领衔的⼦树替换为叶结点,则替换后的叶结点包含编号为 {1, 2, 3, 14} 的训

练样例,叶结点标记为"好⽠",此时决策树的验证集精度提高至 71.4%。于是,后剪枝策略决定剪

枝。对结点3和1,若将其领衔的子树替换为叶结点,则所得决策树的验证集精度分别为 71.4% 与

42.9%,均未得到提高,于是它们被保留。 最终,基于后剪枝策略所⽣成的决策树就如上图所示,

其验证集精度为 71.4%。 

对⽐两种剪枝⽅法:

后剪枝决策树通常⽐预剪枝决策树保留了更多的分⽀。

⼀般情形下,后剪枝决策树的⽋拟合⻛险很小,泛化性能往往优于预剪枝决策树。 但后剪枝过程

是在⽣成完全决策树之后进⾏的。 并且要自底向上地对树中的所有非叶结点进行逐⼀考察,因此

其训练时间开销比未剪枝决策树和预剪枝决策树都要⼤得多。

4. 剪枝的方法

Reduced-Error Pruning(REP,错误率降低剪枝):

REP方法是一种比较简单的后剪枝的方法,在该方法中,可用的数据被分成两个样例集合:一个训

练集用来形成学习到的决策树,一个分离的验证集用来评估这个决策树在后续数据上的精度,确切

地说是用来评估修剪这个决策树的影响。 这个方法的动机是:即使学习器可能会被训练集中的随

机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过

度拟合训练集中的虚假特征提供防护检验。

该剪枝方法考虑将树上的每个节点作为修剪的候选对象,决定是否修剪这个结点由如下步骤组成:

①删除以此结点为根的子树

②使其成为叶子结点

③赋予该结点关联的训练数据的最常见分类

④当修剪后的树对于验证集合的性能不会比原来的树差时,才真正删除该结点

训练集合可能过拟合,使用验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处

理结点,删除那些能够最大限度的提高验证集合的精度的结点,直到进一步修剪有害为止(有害是

指修剪会减低验证集合的精度)。

Pesimistic-Error Pruning(PEP,悲观错误剪枝):

悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概

念弥补REP中的缺陷,在评价子树的训练错误公式中添加了一个常数,假定每个叶子结点都自动对

实例的某个部分进行错误的分类。 把一棵子树(具有多个叶子节点)的分类用一个叶子节点来替

代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是,需要把子树的误判计

算加上一个经验性的惩罚因子。

对于一个叶子节点,它覆盖了N个样本,其中有E个错误,那么该叶子节点的错误率为

(E+0.5)/N。这个0.5就是惩罚因子,那么一棵子树,它有L个叶子节点,那么该子树的误判率估

计为机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

这样的话,可以看到一棵子树虽然具有多个子节点,但由于加上了惩罚因子,所以子树的误判率计

算未必占到便宜。剪枝后内部节点变成了叶子节点,其误判个数J也需要加上一个惩罚因子,变成

J+0.5 。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

的标准误差内。对于样本的误差率e,可以根据经验把它估计成各种各样的分布模型,比如是二项

式分布,比如是正态分布。 那么一棵树错误分类一个样本值为1,正确分类一个样本值为0,该树

错误分类的概率(误判率)为e(e为分布的固有属性,可以通过机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

 统计出来),那么树的误判次数就是伯努利分布,就可以估计出该树的误判次数均值和标准差:

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

把子树替换成叶子节点后,该叶子的误判次数也是一个伯努利分布,其概率误判率e为(E+0.5)/N,

因此叶子节点的误判次数均值为 机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

使用训练数据,子树总是比替换为一个叶节点后产生的误差小, 但是使用校正后有误差计算方法

却并非如此,当子树的误判个数大过对应叶节点的误判个数一个标准差之后,就决定剪枝:

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

这个条件就是剪枝的标准。当然并不一定非要大一个标准差,可以给定任意的置信区间,设定一定

的显著性因子,就可以估算出误判次数的上下界。 

比如:

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

T4这棵子树的误差率:(7+0.5*3)/16=0.53125

子树误判次数的标准误差:机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

子树替换为一个叶节点后,其误判个数为:7+0.5=7.5

因为8.5+1.996>7.5,所以决定将子树T4替换这一个叶子节点。 

Cost-Complexity Pruning(CCP,代价复杂度剪枝):

该算法为子树 Tt 定义了代价(cost)和复杂度(complexity),以及一个可由用户设置的衡量代价

与复杂度之间关系的参数α,其中,代价指在剪枝过程中因子树 Tt 被叶节点替代而增加的错分样

本,复杂度表示剪枝后子树 Tt 减少的叶结点数,α则表示剪枝后树的复杂度降低程度与代价间的关

系,定义为 机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

其中, |N1|:子树 Tt 中的叶节点数;

R(t):结点 t 的错误代价,计算公式为R(t)= r(t)*p(t), r(t)为结点 t 的错分样本率,

p(t)为落入结点 t 的样本占所有样本的比例;

R(Tt):子树 Tt 错误代价,计算公式为R(Tt)=∑R(i),i为子树 Tt 的叶节点。

比如:

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

我们以非叶结点 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 

CCP剪枝算法分为两个步骤:

①对于完全决策树 T 的每个非叶结点计算 α 值,循环剪掉具有最小 α 值的子树,直到剩下根节

点。在该步可得到一系列的剪枝树{T0, T1,T2......Tm}。其中 T0 为原有的完全决策树,Tm为

根结点,Ti+1为对 Ti 进行剪枝的结果;

②从子树序列中,根据真实的误差估计选择最佳决策树。

通常使用1-SE(1 standard error of minimum error)规则从步骤1产生的一系列剪枝树中选择一棵

最佳的剪枝决策树。方法为,假定 一个含有N'个样本的剪枝集,分别用在步骤1中产生的剪枝树

Ti 对该剪枝集进行分类,记 Ti 所有叶结点上长生的错分样本数为Ei,令E'=min {Ei},定义E'

的标准错误为:机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能

所得的最佳剪枝树 Tbest 是满足条件 Ei ≤ E'+ SE(E')且包含的接点数最少的那棵剪枝树 Ti。

几种后剪枝方法的比较:

机器学习---预剪枝、后剪枝(REP、CCP、PEP、),机器学习,机器学习,剪枝,人工智能文章来源地址https://www.toymoban.com/news/detail-707153.html

到了这里,关于机器学习---预剪枝、后剪枝(REP、CCP、PEP、)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习--人工智能概述

    入门人工智能,了解人工智能是什么。为啥发展起来,用途是什么,是最重要也是最关键的事情。大致有以下思路。 人工智能发展历程 机器学习定义以及应用场景 监督学习,无监督学习 监督学习中的分类、回归特点 知道机器学习的开发流程 人工智能在现实生活中的应用

    2024年01月19日
    浏览(60)
  • 人工智能与机器人|机器学习

    原文链接: https://mp.weixin.qq.com/s/PB_n8woxdsWPtrmL8BbehA 机器学习下包含神经网络、深度学习等,他们之间的关系表示如图2-7所示。 图2-7 关系图 那么什么是机器学习、深度学习、他们的区别又是什么呢? 2.7.1 什么是机器学习? 机器学习是 人工智能 (AI) 和计算机科学的一个分支,

    2024年02月06日
    浏览(79)
  • 人工智能、机器学习、深度学习的区别

    人工智能涵盖范围最广,它包含了机器学习;而机器学习是人工智能的重要研究内容,它又包含了深度学习。 人工智能是一门以计算机科学为基础,融合了数学、神经学、心理学、控制学等多个科目的交叉学科。 人工智能是一门致力于使计算机能够模拟、模仿人类智能的学

    2024年02月08日
    浏览(56)
  • 人工智能与开源机器学习框架

    链接:华为机考原题 TensorFlow是一个开源的机器学习框架,由Google开发和维护。它提供了一个针对神经网络和深度学习的强大工具集,能够帮助开发人员构建和训练各种机器学习模型。 TensorFlow的基本概念包括: 张量(Tensor):张量是TensorFlow中的核心数据结构,它表示多维数

    2024年02月22日
    浏览(63)
  • 【人工智能技术】机器学习工具总览

    当谈到训练计算机在没有明确编程的情况下采取行动时,存在大量来自机器学习领域的工具。学术界和行业专业人士使用这些工具在MRI扫描中构建从语音识别到癌症检测的多种应用。这些工具可在网上免费获得。如果您感兴趣,我已经编制了这些的排名(请参阅本页底部)以

    2024年02月04日
    浏览(65)
  • 一探究竟:人工智能、机器学习、深度学习

    1.1 人工智能是什么?          1956年在美国Dartmounth 大学举办的一场研讨会中提出了人工智能这一概念。人工智能(Artificial Intelligence),简称AI,是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的

    2024年02月17日
    浏览(53)
  • 12、人工智能、机器学习、深度学习的关系

    很多年前听一个机器学习的公开课,在QA环节,一个同学问了老师一个问题“ 机器学习和深度学习是什么关系 ”? 老师先没回答,而是反问了在场的同学,结果问了2-3个,没有人可以回答的很到位,我当时也是初学一脸懵,会场准备的小礼品也没有拿到。 后来老师解释“机

    2024年02月05日
    浏览(72)
  • 机器学习、人工智能、深度学习三者的区别

    目录 1、三者的关系 2、能做些什么 3、阶段性目标 机器学习、人工智能(AI)和深度学习之间有密切的关系,它们可以被看作是一种从不同层面理解和实现智能的方法。 人工智能(AI):人工智能是一门研究如何使计算机能够模仿人类智能的学科。它涵盖了各种技术和方法,

    2024年02月14日
    浏览(61)
  • 人工智能、机器学习与深度学习之间的关系

    图1. AI、ML与DL关系图 在我们深入研究机器学习和深度学习之前,让我们快速浏览一下它们所属的分支:人工智能(AI)。简而言之,人工智能是一个将计算机科学与大量数据相结合以帮助解决问题的领域。人工智能有许多不同的用例。图像识别,图像分类,自然语言处理,语音

    2024年01月18日
    浏览(63)
  • 深度学习2.神经网络、机器学习、人工智能

    目录 深度学习、神经网络、机器学习、人工智能的关系 大白话解释深度学习 传统机器学习 VS 深度学习 深度学习的优缺点 4种典型的深度学习算法 卷积神经网络 – CNN 循环神经网络 – RNN 生成对抗网络 – GANs 深度强化学习 – RL 总结 深度学习 深度学习、机器学习、人工智能

    2024年02月11日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包