随机森林算法介绍(理论)

浏览: 470

作者:皮吉斯 人工智能爱好者社区专栏作者

知乎专栏:

https://www.zhihu.com/people/huang-jing-ji-89/activities

一、集成学习和体格学习器的概念

集成学习:通过构建并结合多个学习器来完成任务,有时也被称为多分类器系统、基于委员会的学习等。

个体学习器:也就是常见的学习算法,如逻辑回归,神经网络等,根据个体学习器间的强弱依赖关系,可以分类两类集成学习算法。一类是具有强依赖性,个体学习器必须串行生成的序列化方法,代表算法是Boosting。另一类的具有弱依赖性,个体学习器可同时生成的并行化方法,代表算法是Bagging和"随机森林"。

下图显示出集成学习的一般结构:

先产生一组"个体学习器",再用某种策略将他们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生,例如C4.5决策树算法、BP神经网络算法等,此时集成中只包含同种类型的个体学习器,例如"决策树集成"中全是决策树,"神经网络集成"中全是神经网络,这样的集成叫同质集成,同质集成中的个体学习器也叫"基学习器",相应的学习算法叫"基学习算法"。集成也可包含不同类型的个体学习器,例如同时包含决策树和神经网络,这样的集成叫异质集成,异质集成中的个体学习器由不同的学习算法生成,这时的个体学习器叫做组间学习器或者直接叫个体学习器。

集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能。这对"弱学习器"尤为明显,因此集成学习的很多理论都是针对弱学习器进行的,而基学习器有时也被称为弱学习器,但要注意的是,虽然理论上来说使用弱学习器集成足以获得好的性能,但在实践中处于种种考虑,例如希望使用较少的个体学习器,或是重用关于常见学习器的一些经验等,人们往往会使用比较强的学习器。

弱学习器常指泛化性能略优于随机猜测的学习器

原则

  1. 集成学习的结果通过投票法产生,即"少数服从多数"。

  2. 个体学习器要有一定的准确性,至少不差于若学习器,即"学习器不能太坏"。

  3. 个体学习器要有多样性,即学习器间有差异。

二、Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似:先从初始训练集训练出一个基学习器,再根据基学习器的表现对训练样本分布进行调整,使得先前基学习器做错的训练样本在后续受到更多关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复进行,直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合。

Boosting算法要求基学习器能对特定的数据分布进行学习,这可通过"重赋权法"实施,即在训练过程的每一轮中,根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基学习算法,则可通过"重采样法"(re-sampling)来处理,即在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样而得的样本集对基学习器进行训练。一般而言,这两种做法没有显著的优劣差别。需注意的是,Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件,即检查当前基分类器是否比随机猜测的好,一旦条件不满足,则当前基学习器即被抛弃,且学习过程停止。在此种情形下,初始设置的学习轮数T也许还远未达到,可能导致最终集成中只包含很少的基学习器而性能不佳。若采用"重采样法",则可获得“重启动”机会以避免训练过程中过早停止,即在抛弃不满足条件的当前基学习器之后,可根据当前分布重新对训练样本进行采样,再基于新的采样结果重新训练出基学习器,从而使得学习过程可以持续到预设的T轮完成。

从偏差-方差分解的角度看,Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

三、Bagging

由前面介绍可知,想要得到泛化能力强的集成,集成中的个体学习器应尽可能相互独立;虽然"独立"在现实任务中无法做到,但可以设法使基学习器尽可能具有较大的差异。给定一个训练数据集,一种可能的做法是对训练样本进行采样,产生出若干不同的子集,再从每个数据子集中训练出一个基学习器。这样,由于训练数据不同,我们获得的基学习器可望具有较大的差异。然而,为获得好的集成,我们还希望个体学习器不能太差。如果采样出的每个子集都完全不同,则每个基学习器只用到了一小部分训练数据,甚至不足以进行有效学习,这显然无法确保产生出比较好的基学习器。为了解决这个问题,我们可以考虑使用相互有交叠的采样子集。

Bagging是并行式集成学习方法最著名的代表。它直接基于自助采样法(bootstrap sampling),给定包含m个样本的数据集,我们先随机取出一个样本放入采样集中,再把该样本放回初始数据集,使得下次采样时该样本仍有可能被选中,这样,经过m次随机采样操作,我们得到含m个样本的采样集,初始训练集中有的样本在采样集里多次出现,有的则从未出现。

照这样,我们可采样出T个含m个样本的采样集,然后基于每个采样集训练出一个基学习器,再将这些基学习器进行结合,这就是Bagging的基本流程。在对预测输出进行结合时,Bagging通常对分类任务使用简单投票法,对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形,则最简单的做法是随机选择一个,也可进一步考察学习器投票的置信度来确定最终胜利者。

为处理多分类或者回归任务。Adaboost需进行修改,与标准AdaBoost只适用于二分类任务不同,Bagging能不经修改的用于多分类、回归等任务。而且自助采样过程还给Bagging带来另一个优点:由于每个基学习器只使用了初始训练集中部分样本(63.2%),剩下的样本(36.8%)的样本可用作验证集来对泛化性能进行"包外估计"(out-of-bag estimate)。

自助法:我们希望评估的是用D训练出的模型。但在留出法和交叉验证法中,由于保留了一部分样本用于测试,因此实际估计的模型所使用的训练集比D小,这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小,但计算复杂度又太高。"自助法"是一个好的解决办法,它直接以自助采样法为基础。给定包含m个样本的数据集D,我们对他进行采样产生数据集D1:每次随机从D中挑选一个样本,将其拷贝放入D1,然后再将该样本放回初始数据集D中,使得该样本在下次采样时扔有可能被采到;这个过程重复执行m次后,我们就得到了包含m个样本的数据集D1,这就是自助采样的结果。显然,D中有一部分样本会出现多次,而另一部分样本不出现。样本在m次采样中始终不被采样的概率是 ,取极限得到0.368。即通过采样法,初始数据集D中约有36.8%的样本未出现在采样数据集D1中。于是我们可将D1用作训练集,D\D1用作测试集。这样,实际评估的模型与期望评估的模型都是用m个训练样本,而我们扔有1/3的,没在训练集出现的样本用于测试。这样的测试结果也叫"包外估计"。

事实上,包外估计还可用来在决策树时辅助剪枝;估计决策树中各节点的后验概率以辅助对零训练样本结点的处理;在基学习器是神经网络时,可用来辅助早起停止以减小基学习器是神经网络的过拟合风险。

从偏差-方差角度分析,Bagging主要关注降低方差,因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

四、结合策略 

学习器结合可能会从三个方面带来好处:首先,从统计的方面来看,由于学习任务的假设空间往往很大,可能有多个假设在训练集上达到同等性能,此时若使用单学习器可能因误选而导致泛化性能不佳,结合多个学习器则会减少这一风险;第二,从计算方面来看,学习算法往往会陷入局部极小,有的局部极小点所对应的泛化性能可能糟糕,而通过多次运行之后进行结合,可降低糟糕局部极小点的风险;第三,从表示的方面来看,某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中,此时若使用单学习器则肯定无效,而通过结合多个学习器,由于相应的假设空间扩大,有可能学得更好的近似。

  • 平均法:对于数值型输出,最常见的结合策略是使用平均法。

    一是简单平均法,二是加权平均法,T是学习器个数, 是个体学习器 的权重,通常。加权平均法的权重一般是从训练数据中学习而得,例如估计出个体学习器的误差,然后令权重大小与误差大小成反比。现实任务中的训练样本通常不充分或存在噪声,这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说,要学习的权重比较多,较容易导致过拟合。因此,实验和应用均显示出,加权平均法未必一定由于简单平均法。一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近时宜使用简单平均法。

  • 投票法:即少数服从多数。聚合每个分类器的预测,然后将得票最多的结果作为预测类型,这种大多数投票分类器被称为硬投票分类器。

  • 学习法:当训练数据很多时,一种更为强大的结合策略是使用“学习法”,即通过另一个学习器来进行结合。Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器,用于结合的学习器称为次级学习器。

stacking是一种分层模型集成框架。以两层为例,第一层由多个基学习器组成,其输入为原始训练集,第二层的模型则是以第一层基学习器的输出作为训练集进行再训练,从而得到完整的stacking模型。

五、随机森林

理解了bagging算法,随机森林(Random Forest)就好理解了。它是Bagging算法的进化版。首先,RF使用了CART决策树作为弱学习器。第二,在使用决策树的基础上,RF对决策树的建立做了改进,对于普通的决策树,我们会在节点上所有的n个样本特征中选择一个最优的特征来做决策树的左右子树划分,但是RF通过随机选择节点上的一部分样本特征,这个数字小于n,为m,然后在这些随机选择的m个样本特征中,选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。    

如果m=n,则此时RF的CART决策树和普通的CART决策树没有区别。m越小,则模型约健壮,当然此时对于训练集的拟合程度会变差。也就是说m越小,模型的方差会减小,但是偏倚会增大。在实际案例中,一般会通过交叉验证调参获取一个合适的m的值。除了上面两点,RF和普通的bagging算法没有什么不同。

六、随机森林的推广

由于RF在实际应用中的良好特性,基于RF,有很多变种算法,应用也很广泛,不光可以用于分类回归,还可以用于特征转换,异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

extra trees

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

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

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

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

2. Totally Random Trees Embedding

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

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

七、随机森林的优缺点

作为一个可以高度并行化的算法,RF在大数据时大有可为。

RF的主要优点有:

⒈训练可以高度并行化,对于大数据的大样本训练速度有优势。

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

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

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

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

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

RF的主要缺点:

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

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

八、sklearn参数

RF的分类器是RandomForestClassifier,回归器是RandomForestRegressor。RF需要调的参数包括两部分,第一部分是Bagging框架的参数,第二部分是CART决策树的参数。



classsklearn.ensemble.RandomForestClassifier(
       n_estimators=10, criterion='gini',
       max_depth=None,min_samples_split=2,
       min_samples_leaf=1, min_weight_fraction_leaf=0.0,
       max_features='auto', max_leaf_nodes=None,
       min_impurity_split=1e-07,bootstrap=True,
       oob_score=False, n_jobs=1,
       random_state=None, verbose=0,
       warm_start=False, class_weight=None)



Bagging框架的参数解释:

n_estimators:弱学习器的最大迭代次数,或者说最大的弱学习器的个数。一般来说n_estimators太小,容易过拟合,太大又容易欠拟合,一般选择一个适中的数值。默认是100.实际调参的过程中,我们常常将n_estimators和下面介绍的参数learning_rate一起考虑。
oob_score:即是否采用袋外样本来评估模型的好坏。默认设置False。个人推荐设置为True,因为袋外分数反应了一个模型拟合后的泛化能力。
criterion:即CART决策树做划分时对特征的评价标准。分类模型和回归模型的损失函数不一样。分类RF对应的CART分类树默认是基尼系数,另一个可选择的标准是信息增益。回归RF对应的CART回归树默认是均方差mse,另一个可以选择的标准时绝对值mae。一般来说选择默认的标准就已经很好了。

RF重要的框架参数比较少,主要关注的是n_estimators,即RF最大的决策树个数。

RF决策树参数

RF的决策树参数,它要调参的参数基本和GBDT相同,如下:

max_features:RF划分时考虑的最大特征,可以使用很多种类型的值,默认是"auto",意味着划分时最多考虑个特征;如果是"log2"意味着划分时最多考虑个特征;如果是"sqrt"或者"auto"意味着划分时最多可考虑个特征。如果是整数,代表老驴的特征绝对数。如果是浮点数,代表老驴特征百分比,即考虑取整后的特征数。其中N为样本总特征数。一般我们默认的"auto"就可以了,如果特征数非常多,我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数,以控制决策树的生成时间。

max_depth: 决策树最大深度。默认可以不输入,如果不输入的话,决策树在建立子树的时候不会限制子树的深度。一般来说,数据少或者特征少的时候可以不管这个值。如果模型样本量多,特征也多的情况下,推荐限制这个最大深度,具体的取值取决于数据的分布。常用的可以取值10-100之间。
min_samples_split: 内部节点再划分所需最小样本数。这个值限制了子树继续划分的条件,如果某节点的样本数少于min_samples_split,则不会继续再尝试选择最优特征来进行划分。 默认是2.如果样本量不大,不需要管这个值。如果样本量数量级非常大,则推荐增大这个值。
min_samples_leaf: 叶子节点最少样本数。这个值限制了叶子节点最少的样本数,如果某叶子节点数目小于样本数,则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数,或者最少样本数占样本总数的百分比。如果样本量不大,不需要管这个值。如果样本量数量级非常大,则推荐增大这个值。
min_weight_fraction_leaf:叶子节点最小的样本权重和。这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和兄弟节点一起被剪枝。 默认是0,就是不考虑权重问题。一般来说,如果我们有较多样本有缺失值,或者分类树样本的分布类别偏差很大,就会引入样本权重,这时我们就要注意这个值了。
max_leaf_nodes: 最大叶子节点数。通过限制最大叶子节点数,可以防止过拟合,默认是"None”,即不限制最大的叶子节点数。如果加了限制,算法会建立在最大叶子节点数内最优的决策树。如果特征不多,可以不考虑这个值,但是如果特征分成多的话,可以加以限制,具体的值可以通过交叉验证得到。
min_impurity_split: 节点划分最小不纯度。这个值限制了决策树的增长,如果某节点的不纯度(基于基尼系数,均方差)小于这个阈值,则该节点不再生成子节点。即为叶子节点 。一般不推荐改动默认值1e-7。

上面决策树参数中最重要的包括最大特征数max_features, 最大深度max_depth, 内部节点再划分所需最小样本数min_samples_split和叶子节点最少样本数min_samples_leaf。


推荐 0
本文由 人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册