集成学习是模式识别和机器学习领域研究的热点问题^[1-2]，它能够显著提高学习系统的准确性及泛化性能，因此受到了越来越多的关注. 在众多集成学习方法中，AdaBoost因具有实现简单、适应性强的优势成为当前主流算法之一. AdaBoost是由Freund和Schapire提出的用于二分类问题的集成分类方法^[3]. 该算法根据弱分类器的分类效果自适应地改变训练样本权重，通过关注被弱分类器错分的样本获得新的分类器，从而将弱分类器提升为强学习器. AdaBoost.M1^[4]、AdaBoost.M2^[4]与AdaBoost.MH^[5]等算法在AdaBoost基础上实现多分类问题求解. Zhu等^[6]提出新的适用于多分类问题的方法SAMME. 该算法降低了弱分类器正确率的要求，因此无法有效提升最终强分类器的准确率. 在此基础上，杨新武等^[7]提出SAMME_R算法，通过增加对弱分类器的限制保证了弱分类器的有效性.

目前，现有针对AdaBoost算法的研究主要包括噪声检测和分类器性能提升2个方面. 在噪声检测方面，楼晓俊等^[8]根据样本K近邻中与其类别不一致的样本比率确定该样本是否可能为噪声. Cao等^[9]提出基于K近邻去噪的AdaBoost算法. 算法通过统计某样本K近邻样本的预测类别来确定该样本是否为噪声样本，缺点在于忽略了样本的真实标签信息. 张子祥等^[10]重新定义了样本距离评价函数，通过结合样本真实标签信息与基分类器对K近邻样本的预测结果实现噪声样本检测，但不足之处在于未考虑不同类别样本集密度可能不同的特点. 为了降低样本分布密度不均带来的影响，Yang等^[11]提出邻居熵局部离群值因子的离群点检测算法. 该算法先使用改进的自组织映射（self organizing map，SOM）算法对数据集进行聚类，然后在每个聚类中计算样本的K近邻信息熵以实现离群点检测. 该算法能有效检测样本集边缘的噪声样本，但难以检测处于聚类中心附近的噪声样本.

在分类器性能提升方面，现有算法大多从特征选择、损失函数优化、弱分类器选择等角度展开研究，目的在于提升分类器的训练效率、分类精度及泛化能力. 姚旭等^[12]利用粒子群优化（particle swarm optimization，PSO）算法寻找使得AdaBoost依样本权重抽取的数据集分类错误率最小的最优特征权重分布，依据此最优权重分布对特征随机抽样生成随机子空间并应用于AdaBoost的训练过程中，在增加分类器间差异性的同时保证了弱分类器的准确度. 为了避免噪声样本的影响，曹莹等^[13]提出抗噪声损失函数，限制始终不能被正确分类的样本权值，防止算法过度聚焦于噪声或是奇异值样本点. Sun等^[14]设计了新的多类别损失函数，并通过优化该函数获得弱分类器最佳权重，有效提升了算法的分类精度. 此外，为了结合不同分类器的优势，Yousefi等^[15]将自适应神经模糊推理系统（adaptive network-based fuzzy inference system，ANFIS）、前馈神经网络（feed forward neural network，FFNN）和循环神经网络（recurrent neural network，RNN）作为弱分类器，有效提升了AdaBoost算法的分类精度. Chen等^[16]提出基于多分类器组合的改进AdaBoost算法并将其用于分析土地的利用情况. 该算法通过实验确定支持向量机（support vector machine，SVM）、C4.5决策树和人工神经网络（artificial neural network，ANN）等分类器的权重，并对分类器加权组合以获得性能更强的弱分类器.

研究发现，现有的AdaBoost改进算法普遍面临以下问题：1）大多数噪声检测算法仅考虑待检测样本与其K近邻样本的相似性，忽略该样本偏离其所属类别的程度信息，导致评价结果受样本集分布影响严重；2）现有特征选择方法忽略样本权重的动态变化，难以捕获那些能够有效区分当前被错分样本的特征信息. 为此，本研究在现有AdaBoost算法的基础上，综合考虑样本集密度和样本权重的影响，提出改进的AdaBoost算法. 1）针对噪声检测过程中样本集密度的影响，提出基于合群度-隶属度的噪声检测方法，提高噪声检测的准确性；2）充分考虑AdaBoost算法迭代过程中样本权重的动态变化，提出通用的基于传统过滤器的动态特征选择方法，以提高针对错分样本的分类能力.

传统AdaBoost算法针对不同的训练集训练多个弱分类器，然后将这些在不同训练集上得到的分类器组合起来构成一个强分类器. 给定训练样本集：S = {s₁, s₂,···, s_M}，M为样本数，S对应的类别标签集为Y={y_i| y_i∈{−1, +1}}，AdaBoost算法执行过程^[3-4]如下.

算法1. 传统AdaBoost算法

输入：训练样本集S_t，标签集Y，弱分类器h，S_t所含样本数M，样本权重矩阵D，迭代次数T.

输出：最终分类器H.

1. For i=1∶1: M

2. 初始化样本s_i的权值：D_{1, i}=1/M.

3. end for

4. fort=1∶1∶T

5. 随机从训练集S_t中选择子样本集S，训练得到弱分类器h_t，计算加权错误率：

(1) $ {\varepsilon _t} = \sum\limits_{{s_i} \in S,\;{h_t}\left( {{s_i}} \right) \ne {y_i}} {{D_{t,i}}}. $

式中：h_t（s_i）为使用h_t预测的s_i的类别.

6. 计算弱分类器h_t的权重：

(2) $ {\alpha _t} = \frac{1}{2}\ln \;\left( {\frac{{1 - {\varepsilon _t}}}{{{\varepsilon _t}}}} \right).\; $

7. 更新训练集中每个样本的权值：

8. Fori=1∶1∶M

(3) $ {D}_{t+1,i}=\frac{{D}_{t,i}}{{Z}_{t}}\times \left\{ {\begin{array}{l}{{\rm{e}}}^{-{\alpha }_{t}},\;\;\;\;\;\;{h}_{t}\left({s}_{i}\right)={y}_{i};\\ {{\rm{e}}}^{{\alpha }_{t}},\;\;\;\;\;\;\;{\text{其他}}{.}\end{array}} \right. $

式中：Z_t为归一化因子，即

(4) $ {Z_t} = \sum\limits_{{s_j} \in S} {{D_{t,j}}\exp \;\left[ { - {\alpha _t}{y_j}{h_t}\left( {{s_j}} \right)} \right]} . $

9. end for

10. end for

11. 得到最终的强分类器H. 针对样本s，其类别为

(5) $ H\left( s \right) = {\rm{sign}}\;\left( {\sum\limits_{t = 1}^T {{\alpha _t}{h_t}\left( s \right)} } \right). $

Cao等^[9]根据样本邻居节点被错分的可能性判定其是否为噪声，但是该方法忽略了样本自身真实标签的影响. 楼晓俊等^[8]根据样本邻居中与其类别不一致的样本比率确定该样本是否可能为噪声，该方法针对特定情况的噪声样本识别效果较好，但是未考虑不同类别样本集密度可能不同的特点. 如图1所示，设C₁类样本和C₂类样本在去噪前对应的分类边界为L₁，邻居样本数量k=5，则由文献[8]知，样本s将被识别为噪声，样本集在去噪后对应的分类边界将变为L₂，这将使得待预测样本s₁被错分至C₂类. 可见，样本s对分类边界位置起关键作用，单纯利用k近邻方法将其认定为噪声样本是不合理的. 进一步发现，样本s₂和s被文献[8]检测为噪声的可能性是一样的，但由于s₂位于C₂内部，因此其为噪声的可能性应该大于s，这与文献[8]的结论是不符的.

为此，本研究在文献[8]的基础上引入样本合群度、隶属度的概念，通过综合考虑待检测样本与邻居样本的相似度及与不同类别样本集的隶属关系实现噪声样本检测，具体如下.

定义1　合群度. 样本s的k邻域样本中与其类别相同的样本所占比例，记为s的合群度：

(6) $g\left( s \right) = \frac{1}{k}\sum\limits_{{s_i} \in {\rm{Neig}}\left( {s,k} \right)} {C\left( s \right) = = C\left( {{s_i}} \right)}. $

式中：C(s)为样本s的类别，Neig(s, k)为s的k邻居样本. 可见，g(s)反映样本s与其邻居样本的相似性关系. g(s)∈[0, 1.0]，g(s)越小，说明s与邻居样本的相似性越小，其为噪声样本的可能性越大；g(s)越大，说明s与邻居样本的相似性越大，s为正常样本的可能性越大.

定义2　隶属度. 样本s属于类别c的程度记为s针对c的隶属度l(s, c). 基于sigmoid fitting的支持向量机（sigmoid fitting based support vector machine，SFSVM）可以准确计算每个样本属于各个类别的概率^[17]，因此可以利用SFSVM获得样本s针对类别c的隶属度：

(7) $l\left( {s,c} \right) = {\rm{SFSVM}}\left( {s,c} \right).$

式中：SFSVM(s,c)输出样本s属于类别c的概率. 可见，l(s,c)∈[0,1.0]，该值越大，说明s属于类别c的可能性越大；该值越小，说明s属于类别c的可能性越小.

定义3　非噪度. 样本s的非噪度η(s)描述s不是噪声样本的可能性. 由定义1、2可知，样本s合群度g(s)越小且s相对于其真实类别C(s)的隶属度越小，则s的非噪度η(s)越小，即

(8) $\eta \left( s \right) = g\left( s \right) l\left( {s,C(s)} \right).$

可见，η(s)越小，s为噪声的可能性越大；反之，s为噪声的可能性越小. 针对图1中的s和s₂ 2个样本，存在g(s)=g(s₂)，l(s,C₁)>l(s₂,C₁)，因此，由式(8)可知，s和s₂的非噪度满足η(s)>η(s₂)，符合样本s被判定为噪声的可能性小于s₂的判定.

在此基础上，给出本研究基于合群度-隶属度的噪声检测算法执行流程如下.

算法2. 基于合群度-隶属度的噪声检测算法

输入：样本集S_t={s_i} (1≤i≤M)，样本集类别Y={y_i}(1≤i≤M)，样本邻居数量k，样本类别数L，非噪度阈值th.

输出：样本集S_t中的噪声样本集合ns.

1. 对样本集S_t进行SFSVM训练.

2. for each s_i in S_t

3. 获得s_i的k近邻样本集Neig(s_i, k).

4. 按照式(6)计算s_i的合群度g(s_i).

5. 按照式(7)计算s_i针对其真实类别C(s_i)的隶属度l(s_i, C(s_i)).

6. 按照式(8)计算样本s_i的非噪度η(s_i).

7. if η(s_i)<th

8. ${\rm{ns}} \leftarrow {\rm{ns}} \cup \left\{ {{s_i}} \right\}$.

9. end if

10. end for

由定义2、3可知，当g(s_i)<1/k且l(s_i, C(s_i))<1/L时，s_i为噪声的可能性较大，因此，这里设置阈值 ${\rm{th}} = {1}/({{k L}})$. SFSVM算法时间复杂度为T_SFSVM=M²N^2[18]，可以得到本研究噪声检测算法时间复杂度为

(9) $\begin{split} T_{\rm{pro}} =& {M^{\rm{2}}}{N^{\rm{2}}} + M\left( {MN + M\log_2\; M} \right) =\\ & {M^{\rm{2}}}\left( {{N^{\rm{2}}} + N + \log_2\; M} \right). \\ \end{split} $

在AdaBoost多分类任务中，每个弱分类器所用特征将直接影响分类质量. 文献[12]引入PSO优化来获得随机子空间，通过更新的样本权重分布和特征权重分布来训练AdaBoost分类器. 但是，PSO优化参数依赖性较大，且易陷入局部极值，继而影响特征选择的执行效果. 研究发现，传统AdaBoost算法大多并未进行特征选择或者仅使用较为简单的过滤器特征选择方法（如IG^[19]、CHI^[20]、MRMR^[21]、CMFS^[22]等），因此存在2个问题：1）若不进行特征选择，则在处理大规模数据集时耗时较大；2）简单的特征选择方法在每次选择特征时将所有样本平等对待，忽略样本权重对特征选择结果的影响，使得所选特征仅能区分当前训练集中的“大多数”样本，而无法处理先前被错分的“少数”样本.

为了解决上述问题，在传统方法的基础上进行改进，提出通用的基于过滤器的动态特征选择方法. 该方法强调样本权重的动态变化，针对权重较大样本中所含的特征赋予较大权重，以更好地选择出那些包含在错分样本中的代表性特征. 给定传统过滤器特征选择算法FFS，基于FFS的动态特征选择方法FFSW执行过程如下.

算法3. FFSW算法执行过程

输入：训练样本集S_t={s_i}={x_i, y_i}(1≤i≤M), x_i={x_ij}(1≤j≤N)，样本集类别标签Y={y_i}(1≤i≤M)，类别集C={C_i}(1≤i≤L)，样本权重矩阵D={d_i}(1≤i≤M, d_i为样本s_i的权重)，总特征集F={f_i}(1≤i≤N)，所选特征数目N₁.

输出：所选特征集s_f.

1. fori=1∶1∶N

2. 利用FFS算法，计算特征f_i的得分FFS(f_i).

3. 计算出现f_i的所有样本权重之和：

(10) $ {w_i} = \sum\limits_{{s_j} \in {S_{\rm{t}}},{f_i} \Rightarrow {s_j}} {{d_j}} . $

式中： ${f_i} \Rightarrow {s_j}$表示特征f_i出现在样本s_j中.

4. end for

5. fori=1∶1∶N

6. 将FFS(f_i)、w_i归一到区间[0,1.0]：

(11) $ \left. {{\begin{array}{*{20}{l}} {{{\rm{FFS} }_{\rm{N}}}\left( {{f_i}} \right) = \dfrac{{{\rm{FFS}} \left( {{f_i}} \right)}}{{\mathop {\max }\limits_k \;\left( {{\rm{FFS}} \left( {{f_k}} \right)} \right)}}} ,\\ {{w_{{\rm{N}}i}} = \dfrac{{{w_i}}}{{\mathop {\max }\limits_k \;\left( {{w_k}} \right)}}} . \end{array}} } \right\} $

7. 计算f_i的权重

(12) $ {\rm{FFSW}} \left( {{f_i}} \right) = {{\rm{FFS}} _{\rm{N}}}\left( {{f_i}} \right) \times {w_{\rm{N}}}_i. $

8. end for

9. 按照FFSW对集合F中所有特征进行从大到小排序，前N₁个特征即为所选特征集s_f.

由式（12）可知，FFSW算法弱化了权重较小的样本所含的特征信息. 由于权值较大的样本即为先前被错分的样本，选择这些样本中所含的特征有助于提升弱分类器针对它们的处理能力，继而提高AdaBoost算法的整体分类性能.

鉴于SVM分类器具有泛化能力强、准确性高的优势，使用SVM作为AdaBoost算法的弱分类器，在此基础上提出基于合群度-隶属度噪声检测及动态特征选择的改进AdaBoost算法. 如图2所示，本算法执行步骤如下.

算法4. 基于合群度-隶属度噪声检测及动态特征选择的改进AdaBoost算法

输入：样本集S_t={s_i}={x_i,y_i}(1≤i≤M)，标签集Y={y_i}(1≤i≤M)，所选特征数目N₁，迭代次数T，样本权重矩阵D={D_i,j}(1≤i≤T, 1≤j≤M).

输出：最终分类器H.

1. fori=1∶1∶M

2. D_1,i=1/M.

3. end for

4. fori=1∶1∶T

5. 对训练集S_t进行随机采样，获得包含m个样本的训练集s_ti.

6. 利用算法2获得s_ti中的噪声集合s_ni.

7. for eachs_j∈s_ni

(13) $ {D_{i,\varphi \left( {{s_j}} \right)}} = 0. $

式中：ϕ(s_j)为样本s_j在原始训练集S_t中的编号.

8. end for

9. 按照算法3从s_ti中选择最优特征集f_si.

10. 利用f_si对s_ti中的样本进行表示，使用SVM对s_ti训练得到弱分类器h_i.

11. 按照式(1)、(2)计算h_i在集合s_ti−s_ni上的错误率δ_i以及分类器权重α_i.

12. if${\delta _i} \geqslant {{\left( {L - {\rm{1}}} \right)} / L}\;{\rm{or}}\;{\delta _i} = 0$

13. 删除h_i，跳转至步骤4）.

14. end if

15. 按照式(3)、(4)更新样本权重矩阵D_i.

16. end for

17. 重复执行步骤4）~16）以获得弱分类器集hs={h₁, h₂, ···, h_T}，按照式(5)获得最终集成分类器H.

实验选用UCI数据库中8个典型数据集^[23]，每个数据集对应的样本数范围为300~4601，特征维数范围为34~10000，类别数范围为2~16. 各个数据集的具体信息如表1所示.

实验随机选择每个数据集中90%的样本作为训练集，10%的样本作为测试集. 为了衡量算法在不同训练集上的表现，选用F₁值^[20]作为算法准确性衡量标准. 设置迭代次数T=10，噪声检测算法中邻居数量k=10. 为了保证分类结果的准确性，SVM相关参数设置如下：核函数为RBFKernel，惩罚系数C=40000，核函数中参数g=0.07. 实验采用的机器配置如下：内存：8G，CPU为Core i7、3.40 G Hz，相关算法使用Matlab 2013实现.

在不同的测试集情况下，将本研究噪声检测方法与文献[8]、[9]、[10]及[11]中方法进行比较. 设置文献[8]中噪声敏感因子β=0.1，文献[11]中隐藏层神经元数量som_num=25、迭代次数T=100. 在保证其他条件相同的情况下，当所选特征比例rf=0.1、0.2、0.3、0.4、0.5时统计不同算法对应的F₁值均值（记为F_a），结果如表2所示. 可以看出，文献[10]相对于文献[8]所得F_a普遍偏高，说明综合考虑样本真实标签信息和预测标签信息能有效提高噪声检测效果. 本研究所得结果均普遍高于文献[8]及文献[10]，说明在噪声识别过程中考虑样本的类别隶属度能有效降低噪声误识率、提高噪声检测精度. 除KDD99和AntiVirus这2个数据集之外，本研究所得F_a相对文献[9]、[11]在其他数据集上具有明显提高，可能是由于：1）文献[9]仅通过判断样本邻居来获得其为噪声的可能性，忽略了样本自身真实标签的影响；2）文献[11]仅考虑待检测样本与邻居样本的特征相似性，难以检测处于聚类中心附近的噪声样本.

进一步地，将不同噪声检测算法的执行效率进行比较. 当rf=0.1、0.2、0.3、0.4、0.5时统计不同噪声检测算法对应的运行时间均值t_s，结果如表3所示. 可以看出，由于文献[11]使用SOM算法来对训练样本集进行聚类，噪声检测耗时最大. 相对于文献[8]而言，本研究考虑了待检测样本针对各个类别的偏离度，因此对应的运行时间稍高；与文献[9]、[10]相比，本研究在执行效率上优势明显，主要是因为前2种方法须使用SVM分类器预测待检测样本的所有邻居样本类别，相对于本研究仅预测待检测样本类别而言带来了额外的计算开销.

为了验证不同特征选择方法的执行效率，将几种典型的FFS方法（IG、CHI、MRMR及CMFS）与相应的FFSW方法（IGW、CHIW、MRMRW及CMFSW）的时间复杂度进行比较，结果如表4所示. 可以看出，IG和CMFS对应的时间复杂度相等，且均小于CHI的时间复杂度. 由于FFSW方法须计算特征出现的样本权重和，对应的时间复杂度较相应的FFS方法稍高. 以CMFS为例，存在

(14) $\begin{split} \dfrac{{{T_{{\rm{CMFSW}}}} - {T_{{\rm{CMFS}}}}}}{{{T_{{\rm{CMFS}}}}}} =& \dfrac{{NM}}{{N\left( {M + L + ML + {\rm{log_2\;}}N} \right)}} = \\ &\frac{1}{{\left( {1 + {L}/{M} + L + ({{{\rm{log_2\;}}N}})/{M}} \right)}} .\\[-8pt] \end{split} $

由于L<<M且log₂ N<<M，式（14）可以简化为

(15) $\frac{{{T_{{\rm{CMFSW}}}} - {T_{{\rm{CMFS}}}}}}{{{T_{{\rm{CMFS}}}}}} \approx \frac{1}{{1 + L}}.$

可见，FFSW方法的时间复杂度受L影响，其相对于FFS的增幅不超过1/3（L=2时），L越大，FFSW相对于FFS带来的额外计算开销将越小.

为了验证样本权重对特征选择结果的影响，分别在所选特征比例rf=0.1、0.2、0.3、0.4、0.5情况下，将上述不同的特征选择方法应用于算法4中的步骤9），计算10次实验对应的F₁均值（F_a），结果如图3所示. 图中，细虚线为FFS方法对应结果，粗实线为FFSW方法对应结果. 可以看出，针对所含特征总数小于100的样本集（Spambase、KDD99及Dermatology）而言，rf的变化对于F_a影响较大；针对所含特征总数大于5000的样本集（DrivFace及Amazon）而言，rf的变化对于F_a的影响不明显. 整体来看，FFSW方法所得结果明显高于FFS方法. 例如，在Amazon数据集中，CMFSW对应结果除rf=0.5情况外均高于CMFS；当rf=0.3时，CHIW相对于CHI方法的F_a提高约0.1. 在Dermatology数据集中，IGW对应结果均高于IG. 在Arrhythmia数据集中，IGW和CHIW表现在除rf=0.1情况外均优于IG和CHI方法，MDMRW方法在rf=0.5条件下取得最大值约0.75.

如表5所示为上述FFSW方法相对于FFS方法在不同数据集上的F_a增幅均值F_ai. 可以看出，F_a增幅均值大于0和0.05（加粗表示）的概率分别为93.75%和34.38%，验证了改进的特征选择方法在提升AdaBoost分类精度方面仍具有一定优势. 进一步地，如表6所示为FFSW方法相对于FFS方法在不同特征比例下的平均运行时间增幅均值r_ai. 可以看出，IGW、CHIW和CMFSW在所有数据集上的运行时间与IG、CHI和CMFS相近；MRMRW在所含特征总数大于1000的数据集（AD、DrivFace及Amazon）上执行速度慢于MRMR，而在其他数据集上表现与MRMR相近. 可见，在选择合适的FFS方法的情况下，FFSW方法相对于FFS方法不会带来显著的计算开销.

在不同迭代次数情况下，将本研究算法与几种典型的改进AdaBoost算法进行比较. 选择的改进AdaBoost算法包括Ada_M1^[4]、SAMME^[6]、SAMME_R^[7]、AW_Ada^[24]、ND_Ada^[9]、ROB_Ada^[14]. 相关参数设置如下：1）在本研究、ND_Ada及ROB_Ada噪声检测过程中，取邻居样本数量为k=10；2）本研究采用CMFSW特征选择方法，其他算法统一使用CMFS特征选择方法. 令迭代次数T=10、30、50、70、90、110，在每个数据集上统计每种算法在特征选择比例为0.1、0.2、0.3、0.4、0.5情况下的F₁均值F_aa，所得结果如图4所示. 可以看出，随着迭代次数T取值增大，本研究算法在数据集KDD99、Arrhythmia及Dermatology上表现明显优于其他算法，对应的F_aa相对其他算法均明显偏高. 并且，本研究算法在数据集Spambase和AD上表现与ND_Ada、ROB_Ada相近且明显优于其他算法，说明检测训练集中的噪声样本对于提高分类精度具有重要作用. 进一步发现，虽然本研究在数据集DrivFace、AntiVirus和Amazon上不能针对每一个T均取得最大值，但从总体上来看其对应的F_aa仍普遍高于大部分算法，验证了基于合群度-隶属度噪声检测及动态特征选择的改进AdaBoost算法在提升分类精度方面的有效性.

提出基于合群度-隶属度噪声检测及动态特征选择的改进AdaBoost算法. 为了验证算法的有效性，在8个典型数据集上分别从噪声检测、特征选择以及与现有AdaBoost算法比较3个方面展开实验. 主要结果如下.

（1）基于合群度-隶属度的噪声检测方法综合考虑了样本邻居样本及其同类别样本的分布特征，有效提高了噪声检测的准确性.

（2）FFSW方法结合了样本权重的影响，在保证不带来较大计算开销的情况下有效提升了分类器对于错分样本的处理能力.

（3）与现有典型的AdaBoost方法比较，本研究在多个数据集上获得较明显的优势，验证了其在数据分类方面的有效性.

（4）由于本研究在错误率计算过程中并未考虑不同类别样本集规模的影响，未来将结合不同类别召回率设计新的错误率计算方法以进一步改善AdaBoost算法分类性能.