通过聚集多个分类器的预测来提高分类准确率的技术称为组合学习/集成学习(Ensemble Learning)。本文主要介绍相关概念,叙述几种常见集成学习模型的构造。
集成学习中构建组合分类器的方法如下: 1、 通过处理训练数据集 根据某种抽样,对原始数据进行再抽样得到多个训练集。使用特定的学习算法对每个训练集建立一个分类器。
Bagging(基分类器通常是同一个,如决策树) Boosting(基分类器通常是同一个,如决策树)2、 通过处理特征 通过选择输入特征的子集形成每个训练集,对于含有大量冗余特征的数据集,这种方法性能好。
RandomForest(基分类器通常是同一个,如决策树)3、 通过组合不同分类器 通过训练多个模型,学习如何把各个模型组合达到最优性能。
Stacking(基分类器通常是多个不同的分类器)Bagging(袋装)又称自助聚集,是一种根据均匀概率分布从数据集中重复抽样(有放回)的技术。每一次抽样的样本大小和原训练集大小一致,一般而言,抽样产生的数据集大约包含 63 的原来数据,因为每一个样本被抽到的概率为 1−(1−1/N)N , N 足够大时,取极限为1−1/e≈0.63。具体算法如下:
通俗地讲,Bagging主要流程如下: 1. 先确定自助样本集的数目 k ,即有放回的抽样N次获得一个自助样本集,如此重复 k 次 2. 在k个数据集上训练一个基分类器(通常是决策树) 3. 预测时,使用投票算法,每个分类器的权重相同
机器学习问题存在偏差-方差权衡的问题,那么Bagging如何处理这个问题呢?先说答案,一般来说Bagging不能显著降低bias,但是可以降低variance。 下面主要观点来自知乎网友–过拟合: 1、 Bias Bagging对样本重采样,对每一重采样得到的子样本集训练一个模型,最后取平均。由于子样本集的相似性以及使用的是同种模型,因此各模型有近似相等的bias和variance(事实上,各模型的分布也近似相同,但不独立)。
E[∑fin]=E[fi] 这个公式的前提是模型 fi 的期望相同,似乎没有严格的证明,但是符合直觉。所以bagging之后的bias和单个子模型的bias接近。 2、 Variance 如果各子模型 fi 独立,那么有方差公式: Var(∑fin)=nVar(fi)n2=Var(fi)n 此时可以显著降低Variance。 如果各子模型 fi 完全相同,那么有方差公式: Var(∑fin)=n2Var(fi)n2=Var(fi) 此时不会降低Variance。那么Bagging呢,假设训练集中的 n 个样本是来源于n个独立同分布随机变量的一次采样,Bagging时用有放回抽样形成多个自助样本集,此时会造成自助样本集之间有重叠,因此模型是不独立的,可以一定程度上降低方差。
也看到一个通俗点的回答,因为基分类器相同,所以损失函数没有变化,因此模型的预测能力并没有提高,但是多模型的组合对异常点不是很敏感,降低了方差。当然还是上面数学化的语言有说服力,但是感觉还是不完整,要是有完整的偏差方差推导就好了。
Boosting是迭代过程,每一次迭代都从训练集中抽取样本,每个样本被抽取的概率不同,且每一轮迭代概率发生改变。目的是使得上一轮被误分类的样本被抽取的概率更大。每一轮训练出一个基分类器,最终预测采用这些基分类器预测结果的加权结合。
符号标记: {(xj,yj)∣∣j=1,2,…,N} :训练集 Ci :第 i 轮的基分类器 εi:基分类器 Ci 的错误率 αi :基分类器 Ci 的权重,最后预测时投票的权重 w(i+1)j :第 i 迭代时,第j个样本的权重,也就是被抽到的概率,满足所有样本的概率和为1 其中,错误率公式:
εi=∑j=1Nw(i)jI(Ci(xj)≠yj) I 示性函数,预测正确为1,否则为0。可以理解为加权错误率基分类器Ci的权重 αi 为:
αi=12ln(1−εiεi) 如果错误率很小,那么权重很大,最终预测是该基分类器”话语权”重。
第 i 迭代时,第j个样本被抽到的概率 w(i+1)j 为:
w(i+1)j=w(i)jZj×{e−αiifCi(xj)=yjeαiifCi(xj)≠yj Zj 是正规化因子,确保 ∑jw(i+1)j=1
简述下算法流程:
Step1:以初始权值 w(1)j=1/N 抽取样本,训练第一个基分类器 Step2:每一轮计算模型误差率,迭代样本权重,计算模型权重 Step3:如果Step2中误差率大于0.5,回到Step1 直到提升次数达到设定通俗地解释,我也没太看懂。Boosting关注错分样本,一次一次的迭代中,bias会逐渐减小,而序列化迭代的方式使得各个子模型之间强相关(为什么?)。有空了,搞一搞paper看一看吧。
随机森林相当于Bagging的改进版,在基分类器生成时,每次分裂节点都随机选择部分特征,选取其中最优特征进行分裂。流程如下:
分裂节点是具体如下: 当每个样本有M个属性时,在决策树的每个节点需要分裂时,随机从这M个属性中选取出m个属性,满足条件m < M(建议分类中 m=log2M+1 或 M−−√ ,回归 M/3 )。然后从这m个属性中采用某种策略(比如说信息增益)来选择1个属性作为该节点的分裂属性。
先定义袋外数据:在进行bootstrap sample生成第 k 棵树时,大约有1/3的训练数据没有被抽样到,这些数据称为第 k 棵树的oob样本。计算袋外错误率obb-error具体如下: 1. 对每个样本,计算它作为oob样本的树对它的分类情况 2. 等权重投票预测分类结果 3. 误分类个数/样本总数作为oob误分率 Breiman论文有证明oob误分率是随机森林泛化误差的一个无偏估计,近似于需要大量计算的k折交叉验证。
设有i.d.(同分布)的n个随机变量,方差记为 σ2 ,两两变量之间的相关性为 ρ ,则 ∑Xin 的方差为 ρ∗σ2+(1−ρ)∗σ2n ,由这个公司可以看出Bagging是听过增加了 n ,减少第二项来降低方差。而RandomForests通过特征的随机化进一步降低ρ,使得第一项显著下降第二项略微增加。
简单讲讲stacking的构造逻辑,我自己只用caretEnsemble跑过demo,实际用过一次效果没有提高,反而下降。 假设Stacking有两层,第一层基学习器为 M1,M2,M3 ,第二层学习器为 M4 。算法流程如下: 1. 对于训练集 Train 随机拆分成互斥的 k 个样本 2. 取出其中一份样本做测试集Trainsub,剩下 k−1 份数据训练模型 M1 ,用训练好的 M1 预测 Trainsub 得到预测值 Trainsub−label 3. 重复step2, k−1 次,得到所有训练集的预测label 4. 对剩下的基学习器重复step2,step3,可以得到3个同样维度的label,作为第二层模型的训练数据,训练模型 M4 5. 真正做预测时,用 k 个M1模型预测,vote得到最后的label。其余基学习器类似操作,如此可以得到3个(基学习器的数量)预测值,以供 M4 进行预测
各个集成学习算法在降低Bias-Variance上的作用~ 后面有精力的话,希望能够就不同模型单独分析下~
简单的总结集成学习的概念,Bagging、AdaBoost、RandomForests的算法流程还算比较容易理解。我们都知道,机器学习算法的重点是Bias-Variance。如何分析各个集成学习模型中的Bias-Variance还是有点难搞,后面争取多多学习。
[1] 《The Element of Statistical Learning》 [2] 《数据挖掘导论》(PS:中文翻译有点难理解) [3] 《机器学习》周志华 [4] http://www.cnblogs.com/jasonfreak/p/5657196.html [5] http://www.cnblogs.com/jasonfreak/p/5720137.html 推荐[4、5]写的很清楚,图文并茂
2018-03-12 于杭州