决策树(中)集成学习、RF、AdaBoost、BoostTree、GBDT
参考资料(要是对于本文的理解不够透彻,必须将以下博客认知阅读):
1. https://zhuanlan.zhihu.com/p/86263786
2.https://blog.csdn.net/liuy9803/article/details/80598652
3.https://blog.csdn.net/perfect1t/article/details/83684995
4.GBDT算法原理以及实例理解(!!)
5.Adaboost算法原理分析和实例+代码(简明易懂)(!!)
6.集成学习之Adaboost算法原理小结(!!刘建平,大牛博客)
7.gbdt、xgb、lgb、cat面经整理——from牛客(必须掌握)
目录
1.集成学习概念
2.Bagging
3.Random Forest(RF)
4.Boosting
5.Adaboost
6.Boosting tree(提升树)
7.GBDT
8.从偏差和方差的角度理解集成学习
一、集成学习相关知识(Ensemble learning)
1. 集成学习(Ensemble learning)是使用一系列学习器进行学习,并使用某种规则把各个学习结果进行整合,从而获得比单个学习器显著优越的泛化性能。它不是一种单独的机器学习算法,而更像是一种优化策略,其目的在于使得集成模型达到减小方差(bagging)、减小偏差(boosting)或改进预测(stacking)的效果。
2. 根据集成学习的概念以及一般结构,我们能都发现集成学习的两个核心问题:
- 如何选择若干个体学习器?怎么训练每个算法?
- 选择何种策略将这些个体学习器集成为一个强学习器?
2. 集成学习的一般结构是,先产生一组个体学习器,再用某种结合策略将它们结合起来。
3. 集成学习的成功在于保证个体学习器的多样性(好而不同),且集成不稳定的算法也能够得到一个比较明显的性能提升。
4. 根据个体学习器的生成方式,目前的集成学习方法大致可以分为两类:(也有人把集成学习方法分为3类[Bagging、Boosting、stacking],stacking其实可以看成是一种集成学习方法,也可以看成是一种特殊的结合策略)
- 个体学习器间存在强依赖关系、必须串行生成的序列化方法,代表为Boosting;
- 个体学习器间不存在强依赖关系、可同时生成的并行化方法,代表为Bagging和随机森林。
5. 集成学习优势在于:
- 个体学习器之间存在一定的差异性,这会导致分类边界不同,也就是说可能存在错误。那么将多个个体学习器合并后,就可以得到更加合理的边界,减少整体的错误率,实现更好的效果;
- 对于数据集过大或过小的情况,可以分别进行划分和有放回的操作,产生不同的数据子集,然后使用数据子集训练不同的学习器,最终再合并成为一个强学习器;
- 如果数据的划分边界过于复杂,使用线性模型很难描述情况,那么可以训练多个模型,然后再进行模型的融合;
- 对于多个异构的特征集的时候,很难直接融合,那么可以考虑使用每个数据集构建一个分类模型,然后将多个模型融合。
二、Bagging(装袋)
1.概念
- Bagging 是一种个体学习器之间不存在强依赖关系、可同时生成的并行式集成学习方法。
- Bagging 基于自助采样法(bootstrap sampling),也叫有放回重采样法.即给定包含m个样本的数据集,先随机从样本中取出一个样本放入采样集中,再把该样本返回初始数据集,使得下次采样时该样本仍可以被选中,这样,经过m次随机采样操作,就可以得到包含m个样本的采样集,初始数据集中有的样本多次出现,有的则未出现。其中,初始训练集中约有63.2%的样本出现在采样集中。
- 为了使基学习器尽可能的具有较大的差异(好而不同,保持多样性),对训练样本进行采样以产生若干个不同的子集,对每一个子集训练一个基学习器,然后结合策略进行集成的方法。为了不让每个基学习器效果太差,这些子集不能完全不同,因此使用子集之间相互有交叠的采样方法,即bootstrap方法(自助采样法)。
自助采样法:对 m 个样本的训练集,有放回的采样 m 次;此时,样本在 m 次采样中始终没被采样的概率约为 0.368,即每次自助采样只能采样到全部样本的 63% 左右。
2.流程图
3.算法流程
(1)给定包含m个样本的数据集,随机取出一个样本放入采样集中,再把它放回到原始数据集中,重复m次,得到含m个样本的采样集。
(2)进行同样的操作进行T次得到T个每个含m个样本的采样集,基于每个采样集训练一个基学习器。
(3)再将基学习器进行组合,一般使用多数投票或求均值的方式来统计最终的分类结果。
4.Bagging的优点
- 训练一个 Bagging集成与直接使用基分类器算法训练一个学习器的复杂度同阶,说明Bagging是一个高效的集成学习算法。
- 此外,与标准的AdaBoost算法只适用于二分类问题不同,Bagging能不经过修改用于多分类、回归等任务。
- 由于每个基学习器只使用63.2%的数据,所以剩下36.8%的数据可以用来做验证集来对泛化性能进行“包外估计”。
- 从偏差-方差的角度来说,Boosting主要关注减小偏差,而Bagging主要关注降低方差,也就说明boosting在弱学习器上表现更好,而降低方差可以减小过拟合的风险,所以Bagging通常在强分类和复杂模型上表现得很好。(这能否说明Bagging的基学习器选取强学习器效果会更好呢??)
三、Random Forest(RF)(随机森林=Bagging+决策树)
1.概念
- 随机森林是bagging的扩展体。
- RF在以决策树为基学习器,通过Bagging自助采样算法采样训练样本,进一步在决策树的训练过程中引入了随机属性选择。(为了保证多样性)
- 具体地,传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性,而在RF上,对基决策树的每个结点,先从该结点的属性集中随机选择其中的k个属性组成属性集,然后从该属性集中选择最优的划分属性,一般情况下,推荐。
2.随机森林随机的意义表现在哪?
- 随机森林中随机主要体现在对样本的随机采样以及引入了随机属性选择。
- 不管是对样本的随机采样,还是对特征的抽样,甚至对切分点的随机划分,都是为了引入偏差,使基分类器之间具有明显的差异,相互独立,提升模型的多样性,使模型不会受到局部样本的影响,从而减少方差,提升模型的泛化能力。
3.随机森林的优缺点
- 能够处理很高维度的数据,并且不用做特征选择;处理高维数据,处理特征遗失数据,处理不平衡数据是随机森林的长处。
- 随机森林可用于回归问题和分类问题,取决于随机森林的每颗cart树是分类树还是回归树。;
- 容易做成并行化方法,速度快;
- 可以进行可视化展示,便于分析。
- 当数据噪声比较大时,会产生过拟合现象;
- 当随机森林中的决策树个数很多时,训练时需要的空间和时间会比较大
- 随机森林中还有许多不好解释的地方,有点算是黑盒模型
4.随机森林与Bagging算法的比较
- 两者的收敛性相似,但RF的起始性能相对较差,特别只有一个基学习器时。随着基学习器数量的增加,随机森林通常会收敛到更低的泛化误差。
- 随机森林的训练效率常优于Bagging,因为Bagging是“确定型”决策树,而随机森林使用“随机型”决策树。
四、Boosting(提升)
1.概念
(1)Boosting是一簇可将弱学习器提升为强学习器的算法,其基于串行策略:基学习器之间存在依赖关系,新的学习器需要根据上一个学习器生成,每次学习都会使用全部训练样本。
(2)其工作机制为:先从初始训练集训练出一个基学习器,再根据基学习器的表现对样本分布进行调整,使得先前的基学习器做错的训练样本在后续收到更多的关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复进行,直至基学习器数目达到实现指定的值T,或整个集成结果达到退出条件,然后将这些学习器进行加权结合。正确率越高的基学习器的获得的权重越大。Boosting可以用于分类和回归问题。
(3)常见的基于Boosting模型的算法有:AdaBoost、Boosting Tree、GBDT、XGBoost。
2.流程图
3.Boosting的特点
(1)从方差-偏差分解的角度看,Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。
(2)Boosting对样本分布进行调整主要有两种方法:
- 重新赋权法(re-weighting):在每一轮学习中,根据样本分布为每个训练样本重新赋予一个权重值。
- 重采样法(re-sampling):对于无法接受带权样本的基学习算法,在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样得到的样本集对基学习器进行训练。
4.Bagging和Boosting的区别
(1) 样本选择上:
Bagging:训练集是在原始集中有放回选取的,从原始集中选出的各轮训练集之间是独立的。
Boosting:每一轮的训练集不变,只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
(2) 样例权重:
Bagging:使用均匀取样,每个样例的权重相等
Boosting:根据错误率不断调整样例的权值,错误率越大则权重越大。
(3) 预测函数:
Bagging:所有预测函数的权重相等。
Boosting:每个弱分类器都有相应的权重,对于分类误差小的分类器会有更大的权重。
(4) 并行计算:
Bagging:各个预测函数可以并行生成
Boosting:各个预测函数只能顺序生成,因为后一个模型参数需要前一轮模型的结果。
(5) 为什么说bagging是减少variance,而boosting是减少bias(高频面试)
Bagging中每个基学习器都是强学习器,主要关注的问题是降低方差;Boosting中每个基学习器都是弱学习器,主要关注的问题是降低偏差。具体解答分析见7.从偏差和方差的角度理解集成学习
五、AdaBoost(只对AdaBoost做了简单的推导,具体推导细节请看统计学习方法)
1.概念
(1)AdaBoost [ adaptive boosting(自适应boosting) ] 是Boosting中的经典算法,其主要应用于二分类问题,也可以用于多分类以及回归问题。
(2)AdaBoost算法思路:如何改变每一轮训练数据的权重?Adaboost 算法采用调整样本权重的方式来对样本分布进行调整,即提高前一轮个体学习器错误分类的样本的权重,而降低那些正确分类的样本的权重,这样就能使得错误分类的样本可以受到更多的关注,从而在下一轮中可以正确分类,使得分类问题被一系列的弱分类器“分而治之”。如何将弱分类器组合成一个强分类器?对于组合方式,AdaBoost采用加权多数表决的方法,具体地,加大分类误差率小的若分类器的权值,减小分类误差率大的若分类器的权值,从而调整他们在表决中的作用。
2.算法流程(摘自西瓜书与统计学习方法)
3.结合一个例子来理解整个算法的流程,这个例子摘自李航《统计学习方法》:
4.AdaBoost算法的理解
AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类算法。AdaBoost算法中最重要的应该就是样本权重更新公式的推导。
加法模型:最终的强分类器是由若干个弱分类器加权平均得到的。
前向分布学习算法:算法是通过一轮轮的弱学习器学习,利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。第 k 轮的强学习器为:
定义损失函数为 n 个样本的指数损失函数:
利用前向分布学习算法的关系可以得到:
因为 已知,所以令 ,随着每一轮迭代而将这个式子带入损失函数,损失函数转化为:
我们求 ,可以得到:
将 带入损失函数,并对 求导,使其等于 0,则就得到了:
其中, 即为我们前面的分类误差率。
最后看样本权重的更新。利用 和 ,即可得:
这样就得到了样本权重更新公式。
5.AdaBoost优缺点
- 分类精度高;
- 可以用各种回归分类模型来构建弱学习器,非常灵活;
- 不容易发生过拟合。
- 对异常点敏感,异常点会获得较高权重。
六、Boosting tree(提升树)(年龄例子)
1.概念
- 提升树是以分类树或回归树为基本分类器的提升方法。Boosting Tree被认为是统计学习中性能最好的方法之一。
- 提升方法采用加法模型(即基函数的线性组合)与前向分步算法,以决策树为基函数的提升方法称为提升树(boosting tree)。
- 对于分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。
- 从某种角度可以理解为Boosting tree = Adaboost + tree
2.提升树模型表示
其中,表示决策树;为决策树的参数;为决策树的个数。
3.多种类型提升树算法
提升树对不同问题有不同的提升树学习算法,其主要区别在于使用的损失函数不同。
(1)用平方误差损失函数的回归问题。
(2)用指数损失函数的分类问题。
(3)一般损失函数的一般决策问题。(引出了GB[Gradient Boosting 梯度提升]算法,GB+决策树(回归树)就得到了GBDT)
4.用于分类问题的提升树
对于二分类问题,Boosting Tree算法只需要将AdaBoost算法中的基分类器限制为CART二分类树即可。
从这个角度可以反应出,在二分类问题中 Boosting Tree = AdaBoost + Tree(二分类树)
5.用于回归问题的提升树(推导过程,详细过程见统计学习方法)
(1)把输入空间X划分为J个互不相交的区域,并且在每个区域上确定的输出常量,那么树可以表示为如下:
其中,参数表示树的区域划分和各个区域上的常数。J是回归树的复杂度即叶子结点个数。
(2)回归问题提升树使用以下前向分布算法:
在第m步,给定当前模型,需要求解
得到,即第m棵树的参数。
(3)因为为回归问题,所以采用平方误差损失函数,所以
由上式容易知道,为使损失函数最小,则需要
即需要拟合r,其中,
为当前模型拟合数据的残差(residual),所以对于回归问题的提升树算法来说,只需要简单的拟合当前模型的残差。
算法流程如下图所示:(摘自统计学习方法)
李航的《统计学习方法》中也给出了相应的例子来说明整个解决回归问题提升树的算法流程。由于题目太长,在这我就不粘贴出来了,有需要自己去看!
七、GBDT
GBDT = GB + DT + Shringkage(一个重要演变),在了解GBDT之前,首先让我了解一下GB(Gradient Boosting,梯度提升)算法以及DT(Decision Tree)。
1.DT(Decision Tree)
- 首先,GBDT使用的决策树是CART回归树,无论是处理回归问题还是二分类以及多分类,GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢?因为GBDT每次迭代要拟合的是梯度值,是连续值所以要用回归树。
- 对于回归树算法来说最重要的是寻找最佳的划分点,那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数,都是用纯度来衡量的,但是在回归树中的样本标签是连续数值,所以再使用熵之类的指标不再合适,取而代之的是平方误差,它能很好的评判拟合程度
Cart回归树生成算法(用于回归问题的Boosting Tree也需要用到Cart回归树生成算法)(有关Cart回归树以及分类树的详细知识可查看博主的上一篇博客)
2.GB(Gradient Boosting)
梯度提升树(Grandient Boosting)是提升树(Boosting Tree)的一种改进算法。
提升树利用加法模型与前向分步算法实现学习的优化过程,当损失函数是平方损失和指数损失函数时,梯度提升树每一步优化是很简单的,但是对于一般损失函数而言,往往每一步优化起来不那么容易,针对这一问题,Friedman提出了梯度提升树算法,这是利用最速下降的近似方法,其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。那么负梯度长什么样呢?第t轮的第i个样本的损失函数的负梯度为:
此时不同的损失函数将会得到不同的负梯度,如果选择平方损失
则负梯度为
从上述推导过程中,可以看出当损失函数为平方损失函数时,损失函数的负梯度 = 残差。但是在GBDT中,损失函数一般不会选择平方损失函数,所以我们利用损失函数的负梯度作为提升树算法中的残差的近似值。
3.GBDT算法
介绍完了GB和DT,将两者结合起来就得到GBDT算法。GBDT(Gradient Boosting Decision Tree)是一种迭代的决策树算法,该算法由多棵决策树组成,从名字中我们可以看出来它是属于 Boosting 策略。GBDT 是被公认的泛化能力较强的算法。
首先必须明确一点 ,GBDT 使用的是绝对损失或者 Huber 损失函数,而不是平方损失函数(网上很多博客把GBDT的损失函数当作平方损失函数,这是错误的)
GBDT算法的整个流程:
通常在2(d)步骤时,GBDT会引入缩减(Shrinkage)思想(正则化的一种)
Shrinkage 的思想认为,每走一小步逐渐逼近结果的效果要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它并不是完全信任每一棵残差树。
Shrinkage 不直接用残差修复误差,而是只修复一点点,把大步切成小步。本质上 Shrinkage 为每棵树设置了一个 weight,累加时要乘以这个 weight,当 weight 降低时,基模型数会配合增大。
4.如何使用GBDT解决二分类问题?
在梯度提升决策树GBDT中,通过定义不同的损失函数,可以完成不同的学习任务,二分类是机器学习中一类比较重要的分类算法,对于分类问题,一般将损失函数改为指数损失(二分类)或者对数似然损失(多分类)。在二分类中,其损失函数为:
其余过程见:深入理解GBDT二分类算法(此篇博客的博主是个大牛!@!!!!!!!)
5.GBDT正则化
和Adaboost一样,我们也需要对GBDT进行正则化,防止过拟合。GBDT的正则化主要有三种方式。
(1)第一种是和Adaboost类似的正则化项,即步长(learning rate)。定义为ν,对于前面的弱学习器的迭代,如果我们加上了正则化项,则有
ν的取值范围为0<ν≤1。对于同样的训练集学习效果,较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
(2)第二种正则化的方式是通过子采样比例(subsample)。取值为(0,1]。注意这里的子采样和随机森林不一样,随机森林使用的是放回抽样,而这里是不放回抽样。如果取值为1,则全部样本都使用,等于没有使用子采样。如果取值小于1,则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低。推荐在[0.5, 0.8]之间。使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样,程序可以通过采样分发到不同的任务去做boosting的迭代过程,最后形成新树,从而减少弱学习器难以并行学习的弱点。
(3)第三种是对于弱学习器即CART回归树进行正则化剪枝。在决策树原理篇里我们已经讲过,这里就不重复了。
6.GBDT的优缺点
GBDT主要的优点有:
- 可以灵活处理各种类型的数据,包括连续值和离散值。
- 在相对少的调参时间情况下,预测的准确率也可以比较高。这个是相对SVM来说的。
- 使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
GBDT的主要缺点有:
- 由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
7.与Adaboost的对比
相同点:
- 都是 Boosting 家族成员,使用弱分类器;
- 都使用前向分布算法;
不同点:
- 迭代思路不同:Adaboost 是通过提升错分数据点的权重来弥补模型的不足(利用错分样本),而 GBDT 是通过算梯度来弥补模型的不足(利用残差);
- 损失函数不同:AdaBoost 采用的是指数损失,GBDT 使用的是绝对损失或者 Huber 损失函数;
8.与Boosting Tree(提升树)的却别
- 在拟合值方面,GBDT用负梯度代替了BT中的残差,其本质是用泰勒一阶展开式近似值。
- BT中,叶子节点的输出取平均值(由CART回归树的建立过程决定);而GBDT叶子节点的输出需要拟合损失函数最好的输出。
9.GBDT与RF的区别
- 组成随机森林的树可以是分类树,也可以是回归树;而GBDT只由回归树组成,GBDT的会累加所有树的结果,而这种累加是无法通过分类完成的,因此GBDT的树都是CART回归树,而不是分类树(尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树)
- 组成随机森林的树可以并行生成;而GBDT只能是串行生成
- 对于最终的输出结果而言,随机森林采用多数投票或简单平均等;而GBDT则是将所有结果累加起来,或者加权累加起来(存在学习率)
- 随机森林对异常值不敏感,GBDT对异常值非常敏感
- 随机森林对训练集一视同仁,GBDT是基于权值的弱分类器的集成
- 随机森林是通过减少模型方差提高性能,GBDT是通过减少模型偏差提高性能,但是xgb引入了正则项和列采样等等正则化手段之后,可以在少量增加偏差的情况下大幅度缩减模型的方差。
八、从偏差和方差的角度理解集成学习
8.1 集成学习的偏差与方差
偏差(Bias)描述的是预测值和真实值之差;方差(Variance)描述的是预测值作为随机变量的离散程度。放一场很经典的图:
模型的偏差与方差
- 偏差:描述样本拟合出的模型的预测结果的期望与样本真实结果的差距,要想偏差表现的好,就需要复杂化模型,增加模型的参数,但这样容易过拟合,过拟合对应上图的 High Variance,点会很分散。低偏差对应的点都打在靶心附近,所以喵的很准,但不一定很稳;
- 方差:描述样本上训练出来的模型在测试集上的表现,要想方差表现的好,需要简化模型,减少模型的复杂度,但这样容易欠拟合,欠拟合对应上图 High Bias,点偏离中心。低方差对应就是点都打的很集中,但不一定是靶心附近,手很稳,但不一定瞄的准。
我们常说集成学习中的基模型是弱模型,通常来说弱模型是偏差高(在训练集上准确度低)方差小(防止过拟合能力强)的模型,但并不是所有集成学习框架中的基模型都是弱模型。Bagging 和 Stacking 中的基模型为强模型(偏差低,方差高),而Boosting 中的基模型为弱模型(偏差高,方差低)。
在 Bagging 和 Boosting 框架中,通过计算基模型的期望和方差我们可以得到模型整体的期望和方差。为了简化模型,我们假设基模型的期望为 ,方差 ,模型的权重为 ,两两模型间的相关系数 相等。由于 Bagging 和 Boosting 的基模型都是线性组成的,那么有:
模型总体期望:
模型总体方差(公式推导参考协方差的性质,协方差与方差的关系):
模型的准确度可由偏差和方差共同决定:
8.2 Bagging 的偏差与方差
对于 Bagging 来说,每个基模型的权重等于 1/m 且期望近似相等,故我们可以得到:
通过上式我们可以看到:
- 整体模型的期望等于基模型的期望,这也就意味着整体模型的偏差和基模型的偏差近似。
- 整体模型的方差小于等于基模型的方差,当且仅当相关性为 1 时取等号,随着基模型数量增多,整体模型的方差减少,从而防止过拟合的能力增强,模型的准确度得到提高。但是,模型的准确度一定会无限逼近于 1 吗?并不一定,当基模型数增加到一定程度时,方差公式第一项的改变对整体方差的作用很小,防止过拟合的能力达到极限,这便是准确度的极限了。
在此我们知道了为什么 Bagging 中的基模型一定要为强模型,如果 Bagging 使用弱模型则会导致整体模型的偏差提高,而准确度降低。
Random Forest 是经典的基于 Bagging 框架的模型,并在此基础上通过引入特征采样和样本采样来降低基模型间的相关性,在公式中显著降低方差公式中的第二项,略微升高第一项,从而使得整体降低模型整体方差。
8.3 Boosting 的偏差与方差
对于 Boosting 来说,由于基模型共用同一套训练集,所以基模型间具有强相关性,故模型间的相关系数近似等于 1,针对 Boosting 化简公式为:
通过观察整体方差的表达式我们容易发现:
- 整体模型的方差等于基模型的方差,如果基模型不是弱模型,其方差相对较大,这将导致整体模型的方差很大,即无法达到防止过拟合的效果。因此,Boosting 框架中的基模型必须为弱模型。
- 此外 Boosting 框架中采用基于贪心策略的前向加法,整体模型的期望由基模型的期望累加而成,所以随着基模型数的增多,整体模型的期望值增加,整体模型的准确度提高。
基于 Boosting 框架的 Gradient Boosting Decision Tree 模型中基模型也为树模型,同 Random Forrest,我们也可以对特征进行随机抽样来使基模型间的相关性降低,从而达到减少方差的效果。
原文出处:https://www.cnblogs.com/XDU-Lakers/p/11887735.html
以上是 决策树(中)集成学习、RF、AdaBoost、BoostTree、GBDT 的全部内容, 来源链接: utcz.com/z/509313.html