机器学习三人行-千变万化的组合算法

本文我们在决策树的基础上，更进一步的讨论由常用机器学习算法进行组合的集成算法，对集成算法最直接的理解就是三个臭皮匠赛过诸葛亮，通常我们已经建立了一些预测效果较好的算法之后，如果想要得到更好的预测效果，一种思路就是将这些算法组成起来来获取更好的预测效果。在很多的机器学习算法竞赛中，获胜者的方案通常就是将一些效果较好的算法通过集成算法的方式组成起来而获胜的，最著名的当属2006年美国Netflix prize竞赛，获胜方通过融合了107种算法最终获得百万美元的奖金。本文将讨论最常用的几种集成算法:

投票分类器

Bagging和Pasting

Boosting

Stacking

(文末附代码下载关键字，公众号回复即可下载)

一、投票分类器

假如你已经用逻辑回归，支持向量机，随机森林，k近邻，或更多其他的算法训练了一些分类器，每一个能够达到80%的准确率，如下图：

如果想再提高分类器的准确率，那么一个较好的方法是将这些分类器算法的预测结果收集起来，通过投票的方式来预测，票数最高的为我们最终的预测结果，这种少数服从多数的投票方式获取的集成算法叫做硬投票分类器。

如下图：

这种集成的方式往往能够获得比单个分类器中最佳分类器更高的预测准确率。这种方法对一些弱分类器（即预测效果只比随机猜测好一点）的组合之后，也能获得一个强分类器。因为很多的弱分类器，组合之后能够获取这些弱分类的多样性，使分类时能够全面的比较不同类别之间的差异。因此在选择这些分类器时，分类器相关性不能太强，最好能够保持独立，否则看的视角都一样的话，组合之后提升效果非常有限。下面的让我们来试试这种方法来组合我们的算法。还是选用系列七中的月牙形数据。

让我们来看一下，不同分类器之间准确率的比较：

可以发现通过投票组成的算法，比任何单个算法的效果都要好。

另外，如果所有的分类器能够输出分类的预测概率的话（即，分类器有predict_proba()方法），通过对所有分类器的预测概率求平均，这种方法组合方法叫软投票分类器。软投票分类器能够获取比硬投票分类器更好的分类效果，因为通过预测概率的方式合并，间接的给高预测概率的分类器一个更高的权重，而不是简单的一视同仁。实现软投票分类器的方法，只需要将代码中VotingClassifier分类器的voting参数改成“soft”，和保证所有分类器能够输出分类预测的概率。具体代码公众号回复文末关键字即可查看。通过软投票分类器组成之后的算法，能够获得91%的准确率。

二、Bagging和Pasting

另一种组合算法的方式，和前面的组合方法获得不同算法的多样性不同，是通过Bagging或者Pasting从原训练集中多次随机采样出不同的数据子集，在不同的子集中使用相同的算法构建。Bagging和Pasting统计学上的概念，Bagging是一种有放回的采样方式，Pasting是一种无放回的采样方式。构建方式如下图：

一旦所有预测器训练完成，预测时，组合所有预测器的结果来输出最终的预测结果。对于分类器来说，最常用的组合方法是硬投票方式，而回归是通过取平均的方式。另外通过上图，我们可以发现，通过Bagging或Pasting的方式组合，在训练和预测时，都能很好的支持并行的完成。在不同的CPU核或不同服务器上训练不同的子分类器，这也就是为什么Bagging和Pasting这么流行的原因之一。下面来看一下实现代码：

上面BaggingClassifier参数的解释如下：

n_estimators：基学习器的数量

max_samples：每个基学习器中的样本数，如果是整形，则就是样本个数；如果是float，则是样本个数占所有训练集样本个数的比例

bootstrap ：是否采用有放回抽样(bagging)，为True表示采用，否则为pasting。默认为True

n_jobs：指定并行运行时CPU核的数量。-1时，个数为处理器核的个数

另外，如果基学习器中包含预测概率predict_proba()的方法，BaggingClassifier会自动的选择效果更好的软投票分类器。下面我们来比较一下，单个决策树和组合决策树训练之后的差别：

相比较而言，组合决策树拥有比单个决策树更好的泛化能力，即组合决策树和单个决策树，虽然拥有相同的bias偏差，但是组合决策树拥有更小的variance方差，这也就导致了虽然在训练集上，两者拥有差不多的预测准确率，但是在测试集上，却有着较大的差别，其根本原因就是Bagging和Pasting在训练时，加入了随机性。

而对于Bagging和Pasting两者，虽然都是通过在不同训练子集中训练学习器来增加学习器的多样性来能提升单个基分类器的预测效果，但是两种组合方法还是有差别的，由于Bagging训练时，是有放回的采样，使得部分训练集始终都没有用到，因此想比较Pasting而言，Bagging拥有更高的bias偏差。但是也是由于有放回的采样，能够保证在不同子集中训练出来的模型拥有更少的相关性，从而降低模型的variance方差。通常来说，通过Bagging组合出来的模型拥有更好的更好的效果，这也是为什么Bagging方式更加流行的原因。

2.1、Out-of-Bag评估

在上面的bagging方法中，一些实例可能会被采样多次用于建模，而其他的可能一次都没有被采样到。通常来说，通过Bagging的方式采样，大约只会用到全部样本的63.2%，剩下的36.8%一次都没有被用到（为什么是63.2%，读者可以推导一下）。由于36.8%一次都没被用到，因此我们可将这部分样本再次利用起来，用于评估模型，而不用再从样本中分出验证样本或交叉验证了。在sklean中，可以通过设置参数oob_score=True，在训练完模型后，BaggingClassifier能够自动完成Out-of-Bag评估，下面来展示这种用法。

我们通过测试集来验证一下：

可以发现两者比较的接近，因此Out-of-Bag评估是可信的。

2.2、Random Patches

BaggingClassifier除了能对样本采样外，还支持对特征的采样来训练。是通过max_features和bootstrap_features两个超参数来控制的。实现方式和前面的对样本采样的max_samples和boostrap是一样的。这种方式在处理高维特征输入时（例如，图像），非常的有用。当然除了对特征采样之外，我们还可以对数据采用和特征采用进行搭配使用，即对数据和特征同时采用等方式，这些都可用通过对bootstrap,max_samples和bootstrap_features，max_features调整来实现。

2.3、随机森林

Bagging方法中，使用最广的当属随机森林了，它是一种对决策树进行组合的算法。对随机森林的原理就不讨论了，读者可以查看公众号之前的文章：

2.4 特征重要性

从构建单棵树来看，越重要的特征似乎越靠近根节点，而不那么重要的特征往往靠近叶子节点位置，或者根本不出现，这是因为我们构建树的，使用gini或者信息增益选择最佳分支，其实已经做了一次特征选择，因此随机森林能够计算出特征的重要性，方法是通过计算特征在所有的树中的平均深度。调用sklearn中的随机森林方法，会在每次训练完成后，自动计算出每个特征的重要性，我们能通过feature_importances_变量来获取，下面通过一个例子来查看。

三、Boosting

Boosting算法是一种把若干个分类器整合为一个分类器的方法，它的思想是，有次序的训练不同的分类器，每次训练的分类器都重点关注上一个分类器中分类错误的样本，并尝试纠正。目前有很多的boosting算法，而使用最多当属adboost和Gradient Boosting了。

这里给出一个简单的实例：

下面来讨论一下Gradient Boosting，和前面一样也是多个分类器，每次尝试修改上个分类器分类错误的样本，但是和adboost不同，不是通过每次改变实例的权重的方式，而是对前一个分类器分类之后的残差学习出一个新的分类器，如果使用决策树作为基学习器，就是常见的GBDT，

或GBRT，我们通过用一个带有噪声的二次方数据作为训练集，构建实例来看一些GBDT的原理：

首先，在训练集上构建一颗决策树：

接下来，在第一棵决策树的残差基础上训练第二棵决策树，

再在第二棵决策树的残差基础上训练第三棵树，

接下来可以组合这三棵决策树的结果，用来做预测了。

下图展示了训练过程：

左图是构建的三棵决策树，右图组合之后的算法。

当然我们有更加简单的构建方法，sklearn中提供了GradientBoostingRegressor算法，算法既包含了决策树的超参数，如，max_depth,min_samples_leaf等，也有组合算法的参数，如控制决策树数量参数n_estimators，下面是直接的调用。

超参数learnging_rate是限制每棵树的贡献度，如果设置很低的话，比如0.1，那么需要设置更多的树来训练数据集，不过也因此可以获得更好的泛化能力，这是一种正则化技术被称为shrinkage,可以通过下图比较两者差别。

左图中没有足够的树，无法学习完全，因此出现欠拟合，而右边的树太多，出现了一些明显的过拟合，因此为了找到最优的树数量，我们可以使用系列五中的early stopping方法，在sklearn中只需要使用staged_predicted方法就可以实现，staged_predicted会返回一个迭代器，是组合算法在训练中每个阶段用到的树，通过计算每个阶段中，预测的验证误差来找到最优的决策树的数量，最终使用最优数量的决策树构建最终的组合算法。

可以图看出整个变化，和最终最优模型的训练效果：

但是我们在优化的时候往往树的数量很多，如果每次优化都需要全部训练一遍才能得到我们最优的结果的话，那似乎也就不能叫做early stopping了。因此我们希望一旦达到最优的决策树数量就停止训练，我们可以通过设置warm_start=True来实现，代码如下：

也就是说，如果在连续五次的训练都不能降低验证误差的话，就停止训练。

四、stacking

最后一种组合算法叫stacking，和最开始提到的投票分类器有点相同，不过这里讲多个算法的合并不是通过简单的投票，而是对多个模型预测结果再次构建模型。下图使用stacking组合的一个简单的模型在预测阶段的工作方式。

从上图可以发现，最底下的三个预测器预测了三个不同的值（3.1,2.7,2.9），然后最终的预测器（或叫元学习器）将三个不同的预测值作为输入，来做最终的预测(3.0)。

构建一个stacking算法，常用的方式是使用留一法，首先，将数据集分成两个子训练集，第一个用于训练第一层的模型。

接下来，用第一层的模型去对第二个子训练集做预测，这样可以保证训练不出来的模型不受污染，因此模型在训练阶段没有看到过第二个子训练集。现在第二个子训练集中每个实例都有三个预测值了，我们可以用这些预测值来构建一个新的训练集作为输入了，另外新的训练集还需要加上目标值。stacking模型在这个新的训练集上训练。

实际上，我们可以在第二层新的数据集上训练时，使用不同的算法模型，来得到多个不同的stacking模型，然后第多个stacking再次组合。构建这样多层的stacking模型，需要将数据划分成三个不同子训练集，第一个用于构建第一层的基础模型，第二个用基础模型对做预测，构建新的训练集用于训练多个stacking，第三个用多个stacking模型来做预测，将预测值构建最后的训练集，用最后的训练集训练出最终的模型，整个过程如下：

目前，sklearn并没有stacking组合方法的实现，但是实现起来并不难，该方法在很多机器学习竞赛非常的常见，而且工业界也已经在开始使用，目前github有一些开源的实现，像brew(github.com/viisar/brew)。

五、总结

本文主要讨论目前机器学习算法中常用的三种集成算法，bagging，boosting和stacking。已经讨论了bagging的用法和bagging最流行随机森林，和通过实例解释了boosting中Gradient boosting的构建过程，最后讨论了stacking的实现方法。

（如需更好的了解相关知识，欢迎加入智能算法社区，在“智能算法”公众号发送“社区”，即可加入算法微信群和QQ群）

本文代码回复关键字：ensemble code