近年来，多种算法应用于对事物对象的分类识别研究，AdaBoost算法^[1]在被提出后因其较高的检测速度广泛应用于人脸检测中，其技术已经甚为成熟。针对传统AdaBoost算法存在的问题，许多研究学者如钱志明、李文辉、刘王胜、付忠良等^[2-5]提出了不同的改进方法，并取得了较好的改进效果。AdaBoost算法的思想是通过调整样本权重和弱分类器权值，从训练出的弱分类器中筛选出权值系数最小的弱分类器组合成一个最终强分类器^[6]。在以往的改进算法中，对弱分类器加权系数未同时考虑到弱分类器的可靠性及对正样本的识别能力。本文在传统算法的基础上，利用改进的细菌觅食优化算法的思想全局优化提升弱分类器的权重系数，并提出新的权重系数求解方式，使得弱分类器在FRR一定的情况下得到更低的FAR，从而使目标检测算法的分类识别性能得以提高。

1 Adaboost算法

AdaBoost算法是最著名的且被广泛使用的Boosting算法，在训练集上依次训练弱分类器，每次下一个弱分类器是在训练样本的不同权重集合上训练的。权重由每个样本分类的难度确定，而分类的难度是通过前面步骤中的分类器的输出估计得到^[7]。AdaBoost算法在样本训练集使用过程中，对其中的关键分类特征集进行多次挑选，逐步训练分量弱分类器，用适当的阈值选择最佳弱分类器，最后将每轮训练确定的最佳弱分类器组合为强分类器。其中，级联分类器的设计模式为在尽可能保证感兴趣图像输出率的同时，减少非感兴趣图像的输出率，随着迭代次数不断增加，所有的非感兴趣图像样本都不能通过，而感兴趣样本始终保持尽可能通过为止。

1.1 AdaBoost算法训练过程

算法训练过程^[8]描述如下：

1) 输入样本集S={(x₁, B₁), (x₂, B₂), …, (x_n, B_n)}, B_i=y_i为样本类别, y_i∈{1, -1}即分别表示正样本和负样本, n为总的训练样本数量。

2) 初始化样本权值, 令w_{1, i}=1/n

3) 对于迭代次数t=1, 2, …, T

① 对于每个所选特征训练一个弱分类器f_t(x_i), 误差值根据样本权值计算, , (μ∈{1, -1}), μ取1表示样本被正确分类, 取-1表示被错误分类。

② 计算f_t的缩放系数, α_t的作用是强调样本权重的调整以及表示在最终强分类器中弱分类器的加权系数。

③ 从生成的弱分类器中, 找出一个具有最小ε_t的弱分类器f_t更新每个样本对应的权重, 使更新后的错误样本权重相对增加, 而正确分类的样本权重相应减小, w_{t+1, i}=w_{t, i}exp(-α_ty_if_t(x_i))/z_t, z_t=, 其中f_t=y_i(样本被正确分类), f_t≠y_i (样本被错误分类)。

1.2 AdaBoost算法分类过程

算法分类过程描述如下:

1) 弱分类器级联成强分类器F(x)=

2) 分类结果输出

由AdaBoost算法的描述过程可知, 该算法在实现过程中根据训练集的大小初始化样本权值, 使其满足均匀分布, 在后续操作中通过公式来改变和规范化算法迭代后样本的权值。样本被错误分类导致权值增大, 反之权值相应减小, 这表明被错误分类的训练集包含一个更高的权值。这就会使在下轮时训练样本集更注重于难以分类的样本, 针对这些关键样本的不断学习来构建下一个弱分类器, 直至样本被正确分类^[9]。在达到规定的迭代次数或者预期的误差率时, 则强分类器构建完成。

2 快速的变概率细菌觅食算法

细菌觅食算法(BFO)^[10]是一种新兴的智能优化算法, 受到不同领域及专家学者的广泛关注。目前广泛应用于工程参数优化、神经网络、模式识别、图像处理问题等方面。

针对BFO存在的缺陷, 目前已有的改进算法大多针对问题的某个方面在一定程度上进行了改进。周佳薇等^[11]提出的变概率的混合细菌觅食优化算法(VPBFO), 有效提高了求解精度及早熟收敛能力, 但选择合适的控制参数及其他方面还有待提高。本文提出了一种快速的变概率细菌觅食算法, 算法利用改进的随机化佳点集方法初始化种群, 这使得产生的菌群具有全局搜索空间、多样性和均匀性; 由于细菌觅食算法3个主要操作中最重要的是趋化操作, 其他2种操作主要是辅助优化, 故本文为提高算法的收敛速度, 在进行趋化性操作时将旋转和直向结合为一步完成, 利用PSO的快速搜索能力的思想^[12], 直接以粒子移动方法替换趋化操作的方向和步长, 样本中的每个个体都进行一次趋化性操作后, 更新细菌个体最佳位置和菌群最佳位置; 采用变概率的迁徙-消亡策略, 利用菌群适应度方差的稳定性自适应改变迁徙概率, 由此避免菌群陷入局部极值。

设p(i, j, k, m)为细菌i在第j次趋向操作、第k次复制操作及第m次迁徙操作后的位置, 其中j, k, m的初始值均为0, 设第i个细菌的位置为N_i=[x_i¹, x_i², …x_iⁿ], 基准概率值a=0.1, 上限控制变量b=0.3。

快速的变概率细菌觅食优化算法的过程描述如下:

1) 初始化参数。菌群大小S、搜索空间维度v、趋化次数T_d、复制次数T_re、迁徙次数T_ed。

2) 初始化菌群位置。利用随机化佳点集方法初始菌群, 并计算细菌个体的适应度值h。设置细菌个体最佳位置初始值和全局最佳位置初始值。

3) 设置变量。其中趋化次数j=1:T_d, 复制次数k=1:T_re, 迁徙-消亡次数m=1:T_ed。

4) 进行趋化操作。对细菌位置以粒子群算法的更新方式(1)、(2)式进行更新并计算新位置上的适应度函数值。

(1)

(2)

5) 进行复制操作。趋化操作完成后, 累加每个细菌在周期内的适应度函数值得到健康值, 对健康值进行排序, 复制健康值优的细菌, 而对于健康值劣的细菌进行淘汰。

6) 进行迁徙操作。完成复制操作后, 对每个细菌个体产生一个随机概率, 将其与(3)式变化的P_ed进行比较, 小于P_ed的细菌执行消亡操作, 同时累加所有小于P_ed的细菌总数r, 采用随机化佳点集方法生成S个新个体, 按照健康值的优劣排序, 选择较优的前r个细菌作为迁徙-消亡后的新个体, 在解空间按照式(4)初始化, [X_min, X_max]为优化区间, X为细菌的初始化位置。

(3)

(4)

7) 判断。若循环结束, 则输出结果, 否则跳转至步骤4), 继续执行直至符合终止条件。

3 基于快速的变概率细菌觅食的AdaBoost弱分类器优化权重

在基于快速的变概率细菌觅食的AdaBoost算法中, 样本在样本搜索空间中找到最佳弱分类器, 通过优化弱分类器权重来提高训练速度与精度。弱分类器的加权系数优化不仅仅与误差率有关, 在利用AdaBoost算法时主要实现的是分类识别作用, 故组合成强分类器时也应考虑到弱分类器的可靠性及对正样本的识别能力。在本文中, 为了将识别率和可靠性同时考虑进去, 故设正样本的拒绝率为δ, 该拒绝率的取值是由被错误分类的正样本占总样本的百分比决定。

3.1 训练弱分类器流程

算法流程如下:

1) 输入训练样本集S, 初始化样本权值w_{1, i}。

2) Do for t=1, 2, …T

① 利用随机化佳点集方法初始化样本集个体的位置与速度, 并计算每个样本的初始化适应度值。

② 根据样本误差公式求得ε_t。

③ 对于每个样本将其适应函数值与其趋化过程中经过的个体最佳位置P_best比较, 确定是否替换最佳位置值, 否则保持个体经历过的最佳位置值不变; 同时将适应值与全局历史最佳位置g_best比较, 较好则选取当前值为最佳位置值, 否则全局历史最佳位置值不变。

④ 进行个体的趋化、复制及迁徙-消亡操作。

⑤ 搜索出一个具有最小ε_t的弱分类器f_t计算弱分类器的权值系数。

(5)

k为一常数, 0＜k＜1, 其值满足在第t次循环中使最小误差率的上界下降。

⑥ 更新每个样本对应的权重w_{t+1, i}, 归一化样本权值。

(6)

⑦ 判断。若循环结束, 则输出结果, 否则跳转至②, 继续执行直到符合终止条件。

3) 分类结果输出

3.2 对改进的求解方式的理论分析与验证

AD AdaBoost算法^[13]考虑弱分类器的权重与错误率及对正样本的识别能力有关, 有效地降低了分类器在低FRR端的FAR。本文通过对传统算法和已改进算法的分析, 提出弱分类器的权值不仅与错误率及对正样本的识别能力有关, 还应与弱分类器的可靠性有关。通过对求解加权系数的方式作以改进, 经过理论分析和实验验证, 得出该算法的求解方式比传统AdaBoost算法的求解方式效率有了更大的提升。下面证明本文算法通过改善样本H(x_i)值的分布来改进弱分类器的分类性能。已知可靠性=识别率/1-拒绝率，为同时考虑分类器对正样本的识别能力及可靠性, 在此用识别率乘以可靠性。

令, 则样本x_i对应的F_x为

(7)

该式右端第一项与AdaBoost算法的形式一致, 故只考虑后一项, 令则正样本

(8)

对应的负样本

(9)

n_p和n_n分别表示样本集中正样本数和负样本数, 则在t次循环中, 识别错误的正样本数为(n_p+n_n)δ, 识别正确的正样本数表示为n_p-(n_p+n_n)δ, 故

(10)

将(10)式代入(8)式得

(11)

第t个弱分类器识别错误的样本总数(n_p+n_n)ε, 则识别错误的负样本数表示为(n_p+n_n)ε-(n_p+n_n)δ, 识别正确的负样本数为n_n-[(n_p+n_n)ε-(n_p+n_n)δ]。故

(12)

在训练过程中, 要求ε_t＜0.5, 故

(13)

综合(9)式、(11)式及(13)式得到

(14)

通过理论分析得到, 该求解方式能够满足检测条件, 并且能够保证正负样本具有更好的分布。图 1给出了传统AdaBoost算法以及本文算法在Heart数据集^[14]中的F(x_i)分布的对比。

由图 1可以看出本文算法下正负样本分布能更好的向外延伸, 且FAR值低于传统AdaBoost算法下的值, 说明本文算法的改进效果更胜一筹, 在符合FRR要求的阈值处具有更低的FAR。

4 实验与分析

为了验证本文算法的改进效果, 在UCI数据集上选取4组实验数据集, 分别为Diabetis、Heart、Segment、Yeast。该4个数据集均选择200个训练样本和100个测试样本(实例数目范围是303~2 308, 属性范围是8~75)。在MATLAB上应用传统AdaBoost算法和本文改进算法进行实验, 选用SVM作为基分类器, 设置算法的迭代次数为65次, 趋化次数取10, 复制次数取4, 迁徙-消亡次数取4, 样本实验数据集如下表 1所示。

实验结果如下图 2至图 5所示。

由以上实验结果分析得到, Diabetis、Yeast 2种数据集在初始训练时误检率相同, 随着迭代次数的增加, 误检率降低得更快, 在精度一定的情况下, 训练次数更少; Heart数据集的检测结果可以看出在初始时本文算法的误检率明显低于传统AdaBoost算法; 而Segment数据集上的检测结果显示在初始时误检率高于传统算法, 经过训练次数的不断增加, 误检率得到明显改善。通过分析得出, 针对不同数据集, 改进算法的误检率随着迭代次数增加而不断降低, 最终达到一个稳定值, 且收敛速度相比较传统AdaBoost算法降低的更快, 说明改进算法更具高效性。同时, 在误检率相同时, 改进算法训练出的弱分类器数目少于传统AdaBoost算法, 说明在相同精度下本文算法的强分类器级联数较少, 其运算速度更快, 从而泛化能力更强。本文对所选弱分类器的加权系数作以改进, 同时考虑错误率、对正样本的识别能力及弱分类器的可靠性, 使得每轮训练中在注重错分类样本的同时, 提高对正样本的正确分类能力, 结合实验结果得出算法的检测精度与速度得到明显提高。

5 结论

本文结合细菌觅食优化算法及AdaBoost算法的优缺点, 将改进的细菌觅食算法结合AdaBoost算法来优化弱分类器权重, 对提出的算法进行了严密的理论分析和实验验证, 结果表明本文改进算法比传统AdaBoost算法具有较高的分类性能。现今各种改进的AdaBoost算法在人脸识别方面已取得了较大的成功, 此类问题涉及二分类问题, 在接下来的工作中, 将本文改进算法应用于人脸检测中验证该算法的高效性, 后续工作中将该算法推广至多分类问题中, 实现识别分类功能。