这个算法的原名叫什么相信大家都清楚，不知道标题为什么变成了敏感词。
组合方法（集成方法）
两种不同的翻译，这种方法是聚集多个分类算法的预测来提高分类的准确率，组合方法由训练数据构建一组基分类器，然后通过对每个基分类器的预测进行投票来进行分类。
组合方法的类型：
常用的构建组合方法有以下几种类型：
- 通过处理训练数据集来组合方法：根据某种抽样分布对训练集进行抽样，从而得到多个训练集，用特定的算法为每个训练集建立一个分类模型。这种方式有两种常用的技术，装袋（Bagging）和提升（boosting）。
- 通过选择不同的输入特征的子集来形成训练集，随机森林（RandomForest）就是这种方式的代表。
- 处理类标签的方式，当有足够多的类数时，通过将类标签划分成两个不相交的子集，把训练集变成二元分类，之后进行分类，之后再用标记过的数据再进行一次这个步骤，重复多次就能得到一组基分类器。
- 通过多次处理学习算法的参数来得到不同的结果，在同一个训练集上执行算法可能得到不同的模型，通过多个不同模型得到一个最好的。
大概逻辑如图（手画的丑了点2333）：
组合方法对于不稳定的分类算法效果较好，所谓不稳定的分类算法就是对训练集的微小变化都很敏感的算法，包括决策树、人工神经网络等。
装袋（Bagging）
装袋是一种根据均匀分布从数据集中进行有放回的重复抽样的技术。每个自主样本集都和原数据集一样大，因为是有放回的，所以肯定会重复。这也就保证了虽然自助集和给定集一样大，但是多次抽样肯定每个自助集都不会一样，保证了随机性。
装袋的应用
以每个样本集采用一个二叉决策树为例，每个抽样都能产生不同的分类条件。
把所有的样本代入到这些抽样条件中进行分类，记二元分类为（1，-1），则可以得到根据所有二叉决策树分类的样本的加权值，根据这个值判断正负号即可得到分类。
提升（Boost）
装袋技术中的取样是均匀分布的，无论哪次抽样，分类是否正确，各个样本都有同等机会被抽取到，这样容易引起一定的偏差。
而提升技术有效的改进了这个问题，提升会给每一个训练样本一个权重，在每一轮提升过程结束时自动的调整权重。
权重作用于两个方面：
- 用作抽样分布，权重越大的样本越容易被抽到。
- 用作基分类器的比重，分类越准的基分类器权重越高，可以利用权重学习高权重样本的模型。
adaboost算法就是运用了提升技术的一种算法。
AdaBoost
该算法简要步骤如下：
- 假设现在有一组样本，则所有样本的权重相等，和为1（视作抽样概率）。
- 按照概率有放回的抽样，组成一个等长度的新样本集。
- 根据该样本集学习分类模型。
- 用该模型对原样本集所有样本进行分类。
- 根据分类结果调整样本权重，增加被错误分类的样本权重，降低正确的样本权重。
- 下一轮抽样时，有更大权重的样本更容易被抽到。
- 递归如下过程，直到迭代出合适的预测模型。
第1，2步比较常规，略过。
第三步中的模型一般采用决策树桩（decision stump），这里面的分类器一定要是弱分类器，这个是比较合适的。
决策树桩（decision stump）
就是上文提到的二叉决策树，这种树只有一个测试条件，如为，则k为条件分支，使得叶节点的熵最小的分裂点。
这样的话，可以有效地计算各个样本点的权重，对于二元分类，有一个条件即可区分两个分类，记为1，-1。
第四步中，对原样本集中样本用该决策树桩进行分类，正常来说，肯定有错的，我们可以用这个错误率来调整权重，也就是第五步。
先来看错误率的公式：
其中，表示包含N个训练样本的集合，I是函数，如果满足里面的条件
，则I的值为1，否则为0。
就是样本代入分类器的结果。
公式可能有些复杂，翻译成白话就是，用原样本集中的每一个往分类器模型中套，如果有分类和样本集中标签不一样的，I就是1，再乘上这个样本自身的权重，一样的就是0，不用算。这样算完N个样本之后加到一起，再除以N就是这个ε。
请注意，这个是调整权重的一个中间变量。
我们用这个ε可以计算出分类器的权重α，公式如下：
从这个公式中我们可以得出，首先ε<=1是肯定的（因为最多也就是所有的样本全部分类错误），那么当ε接近于0的时候，α会有一个很大的正值，而当ε接近于1的时候，α会有一个很大的负值。
也就是说，当错误率低的时候，分类器的权重大，这个分类器更加有效，而错误率高时，权重甚至可能是负的，那么在最后计算结果时，就起不到什么作用。
用这个α，我们可以进一步计算出接下来一轮抽样中，样本的权重w，假设代表在第j轮提升迭代中赋给样本
的权重，则有公式如下：
当时，
当时，
其中，是一个正规因子，用来确保
，（因为w这里代表的是样本的权重，样本要以权重为概率进行抽样，所以总体权重和肯定是1）。根据这个公式，错误分类的样本权重会增加，更容易被抽到进行下一次分类。
另外，如果任何中间迭代过程出现了高于50%的误差，则所有样本的权重将恢复为1/N，并重新进行抽样。
例子
假定有数据集如下：
| x | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| y | 1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
我们进行第一轮抽样，并进行分类，因为总共十个样本，那么权重都是1/10=0.1。
第一轮抽样分类结果可能如下（以0.75为界，小于0.75的均为-1类）：
| x | 0.1 | 0.4 | 0.5 | 0.6 | 0.6 | 0.7 | 0.7 | 0.7 | 0.8 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| y | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 |
其中可以对照发现，其中0.1，0.2，0.3都分了错误的类，我们把这几个类和权重代入公式，可以算出ε为
用epsilon来计算alpha，可以得到alpha为
接下来，用α来算下一轮各个样本的权重，对于正确的样本，有，则有3个0.176。
对于错误的0.1，0.2，0.3，有
为了保证权重之和等于1，我们要求出Z，根据公式可以得到：
这样可以求出各个样本的权重，0.1，0.2，0.3样本的权重为：
其他样本的权重为：
这样可以得到全部样本的权重，进行第二次抽样，进行三次迭代之后，结果如下：
| x | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 权重 | 0.029 | 0.029 | 0.029 | 0.228 | 0.228 | 0.228 | 0.228 | 0.009 | 0.009 | 0.009 |
每次迭代分类器的分界和权重如下：
| 轮次 | 划分点 | 左类 | 右类 | α |
|---|---|---|---|---|
| 1 | 0.75 | -1 | 1 | 1.738 |
| 2 | 0.05 | 1 | 1 | 2.7784 |
| 3 | 0.3 | 1 | -1 | 4.1198 |
由于决策树的特性，不一定大于就是1类，小于就是-1类。
用三次分类器的权重*分类的结果（无论对错）求和，就可以得到最终结果的符号，用符号来判断分类即可。
| 轮次 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 加权和 | 5.16 | 5.16 | 5.16 | -3.08 | -3.08 | -3.08 | -3.08 | 0.397 | 0.397 | 0.397 |
| 分类 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
可以看到，经过三次迭代，已经与原样本集的标签匹配。
