机器学习(24)之Bagging与随机森林

关键字全网搜索最新排名

【机器学习算法】:排名第一

【机器学习】:排名第一

【Python】:排名第三

【算法】:排名第四

前言

在(机器学习(17)之集成学习原理总结)中,我们谈到了集成学习有两个流派,一个是boosting派系,它的特点是各个弱学习器之间有依赖关系。另一种是bagging流派,它的特点是各个弱学习器之间没有依赖关系,可以并行拟合。本文就对集成学习中Bagging与随机森林算法做一个总结。随机森林是集成学习中可以和梯度提升树GBDT分庭抗礼的算法,尤其是它可以很方便的并行训练,在如今大数据大样本的的时代很有诱惑力。

Bagging原理

如图所示,Bagging的弱学习器之间的确没有boosting那样的联系。它的特点在“随机采样”。那么什么是随机采样?

随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本,但是每采集一个样本后,都将样本放回。也就是说,之前采集到的样本在放回后有可能继续被采集到。对于Bagging算法,一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同,但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样,则由于随机性,T个采样集各不相同(注意到这和GBDT的子采样是不同的。GBDT的子采样是无放回采样,而Bagging的子采样是放回采样)。

对于一个样本,它在某一次含m个样本的训练集的随机采样中,每次被采集到的概率是1/m。不被采集到的概率为1−1/m。如果m次采样都没有被采集中的概率是(1−1/m)^m。当m→∞时,(1−1/m)^m→1/e≃0.368。也就是说,在bagging的每轮随机采样中,训练集中大约有36.8%的数据没有被采样集采集中。对于这部分大约36.8%的没有被采样到的数据,我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合,因此可以用来检测模型的泛化能力。

Bagging对于弱学习器没有限制,这和Adaboost一样。但是最常用的一般也是决策树和神经网络。Bagging的集合策略也比较简单,对于分类问题,通常使用简单投票法,得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题,通常使用简单平均法,对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。由于Bagging算法每次都进行采样来训练模型,因此泛化能力很强,对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些,也就是模型的偏倚会大一些。

Bagging算法流程

相对于Boosting系列的Adaboost和GBDT,Bagging算法要简单的多。

输入:样本集D={(x,y1),(x2,y2),...(xm,ym)},弱学习器算法, 弱分类器迭代次数T。

输出:最终的强分类器f(x)

1)对于t=1,2...,T:

a)对训练集进行第t次随机采样,共采集m次,得到包含m个样本的采样集Dm

  b)用采样集Dm训练第m个弱学习器Gm(x)

2) 如果是分类算法预测,则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法,T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

随机森林

随机森林(Random Forest,以下简称RF),它是Bagging算法的进化版,也就是它的思想仍然是Bagging,但是进行了独有的改进。我们现在就来看看RF算法改进了什么。   

首先,RF使用了CART决策树作为弱学习器,这让我们想到了梯度提示树GBDT。

第二,在使用决策树的基础上,RF对决策树的建立做了改进,对于普通的决策树,我们会在节点上所有的n个样本特征中选择一个最优的特征来做决策树的左右子树划分,但是RF通过随机选择节点上的一部分样本特征,这个数字小于n,假设为nsub,然后在这些随机选择的nsub个样本特征中,选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。如果nsub=n,则此时RF的CART决策树和普通的CART决策树没有区别。nsub越小,则模型约健壮,当然此时对于训练集的拟合程度会变差。也就是说nsub越小,模型的方差会减小,但是偏倚会增大。在实际案例中,一般会通过交叉验证调参获取一个合适的nsub的值。

除了上面两点,RF和普通的bagging算法没有什么不同, 下面简单总结下RF的算法。

输入:样本集D={(x,y1),(x2,y2),...(xm,ym)},弱分类器迭代次数T。

输出:最终的强分类器f(x)

1)对于t=1,2...,T:

a) 对训练集进行第t次随机采样,共采集m次,得到包含m个样本的采样集Dm

  b) 用采样集Dm训练第m个决策树模型Gm(x),在训练决策树模型的节点的时候, 在节点上所有的样本特征中选择一部分样本特征, 在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分

2) 如果是分类算法预测,则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法,T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

随机森林的推广

Extra trees

extra trees是RF的一个变种, 原理几乎和RF一模一样,仅有区别有:

1) 对于每个决策树的训练集,RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集,而extra trees一般不采用随机采样,即每个决策树采用原始训练集。

2) 在选定了划分特征后,RF的决策树会基于信息增益,基尼系数,均方差之类的原则,选择一个最优的特征值划分点,这和传统的决策树相同。但是extra trees比较的激进,他会随机的选择一个特征值来划分决策树。

从第二点可以看出,由于随机选择了特征值的划分点位,而不是最优点位,这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说,模型的方差相对于RF进一步减少,但是偏倚相对于RF进一步增大。在某些时候,extra trees的泛化能力比RF更好。

Totally Random Trees Embedding

Totally Random Trees Embedding(以下简称 TRTE)是一种非监督学习的数据转化方法。它将低维的数据集映射到高维,从而让映射到高维的数据更好的运用于分类回归模型。我们知道,在支持向量机中运用了核方法来将低维的数据集映射到高维,此处TRTE提供了另外一种方法。

TRTE在数据转化的过程也使用了类似于RF的方法,建立T个决策树来拟合数据。当决策树建立完毕以后,数据集里的每个数据在T个决策树中叶子节点的位置也定下来了。比如我们有3颗决策树,每个决策树有5个叶子节点,某个数据特征x划分到第一个决策树的第2个叶子节点,第二个决策树的第3个叶子节点,第三个决策树的第5个叶子节点。则x映射后的特征编码为(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。映射到高维特征后,可以继续使用监督学习的各种分类回归算法了。

Isolation Forest

Isolation Forest(以下简称IForest)是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点。

对于在T个决策树的样本集,IForest也会对训练集进行随机采样,但是采样个数不需要和RF一样,对于RF,需要采样到采样集样本个数等于训练集个数。但是IForest不需要采样这么多,一般来说,采样个数要远远小于训练集个数?为什么呢?因为我们的目的是异常点检测,只需要部分的样本我们一般就可以将异常点区别出来了。对于每一个决策树的建立, IForest采用随机选择一个划分特征,对划分特征随机选择一个划分阈值。这点也和RF不同。另外,IForest一般会选择一个比较小的最大决策树深度max_depth,原因同样本采集,用少量的异常点检测一般不需要这么大规模的决策树。

随机森林小结

RF作为一个可以高度并行化的算法,在大数据时候大有可为。 这里也对常规的随机森林算法的优缺点做一个总结。

优点

1) 训练可以高度并行化,对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。

2) 由于可以随机选择决策树节点划分特征,这样在样本特征维度很高的时候,仍然能高效的训练模型。

3) 在训练后,可以给出各个特征对于输出的重要性

4) 由于采用了随机采样,训练出的模型的方差小,泛化能力强。

5) 相对于Boosting系列的Adaboost和GBDT, RF实现比较简单。

6) 对部分特征缺失不敏感。

缺点

1)在某些噪音比较大的样本集上,RF模型容易陷入过拟合。

2) 取值划分比较多的特征容易对RF的决策产生更大的影响,从而影响拟合的模型的效果。

欢迎分享给他人让更多的人受益

参考:

  1. 周志华《机器学习》
  2. Neural Networks and Deep Learning by By Michael Nielsen
  3. 博客园 http://www.cnblogs.com/pinard/p/6156009.html
  4. 李航《统计学习方法》

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2017-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉战队

通过部分感知深度卷积网络进行人脸特征点定位

人脸特征点定位是一个非常具有挑战性的研究课题。由于纹理和形状的不同,不同人脸特征点的定位精度差异很大。但大多数现有的方法不能考虑特征点的部分位置。 为了解决这个...

32760
来自专栏智能算法

机器学习三人行(系列九)----千变万化的组合算法(附代码)

上节中我们讲解了决策树的使用: 机器学习三人行(系列八)----神奇的分类回归决策树(附代码) 本文我们在决策树的基础上,更进一步的讨论由常用机器学习算法进行组...

408110
来自专栏AI科技大本营的专栏

从YOLOv1到YOLOv3,目标检测的进化之路

这是继 RCNN,fast-RCNN 和 faster-RCNN之后,Ross Girshick 针对 DL 目标检测速度问题提出的另外一种框架。YOLO V1...

49830
来自专栏SnailTyan

YOLO,You Only Look Once论文翻译——中英文对照

You Only Look Once: Unified, Real-Time Object Detection Abstract We present YOLO...

33800
来自专栏磐创AI技术团队的专栏

干货 | 基于深度学习的目标检测算法综述(一)

目标检测(Object Detection)是计算机视觉领域的基本任务之一,学术界已有将近二十年的研究历史。近些年随着深度学习技术的火热发展,目标检测算法也从基...

26920
来自专栏人工智能

用PaddlePaddle和Tensorflow实现经典CNN网络GoogLeNet

前面讲了LeNet、AlexNet和Vgg,这周来讲讲GoogLeNet。GoogLeNet是由google的Christian Szegedy等人在2014年...

33090
来自专栏人工智能

通过部分感知深度卷积网络进行人脸特征点定位

人脸特征点定位是一个非常具有挑战性的研究课题。由于纹理和形状的不同,不同人脸特征点的定位精度差异很大。但大多数现有的方法不能考虑特征点的部分位置。 为了解决这个...

226100
来自专栏机器之心

入门 | 了解神经网络,你需要知道的名词都在这里

338130
来自专栏SIGAI学习与实践平台

用一张图理解SVM的脉络

SVM在之前的很长一段时间内是性能最好的分类器,它有严密而优美的数学基础作为支撑。在各种机器学习算法中,它是最不易理解的算法之一,要真正掌握它的原理有一定的难度...

1.2K10
来自专栏AI科技评论

干货 | 基于深度学习的目标检测算法综述(一)

目标检测(Object Detection)是计算机视觉领域的基本任务之一,学术界已有将近二十年的研究历史。近些年随着深度学习技术的火热发展,目标检测算法也从基...

17720

扫码关注云+社区

领取腾讯云代金券