数据挖掘-提升算法-AdBoost算法

作者: 花讽院_和狆 | 来源:发表于2020-03-20 22:08 被阅读0次

这个算法的原名叫什么相信大家都清楚，不知道标题为什么变成了敏感词。

组合方法（集成方法）

两种不同的翻译，这种方法是聚集多个分类算法的预测来提高分类的准确率，组合方法由训练数据构建一组基分类器，然后通过对每个基分类器的预测进行投票来进行分类。

组合方法的类型：

常用的构建组合方法有以下几种类型：

通过处理训练数据集来组合方法：根据某种抽样分布对训练集进行抽样，从而得到多个训练集，用特定的算法为每个训练集建立一个分类模型。这种方式有两种常用的技术，装袋（Bagging）和提升（boosting）。
通过选择不同的输入特征的子集来形成训练集，随机森林（RandomForest）就是这种方式的代表。
处理类标签的方式，当有足够多的类数时，通过将类标签划分成两个不相交的子集，把训练集变成二元分类，之后进行分类，之后再用标记过的数据再进行一次这个步骤，重复多次就能得到一组基分类器。
通过多次处理学习算法的参数来得到不同的结果，在同一个训练集上执行算法可能得到不同的模型，通过多个不同模型得到一个最好的。

大概逻辑如图（手画的丑了点2333）：

组合方法

组合方法对于不稳定的分类算法效果较好，所谓不稳定的分类算法就是对训练集的微小变化都很敏感的算法，包括决策树、人工神经网络等。

装袋（Bagging）

装袋是一种根据均匀分布从数据集中进行有放回的重复抽样的技术。每个自主样本集都和原数据集一样大，因为是有放回的，所以肯定会重复。这也就保证了虽然自助集和给定集一样大，但是多次抽样肯定每个自助集都不会一样，保证了随机性。

装袋的应用

以每个样本集采用一个二叉决策树为例，每个抽样都能产生不同的分类条件。
把所有的样本代入到这些抽样条件中进行分类，记二元分类为（1，-1），则可以得到根据所有二叉决策树分类的样本的加权值，根据这个值判断正负号即可得到分类。

提升（Boost）

装袋技术中的取样是均匀分布的，无论哪次抽样，分类是否正确，各个样本都有同等机会被抽取到，这样容易引起一定的偏差。
而提升技术有效的改进了这个问题，提升会给每一个训练样本一个权重，在每一轮提升过程结束时自动的调整权重。
权重作用于两个方面：

用作抽样分布，权重越大的样本越容易被抽到。

用作基分类器的比重，分类越准的基分类器权重越高，可以利用权重学习高权重样本的模型。

adaboost算法就是运用了提升技术的一种算法。

AdaBoost

该算法简要步骤如下：

假设现在有一组样本，则所有样本的权重相等，和为1（视作抽样概率）。
按照概率有放回的抽样，组成一个等长度的新样本集。
根据该样本集学习分类模型。
用该模型对原样本集所有样本进行分类。
根据分类结果调整样本权重，增加被错误分类的样本权重，降低正确的样本权重。
下一轮抽样时，有更大权重的样本更容易被抽到。
递归如下过程，直到迭代出合适的预测模型。

第1，2步比较常规，略过。
第三步中的模型一般采用决策树桩（decision stump），这里面的分类器一定要是弱分类器，这个是比较合适的。

决策树桩（decision stump）

就是上文提到的二叉决策树，这种树只有一个测试条件，如为 $x<=k$ ，则k为条件分支，使得叶节点的熵最小的分裂点。

decision stump

这样的话，可以有效地计算各个样本点的权重，对于二元分类，有一个条件即可区分两个分类，记为1，-1。

第四步中，对原样本集中样本用该决策树桩进行分类，正常来说，肯定有错的，我们可以用这个错误率来调整权重，也就是第五步。
先来看错误率的公式： $ε = \frac{1}{{N}}[\sum^N_{j=1}w_jI(C(x_j)\not=y_j)]$
其中， $[{(x_j,y_j)|j = 1,2,……,N}]$ 表示包含N个训练样本的集合，I是函数，如果满足里面的条件 $C(x_j)\not=y_j$ ，则I的值为1，否则为0。 $C(x)$ 就是样本代入分类器的结果。
公式可能有些复杂，翻译成白话就是，用原样本集中的每一个往分类器模型中套，如果有分类和样本集中标签不一样的，I就是1，再乘上这个样本自身的权重，一样的就是0，不用算。这样算完N个样本之后加到一起，再除以N就是这个ε。
请注意，这个 $ε$ 是调整权重的一个中间变量。

我们用这个ε可以计算出分类器的权重α，公式如下：
$α_i = \frac{1}{2}ln[\frac{{1-\epsilon_i}}{{\epsilon_i}}]$
从这个公式中我们可以得出，首先ε<=1是肯定的（因为最多也就是所有的样本全部分类错误），那么当ε接近于0的时候，α会有一个很大的正值，而当ε接近于1的时候，α会有一个很大的负值。
也就是说，当错误率低的时候，分类器的权重大，这个分类器更加有效，而错误率高时，权重甚至可能是负的，那么在最后计算结果时，就起不到什么作用。

用这个α，我们可以进一步计算出接下来一轮抽样中，样本的权重w，假设 $w_i^{(j)}$ 代表在第j轮提升迭代中赋给样本 $(x_i,y_i)$ 的权重，则有公式如下：
当 $C_j(x_i) = y_i$ 时， $w_i^{(j+1)} = \frac{w_i^{(j)}}{Z_j}e^{{-\alpha_j}}$
当 $C_j(x_i) \not= y_i$ 时， $w_i^{(j+1)} = \frac{w_i^{(j)}}{Z_j}e^{{\alpha_j}}$

其中， $Z$ 是一个正规因子，用来确保 $\sum_iw_i^{(j+1)}=1$ ，（因为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都分了错误的类，我们把这几个类和权重代入公式，可以算出ε为 $\frac{0.1*1+0.1*1+0.1*1}{10} = 0.03$
用epsilon来计算alpha，可以得到alpha为 $\alpha = \frac{1}{2}ln[\frac{1-0.03}{0.03}] = 1.738$
接下来，用α来算下一轮各个样本的权重，对于正确的样本，有 $e^{-1.738} = 0.176$ ，则有3个0.176。
对于错误的0.1，0.2，0.3，有 $e^{1.738} = 5.686$
为了保证权重之和等于1，我们要求出Z，根据公式可以得到： $\frac{{0.1*7*0.176 + 0.1*3*5.686}}{Z} = 1$
$Z = 1.829$