前言
上一篇文章中我们讲到了一种常用的分类算法——决策树,今天我们要用到的随机森林算法,正是基于决策树的变种算法。随机森林算法(Random Forest) 和 *梯度提升决策树(*GradientBoosted Trees) 都是一种 集成学习(Ensemble Learning) 算法,核心的思想就是 “三个臭皮匠顶得过一个诸葛亮” 哈哈哈,就是假如一棵决策树他的分类预测可能是错的话,那么多颗树组成的森林,各自预测后通过投票得到一致的分类预测,那应该就不会错了吧,毕竟一棵错不可能棵棵都是错的嘛,这背后其实体现了一种群体的智慧。
集成学习(Ensemble Learning)
在机器学习的有监督学习算法中,我们的目标是学习出一个稳定的且在各个方面表现都较好的模型,但实际情况往往不这么理想,有时我们只能得到多个有偏好的模型(弱监督模型,在某些方面表现的比较好)。集成学习就是组合这里的多个弱监督模型以期得到一个更好更全面的强监督模型,集成学习潜在的思想是即便某一个弱分类器得到了错误的预测,其他的弱分类器也可以将错误纠正回来。
集成学习在各个规模的数据集上都有很好的策略。
- 数据集大:划分成多个小数据集,学习多个模型进行组合
- 数据集小:利用Bootstrap方法进行抽样,得到多个数据集,分别训练多个模型再进行组合
而集成学习算法里面,用得最多的就是 套袋法(Bagging) 和 提升法(Boosting) ,当决策树和套袋法结合到一起的时候,就是我们今天要讲的随机森林(Random Forest),而当决策树和提升法结合到一起就是梯度提升决策树(GradientBoosted Trees)了。下面简单地说下Bagging 和 Boosting两种算法的算法过程和区别。
套袋法(Bagging)
Bagging的算法过程如下:
- 从原始样本集中使用 Bootstrapping 方法随机抽取n个训练样本,共进行k轮抽取,得到k个训练集。(k个训练集之间相互独立,元素可以有重复)
- 对于k个训练集,我们训练k个模型(这k个模型可以根据具体问题而定,比如决策树,knn等)
- 对于分类问题:由投票表决产生分类结果;对于回归问题:由k个模型预测结果的均值作为最后预测结果。(所有模型的重要性相同)
这里的抽样算法 —— 自助法(Bootstrapping),在统计学中,是一种从给定训练集中有放回的均匀抽样,也就是说,每当选中一个样本,它等可能地被再次选中并被再次添加到训练集中。这里给出一张抽样后生成决策树的图,应该比较容易地去理解了,值得注意的是,样本放回是在每一次抽取样本的时候,所以看下图会发现同一个样本被多次抽了回去。
提升法(Boosting)
Boosting的算法过程如下:
- 对于训练集中的每个样本建立权值wi,表示对每个样本的关注度。当某个样本被误分类的概率很高时,需要加大对该样本的权值。
- 进行迭代的过程中,每一步迭代都是一个弱分类器。我们需要用某种策略将其组合,作为最终模型。(例如AdaBoost给每个弱分类器一个权值,将其线性组合最为最终分类器。误差越小的弱分类器,权值越大)
Bagging,Boosting的主要区别
- 样本选择上:Bagging采用的是Bootstrap随机有放回抽样;而Boosting每一轮的训练集是不变的,改变的只是每一个样本的权重。
- 样本权重:Bagging使用的是均匀取样,每个样本权重相等;Boosting根据错误率调整样本权重,错误率越大的样本权重越大。
- 预测函数:Bagging所有的预测函数的权重相等;Boosting中误差越小的预测函数其权重越大。
- 并行计算:Bagging各个预测函数可以并行生成;Boosting各个预测函数必须按顺序迭代生成。
随机森林算法(Random Forest)
随机森林算法的基本思想
随机森林是决策树的集合,可以说随机森林是用于分类和回归的最成功的机器学习模型之一。它们组合了许多相互独立没有关联的决策树,以降低过度拟合的风险。随机森林的出现也正是为了解单一决策树可能出现的很大误差和过拟合(over-fitting)的问题。
随机森林的“随机“选取
数据的随机选取
关于数据的随机选取,用的就是上面提到的抽样算法——自助法,首先,从原始的数据集中采取有放回的抽样,构造子数据集,子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复,同一个子数据集中的元素也可以重复。第二,利用子数据集来构建子决策树,将这个数据放到每个子决策树中,每个子决策树输出一个结果。最后,如果有了新的数据需要通过随机森林得到分类结果,就可以通过对子决策树的判断结果的投票,得到随机森林的输出结果了。
待选特征的随机选取
与数据集的随机选取类似,随机森林中的子树的每一个分裂过程并未用到所有的待选特征,而是从所有的待选特征中随机选取一定的特征,之后再在随机选取的特征中选取最优的特征(通过上一篇文章提到的信息熵来选取 )。这样能够使得随机森林中的决策树都能够彼此不同,提升系统的多样性,从而提升分类性能。以下图为例来说明随机选取待选特征的方法。
随机森林算法的优缺点
随机森林的优点:
- 具有极高的准确率
- 随机性的引入,使得随机森林不容易过拟合
- 随机性的引入,使得随机森林有很好的抗噪声能力
- 能处理很高维度的数据,并且不用做特征选择
- 既能处理离散型数据,也能处理连续型数据,数据集无需规范化
- 训练速度快,可以得到变量重要性排序
- 容易实现并行化
随机森林的缺点:
当随机森林中的决策树个数很多时,训练时需要的空间和时间会较大
随机森林模型还有许多不好解释的地方,算是个黑盒模型,由于几乎无法控制模型内部的运行,只能在不同的参数和随机种子之间进行尝试。
随机森林算法可以解决回归问题,但是由于不能输出一个连续型值和作出超越训练集数据范围的预测,导致在对某些噪声的数据进行建模时出现过度拟合
基于随机森林的手写数字识别
Spark-Mllib 中带有了随机森林的算法,在org.apache.spark.mllib.tree.RandomForest
这个类里面,我们根据它提供的格式输入数据以及参数即可得到训练模型。因为前几期已经见过如何处理MNIST的手写数字数据,所以这里就不重复说了,代码其实基本和上次的朴素贝叶斯 用到的是一样的,只不过换了一个训练的算法以及多了随机森林算法的可调参数,所以这里我就着重讲解参数,需要看完整的代码的同学可前往github查看:完整代码
MLlib中的参数及部分代码
这里先贴出部分代码,然后介绍参数:
1 | package SparkMLlib.Classification |
用法还是蛮简单的,数据格式处理成LabeledPoint
即可,主要的参数就是这么几个,现在来一一讲解:
- numClasses:分类的数目
- 比如手写数字0 - 9则分类的数目为10。这里定死了也意味着随机森林算法不能增量添加需要训练的分类,也不适合分类数目未知的数据(这种情况用聚类算法=。=)
- categoricalFeaturesInfo: 指定离散特征
- 原文:”Map storing arity of categorical features. An entry (n to k) indicates that feature n is categorical with k categories indexed from 0: {0, 1, …, k-1}.“。是一个map,用来表明特征和类别的类型。
- numTrees: 森林中的树木数量。
- 增加树的数量将减少预测的方差,从而提高模型的测试时间准确性。
- 训练时间在树木数量上大致线性增加。
- featureSubsetStrategy:要用作每个树节点处拆分的候选特征的数量。
- 该数字被指定为特征总数的分数或函数。减少这个数字会加快培训速度,但如果太低,有时会影响性能。一般来说填
auto
让算法自己选择就可以了。
- 该数字被指定为特征总数的分数或函数。减少这个数字会加快培训速度,但如果太低,有时会影响性能。一般来说填
- impurity:用于信息增益计算的标准。详细可查看我上一篇博客。
- “ gini ”:基尼不纯度
- “ entropy ”:信息熵
- maxDepth:森林中每棵树的最大深度。
- 更深的一棵树意味模型预测更有力,需要的训练时间也越长,而且更容易过度拟合。
- 但是值得注意的是,随机森林算法和单一决策树算法对这个参数的要求是不一样的。随机森林由于是多个的决策树预测结果的投票或平均而降低而预测结果的方差,因此相对于单一决策树而言,不容易出现过拟合的情况。所以随机森林可以选择比决策树模型中更大的maxDepth。
甚至有的文献说,随机森林的每棵决策树都最大可能地进行生长而不进行剪枝。但是不管怎样,还是建议对maxDepth参数进行一定的实验,看看是否可以提高预测的效果。
- maxBins:决策规则集,可以理解成是决策树的孩子节点的数量。(suggested value: 100)
对MNIST数据集进行训练并查看准确率
我们先按照Spark MLlib里面demo 的参数来跑一下看看:
准确率才68.48%
。。。。。。甚至比朴素贝叶斯的准确率还低吧(╯‵□′)╯︵┻━┻
不过别急,也就3棵树,深度也就5而已,让我们调大点再来试试:
改了森林中树的数量及深度,把信息增益计算的标准换成了上一篇文章着重讲的信息熵,准确率立马飙升到了95.36%
啊!对比朴素贝叶斯训练出来的模型,准确率只有85.65%
,看来随机森林不愧是最强的分类算法啊。
时间允许的话,应该多尝试不同的参数看看识别率的,理论上来讲应该会在某个概率区间收敛,但是我笔记本真的不行啊。。跑一次要十几分钟说,温度爆表cpu也占满了,最后在网上找资料看别人的设置,针对这个MNIST数据集的话,树的数量大约是29,深度大约是30,就能得到一个不错的识别率了。下面贴出我跑的结果,识别率为96.47%
,有兴趣的小伙伴可以尝试更多的参数组合,并在评论区留言给大家参考下。(PS:有随机因素的影响下,同样参数跑出来的模型也有所偏差,想要得到最完美的模型,只能多试几次随机种子)
更新!!!多试了几次之后(跑一次要20分钟QAQ),得到一个最高的识别率为96.59%
一些有待解决的问题
训练随机森林还是挺吃资源的,至少我的笔记本跑起来并不是很快。。而且第一次跑的时候还内存溢出了,只是13棵树而已,在运行参数里改大了内存分配才解决,添加运行参数-Xmn16m -Xms64m -Xmx8000m
就ok了,不过我的电脑是16G内存的,所以才分配8G左右过去,没有多尝试,不过8G至少能跑到29棵树,深度为30。
机器资源好解决,有机会放上spark集群的话应该会好很多,这方面的暂时还没条件去尝试,毕竟随机森林的这种设计,真的很适合放到分布式集群上去啊。
还有一个需要尝试的就是如何利用显卡的GPU去做运算,有机会查查资料出一期window上怎么利用GPU跑机器学习算法,TensorFlow我倒是知道怎么做,Spark应该也可以才对。
另外还有一些疑问就是,随机森林的两个随机中,样本数据的随机抽样,是不是抽出来的每一个样本都和原始数据样本是一样的,这个可以调整吗? 特征值的随机呢?每次随机抽出n个备选特诊,然后从备选特征中用几个?是否放回或重复? 或许以后的学习中会有新的知识解决我这些疑惑(大概是统计学里抽样的科学)。