写本文的目的:
- 博主本人正在入门机器学习,期间对于每个算法都看了几遍书,写下这篇文章希望可以用自己理解的方式来记录,加深对算法的理解。
- 记下自己的理解,方便日后进行复习。
集成学习(Ensemble learning)通过构建并结合多个学习器来完成学习任务,有时也被称为多分类器系统、基于委员会的学习等。
集成学习的一般结构为:先产生一组“个体学习器”,再用某种策略将它们结合起来。集成中只包含同种类型的个体学习器,称为同质,当中的个体学习器亦称为“基学习器”,相应的算法称为“基学习算法”。集成中包含不同类型的个体学习器,称为“异质”,当中的个体学习器称为“组建学习器”。
要获得好的集成,个体学习器应“好而不同”,即个体学习器要有一定的“准确性”,即学习器不能太坏,并且要有多样性,即个体学习器间具有差异。
根据个体学习器的生成方式,目前的集成学习方法大致可以分为两类:
- 个体学习器间存在强依赖关系、必须串行生成的序列化方法,代表为Boosting;
- 个体学习器间不存在强依赖关系、可同时生成的并行化方法,代表为Bagging和随机森林。
注:所谓串行生成的序列化方法就是除了训练第一个之外,其他的学习器学习都需要依赖于前面生成的学习的结果。
一、Boosting
Boosting是一簇可将弱学习器提升为强学习器的算法。其工作机制为:先从初始训练集训练出一个基学习器,再根据基学习器的表现对样本分布进行调整,使得先前的基学习器做错的训练样本在后续收到更多的关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复进行,直至基学习器数目达到实现指定的值T,或整个集成结果达到退出条件,然后将这些学习器进行加权结合。
1、AdaBoost
AdaBoost 是Boosting中的经典算法,其主要应用于二分类问题。
Adaboost 算法采用调整样本权重的方式来对样本分布进行调整,即提高前一轮个体学习器错误分类的样本的权重,而降低那些正确分类的样本的权重,这样就能使得错误分类的样本可以受到更多的关注,从而在下一轮中可以正确分类,使得分类问题被一系列的弱分类器“分而治之”。对于组合方式,AdaBoost采用加权多数表决的方法,具体地,加大分类误差率小的若分类器的权值,减小分类误差率大的若分类器的权值,从而调整他们在表决中的作用。 其算法流程如下:
【AdaBoost 算法流程】
有如下二分类数据集
输入:数据集 T,弱学习算法
输出:最终分类器G(x)
(1) 初始化训练数据的权值分布
(2) 对m=1,2,…,M (弱分类器的个数,对每个弱分类器做如下):
(a)使用具有权值分布训练数据集学习,得到基本分类器
(b) 计算在训练数据集上的分类误差率 (错误分类的样本的权重之和)
(c) 计算的系数 (弱分类器的权重, 反函数,误差率越大,则权重越小,反之越大)
(d) 更新训练数据集的权值分布
其中,为规范化因子
它使得成为一个概率分布。
(3) 构建基本分类器的线性组合
得到最终的分类器
注:
例子:
AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二分类算法。
加法模型就是说强分类器由一系列弱分类器线性相加而成。
考虑加法模型:
其中为基函数,为基函数的参数,为系数。在给定训练数据及损失函数的条件下,学习加法模型称为经验风险最小化即损失函数极小化问题:
通常该极小化问题是一个复杂的优化问题,常常采用前向分步算法(forward stagewise algorithm)求解该问题,其思路为:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数式,那么就可以简化优化的复杂度。具体的,每步只需优化如下的损失函数:
即每步只需要求解该基学习器的参数以及系数即可。
AdaBoost的公式推导:
假设经过m-1论迭代前向分步算法已经得到:
在第m轮迭代得到和.
目标是前向分步算法得到得到的使得在训练数据集T上的指数损失函数最小,即
又可以表示为
“>
其中,(每轮迭代的样本权重,后面解释)
因为都不依赖于和G,所以与最小化无关。但其依赖于,所以随着每一轮迭代而发生改变。
现在求和:
(1)、求。对任意 0″>,使式<1>最小的由下式得到:
其中。此分类器就是AdaBoost算法的基本分类器,因为它是使得第m轮加权训练数据分类误差率最小的基本分类器。
(2)、求。对损失函数L并把带入得:
L对求导并令结果为0,即可得到使上式为最小值的,
由上面的推导可得,
其中,为分类误差率:
最后我们来看一下每一轮样本权值的更新,由
以及
有:
此处所得权值与算法流程中的权值只差规范化因子,所以等价。
2、提升树(Boosting Tree)
提升树是以分类树或回归树为基本分类器的提升方法。
提升树模型
提升方法采用加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提升方法称为提升树(boosting tree)。对于分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型:
其中,表示决策树;为决策树的参数;为决策树的个数。
提升树算法
提升树算法采用前向分步算法。首先确定初始提升树,第m步的模型为:
其中,为当前模型,通过经验风险极小化确定下一棵决策树的参数,
提升树对不同问题有不同的提升树学习算法,其主要区别在于使用的损失函数不同。主要有用平方误差损失函数的回归问题,用指数损失函数的分类问题,以及一般损失函数的一般决策问题。
对于二分类问题,提升树算法只需将AdaBoost算法的基本分类器限定为二分类决策树即可,此时的提升树算法是AdaBoost算法的特例情况。
回归问题的提升树
把输入空间X划分为J个互不相交的区域,并且在每个区域上确定的输出常量,那么树可以表示为
其中,参数表示树的区域划分和各个区域上的常数。J是回归树的复杂度即叶子结点个数。
回归问题提升树使用以下前向分布算法:
在第m步,给定当前模型,需要求解
得到,即第m棵树的参数。
因为为回归问题,所以采用平方误差损失函数,所以
由上式容易知道,为使损失函数最小,则需要
即需要拟合r,其中,
为当前模型拟合数据的残差(residual),所以对于回归问题的提升树算法来说,只需要简单的拟合当前模型的残差,即输入空间不变,只是对应的输出值( y )改变。
【回归问题的提升树算法】
输入:训练数据集
输出:提升树
(1) 初始化
(2)对m=1,2,…,M (M棵树,对每个树进行遍历)
(a) 计算残差:
(b) 拟合残差学习一个回归树,得到
(c) 更新
(3) 得到回归问题的提升树
3、梯度提升树(Gradient Boosting Decision Tree, GBDT)
GBDT 是多棵树的输出预测值的累加,GBDT的树都是 回归树 而不是分类树
梯度提升树是为了解决提升树在损失函数为一般损失函数时优化算法,称为梯度提升算法,其利用最速下降法的近似方法,关键是利用损失函数的负梯度在当前模型的值
作为回归问题提升树算法中残差的近似值,拟合一个回归树。
对于不同的Loss function,其梯度有不同的表达式:
前三种对应的loss function如下图:其中Huber是低于某个值表现为square error,高于某个值则表现为线性
【梯度提升树算法】
输入:训练数据集,损失函数
输出:提升树
(1) 初始化:
(2)对m=1,2,…,M (M棵树,对每个树进行遍历)
(a) 对i=1,2,…,N,计算
(b) 对拟合一个回归树,得到第m棵树的叶结点区域
(c) 对,计算
(c) 更新
(3) 得到梯度提升回归树
所谓Gradient就是去拟合Loss function的梯度,将其作为新的弱回归树加入到总的算法中即可。
例子:
GBDT——二分类
在梯度提升决策树GBDT中,通过定义不同的损失函数,可以完成不同的学习任务,二分类是机器学习中一类比较重要的分类算法,在二分类中,其损失函数为:
套用上面介绍的GB框架,得到下述的二分类GBDT的算法:
二、Bagging与随机森林
1、Bagging
bagging 是一种个体学习器之间不存在强依赖关系、可同时生成的并行式集成学习方法。
bagging 基于自助采样法(bootstrap sampling),也叫有放回重采样法.即给定包含m个样本的数据集,先随机从样本中取出一个样本放入采样集中,再把该样本返回初始数据集,使得下次采样时该样本仍可以被选中,这样,经过m次随机采样操作,就可以得到包含m个样本的采样集,初始数据集中有的样本多次出现,有的则未出现,其中,初始训练集中约有63.2%的样本出现在采样集中。
照上面的方式进行T次操作,采样出T个含有m个训练集的采样集,然后基于每个采样集训练出T个基学习器,再将这些基学习器进行结合,即可得到集成学习器。在对输出进行预测时,Bagging通常对分类进行简单投票法,对回归使用简单平均法。若出现形同,则任选其一。
Bagging的优点:
- 训练一个 Bagging集成与直接使用基分类器算法训练一个学习器的复杂度同阶,说明Bagging是一个高效的集成学习算法。
- 此外,与标准的AdaBoost算法只适用于二分类问题不同,Bagging能不经过修改用于多分类、回归等任务。
- 由于每个基学习器只使用63.2%的数据,所以剩下36.8%的数据可以用来做验证集来对泛化性能进行“包外估计”。
从偏差-方差的角度来说,boosting主要关注减小偏差,而Bagging主要关注降低方差,也就说明boosting在弱学习器上表现更好,而降低方差可以减小过拟合的风险,所以Bagging通常在强分类和复杂模型上表现得很好。举个例子:bagging在不减枝决策树、神经网络等易受样本扰动的学习器上效果更为明显。
2、随机森林(Random Forest,简称RF)
随机森林是bagging的扩展体。RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入了随机属性选择。具体地,传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性,而在RF上,对基决策树的每个结点,先从该结点的属性集中随机选择其中的k个属性组成属性集,然后从该属性集中选择最优的划分属性,一般情况下,推荐。
随机森林的优势:
- 能够处理很高维度的数据,并且不用做特征选择;
- 在训练完成后,可以给出哪些属性比较重要;
- 容易做成并行化方法,速度快;
- 可以进行可视化展示,便于分析。
随机森林和Bagging比较:
两者的收敛性相似,但RF的起始性能相对较差,特别只有一个基学习器时。随着基学习器数量的增加,随机森林通常会收敛到更低的泛化误差。随机森林的训练效率常优于Bagging,因为Bagging是“确定型”决策树,而随机森林使用“随机型”决策树。
三、结合策略
通过上文,我们对集成学习算法也有了大概的了解,简单来说,集成算法就是训练一堆基学习器,然后通过某种策略把各个基学习器的结果进行合成,从而得到集成学习器的结果。下面我们就来认识一下常用的结合策略:
1、平均法(Averaging)
对数值型(连续)输出,最常见的结合策略为平均法。
—简单平均法(simple averaging)
—加权平均法(weighted averaging)
其中为权重,通常要求:
注:加权平均法的权重一般从训练数据中学习而得,对规模比较大额集成来说,要学习的权重比较多,较容易导致过拟合,因此加权平均法不一定优于简单平均法。一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近时宜使用简单平均法。
2、投票法(Voting)
对分类来说,学习器将从类别集合中预测出一个类别标记,最常用的是投票法。
—绝对多数投票法(majority voting)
0.5\sum_{k=1}^{N}\sum_{i=1}^{T}h_j^k(x);\ \ \ \ \\ \\ reject\ ,\ \ \ \ otherwise\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{matrix}\right.”>
即如某标记的投票过半数,则预计为该标记;否则拒绝预测。
—相对多数投票法(plurality voting)
即预测为得票最多的标记,若同时出现多个票数最多,则任选其一。
—加权投票法(weighted voting)
与加权平均法类似。
3、学习法
当数据很多时,一种更为强大的结合策略是使用“学习法”,即通过另一个学习器来结合。其中典型代表为Stacking,在stacking中我们把个体学习器称为初级学习器,用于结合的学习器称为次学习器或者元学习器。
注:Stacking本身就是一种出名的集成学习方法,且有不少集成学习方法可以认为是其变体或者特例,stacking也可以认是一种结合策略,此处同周志华的西瓜书一样,把其看成一种结合策略。
stacking的主要思想为:先从初始数据集训练出初级学习器,然后“生成”一个新的数据集用于训练次级学习器。生成的该新数据中,初级学习器的输出被当做样例输入特征,而初始样本的标记仍被当做样例标记。也就是说,假设初级学习器有M个,那么对于一个原始数据集中的样本(x; y),通过这M个初级学习器有M个输出{h1(x),h2(x),…,hM(x)},把{h1(x),h2(x),…,hM(x); y}作为新数据的一个样本,所以一个初级学习器的输出作为新数据集中对应样本的一个特征,而其标记为原始数据中该样本的标记。算法描述如下图(图来自周志华《机器学习》),假定初级学习器使用不同的算法,如LR、RF、SVM、GBDT等。
在训练阶段,次级学习器(用来结合结果的学习器)的训练数据集是利用初级学习器来产生的,若直接用初级学习器的训练集来产生训练数据集,则很有可能会出现过拟合,也就是过拟合风险较大;所以一般在使用Stacking时,采用交叉验证或留一法的方式,用训练初级学习器未使用的样本来产生次级学习器的训练样本。下面以k=5折交叉验证作为例子:
首先把整个数据集分成量训练集(Training Data)和测试集(Test Data)两部分,上图最左边,然后把训练数据集进行k折,此处k=5,即把训练数据分成5份,在进行第j折时,使用其余的四份进行初级学习器的训练,得到一个初级学习器,并用该初始学习器把该折(即留下用来验证的)数据进行预测,进行完所有折数,把预测输出作为新数据集的特征,即次级学习器的训练数据集,其中标记没变,用该新数据集训练次级学习器,从而得到一个完整的stacking。最后用原始数据的测试集来对该Stacking进行测试评估。
次级学习器的输入属性表示和次级学习算法的选择对Stacking集成的泛化性能有很大影响。有研究表明,将初级学习器的输出类概率最为次级学习器的输入属性,用多响应线性回归(Multi-reponse Linear Regression,简称MLR)作为次级学习器算法效果更好,在MLR中使用不同的属性集更佳。
注:MLR是基于线性回归的分类器,其对每个类分别进行线性回归,属于该类的训练样例所对应的输出为1,其他类置0;测试示例将被分给输出值最大的类。
四、总结
该文主要写了关于集成学习的一些常用算法,当然最牛逼的XGBoost和lightGBM都没有开始学到,都说想成为一名优秀的机器学习算法er那么肯定绕不过该两个算法,不过在此先不谈,而是来总结一下该文的内容。
一开始先介绍了何为集成学习,然后将了Boosting算法和bagging算法。boosting算法与Bagging算法的主要区别在于:
- Boosting算法中个体学习器间存在强依赖关系、必须串行生成的序列化方法,即下个学习器要依赖删一个学习器进行学习,不能进行并行化。
- Bagging算法个体学习器间不存在强依赖关系、可同时生成的并行化方法,即可以并行化。
Boosting算法的代表有AdaBoost,Boosting Tree和GBDT。boosting是一种模型加法模型、学习方式为前向分步算法的算法,而几种代表的不同在于选择的损失函数不同。
标准的AdaBoost算法用于二分类问题,损失函数为指数函数,其主要思想:通过提高错分类样本的权重使得该样本在下次可以得到更大的关注,从而可以正确分类,降低正确分类的样本的权重,最后在结合的时候,对分类误差率小的个体学习器设置大的权重,对分类误差率大的个体学习器设置小的权重。
Boosting Tree(提升树)是模型为加法模型,学习算法为前向分步算法,个体学习器为决策树的一种集成方法。当Boosting Tree在解决回归问题时,使用CART作为个体学习器,采用平方误差函数作为损失函数,学习过程为不断拟合当前模型的残差,知道满足停止条件的过程。
GBDT与Boosting Tree在解决回顾问题时类似,只是把损失函数的负梯度最为拟合的目标来进行学习。
Bagging方法主要通过又放回抽取样本的方式进行数据集的产生来训练个体学习器,对于一个个体学习器的训练样本,其数目上与原始训练样本数一致,只是有些重复,有些没有出现,出现的样本约为原始样本的63.2%,剩余部分可以用来进行做包外估计。
Random Forest(随机森林)是Bagging的变体,其不同的地方在于在生成个体学习器的过程中不仅有样本扰动,还加入了属性扰动。
最后,讲了结合策略,有平均法、投票法和学习法,其中学习法的代表为Stacking方法,Stacking方法也是一种集成方法,其主要思想为:先从初始数据集训练出初级学习器,然后“生成”一个新的数据集用于训练次级学习器。生成的该新数据中,初级学习器的输出被当做样例输入特征,而初始样本的标记仍被当做样例标记。
五、参考:
周志华 ——《机器学习》
李航 —— 《统计学习方法》
李锐 —— 《机器学习实战》
zhiyong_will的博客:机器学习之集成学习(ensemble learning)
今天的文章机器学习之集成学习(ensemble learning)[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/77765.html