用户1432189
集成学习总结
关注作者
前往小程序,Get
更优
阅读体验!
立即前往
腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
用户1432189
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
社区首页
>
专栏
>
集成学习总结
集成学习总结
用户1432189
关注
发布于 2019-06-25 11:46:21
654
0
发布于 2019-06-25 11:46:21
举报
文章被收录于专栏:
zingpLiu
1 基本概念
集成学习的主要思路是先通过一定的规则生成多个学习器,再采用某种集成策略进行组合,最后综合判断输出最终结果。一般而言,通常所说的集成学习中的多个学习器都是同质的"弱学习器"。基于该弱学习器,通过样本集扰动、输入特征扰动、输出表示扰动、算法参数扰动等方式生成多个学习器,进行集成后获得一个精度较好的"强学习器"。
目前集成学习算法大多源于
bagging、boosting、stacking
三种思想。
2 bagging
一种提高分类模型的方法。
(1) 从训练集\(S\)中有放回的随机选取数据集\(M\)\((∣M∣ < ∣S∣)\);
(2) 生成一个分类模型\(C\);
(3) 重复以上步骤\(m\)次,得到\(m\)个分类模型\(C_1,C_2,...,C_m\);
(4)对于分类问题,每一个模型投票决定,少数服从多数原则;
(5)对于回归问题,取平均值。
注意:这种抽样的方式会导致有的样本取不到,大约有\(\lim_{n \to \infty}(1-\frac{1}{n})^n\) = \(36.8%\)的样本取不到,这部分可用来做测试集。
优点: 通过
减少方差
来提高预测结果。
缺点:
失去了模型的简单性
。
2.1 Random Forest
是一种基于
树模型的bagging算法
改进的模型。假定数据集中有\(M\)个特征和 \(N\)个观测值。每一个树有放回的随机抽出\(N\)个观测值\(m\)(\(m=M\)或者\(m=logM\))个特征。把每一个单一决策树的结果综合起来。
优点:
(1) 减少了模型方差,提高了预测准确性。
(2) 不需要给树做剪枝。
(3) 在大规模数据集,尤其是特征较多的情况下,依然可以保持高效率。
(4) 不用做特征选择,并且可以给出特征变量重要性的排序估计。
缺点:
(1) 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
(2) 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的。
3 boosting
每一轮根据上一轮的分类结果动态调整每个样本在分类器中的权重,训练得到k个弱分类器,他们都有各自的权重,通过加权组合的方式得到最终的分类结果(综合所有的基模型预测结果)。主要算法有AdaBoost/GBDT/Xgboost/LightGBM。
3.1 Adboost
给定数据集\(S\),它包含\(n\)个元组\((X_1,y_1),(X_2,y_2),...,(X_n,y_n)(X_1,y_1), (X_2,y_2), ..., (X_n,y_n)\),其中\(y_i\)是数据对象\(X_i\)的类标号。
(1) 开始时,Adaboost对每个训练元组赋予相等的权重\(1/n\)。组合分类器包含\(T\)个基本分类器。
(2) 针对第\(t\)个分类器\(M_t\):
首先,从S中的元组进行抽样,形成大小为\(n\)的训练集\(S_t\),此处抽样方式为有放回的抽样,抽样过程中,每个元组被选中的机会由它的权重决定;
然后,根据\(S_t\)导出(训练出)分类器\(M_t\),使用\(S_t\)检验分类器\(M_t\)的分类误差,并计算该分类器的“表决权”的权重;
最后,训练元组的权重根据分类器\(M_t\)的分类情况调整。
如果元组被错误分类,则它的权重增加。
如果元组被正确分类,则它的权重减少。
元组的权重反映元组被分类的困难程度——
权重越高
,被错误分类的可能性越高。然后,使用这些权重,为下一轮分类器(下一个分类器)产生训练样本。
其基本的思想是,当建立分类器时,希望它更关注上一轮分类器(上一个分类器)错误分类的元组。整个分类过程中,某些分类器对某些“困难”元组的分类效果可能比其他分类器好。这样,建立了一个互补的分类器系列。
用于二分类或多分类的应用场景。
优点
(1) 很好的利用了弱分类器进行级联。
(2)可以将不同的分类算法作为弱分类器。
(3)AdaBoost具有很高的精度。
(4) 相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重。
缺点:
(1) AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定。
(2) 数据不平衡导致分类精度下降。
(3) 训练比较耗时,每次重新选择当前分类器最好切分点。
3.2 GBDT
采用
决策树
作为弱分类器的
Gradient Boosting
算法被称为
GBDT
,有时又被称为MART(Multiple Additive Regression Tree)。GBDT中使用的决策树通常为CART。
用一个很简单的例子来解释一下GBDT训练的过程,如图下图所示。模型的任务是预测一个人的年龄,训练集只有A、B、C、D 4个人,他们的年龄分别是14、16、24、26,特征包括了
"月购物金额"、"上网时长"、"上网历史"
等。
下面开始训练第一棵树:
训练的过程跟传统决策树相同,简单起见,我们只进行一次分枝。训练好第一棵树后,求得每个样本预测值与真实值之间的残差。
可以看到,A、B、C、D的残差分别是−1、1、−1、1。
这时我们就用每个样本的残差训练下一棵树,直到残差收敛到某个阈值以下,或者树的总数达到某个上限为止。
image
由于GBDT是利用残差训练的,在预测的过程中,我们也需要把所有树的预测值加起来,得到最终的预测结果。
优点:
(1)预测阶段的计算速度快,树与树之间可并行化计算。
(2)在分布稠密的数据集上,泛化能力和表达能力都很好,这使得GBDT在Kaggle的众多竞赛中,经常名列榜首。
(3)采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性,能够自动发现特征间的高阶关系,并且也不需要对数据进行特殊的预处理如归一化等。
缺点:
(1)GBDT在高维稀疏的数据集上,表现不如支持向量机或者神经网络。
(2)GBDT在处理文本分类特征问题上,相对其他模型的优势不如它在处理数值特征时明显。
(3)训练过程需要串行训练,只能在决策树内部采用一些局部并行的手段提高训练速度。
3.3 Xgboost
XGBoost是陈天奇等人开发的一个开源机器学习项目,高效地实现了GBDT算法并进行了算法和工程上的许多改进。
目标函数: \[L^{(t)} = \sum_{i=1}^{n}l(y_i, \hat{y}_i^{(t)}) + \Omega(f_t) \]
优点:
(1)计算效率高,使用了二阶导。
(2)有正则化,减少过拟合。
(3)列特征抽样减少过拟合,同时有利于并行计算。
缺点:
(1)每次迭代时都要遍历整个数据集。
(2)内存占用大。
3.4 GBDT与XGboost联系与区别
(1) GBDT是机器学习算法,XGBoost是该算法的工程实现。
(2) 在使用CART作为基分类器时,XGBoost显式地
加入了正则项
来控制模型的复杂度,有利于
防止过拟合
,从而提高模型的
泛化能力
。
(3) GBDT在模型训练时只使用了代价函数的
一阶导数
信息,XGBoost对代价函数进行
二阶泰勒展
开,可以同时
使用一阶和二阶导
数。
(4) 传统的GBDT采用CART作为基分类器,XGBoost
支持多种类型
的基分类器,比如线性分类器。
(5) 传统的GBDT在每轮迭代时使用
全部的数据
,XGBoost则采用了与随机森林相似的策略,支持对
数据进行采样
。
(6) 传统的GBDT
没有设计对缺失值进行处
理,XGBoost能够
自动学习出缺失值的处理策略
。
3.5 LightGBM
LightGBM
也是一种基于决策树的梯度提升算法,相比XGboost有做了许多改进。 在树分裂计算分裂特征的增益时,xgboost 采用了预排序的方法来处理节点分裂,这样计算的分裂点比较精确。但是,也造成了很大的时间开销。为了解决这个问题,Lightgbm 选择了基于 histogram 的决策树算法。相比于
pre-sorted
算法,
histogram
在内存消耗和计算代价上都有不少优势。
Histogram
算法简单来说,就是先对特征值进行装箱处理,形成一个一个的bins。在Lightgbm中默认的#bins为256(1个字节的能表示的长度,可以设置)。具体如下:
(1) 把连续的浮点特征值离散化成N个整数,构造一个宽度为N的直方图;对于分类特征,则是每一种取值放入一个bin,且当取值的个数大于max_bin数时,会忽略那些很少出现的category值。
(2) 遍历数据时,根据离散化后的值作为索引在直方图中累积统计量。
(3) 一次遍历后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。
Level-wise 和 Leaf-wise
相对于xgboost的level—wise的生长策略,lightgbm使用了leaf-wise树生长策略。由于level-wise在分裂时,部分增益小的树也得到了增长,虽然容易控制误差,但是分裂有时是不合理的,而lightgbm使用level-wise,只在增益大的树上分裂生长,甚至对Feature f如果分裂无收益,那么后续也将不会对f计算。体现在参数上,xgboost使用max_depth,而lightgbm使用num_leaves控制过拟合。
Level-wise过一次数据
可以同时分裂同一层的叶子,容易进行多线程优化
,也
好控制模型复杂度,不容易过拟合
。但实际上Level-wise是一种低效的算法,因为它不加区分的对待同一层的叶子,带来了很多没必要的开销,因为实际上
很多叶子的分裂增益较低,没必要进行搜索和分裂
。
image
Leaf-wise则是一种
更为高效
的策略,每次从当前所有叶子中,
找到分裂增益最大的一个叶子,然后分裂,如此循环
。因此同Level-wise相比,在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度。Leaf-wise的缺点是
可能会长出比较深的决策树,产生过拟合
。因此LightGBM在Leaf-wise之上增加了一个
最大深度的限制
,在保证高效率的同时防止过拟合。
image
3.6 Xgboost与LightGBM对比
3.6.1 切分算法(切分点的选取)
占用的内存更低,只保存特征离散化后的值
,而这个值一般用8位整型存储就足够了,内存消耗可以降低为
原来的1/8
。
降低了计算的代价
:预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k次(k可以认为是常数),时间复杂度从O(#data#feature)优化到O(k#features)。(相当于LightGBM牺牲了一部分切分的精确性来提高切分的效率,实际应用中效果还不错)
空间消耗大,需要保存数据的特征值以及特征排序的结果(比如排序后的索引,为了后续快速计算分割点),需要消耗两倍于训练数据的内存
时间上也有较大开销,遍历每个分割点时都需要进行分裂增益的计算,消耗代价大
对cache优化不友好,在预排序后,特征对梯度的访问是一种随机访问,并且不同的特征访问的顺序不一样,无法对cache进行优化。同时,在每一层长树的时候,需要随机访问一个行索引到叶子索引的数组,并且不同特征访问的顺序也不一样,也会造成较大的cache miss。
XGBoost使用的是pre-sorted算法(对所有特征都按照特征的数值进行预排序,基本思想是对所有特征都按照特征的数值进行预排序;然后在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点最后,找到一个特征的分割点后,将数据分裂成左右子节点。优点是能够更精确的找到数据分隔点;但这种做法有以下缺点
LightGBM使用的是histogram算法,基本思想是先把连续的浮点特征值离散化成k个整数,同时构造一个宽度为k的直方图。在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点;优点在于
3.6.2 决策树生长策略
XGBoost采用的是带深度限制的level-wise生长策略,Level-wise过一次数据可以能够同时分裂同一层的叶子,容易进行多线程优化,不容易过拟合;但不加区分的对待同一层的叶子,带来了很多没必要的开销(因为实际上很多叶子的分裂增益较低,没必要进行搜索和分裂)
LightGBM采用leaf-wise生长策略,每次从当前所有叶子中找到分裂增益最大(一般也是数据量最大)的一个叶子,然后分裂,如此循环;但会生长出比较深的决策树,产生过拟合(因此 LightGBM 在leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合)。
Histogram做差加速。一个容易观察到的现象:一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。利用这个方法,LightGBM可以在构造一个叶子的直方图后,可以用非常微小的代价得到它兄弟叶子的直方图,在速度上可以提升一倍。
直接支持类别特征:LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。
3.6.3 分布式训练方法上(并行优化)
在特征并行算法中,通过在本地保存全部数据避免对数据切分结果的通信;
在数据并行中使用分散规约(Reducescatter)把直方图合并的任务分摊到不同的机器,降低通信和计算,并利用直方图做差,进一步减少了一半的通信量。基于投票的数据并行(ParallelVoting)则进一步优化数据并行中的通信代价,使通信代价变成常数级别。
特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点,然后在机器间同步最优的分割点。
数据并行则是让不同的机器先在本地构造直方图,然后进行全局的合并,最后在合并的直方图上面寻找最优分割点。
Cache命中率优化
基于直方图的稀疏特征优化
DART(Dropout + GBDT)
GOSS(Gradient-based One-Side Sampling):一种新的Bagging(row subsample)方法,前若干轮(1.0f /gbdtconfig->learning_rate)不Bagging;之后Bagging时, 采样一定比例g(梯度)大的样本。
4 stacking
stacking的思想是将每个基模型的输出组合起来作为一个特征向量,重新进行训练
。可以理解为:将训练好的所有基模型对整个训练集进行预测,第j个基模型对第i个训练样本的预测值将作为新的训练集中第i个样本的第j个特征值,最后基于新的训练集进行训练。同理,预测的过程也要先经过所有基模型的预测形成新的测试集,最后再对测试集进行预测。
具体算法如下(为方便理解我举例说明)
:
(1) 训练集大小\(400\times10\),400个样本,每个样本10个特征,(如果算上target有11列)。测试集大小为\(120\times10\)。
(2) 首先对训练集4折划分:\(S_1\),\(S_2\),\(S_3\),\(S_4\),每个\(S_i\)的大小都收是\(100\times10\)。模型\(M_1\)第一次用\(S_1\),\(S_2\),\(S_3\)训练,用\(S_4\)预测得到预测结果\(100\times1\)。重复训练步骤,直到每一个\(S_i\)都有对应的预测结果\(100\times1\)。合并所有预测结果得到\(P_1\)\(400\times1\)。用\(M_1\)预测得到原始测试集的预测结果\(T_1\)\(120\times1\)。
(3) 模型\(M_2\)用4折叫交叉得到训练集的预测结果:\(P_2\)\(400\times1\);得到测试集的预测结果:\(T_2\)\(120\times1\)。
(4) 模型\(M_3\)用4折叫交叉得到训练集的预测结果:\(P_3\)\(400\times1\);得到测试集的预测结果:\(T_3\)\(120\times1\)。
(5) 综合(2)(3)(4)底层模型得到的训练集的预测结果\(P_1\)、\(P_2\)、\(P_3\),得到上层模型的训练集\(P_{train}\)\(400\times3\);得到上层模型的测试集\(T_{test}\)\(120\times3\)。
(6) 用(5)得到的训练集和测试集进行上层模型的训练。
优点:学习了底层模型之间的关系
缺点:对于数据量要求比较大,因为要平衡第一层和第二层 5 参考
《百面机器学习》
https://zhuanlan.zhihu.com/p/26890738
https://www.imooc.com/article/29530
https://blog.csdn.net/anshuai_aw1/article/details/83040541
本文参与
腾讯云自媒体同步曝光计划
,分享自作者个人站点/博客。
原始发表:2019-06-24 ,如有侵权请联系
cloudcommunity@tencent.com
删除
前往查看
决策树
神经网络
深度学习
人工智能
编程算法
本文分享自
作者个人站点/博客
前往查看
如有侵权,请联系
cloudcommunity@tencent.com
删除。
本文参与
腾讯云自媒体同步曝光计划
,欢迎热爱写作的你一起参与!
决策树
神经网络
深度学习
人工智能
编程算法
评论
登录
后参与评论
0 条评论
热度
最新
推荐阅读
LV.
文章
0
获赞
0
目录
1 基本概念
2 bagging
2.1 Random Forest
3 boosting
3.1 Adboost
3.2 GBDT
3.3 Xgboost
3.4 GBDT与XGboost联系与区别
3.5 LightGBM
3.6 Xgboost与LightGBM对比
3.6.1 切分算法(切分点的选取)
3.6.2 决策树生长策略
3.6.3 分布式训练方法上(并行优化)
4 stacking
相关产品与服务
GPU 云服务器
GPU 云服务器(Cloud GPU Service,GPU)是提供 GPU 算力的弹性计算服务,具有超强的并行计算能力,作为 IaaS 层的尖兵利器,服务于生成式AI,自动驾驶,深度学习训练、科学计算、图形图像处理、视频编解码等场景。腾讯云随时提供触手可得的算力,有效缓解您的计算压力,提升业务效率与竞争力。
产品介绍
产品文档
2核2G3M云服务器38元/年,领劵最高省3150元
领券
问题归档
专栏文章
快讯文章归档
关键词归档
开发者手册归档
开发者手册 Section 归档
0
0
0
推荐