1.前言

本节基于视频：https://www.youtube.com/watch?v=LsK-xG1cLYA

有时候单一的模型可能效果不够好，或者我们想把多个效果还不错的模型结合起来，看看能不能获得更好的效果，于是，就诞生了集成学习。集成学习就是基于多个模型来提高整体的效果，具体根据集成的方法不同大致分为三类：

• boost
• bagging
• 随机森林（但是随机森林只是bagging的一个扩展变体，本质上还是bagging）

其中，bagging和随机森林属于一个大类：子模型之间不存在强关联性，可同时生成的并行化方法。而boost属于子模型之间存在强依赖关系，必须串行生成的序列化方法。
不论是上面的哪几个大类或者小类，他们的子模型（或者说个体学习器）都是基于决策树的。原因：

实验证明，决策树模型在集成之后效果最好，其他的模型也可以集成，但是效果并没有决策树的好

所以，你需要先了解决策树算法。
集成学习是非常强大的，各种机器学习比赛基本上都会有很多人使用它，尤其是其中的boost，各种boost：xgboost，catboost，lgbm。但是这些乍一看可能比较难看懂，所以还是先建议学习决策树，随机森林，然后去学习bagging和boost的基本原理。之后学习各种boost。当然，如果只是要用的话，还是比较简单的，几行代码就可以使用了。

本节主要介绍boost中的adaboost。

2.AdaBoost

在随机森林中，你每次建立一棵决策树，都是full size的。即，不加任何限制，任这棵树进行分支。有些树可能更大更深，但是，并没有一个预定的最大深度。

相反，在AdaBoost中，决策树通常都是很浅的，通常都只有一个根节点加两个叶节点。

像上面的这种只有一个根节点加两个叶节点的树叫做stump。所以，现在已经不叫随机森林了，而是随机树桩林（抖机灵，Forest of Stumps）。

但是，stumps并不能很准确的进行分类。毕竟那么浅，很可能欠拟合。

2.1 例子

例如，我们要拿这么一个数据来建立随机森林判断一个人是否有心脏病。

一个full sized 的决策树会利用四个属性进行划分。最后得到一个这样的决策树：

但是，stump只能使用一个属性来建立树：

所以，这样的树一看就知道效果不咋的（weak learner）。但是，AdaBoost就是喜欢这种。

随机森林中，每一棵树都有同样的投票权，但是在AdaBoost里，有的树有更多的话语权，有的更小。

在随机森林中，树与树之间是独立的，哪一棵树先生成，哪一棵树后生成是无所谓的。但是，在AdaBoost中，生成树的顺序就很重要了。第一棵树犯的错会影响第二棵树的生成，第二棵树犯的错会影响第三棵树的生成，以此类推：

总结起来，AdaBoost有三个要点：

• AdaBoost把很多weak learners联合起来，这些weak learners都是stumps
• 一些stump有更多的投票权
• 每一个stump都是基于前一个stump的错误生成的

2.2 建立一个AdaBoost的Forest of Stumps

这是我们要使用的数据：

step1：给每一个样本一个权重

一开始，我们先给每一个样本一个权重，这个权重意味着把这个样本被正确分类的重要性。最初，每个样本的权重都是一样的：1 / 样本数。这样，每个样本的重要性相同。

然而，一旦第一个stump被建立之后，样本权重（sample weight）就会改变，以此来引导下一个stunp的建立。

step2：建立第一棵stump

从样本的属性里找到最优的划分属性（第一次时sample weight都是一样的，所以不用考虑它）。这和建立决策树是一样的。
第一棵stump建立之后是这样的，选择的划分属性是weight：

然后，我们需要决定第一棵stump的投票权。投票权的决定基于这个stump的分类效果。也就是说，准确率越高，投票权就越多。
这个stump只有一个错误。

一个stump的total error是分类错误的样本权重的和。所以，第一棵stump的total error就是1/8.
注意：sample weight总和为1.所以，total error也是属于0到1的（0是完美的stump，1是最差的stump）
我们使用total error来决定stump的投票权。公式如下：

这个函数画出图像为：

横坐标是total error。纵坐标是amount of say。当一个stump的效果很好时，total error很小，所以投票权是一个很大的正数。当stump的准确率跟瞎猜一样是（0.5），投票权为0.当stump的total error很大时，接近于1，投票权就是一个很小的负值。

所以，最后投票时，这些表现差（投票权为负值）的stump相对于在投相反的票（也就是这个stump说这个人没病，那他就是有病，而且负值越小[-100<-1]，投相反票的投票权相对于越重）。

你可能会问，上面这个式子在total error为0或是1的时候，会出现问题。对，没错。所以实际中经常加一个small error的数来避免这种情况。

按照公式，我们可以计算出第一棵stump的投票权是0.97.
现在，我们已经知道了，我们根据sample weight来计算stump的投票权。接下来，就是该怎么挑战sample weight来指导下一次stump的建立了。

step3：调整sample weight

回到第一个stump，我们知道他又一个错误分类的样本：

既然如此，我们就需要在下一个stump中尽可能的把它分类正确。所以，我们需要增加它的sample weight，减小其他的样本的sample weight。
对于错误分类的样本来说，增加其weight的公式如下：

图如下：

可见，投票权越大，新的sample weight也越大。
第一个stump的投票权是0.97，所以，新的sample weight就是1/8 * e^0.97 = 0.33.(>0.125)

然后，我们需要降低其他正确分类的样本的sample weight。这是降低正确分类的样本的sample weight的公式：

这是图像：

第一个stump的投票权是0.97.所以，代入公式，可得正确分类的样本的sample weight变为：
1/8 * e^-0.97 = 0.05

之后，我们得到新的sample weight：

但是，新的weight和可能不为1（本例中为0.68）.所以，需要进行归一化。归一化很简单，每一个数除以总数就行了。

虽然可能会由于保留的位数造成结果还不为1，但是也是很接近1了。
新的数据集就是这样了：

step4：建立第二个stump

由于第二次sample weight不再相同，所以，就需要考虑它了。我们可以使用带权重的基尼指数来选择第二个stump的最优化分属性。上次被错误分类的样本在这次就会被更加重视，因为它含有最大的sample weight。

如果不使用带权重的基尼指数，我们也可以用另一种方法：
建立一个新的空的数据集（还是这些属性），然后，随机选择一个0到1的数字，如果这个数字在0到0.07之间（例子中新的sample weight是0.07），就把第一个样本加到新的数据集中，如果在0.07到0.14之间，就把第二个加到新的数据集中，以此类推：


注意，这样做肯定会有样本被重复添加到新的数据集中。当新数据集的样本个数和原来的一样时，就停止。
你会发现，那些sample weight比较大的样本，被添加到新的数据集中的可能性就越大。所以，重复选这个的概率也越大。很有可能最后的新数据集里有好几个这个样本。比如下面，之前sample weight最大的样本出现了4次：

之后，我们抛弃原来的数据集，使用新的数据集，并且，给新数据集的每一个样本同样的权重，这里一共8个样本，所以每个样本的权重还是1/8.

虽然每个样本的权重都一样，但是，这并不代表我们没更加关注那个之前被错误分类的样本。实际上，由于它出现的次数更多，所以，相对于它的权重还是很大。

step5：重复

之后，就是重复之前的操作了。寻找最优的划分属性，计算total error和投票权，更新sample weight。按照一定规则建立新的数据集，再重复。

2.3 如何使用基于AdaBoost建立的forest of stumps进行分类

还是一样的投票，只不过之前是统计票数，现在是对投票权求和。

比如，一个新的样本进来。我们在每一个stump上对它进行测试，一些stump说他是positive，一些说是negative。

我们把那些说positive的stump的投票权加起来，把说negative的投票权加起来，谁大就说谁是对的。

3.Warning of Math

待更新