0 引言

Boosting算法^[1]是基于可能近似正确(Probably Approximately Correct, PAC)可学习性模型而提出的一种经典集成算法。由于Boosting算法存在缺陷，很难应用于实际问题，针对此问题Freund等^[2]1995年提出了AdaBoost(Adaptive Boosting)算法。AdaBoost算法是最常用的一种Boosting算法的变形，更加面向实际，可以有效提升弱分类器的性能。

传统的AdaBoost算法只能解决二分类问题，然而在实际应用中要处理的问题经常是多分类问题。基于此, 需要把AdaBoost算法扩展为多分类算法，现有的扩展方法可以分为两种：一种直接把AdaBoost算法扩展为多分类算法，另一种使用多个二分类算法去解决多分类问题。传统的多分类AdaBoost算法主要有AdaBoost.M1^[3]、AdaBoost.M2^[3]和AdaBoost.MH^[4]。AdaBoost.M1是一种直接由AdaBoost算法扩展而成的多分类算法，这种扩展比较容易，但是它对基分类器的要求过高，它要求基分类器的分类正确率大于1/2，这对于多类的弱分类器而言是比较难以达到的条件，基分类器的获取变得困难，可能导致基分类器数目不足，无法集成出足够好的强分类器。AdaBoost.M2是在AdaBoost.M1的基础上提出的一种多分类算法，它在算法中使用伪损失来代替错误率作为选取基分类器的标准。它对基分类器的要求有所降低，只需要伪损失比1/2略高，而且由于使用伪损失使算法不仅关注错分样本同时关注难分样本。但是伪损失的计算比较复杂，算法的时间复杂度较高，同时由于使用伪损失造成的退化现象可能更为严重。AdaBoost.MH是一种典型的把多类问题转换为二类问题处理的算法，由于多类问题转变成了二类问题，基分类的获取变得相对容易，但是算法的复杂度却大大增加，尤其是在类别数较大时增加得更为明显。

传统的多分类AdaBoost算法存在时间复杂度高和获取基分类器困难的问题。针对这些缺点，文献[5]提出了一种改进的从两类直接扩展为多类的AdaBoost算法——多类指数损失函数逐步添加模型(Stagewise Additive Modeling using a Multi-class Exponential loss function, SAMME)，通过扩展算法的指数损失函数把对基分类器正确率的要求降低到1/K(K为类别数)这就使得基分类的获取变得相对容易。文献[6]对此算法进行了证明，并把它应用于航空发动机故障诊断之中。文献[7]指出SAMME算法对基分类器的要求过低，容易使算法陷入退化。针对此问题，杨新武等^[7]提出了一种基于弱分类器调整的SAMME.R算法，并且达到了不弱于AdaBoost.M1的效果。

AdaBoost算法已经广泛应用于人脸识别^[8-10]、目标检测^[11]和网络异常检测^[12]之中。SAMME算法解决了由二类算法扩展而来的多类算法所存在的问题，使AdaBoost算法处理多类问题更加方便。为进一步提升SAMME算法的性能，本文研究了使用加权错误率和伪损失对算法性能的影响，并且提出了一种改进的多分类算法——SAMME.RD(SAMME with Resampling and Dynamic weighting)。首先确定是否使用加权的错误率和伪损失，之后判断是否需要求出待测样本在测试集中的有效邻域，不需要则直接输出分类结果，若需要则求出有效邻域，并使用基分类器对有效邻域进行分类，由此得出基分类器的加权系数，最后求出待测样本的分类结果。实验结果表明，本文提出的算法相比SAMME和SAMME.R算法，分类性能有所提高。

1 SAMME和SAMME.R

对于多类问题，要获取分类正确率大于1/2的基分类器比较困难，针对此问题SAMME算法改变了传统的AdaBoost算法的权值分配策略，令α_t=ln(ε_t/(1－ε_t))+ln(k－1) 来降低对基分类器分类正确率的要求。文献[5]使用统计学的观点证明了α_t的合理性，但文献[7]指出，SAMME算法对基分类器的要求过低可能会导致强分类器分类结果偏向于分类正确率较大的错误类，为此文献[7]提出了一种基于弱分类器调整的SAMME.R算法。

1.1 SAMME

SAMME算法通过扩展指数损失函数直接把二类的AdaBoost算法扩展为多类，使分类器的要求得到降低，它的合理性也从统计学方面得到了证明。SAMME算法的流程与传统的AdaBoost算法相似，具体如下：

步骤1  初始化权值:

$ w_i^1 = 1/m;\;\;i = 1, 2, ..., m $

步骤2  对于t=1, 2, …, T，执行以下1)~6) 步：

1) 依据权值w^t，选择训练样本。

2) 对样本进行分类识别h_t:X→Y。

3) 计算h_t的伪错误率：

$ {\xi _t} = \sum\limits_{i = 1}^m {w_i^t} \left[{{h_t}\left( {{x_i}} \right) \ne {y_i}} \right] $

4) 置α_t=ln(ξ_t/(1－ξ_t))+ln(k－1)。

5) 计算新的样本权重：

$ w_i^{t + 1} = w_i^t \cdot \exp \left( {{\alpha _t} \cdot \left[{{h_t}\left( {{x_i}} \right) \ne {y_i}} \right]} \right) $

6) 归一化w^t+1。

步骤3  最终强分类器为：

$ {h_f}\left( x \right) = \mathop {\arg \;\max }\limits_{y \in Y} \sum\limits_{t = 1}^T {{\alpha _t} \cdot \left[{{h_t}\left( {{x_t}} \right) = {y_i}} \right]} $

1.2 SAMME.R

SAMME.R是在SAMME的基础上改进而来的，该算法为了解决SAMME算法对基分类器要求过弱的问题，对每次迭代训练出的弱分类器进行检验，判断分类器对于数据分到正确类的概率是否大于分到其他任意错误类的概率，如果满足该条件则保留该基分类器，否则重新训练新的基分类器。SAMME.R算法的主要改进在于通过筛选基分类器保证算法训练出的强分类器可以分类正确。

SAMME.R算法的主要改进就是在步骤2的2)~3) 之间加入了如下的筛选：

a)循环计算各类中，分到各类样本的权值和：

对于j =1, 2, …, K，有：

$ {\gamma _{tkj}} = \sum\limits_{i = 1}^m {w_i^t} \left[{{y_i} = k, {h_t}\left( {{x_i}} \right) = j} \right] $

b)判断各类中分类正确的样本权值和是否大于等于分到其他各类的样本的权值和：

$ {\gamma _{tkj}}\left[{{h_t}\left( {{x_i}} \right) = j} \right] \geqslant \forall {\gamma _{tkj}}\left[{{h_t}\left( {{x_i}} \right) \ne j} \right] $

若满足，则进行下一步骤；若不满足，则返回步骤2。

2 改进的SAMME算法 2.1 错误率和伪错误率对算法影响

文献[13]指出在AdaBoost算法进行权值更新和基分类器加权系数计算时使用真实错误率比加权错误率效果更好，虽然伪错误率在考虑分类是否正确的同时考虑了样本的难分程度，但是随着迭代次数的增加，难分样本权重过大，会出现加权错误率较小而真实错误率较大的基分类器，在最后的加权融合中由于加权错误率较小而权值较大，导致算法出现退化的现象，所以本文对SAMME和SAMME.R算法作出改进，在算法中使用真实的错误率，改进后的SAMME命名为SAMME.RE，改进后的SAMME.R命名为SAMME.RRE。

文献[7]在分析中指出SAMME算法对基分类器的要求过低，给出了进一步的要求，并从直观上和理论上证明了所提要求的合理性。SAMME.R算法指出要循环计算各类中分到每类样本的权值和，并且要求分到正确类的权值和大于分到任意错误类的权值和。文献[7]在进行直观和理论证明时指出，基分类器对每类数据分类时要求分到正确类的概率要大于分到任意错误类的概率，而在SAMME.R中要求分到正确类的权值和大于分到任意错误类的权值和，降低了算法的要求。随着迭代次数的增加，部分难分数据的权值迅速增加，如果只要求分类正确的权值大于分到其他任意类的权值，可能分类器的真实正确率还达不到大于随机的要求，这就会导致随着迭代次数的增加，强分类器陷入退化的现象。但是如果要求分到正确类的概率大于分到其他任意类的概率又会导致对基分类器要求较高，对于有些分布不平衡的数据难以获取足够的基分类器。从直观上可以看出，在数据类别较少、数据分布较平衡时，基分类器获取比较容易，使用真实的概率对基分类器进行筛选效果更好，在数据类别较多、数据分布不平衡时，基分类器获取比较困难，使用加权和对基分类器进行筛选或不筛选效果更好。为了能够更好地使用SAMME.R算法，本文针对使用加权概率或真实概率对算法的影响进行实验研究。把使用真实概率进行基分类器筛选的算法命名为SAMME.R1，在SAMME.R1的基础上又使用真实分类错误率的算法命名为SAMME.R2。

2.2 动态加权SAMME.R算法

动态集成方法根据目标样本的特征和识别性能，动态地组合基分类器或调整基分类器权重^[14]。根据动态集成方法在作出预测时的选择和加权方式，可以把动态集成方法分为动态选择、动态投票和动态选择与动态投票混合使用的三种类型。动态集成方法可以有效地提高集成分类的性能，为进一步提升SAMME.R算法的分类性能，本节在2.1节的基础之上，提出一种动态投票的改进SAMME.R算法，改变SAMME.R预测时的加权方式。传统的AdaBoost算法对待测样本进行预测时各个分类器的加权系数是固定不变的，但是通过分析可以知道基分类器对不同的待测样本的分类能力是不一样的，这是因为基分类器使用不同的训练集训练而来，它们对分布在不同区域的样本分类能力是不一样的。如果在预测时使用相同的加权系数，预测结果的准确性将会受到一定的影响，所以为了进一步提升算法的预测性能，本文提出一种动态加权投票的改进SAMME.R算法SAMME.RD。

改进算法主要包括以下两个方面：1) 对基分类器的分类结果进行统计，统计分到各类的基分类器个数，如果分到某类的个数与基分类器总数的比值大于一个设定的阈值α，则直接输出此类作为待测样本的类别。2) 对于分到各类的数目没有大于设定阈值α的情况，求出待测样本在训练样本中的有效邻域，统计基分类器对有效邻域中的样本的分类能力，根据基分类器对有效邻域分类正确率的大小来确定基分类器的加权系数。

假设有T个基分类器分别为h_t(t=1, 2, …, T)，有M个类别分别为c_i(i=1, 2, …, M)，h_t对待测样本x的输出为h_t(x)。

定义1  定义MC(x)={h₁(x), h₂(x), …, h_T(x)}为T个基分类器对待测样本x的分类行为。

设定阈值α(0 < α≤1)，如果向量MC中有多于T*α个基分类器分到同一个类别，那么直接把这一类别作为待测样本x的分类结果输出，否则求出样本x的有效邻域进行下一步的判断。

待测样本的邻域指的是在空间上与之邻近的部分样本，在这部分样本中有一些样本与待测样本的分类相似度较低，我们认定此类样本为无效的邻域样本对其进行剔除，剔除无效邻域样本后剩余的邻域样本称之为有效邻域。为了描述样本之间的相似程度，在定义2中定义相似度。

定义2  样本x和y之间的相似度定义为$S\left( {x, y} \right) = \frac{1}{T}\sum\limits_{t = 1}^T {{Q_t}\left( {x, y} \right)} $，其中：

$ {Q_t}\left( {x, y} \right) = \left\{ \begin{gathered} 1, \;\;\;\;\;{h_t}\left( x \right) = {h_t}\left( y \right) \hfill \\ 0, \;\;\;\;{h_t}\left( x \right) \ne {h_t}\left( y \right) \hfill \\ \end{gathered} \right. $

由定义2可知0≤S(x, y)≤1，在选取待测样本x的有效邻域时，设定阈值β，如果S(x, y)≥β则认定y为有效的邻域样本，否则认定为无效样本进行剔除。

在获得待测样本的有效邻域后，计算每个基分类器对有效邻域中的样本的分类错误率ε_t(t=1, 2, …, T)，定义基分类器的权值w_dy(t)=lb((1－ε_t)/ε_t)。

改进算法的具体流程如下：

1) 根据2.1节中的AdaBoost算法训练生成基分类器。

2) 输入待测样本x, 计算待测样本的MC值。

3) 计算向量MC中分到某类的基分类器数目与总的基分类器数目的比值是否大于设定阈值α。如果大于阈值α则直接输出对应的类别，算法结束；否则，继续下一步骤。

4) 设定相似度的阈值β，计算待测样本x的有效邻域。

5) 统计基分类器对有效邻域样本的分类效果，为基分类器赋权值w_dy(t)=lb((1－ε_t)/ε_t)，其中ε_t为第t个基分类器的分类错误率。

SAMME.RD算法是一种改变基分类器加权方式的动态加权多分类AdaBoost算法，它对如何训练基分类器没有要求，所以SAMME.RD算法的思想可以通用，把针对SAMME.RRE的改进命名为SAMME.RD1，针对SAMME.R2的改进命名为SAMME.RD2。SAMME.RD算法需要对测试样本在基分类器下的分类情况进行统计，依据分类结果把样本分类分为两种方式：一种直接输出类别；另一种求出待测样本在训练集中的有效邻域，对有效邻域中样本在基分类器下的分类情况进行统计，计算出基分类器的加权系数。由于SAMME.RD算法需要对待测样本的分类结果进行统计，对部分样本求有效邻域并对有效邻域样本分类结果进行统计提高了SAMME.R算法的时间复杂度。提升待测样本有效邻域的求解效率是解决SAMME.RD算法时间复杂度高的关键，还需要进一步研究。

3 实验结果与分析 3.1 实验数据

本次实验所使用的数据均为UCI数据集中的多类数据集，在实验中采用三折交叉验证的方法来获取训练数据和测试数据，数据集的详细情况如表 1所示。

3.2 实验设计

实验通过对比SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1、SAMME.R2、SAMME.RD1和SAMME.RD2这8种算法的分类结果来验证SAMME.RD算法的性能以及使用真实错误率的有效性，并总结出使用加权概率和真实概率进行基分类器筛选的前提。

实验中8种算法所使用的弱分类算法均为决策树，为了实验结果的准确性，本文对每次实验均进行10次三折交叉验证，最后取这10次三折交叉验证的均值作为此次实验的最终结果。实验中为验证几种算法的分类性能随迭代次数增加的变化情况分别取迭代次数为10、20、30、40和50来对比8种算法的分类结果。为了对比算法的分类效率，统计迭代次数为50时算法对实验数据的分类时间。

3.3 结果分析

本次实验得出8种算法对12种UCI数据集的分类结果，如表 2所示，表中的C1~C8分别表示SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1、SAMME.R2、SAMME.RD1和SAMME.RD2这8种算法，每种算法在相应数据集上根据迭代次数的不同获得不同的分类正确率。

首先对比表 2中SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2这6种算法的分类情况，之后对比表 2中SAMME.RRE与SAMME.RD1两种算法的分类结果以及SAMME.R2与SAMME.RD2两种算法的分类结果。在迭代次数相同的情况下对比算法的分类结果可以发现，在迭代次数较少时经常会出现SAMME算法分类结果优于其他几种算法的情况。但是随着迭代次数的增加，SAMME算法分类正确率急剧下降，很快地陷入退化。SAMME.R算法虽然在一定程度上解决了SAMME算法的退化问题但是效果也不太好；其他几种算法分类效果逐渐变优，退化现象发生缓慢，而且退化较弱整体趋于平衡。从分类结果可以看出SAMME.R算法并不是在所有情况下都优于SAMME算法，在数据分类正确率较低、基分类器获取较难时，SAMME算法的分类效果优于SAMME.R，例如在yeast和soybean数据集上。对比SAMME和SAMME.RE、SAMME.R和SAMME.RRE、SAMME.R1和SAMME.R2的分类结果可以看出，在算法中使用真实错误率计算基分类器的加权系数是有效的，避免了算法严重退化现象的发生，但是同时也存在算法正确率提升速度较慢的缺点。对比SAMME.R与SAMME.R2、SAMME.RE与SAMME.RRE和SAMME.R2的分类结果可以看出：在分类正确率较低、数据类别较多且分布不平衡时使用加权概率筛选比真实概率效果好；在分类正确率较高、数据类别较少、分布平衡时使用真实概率筛选比加权概率效果好。对比SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2这6种算法分类结果随迭代次数增加的变化情况：随着迭代次数的增加SAMME算法很快陷入退化之中；SAMME.R算法达到的效果在大部分数据集上优于SAMME，而且陷入退化也较慢；其他几种算法的分类正确率随迭代次数增加稳步上升，达到最大值后基本趋于稳定

接下来对比SAMME.RRE与SAMME.RD1、SAMME.R2与SAMME.RD2，从实验结果可以看出：在大部分数据集上SAMME.RD1与SAMME.RD2的分类正确率优于SAMME.RRE与SAMME.R2，但是在vowel和zoo数据集上却比SAMME.RRE与SAMME.R2差。实验结果验证了本文所提出的动态加权SAMME.RD算法的有效性，但是算法的适用范围还需要进一步研究。在研究算法分类正确率的同时，本文对算法的分类效率也进行了研究。通过对算法的分析可以知道SAMME和SAMME.RE分类时间大致相同，SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2这4种算法的分类时间大致相同，SAMME.RD1和SAMME.RD2分类时间大致相同。为了分析算法的效率，给出迭代次数为50的情况下SAMME、SAMME.R和SAMME.RD1对实验数据的分类时间，如表 3所示。

从表 3的结果可以看出, SAMME和SAMME.R两种算法时间复杂度大致相同，SAMME.R算法略高；SAMME.RD与SAMME和SAMME.R两种算法相比，时间复杂度较高，在数据量较少时，分类时间是SAMME和SAMME.R两种算法的5~10倍，随着数据量的增多，算法的时间迅速增长至SAMME和SAMME.R的几十甚至上百倍，SAMME.RD算法变得不可用。SAMME.RD算法能够有效提升SAMME算法的分类正确率，但在效率上存在时间复杂度高的问题，SAMME.RD算法的时间复杂度主要源于求解待测样本的有效邻域，如何减少求解待测样本有效邻域的时间是降低算法时间复杂度的关键。

4 结语

本文分析了SAMME算法及其改进算法SAMME.R，并针对SAMME和SAMME.R算法使用伪错误率和加权概率对算法性能的影响进行了讨论。得出了使用真实错误率要优于伪损失的结论以及加权概率和真实概率的适用前提。在此研究基础上，本文提出了一种动态加权的SAMME.RD算法。通过实验验证了SAMME.RD算法对分类器性能提升的有效性，但是SAMME.RD算法仍然存在时间复杂度高的问题，如何降低算法的时间复杂度是下一步研究的主要方向。