基于改进涡流搜索算法的支持向量机分类模型

李学贵, 郭远涛, 李盼池,c, 王 艾

(东北石油大学a.计算机与信息技术学院; b.黑龙江省网络化与智能控制重点实验室;c.黑龙江省石油大数据与智能分析重点实验室; d.图书馆, 黑龙江 大庆163318)

0 引 言

支持向量机(SVM: Support Vector Machine)[1-2]是基于统计学习理论的二分类模型。 统计学习理论是一种研究小样本情况下机器学习规律的理论。 因此, SVM 在解决小样本、 非线性和高维问题时有独特的优势。 其主要特点是: 善于处理小样本问题, 目标是获得当前问题在现有信息下的最优解; 最终可转化为一个二次凸优化问题, 理论上可求得全局最优解; 本质上是将输入数据的低维特征映射到高维的特征空间。 在高维特征空间中构造线性分类器, 解决原始空间中的非线性问题。 SVM 具有坚实的理论基础,学习性能突出, 在人脸识别、 图像处理、 去噪和机器翻译等领域得到成功的应用。 因此, 受到大量学者和工业界的关注[3-7]。

在现实生活中, 许多问题的优化通常因其复杂性而得不到确切的解决方案[8]。 而元启发式算法使用问题的近似解代替精确解, 可解决这类问题。 其遵循 “适者生存” 的自然规律, 通过选择和变异两个步骤实现物种的进化。 选择是优化的基础, 变异是随机搜索的根本。 元启发式算法首先计算出适应度, 选择最佳个体, 然后使用遗传算子执行变异操作, 生成新后代。 根据其设计所模拟的自然特征, 可将其分为3 类: 1) 生态系统模拟算法, 如生物地理化学优化算法(BBO: Biogeography-Based Optimization)[9]和入侵性杂草克隆算法(IWO: Invasive Weed Optimization)[10]; 2) 群集智能优化算法, 如蜂群算法( BC: Bee Colony)[11]、 萤火虫算法( FA: Firefly Algorithm )[12]和粒子群优化算法( PSO: Particle Swarm Optimization)[13]; 3) 进化算法, 如遗传算法( GA: Genetic Algorithm)[14]、 差分进化( DE: Differential Evolution)[15]和稻田算法(PFA: Paddy field Algorithm)[16]。

涡流搜索算法(VS: Vortex Search)[17]是受搅动液体引起的涡流现象启发而提出的一种元启发式优化算法。 围绕涡流中心利用正态分布生成可行解, 然后在可行解和最优解之间进行贪婪选择。 其特点是简单、 搜索能力强和迭代时间短[18]。 但是, VS 算法在优化具有多个局部最小值函数时可能陷入局部最小值[19-20]。 而在VS 算法的基础上改进的VS 搜索算法(MVS: Modified Vortex Search)[21]解决了此问题, 其搜索能力更强, 性能超过了其他元启发式算法。

笔者将MVS 算法应用于支持向量机参数的选择, 在不搜索空间中所有参数点的情况下, 可找到全局最优解, 有效地避免了陷入局部最小值, 同时增加了搜索范围, 进而提出了一种基于MVS 算法的支持向量机分类模型。

1 改进的涡流搜索算法

VS 算法在每次迭代中围绕一个涡流中心产生候选解, 根据实际问题的上下限, 对涡流中心μ0进行初始化。 在之后的每次迭代中, 涡流中心的值变化为当前迭代的最优解。 然后, VS 算法通过高斯分布围绕涡流中心生成候选解。 这为算法提供了简单性, 但也带来了问题。 对于具有多个局部最小值的函数,使用单点生成候选解的方法容易陷入局部最小值。 该算法利用自适应步长调整方案的搜索行为模拟涡流现象, 随着迭代次数的增加, 算法候选解的局部性也在增加。 因此, 如果算法不能尽快跳出局部最小值,则随着迭代次数的增加将更难以跳出局部最小值。 MVS 算法克服了VS 算法的缺点。 在MVS 算法中, 每次迭代围绕多个中心生成候选解。 每个中心都会产生一个最佳解, 在所有的最佳解中又会产生一个全局最佳解。 依据全局最佳解生成新的涡流中心。 MVS 算法增加了搜索空间的范围, 降低了陷入局部最小值的可能性。

1.1 初始化涡流搜索中心

首先考虑二维的优化问题, 图1 为利用多个嵌套圆模拟二维空间的涡流搜索过程。 MVS 算法每次迭代围绕m 个中心产生候选解。 MVS 算法的搜索行为可看作是在每次迭代中构造不同中心的多个并行涡流。

图1 涡流搜索中心的搜索过程Fig.1 The search process of vortex search center

用Mt(μ)表示在每次迭代过程中存储每个涡流中心值的矩阵, t 表示迭代次数, 初始值为0。 因此,m 个中心的初始值为M0(μ)= {μ10,μ20,…,μm0}。每个中心的初始值

其中Lupper和Llower都是d 维向量, 分别代表d 维搜索空间的上界和下界。

1.2 生成新的候选解

初始化半径值r0, 围绕m 个中心生成具有高斯分布的多个候选解。 候选解的总数设置为n, 这n 个候选解是围绕m 个中心产生的。 因此, 每个涡流中心产生n / m 个候选解。 设(s)= {s1,s2,…,sn/m}表示第t 次迭代中围绕m 个中心产生的候选解的子集。当t = 0 时, 生成的所有候选解集为C0(s)= {H10,}。

高斯分布的一般形式为

其中d 是维度, x 是d×1 维随机变量, μ 是d×1 维样本均值(涡流中心)向量, Σ 是协方差矩阵。 如果协方差矩阵的对角线元素相等, 并且非对角元素为零, 则分布的形状是球形。 笔者讨论二维问题, 可将其视为圆形。 因此, 协方差矩阵

在优化过程中, 将标准差σ0作为涡流搜索半径。 为使搜索空间能覆盖解空间, 可以给初始半径r0设置一个较大的值。 随着迭代次数的增加, 搜索半径不断减少, 其减少是一个自适应调整的过程。 通过设置半径较大的最外层圆, 实现了搜索空间的全覆盖。

1.3 更新候选解

在选择候选解时, 每个子集都有一个最佳解s′l∈Hm0(s)。 且候选解必须在搜索空间内, 超出范围的候选解需根据

变换到搜索空间内。 其中k =1,2,…,n, i=1,2,…,n, a 是符合均匀分布的随机数。 每次迭代过程中每个子集的最佳解存储在Bt(s)中。 t=0 时, B0(s)= {s1,s2,…,sm}。 矩阵B0(s)中的最佳解为当前迭代中所有候选解的全局最佳解, 记为Gbest。 如果Gbest小于当前最佳解, 则将Gbest更新给sbest。

在VS 算法中, 每次迭代中心都会变换为当前的最佳解sbest。 然而, MVS 算法在下次迭代中需要m 个中心位置。 此为VS 算法和MVS 算法的不同之处。 在MVS 算法中, 这些中心的第m 个中心在下一次迭代中, 变换为当前的最佳解sbest, 余下的m-1 个中心新的位置为

其中a 服从正态分布的随机数, 且s′l∈B0(s′)。 因此, 当t = 1 时, M1(μ)= {μ11,μ21,…,μm1} 由最佳解集s′l∈B0(s′)和最佳解sbest确定。 然后, 算法使用m 个新的涡流搜索中心, 减小新半径, 围绕其生成新的候选解。 重复执行上述过程, 直到满足终止条件。

MVS 算法与VS 算法十分类似, 只是在候选解的选取与更新解的方式上不同。 并且MVS 算法在计算量上要多于VS 算法。 MVS 算法增加了涡流中心的数量, 有利于跳出局部最小值, 搜索到最优的适应度函数。 半径的减少是搜索过程的关键, MVS 算法使用一种自适应调整的方法缩减半径。

1.4 减小搜索半径

在MVS 算法中, 半径的减少过程是一种自适应步长调整过程, 对算法的性能有至关重要的影响。MVS 算法利用逆不完全伽马函数

减小半径。 其中x≥0 为随机变量, e 为自然对数, a＞0 为形状参数, 相当于搜索步长, 在[0,1]内等值取样。 每次迭代都要调整搜索的步长, 因此整个搜索过程按

计算a 的值。 选择a0=1, 确保在第1 次迭代时能覆盖全部的搜索空间。 t 是当前迭代次数, E 为最大迭代数。 每次迭代的涡流半径更新式为

文献[15]指出, 当x =0.1 时, 搜索算法性能最好。 采用逆不完全伽马函数缩减半径, 可使算法在不断的迭代中自适应调整半径。 在初始阶段以全局搜索为主, 在后半阶段专注于局部搜索, 使算法更准确地搜索到最佳解。

2 基于改进涡流搜索算法的支持向量机

2.1 支持向量机

SVM[1-2]基于结构风险最小化, 考虑经验风险和置信界之和的最小化, 具有泛化能力更强, 性能更加优异的特点, 针对小样本问题表现更优, 因此得到广泛关注。SVM 通过在数据集上构造一个最大间隔分类器, 实现数据分类。 针对线性可分问题, 通过硬间隔最大化, 学习一个线性分类器; 针对近似线性可分问题, 通过软间隔最大化, 学习一个线性的分类器; 对线性不可分问题, SVM 通过使用核函数和软间隔最大化, 学习一个非线性支持向量机, 依然可获得优异的分类性能。 核函数一般采用径向基函数, 这是一个常用的核函数。 核方法的应用使SVM 在非线性问题中具有更高的分类精度。

SVM 的学习过程可转化为优化问题, 给定训练样本集D ={( x1,y1),( x2,y2),…,( xm,ym)}, y∈{±1}, 基于训练集D 在样本空间中找到一个划分超平面, 超平面记为(w·x)+b = 0。 为寻找最优超平面, 定义一个损失函数φ(w,ξ)。 通过将其最小化, 求得最优超平面。 即

其中w 为超平面的法向量, φ(x)代表对原始特征的变换, C＞0 为错分样本的惩罚因子, ξi≥0 为松弛变量, b∈R 为阈值。 引入Lagrange 函数, 将二次规划问题转化为相应的对偶问题, 即

图2 支持向量机分类模型图Fig.2 Support vector machine model topology

其中K(xi,xj)为核函数。 支持向量机分类模型如图2所示。

2.2 支持向量机分类模型的参数优化

式(11)中的核函数K(xi,xj)使用径向基核函数(RBF: Radial Basis Function), 也叫高斯核函数[22],是一种常用的核函数

其中τ＞0 是高斯核的带宽, 是影响核函数的重要参数。

通过寻找最优的惩罚因子C 和核函数参数τ, 最大化SVM 的分类正确率。 首先, 在一定的范围内对C 和τ 取值; 然后, 将训练数据作为输入, 计算当前C 和τ 下得到的分类正确率; 最后, 将通过多次迭代取得分类正确率最高的那组参数作为最佳参数。 笔者采用MVS 算法优化支持向量机, 寻找最优的参数C和τ。 此算法的优点是不需搜索整个解空间即可找到最佳解, 解决了其他方法存在的问题。

2.3 基于改进涡流搜索算法的SVM 参数寻优

SVM 是一个分类模型, 通常使用分类准确率作为评价其性能好坏的标准。 因此, 将在训练集下的分类准确率作为MVS 算法的适应度函数, 通过优化适应度函数, 搜索使SVM 分类准确率最大的参数C 和τ。 为优化SVM 的参数, MVS 算法需设置相关参数: 涡流中心的个数、 候选解集大小、 搜索空间上下界和最大迭代数。 基于MVS 算法的SVM 参数寻优算法描述如下。

Step1 利用式(1)初始化搜索中心M0(μ)= {}, 利用式(9)初始化标准差σ0, 最优解的适应度函数设置为f(sbest)= ∞, 迭代步数t=0。

Step2 以搜索半径rt, 围绕搜索中心生成服从高斯分布的候选解(s)。 候选解的总数为

250。 如果候选解的值超出边界范围, 则使用式(5)将其变换到边界内。Step3 从( s) 中选择最佳解, 保存到矩阵Bt( s′), 再从Bt( s′) 中选出全局最佳解存入Gbest。 若Gbest优于当前的全局最优解, 则更新最优解sbest。

Step4 将sbest作为第m 个新涡流中心, 使用式(10) 更新前m-1 个涡流中心, 缩减半径得rt+1,利用变换后的m 个中心作为缩减半径后的涡流中心, 生成服从正态分布的候选解, 变换迭代步数t=t+1。

Step5 判断是否满足终止条件: 如果迭代步数t≥E, 则终止迭代, 输出最优解S; 如不满足终止条件, 则转Step2 重复上述过程。

MVS 的算法流程图如图3 所示。

图3 MVS 算法流程图Fig.3 Flow chart of MVS algorithm

3 仿真实验

笔者选择UCI(University of California Irvine)数据库[23]中的数据集验证笔者的算法。 选择了UCI 数据库中的Ionosphere、 Banknote、 Haberman 3 个常用的数据集进行仿真实验。 Ionosphere 是电离层数据集,根据给定的电离层中的自由电子的雷达回波预测大气结构的好坏。 Banknote 是钞票数据集, 根据给定的钞票属性判断真假钞。 Haberman 是乳腺癌数据集, 根据给定的属性判断病人手术后生存时间是否超过5 年。编写程序在Matlab 2017a 上进行仿真实验, 实验计算机配置为Intel @ coreTMi7-3770, CPU @3.40 GHz, 内存12 GByte, Win10 64 位操作系统。 在实验中, 首先对数据集进行归一化操作, 将属性值归一化到[0,1]区间。 然后, 划分数据集, 取数据集中一部分作为训练集, 剩下的部分作为测试集。 数据的信息如表1 所示。

MVS 算法的参数设置如下。 根据文献[21]的推荐, 涡流搜索中心个数设置为5。 经多次实验, 分别设置邻域解个数为[150,200,250,300,350], 根据实验结果选择250。 涡流搜索算法的性能对迭代步数依赖性不大, 因此设置最大迭代步数为100。 关于支持向量机中惩罚因子C 和核参数τ 取值范围, C 起到正则化的作用, 取值范围为[0,2]。 τ 太小会造成过拟合, 过大导致学习复杂度过高, 因此将τ 设置为[0,4]。

表1 数据集的信息Tab.1 The information of data sets

对算法的性能评价。 笔者设置了算法的平均适应度和全局最佳适应度两个性能指标。 全局最佳适应度是在所有的250 个候选解中的最佳解;算法的平均适应度是每次迭代中所有适应度的平均值。

笔者选择粒子群优化算法、 VS 算法和网格搜索算法3 种对比算法。 经过实验, MVS 算法的全局最佳适应度和平均适应度均高于VS 算法, 因此其性能更优。 MVS 算法与VS 算法的适应度变化曲线如图4 所示。 通过MVS 算法搜索到最优的支持向量机模型后,使用测试数据对模型进行测试, 4 种算法的测试结果如表2 所示。

图4 涡流搜索算法改进前后适应度 随迭代步数的变化曲线Fig.4 The change curve of fitness with the number of iterations before and after the improvement of vortex search algorithm

表2 支持向量机分类平均准确率Tab.2 Average classification accuracy of SVM

为避免智能优化算法的随机性, 针对每种算法进行了30 次试验, 取平均值作为最终的分类准确率。从表2 中每种算法的平均准确率可见, 基于MVS 算法的SVM 模型的平均分类准确率高于基于网格搜索、粒子群算法和VS 算法的SVM 分类模型。 因此, 在搜索SVM 参数的过程中, 采用MVS 算法有助于跳出局部最小值, 搜索到最优的SVM 参数, 提高其分类准确率。

4 结 语

MVS 算法的全局搜索能力强于VS 算法。 通过在每次迭代过程中围绕多个涡流中心产生候选解的方式, 有效避免了算法陷入局部最小值。 SVM 的实质是一个二次凸优化问题, 其参数是影响分类精度的主要因素, 决定了SVM 的学习性能和泛化能力。 笔者采用MVS 算法选择SVM 的参数, 在避免遍历整个搜索空间的情况下, 就可找到最优解。 实验结果表明, MVS 算法可选取更好的SVM 参数。 经过MVS 算法优化的SVM 分类模型获得了高于其他优化方法的分类精度。