基于改进粒子群算法的孪生支持向量机

顾吉峰，王 蓓

(华东理工大学 化工过程先进控制和优化技术教育部重点实验室，上海 200237)

0 引 言

在工业生产中，对生产工艺中的数据进行分析和建模可以提高企业的经济效益[1]。例如在电力行业，判断用户是否存在偷电漏电的行为非常必要[2]，寻找合适的方法对已收集的数据实施分类任务是值得关注的问题。与人工神经网络[3]、决策树[4]、朴素贝叶斯[5]等分类算法相比，支持向量机[6,7](supported vector machine，SVM)以更优越的综合分类性能和可解释性被广泛应用在工业目标检测与分类建模任务中。孪生支持向量机[8](twin support vector machine，TWSVM)是在SVM的基础上发展而产生的一种新二分类的分类器，与SVM相比提升了3/4的效率，而其中的参数选择对TWSVM的分类效果有着重要影响，因此利用搜索算法与TWSVM结合进行参数寻优是一种可行的方案。粒子群优化搜索算法[9](particle swarm optimization，PSO)以其实现容易、精度高、收敛快等优点在解决实际问题中展示了其优越性，PSO算法与SVM相结合构成的分类器也经常被应用于各种数据分类任务中[10,11]。然而，PSO算法在运算迭代过程中，固定部分参数，容易陷入局部最小问题，并且搜索能力较弱。本文提出一种引入适应值增益反馈和渐变随机扰动的改进型粒子群优化搜索算法(improved particle swarm optimization，IPSO)，并利用IPSO优化TWSVM的参数，构建了IPSO-TWSVM分类模型。通过4个标准基准函数进行仿真，对IPSO的搜索性能进行验证。同时，选取了UCI的4组数据集和Kaggle中的Wine industry数据集对IPSO-TWSVM分类模型进行了测试，计算并比较了分类准确率和平均训练时间两个指标，来验证IPSO-TWSVM在不同数据集上的分类性能和效果。

1 改进的粒子群搜索算法

1.1 基本粒子群搜索算法

粒子群搜索算法是基于鸟类觅食原理产生的一种搜索算法，将优化问题的解空间看作觅食中的鸟群，称之为“粒子”。每一个粒子由优化问题函数决定一个适应值，当前最优适应值即代表当前某种鸟距离食物最近，其余粒子追寻当前最优粒子进行搜索，每个粒子都有一个初始状态、飞行速度和飞行距离。假设对于在随机选择的n个粒子的搜索空间中，第i个粒子在d维上的位置与速度更新公式如下

(1)

Yid=Yid+Vid

(2)

其中，ω称为惯性因子；C1和C2称为加速常数；random(0,1) 表示区间[0,1]上的随机数；Pid表示第i个变量的个体极值的第d维；Pgd表示全局最优解的第d维。其中式(1)、式(2)定义请参见参考文献[9]。

为了限制速度的迭代大小并限定迭代位置的发散性，一般添加以下限制条件

(3)

其中，ω为限定Vid基础值的惯性因子，可以限制每次变化中Vid惯性大小，C1,C2决定了每次速度更新中沿个体最优点与全局最优点方向的前进路线长度。

1.2 改进的粒子群搜索算法

PSO主要存在以下两个问题：第一是限定迭代速度后，全局搜索的速度慢且效率低；第二是在样本多样性较大的情况下，易陷入局部最优而造成过早收敛的情况。针对以上两个问题，本文提出了相应的改进，并分别在1.2.1节和1.2.2节中具体描述。

1.2.1 适应值增益反馈

针对算法全局搜索速度慢的不足的问题，不再将位置更新步长固定，而是利用参数λ来调整位置的更新步长，由此将式(2)写成以下形式

(4)

(5)

(6)

其中，α1、α2和α3分别为第t次、第t-1次和第t-2次的适应值增益系数，μ为历史信息残留，为固定常数。

1.2.2 渐变随机扰动

针对算法易陷入局部最优而造成过早收敛的情况，将渐变随机扰动引入速度迭代式(1)中，渐变随机扰动T的定义如下

(7)

其中，N为设置的最大迭代次数，t为当前迭代次数，Accgbest表示全局最优适应值，Accpbest表示第i个粒子的个人最优解。将渐变随机扰动引入惯性因子ω，ω可改写为如下形式

(8)

(9)

为了进一步防止过早局部收敛，增加以下限制条件

(10)

通过引入适应值增益反馈与渐变随机扰动，IPSO能充分利用适应值变化信息改变迭代步长，并通过扰动项增加粒子随机性，跳出局部最优。

2 IPSO-TWSVM算法

2.1 TWSVM基本原理

孪生支持向量机以广义特征值向量机为基础，分别构造正负两个超平面，要求一类样本点尽量接近，另一类样本尽量远离。基于这个特性，TWSVM对不平衡数据集有着较好的分类性能。工艺生产中的数据来源于各个工艺段，数据一般具有非线性的特点。因此，非线性孪生支持向量机将会在处理过程数据中有更好的分类性能。

非线性孪生支持向量机求解优化问题的具体形式如式(11)、式(12)

min(ω1,b1,
s.t-(K(B,ST)ω1+e2b1)+≥e2,≥0

(11)

(12)

其中，ω1和ω2分别为超平面的法向量，b1和b2分别为超平面的偏移向量，e1和e2是列向量，维度与支持向量一致，c1和c2代表支持向量机惩罚项的系数，S代表样本，和η是支持向量机的松弛变量。其中式(11)、式(12)定义请参见参考文献[8]。

对上述式(11)、式(12)进行求解从而确定两个超平面

K(xT,ST)ω1+b1=0

(13)

K(xT,ST)ω2+b2=0

(14)

式(13)、式(14)分别表示为正负两个超平面。对新样本进行分类时，分别计算样本到两个超平面的距离，从而确定样本类别。离正类超平面近的样本划分为正类，离负类超平面近的样本划分为负类，决策函数如式(15)所示

Classi=min|K(xT,ST)ωi+bi|,i=1,2

(15)

本文选取了RBF作为支持向量机的核函数，可以解决没有先验知识的非线性样本函数，其形式如式(16)所示

(16)

2.2 IPSO-TWSVM算法

TWSVM的分类性能由参数c1、c2和核函数参数γ的选取决定。参数c1和c2选取会影响两个超平面间的距离。参数选取过小，则超平面距离会过近，从而导致分类效果较差；而参数选取过大，则样本本身与超平面之间的距离就会被忽略，从而导致分类准确度降低。核函数参数γ选取过小，则无法保证训练时的准确率，进而影响最终的分类准确率；核函数参数γ选取过大，则会使得TWSVM分类作用样本仅在支持向量附近，虽然样本训练的准确率高但最终的预测率较差。因此，本文利用IPSO算法的搜索能力结合TWSVM，对式(11)、式(12)中的c1、c2和式(16)中的核函数参数γ进行参数寻优，从而提高TWSVM的分类性能。

IPSO-TWSVM算法步骤如下：

Input：公共分类数据集

Output：分类器参数

步骤1 初始化粒子群个数、随机位置、速度和迭代终止条件；

步骤2 以参数c1、c2和核函数参数γ为优化对象训练TWSVM，计算粒子的适应度值，取训练精度的相反数作为适应值；

步骤3 更新全局最优值与当前最优值；

步骤4 判断是否达到迭代终止条件，若没有返回步骤2进行下一轮迭代；

步骤5 选择最终的全局最佳粒子作为TWSVM的参数构建IPSO-TWSVM模型。

3 实验验证

3.1 改进粒子群搜索算法的验证

本文选用了4个标准适应度评估函数来评估所提的 IPSO 算法的性能。表1给出了适应度评估函数的表达式及其搜索区间和最小值，其中函数1和函数4位多峰函数，函数2和函数3位单峰函数，搜索区间即表示函数维度。

表1 测试函数

图1至图4分别为IPSO、PSO和引力搜索算法(gravi-tational search algorithm，GSA)算法对Ackley、Girewank、Rosenbrock、Sphere这4个测试函数的测试结果图。结果表明，IPSO算法能够在前期进行快速收敛，在后期进一步收敛至全局最优点。通过图1可以观察到，对于Ackley函数，当迭代至200次时，GSA算法和PSO算法陷入局部最小且无法继续进行搜索，而改进后的粒子群算法能够继续以较快的速度逼近全局最优。图2至图4可以验证，改进后的粒子群算法具有前期搜索速度快，收敛效果更好的特点。总体来说，IPSO算法对以上4个搜索函数，在前期收敛速度和全局搜索精度上，均优于标准粒子群搜索算法和标准引力算法。

图1 Ackley函数搜索效果

图2 Rosenbrock函数搜索效果

图3 Sphere函数搜索效果

图4 Girewank函数搜索效果

3.2 仿真数据集

为了验证IPSO-TWSVM在不同数据集上的分类性能，选取来自UCI的4组公共数据集和来自Kaggle的Wine industry数据集进行测试。表2给出了不同数据集的样本数量等相关信息。其中，Sonar为高维样本数据集，Breast cancer为大容量样本数据集，Ionosphere和Thyroid为中等规模样本数据集。Wine industry将产品质量一等二等构成优秀标签，其余分为一般标签，从而构成二分类标签，本文从中随机抽取了1000组样本进行训练和预测任务。

表2 公共数据集分析

3.3 实验结果及分析

由于算法与初始随机的粒子好坏有关，为了评估IPSO算法的优越性，本文计算了训练准确率与平均训练时间两个指标。准确率是最终分类正确的样本数与总体样本数的比值，平均训练时间为多次不同的训练过程中训练结果到达90%准确度所需要的时间的多次均值。将IPSO与改进前的PSO 算法与GSA算法进行了比对，分别对TWSVM算法进行参数寻优，并在5个数据集中进行分类任务。GSA算法中，令交叉概率为0.65，变异概率为0.06。PSO算法中固定c1=c2=2，惯性权重取0.8，具体算法实验结果见表3。

通过表3可以看出，利用IPSO对TWSVM进行参数寻优时，该算法在高维、高样本量的数据集上均获得了较高的准确率，且在收敛速度上高于其它两种算法。这是因为在IPSO算法迭代的过程中，加入了适应值增益反馈与随机渐变扰动，可以快速跳出局部最小，从而加快收敛速度，在迭代后期，随机渐变扰动又能够保证算法有更高的精度。特别是针对Wine industry数据集，其准确率高达95.85%，且训练时间为521 s，高于PSO-TWSVM算法和GSA-TWSVM。

表3 算法实验结果

4 结束语

本文通过将适应度反馈和渐变随机扰动融入粒子群算法，提出了一种改进的粒子群搜索算法，利用其对孪生支持向量机进行参数寻优构建分类器。首先利用适应值增益反馈增加前期粒子群搜索算法的快速收敛性，然后将渐变随机扰动引入算法，防止局部最优解并调整迭代后期的粒子位置。4个基准搜索函数上的搜索测试结果表明，本文所提出的IPSO算法在搜索能力上，收敛效果和收敛速度相比于传统标准搜索算法有提高。将改进后的IPSO算法结合TWSVM构成分类器，在5个不同公共数据集上进行测试，验证了IPSO算法参数寻优效果较好，IPSO-TWSVM分类器的准确率与前期收敛速度均高于其它两种算法。