第八章：集成学习报告ppt课件.pptx

《第八章：集成学习报告ppt课件.pptx》由会员分享，可在线阅读，更多相关《第八章：集成学习报告ppt课件.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、朱辉星 2016年11月集成学习（ensemble learning）：通过构建并结合多个学习器来完成学习任务。（也被成为：多分类器系统、基于委员会的学习）一般结构：先产生一组“个体学习器”（individual learner），再用某种策略将他们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生C4.5决策树算法、BP神经网络算法同质集成中只包含同种类型的个体学习器个体学习器：基学习器对应算法：基学习算法异质集成中包含不同类型的个体学习器个体学习器：由不同学习算法生成个体学习器：组件学习器（或直接称个体学习器）集成学习优点：通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛

2、化性能。这对“弱学习器”（weak learner）尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被直接成为弱学习器虽然从理论上来说使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，希望使用较少的个体学习器，人们常常会使用比较强的学习器。如何能获得比最好的单一学习器更好的性能呢？在二分类任务中：三个分类器在三个测试样本上的表现如下:分类分类器器测试测试例例1 1测试测试例例2 2测试测试例例3 3h1h2h3集成分类分类器器测试测试例例1 1测试测试例例2 2测试测试例例3 3h1h2h3集成分类分类器器测试测试例例1 1测试测试例例2 2测试测试例例3

3、3h1h2h3集成a.集成提升性能b.集成不起作用c.集成起负作用集成学习的结果通过投票法产生a.每个分类器都只有66.6%的精度，但集成学习却达到了100%；b.三个分类器没有差别，集成后性能没有提高；c.每个分类器精度只有33.3%，集成学习结果变得更糟；以上例子显示要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”。即学习器间具有差异性。个体学习器至少个体学习器至少不差于弱学习器不差于弱学习器考虑二分类问题： 和真实函数 ，假定基分类器的错误率为 ，即对每个基分类器 有假设集成通过简单投票法集合T个基分类器，若超过半数的基分类

4、器正确，则集成分类就正确 1, 1y fih( ( )( )iP h xf x 1( )TiiHxsignh x假设基分类器的错误率相互独立，则由Hoeffding不等式可知，集成的错误率为20( )( )(1)TkT kkTP H xf xk21exp(1 2 )2T上式显示出：随着集成中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。然而我们必须注意到，上面的分析有一个关键假设：及学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，他们显然不可能相互独立。事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性提高之后，要增加多样性就

5、需牺牲正确性。如何产生“好而不同”的个体学习器集成研究核心根据个体学习器的生成方式，集成学习方法可分为两大类：个体学习器间存在强依赖关系、必须串行生成的序列化方法个体学习器间不存在强依赖关系、可同时生成的并行化方法代表：代表：BoostingBoosting代表：代表：BaggingBagging和和 “随机森林随机森林” （Random forestRandom forest）Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制：然后基于调整后的样本分布来训练下一个基学习器再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注先从初

6、始训练集训练出一个基学习器如此重复进行，直至基学习器数目达到事先指定的值如此重复进行，直至基学习器数目达到事先指定的值T T，最终将这最终将这T T个基学习器进行加权结合。个基学习器进行加权结合。Boosting族算法最著名的代表：AdaBoost其中 是真实函数基于“加性模型”，即基学习器的线性组合来最小化指数损失函数（exponential loss function）1, 1 ,iyf 1( )( )TtttH xhx( )( )exp(|)f x H xx DH DEe若H(x)能令指数函数最小化，则考虑（5）式对H(x)的偏导令(6)式为零可解得：exp( )( )(|)( ( )1

7、| )( ( )1| )( )H xH xH DeP f xxeP f xxH x 1( ( )1| )( )ln2( ( )1| )P f xxH xP f xx 因此，有1( ( )1| )( )ln2( ( )1)|P f xxsign H xsignP f xx 1, ( ( )1| )( ( )1| )1, ( ( )1| )( ( )1| )P f xxP f xxP f xxP f xx 1,1argmax( ( )| )yP f xy x 这意味着sign(H(x)达到了贝叶斯最优错误率。换言之，若指数损失函数最小化，则分类错误率也将最小化.在Adaboost算法中，第一个基分

8、类器h1是通过直接将基学习算法用于初始数据分布而得；此后迭代地生成 和 ，当基分类器 基于分布 产生后，该分类器的权重 应使得 最小化指数损失函数：thtthtDttth ( )( )exp(|)t ttf xhxtttx DhDEe( ( )( )( ( )( )tttx DttEef xh xef xh x( ( )( )( ( )( )ttttx Dtx DtePf xh xe Pf xh x(1)ttttee其中：( ( )( )tx DtPh xf x考虑指数损失函数的倒数：令(10)为零可解得：这恰是（）中算法分类器权重更新公式。exp(|)(1)tttttttthDee 11ln

9、2tttAdaBoost算法在获得 之后样本分布将进行调整，使下一轮的基学习器 能纠正 的一些错误。理想的 能纠正 的全部错误，即最小化1tHth1tHth1tH1( )( )( )exp1(|)ttf xHxhxttx DHhDEe1( )( )( )( )ttf x Hxf x hxx DEee注意到 ，式(12)可使用 的泰勒展式近似为于是，理想的基学习器22( )( )1tfxhx( )( )tfx hxe122( )( )exp1( )( )(|)(1( )2tf x Hxtttx Dfx hxHhDEef x1( )( )1(1( ) ( )2tf x Hxx DtEef x h

10、xexp1( )argmin(|)ttthh xHhD注意到 是一个常数，令 表示一个分布1( )( )1argmin1( ) ( )2tf x Hxx DhEef x h x1( )( )argmax( ) ( )tf x Hxx DhEef x h x11( )( )( )( )argmax( ) ( )ttf x Hxx Df x Hxhx DeEf x h xEe1( )( )tf x Hxx DEetD11( )( )( )( )( )( )ttf x Hxtf x Hxx DD x eD xEe则根据数学期望的定义，这等价于令由f(x),h(x) -1,+1，有11( )( )(

11、)( )( )argmax( ) ( )ttf x Hxtx Df x Hxhx Deh xEf x h xEeargmax( ) ( )x DhEf x h x( ) ( ) 1 2( ( )( )f x h xf xh x 1,( )( )1,( )( )f xh xf xh x 这恰是()中算法第7行的样本分布更新公式( )( )1( )( )( )( )ttf x Hxtf x Hxx DD x eDxEe1( )( )( )( )( )( )( )tt ttf x Hxf xhxf x Hxx DD x eeEe1( )( )( )( )( )( )( )tt ttf x Hxx D

12、f xhxtf x Hxx DEeD x eEe由(15)式得1( )( )( )( )tttf x Hxf xh x1( )( )( )tttf xHxh x ( )( )tf x H x 输入：输入：训练集D=(x1,y1),(x2,y2),(xm,ym);基学习算法 ；训练轮数T过程：过程：1( )1.D xm.1, 2,.,_fortTdo( ,);tthD D( )( );ttx DtPhxf x.0.5.tifthen break11ln2ttt于是，由式(11)(19)，我们从基于迭代式优化指数损失函数的角度推导出了算法：1exp(),_( )( )( )( )exp(),_(

13、)( )tttttttifh xf xDxDxifh xf xZ( )exp( ) ( )ttttD xf x h xZend forend for输出：输出：1()()TtttHxsignhx1：2：3：4：5：6：7：8：Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法重赋权法”（re-weighting）实施：对于无法接受带权样本的基学习算法，则可通过“重采样法重采样法”（re-sampling）来处理：在训练过程的每轮中，根据样本分布为每个训练样本重新赋予一个权重在训练过程的每轮中，根据样本分布为每个训练样本重新赋予一个权重在每一轮学习中，根据样本分布对训

14、练集重新进行采样，再用重采样而在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对学习器进行训练得的样本集对学习器进行训练一般而言，这两种做法没有显著的优劣差异，需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（第5行），一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在此时，初始设置的学习轮数也许远未达到，可能导致最终集成只包含很少的基学习器而性能不佳。 若采用“重采样法”则可获得“重启动”机会一避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基

15、学习器，从而使得学习过程可以持续预设的T轮完成。00.050.10.150.20.250.30.350.40.450.500.5100.050.10.150.20.250.30.350.40.450.500.20.40.60.8100.050.10.150.20.250.30.350.40.450.500.20.40.60.813个基学习器5个基学习器11个基学习器+ 好瓜 坏瓜Y 含糖率X 密 度集成：红色基学习器：黑色BoostingBoosting能基于泛化性能相当弱的学习器能基于泛化性能相当弱的学习器构建出很强的集成构建出很强的集成由之前可知，欲得到泛化性能强的集成，集成中的个体学习器

16、应该尽可能相互独立，虽然“独立”在现实中无法做到，但可以设法使基学习器尽可能具有较大的差异。这样。由于训练数据不同，我们获得基学习器可望具有比较大的差异，然而，我们同时还希望个体学习器不能太差。若每个子集完全不同，则每个基学习器只用到一小部分训练数据，甚至不足以进行有效学习，无法保证产生好的学习器，所以，我们考虑使用相互有交叠的采样子集。给定一个训练集，对训练样本进行采样，产生出若干不同的子集，再从每个数据子集中训练出一个基学习器Bagging是并行式集成学习方法最著名的代表。基于自助采样法。初始训练集中约有63.2%的样本出现在采样集中。这样，我们可采样T个含m个训练样本的采样集，然后基于每

17、个采样集训练出一个基学习器，再将这些基学习器进行结合。给定包含m个样本的数据集：先随机取出一个样本放入采样集中；再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中；经过m次随机采样操作，得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的从未出现；BaggingBagging的基本流程的基本流程在对预测输出时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若预测时出现两个类收到同样的票数，则随机选择一个，也可进一步考察学习器投票的置信度来确定最终输出。输入：输入：训练集D=(x1,y1),(x2,y2),(xm,ym); 基学习算法& 训练轮数

18、T过程：过程： end for end for输出：输出：_1,2,.,_fortTdo&( ,)tbshD D1( )arg max( )TttyYHxhxy1：2：3： 是自助采样产生的样本分布bsD对比：Adaboost只适用于二分类任务； Bagging能不经修改地用于多分类、回归任务。自助采样过程给Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下的约36.8%的样本可用作验证集来对泛化性能进行“包外估计”（out-of-bag estimate）.为此需记录每个基学习器所使用的训练样本。令 表示 实际使用的训练样本集，令 表示对样本tDth

19、( )oobHxX的包外预测，即仅考虑那些未使用x训练的基学习器在x上的预测，有则Bagging泛化误差的包外估计为：1( )argmax( ( )()Toobtty YtHxh xyxD( , )1( )ooboobx yDHxyD(21)(21)包外样本还有许多用途:当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险；从偏差方差分解角度看：Boosting主要关注降低偏差，因此其能基于泛化性能相当弱的学习器构建出很强的集成。Bagging主要关注于降低方差，因此

20、它在不剪枝决策树，神经网络等易受样本扰动的学习器上效用更为明显。 00.050.10.150.20.250.30.350.40.450.500.20.40.60.8100.050.10.150.20.250.30.350.40.450.500.20.40.60.8100.050.10.150.20.250.30.350.40.450.500.20.40.60.81西瓜数据集3.0上Bagging集成规模为3,5,11时，集成与基学习器分类边界3个基学习器5个基学习器11个基学习器随机森林是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练

21、过程中引入了随机属性选择。传统决策树在选择划分属性时在当前结点的属性集合（假定有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度：若令k=d，则基决策树的构建与传统决策树相同，若令k=1.则是随机选择一个属性用于划分。一般情况下，推荐值2logdk 随机森林优点：简单、容易实现、计算开销小。在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”。RF对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰

22、动（通过对初始训练集采样）而来不同，RF中基学习器的多样性不仅来自样本扰动，。这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。Rf的收敛性与Bagging相似，RF的起始性能往往相对较差，特别是在集成中只包含一个基学习器时，因为通过引入属性扰动，RF中个体学习器的性能往往有所降低，然而，随着学习器数目的增加，RF通常会收敛到更低的泛化误差、值得一提的是，RF的训练效率常优于Bagging，因为在个体决策树的构建中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而RF使用的“随机型”决策树则只需考察一个属性子集。对每次迭代: 利用buildStump()函数找到最佳的单层决策树 将最佳单层决策树加入到单层决策树数组 计算alpha 计算新的权重向量D 更新累计类别估计值 如果错误率等于0.0，则退出循环