混合核函数支持向量机的参数优化算法研究*

许少榕

(福州职业技术学院文化创意系，福建 福州 350108)

混合核函数支持向量机的参数优化算法研究*

许少榕

(福州职业技术学院文化创意系，福建 福州 350108)

本文研究支持向量机混合核函数参数优选问题，提出将量子进化算法和粒子群算法相结合，得到一种新型混合核函数支持向量机参数优选算法.提出了两种基于收敛因子的优化策略改进量子粒子群算法，改进了量子粒子群算法存在发散和早熟收敛，无法准确搜索全局最优解的难题，避免了算法早熟收敛问题，确保量子粒子群算法能够在全局准确搜索到核函数最优参数，最后通过仿真实验，证明该优化算法可有效避免早熟收敛，提高了向量机预测精度.

支持向量机；混合核函数；参数优选；量子粒子群算法

引言

自机器学习诞生之日起，人们就致力于模拟和提高计算机通过学习过往数据和经验获取认知规律并进行预测的学习能力，统计学的发展为解决上述基于数据的机器学习问题提供了重要的研究方法并且发挥了不可替代的作用[1].以统计学习理论为基础旨在解决小样本集、非线性、复杂高维数等机器学习实际问题的支持向量机(Support Vector Machine，SVM)，以其结构简单、易推广以及解决小样本问题时突出优势的特点，受到了广大学者广泛关注和研究，并取得了丰硕的成果.

在研究采用支持向量机算法解决实际问题时，核函数是研究的重中之重，合理选择核函数是解决小样本学习问题的关键[2].这是因为选择恰当的核函数可以同时提高算法的学习能力和泛化能力.目前被广泛采用的单核函数主要有线性核函数、多项式核函数、高斯核函数和径向基核函数等，基于单核函数自身性能的局限和应用背景，其无法胜任全部的机器学习问题场合[3].因此，很多学者致力于研究将不同的单核函数结合，组成混合核函数支持向量机，应用于复杂机器学习场合和同时对学习能力及泛化能力要求较高的场合，并且取得了极大成功，产生了很多研究成果.研究成果表明混合核函数的参数选择对于支持向量机的性能具有至关重要的作用.然而诸多文献都只指出支持向量机采取混合核函数时优于单核函数，而没有构建出一套完整的参数优选方法体系[4～7].

为了优化支持向量机的性能，必须采用合理的智能算法对混合核函数的参数进行优选.针对传统粒子群算法(PSO)在样本空间进行寻优迭代时易发生早熟收敛，不能精准搜索到全局最优值的问题，本文提出将兼容性极强且易于和其它进化计算方法结合的量子进化算法与粒子群算法相结合，构造出一种量子粒子群算法，将其应用于混合核函数的参数优化选择，在小样本空间进行与传统算法对比的仿真实验，结果表明，这种算法能够更合理的优化核函数的参数，提高支持向量机的性能.

本文所述量子粒子群算法暴露出的算法发散和早熟收敛问题，针对此，提出两种基于收敛因子的优化量子粒子群算法策略，克服算法的早熟收敛问题，确保量子粒子群算法能够在核函数参数寻优选择过程中保持收敛，精确搜索到最优解.将采用优化量子粒子群算法优选参数的核函数应用于支持向量机，进行仿真实验，实验结果表明，采用本文提出的核函数参数优化算法对参数进行寻优，可以有效避免传统量子粒子群算法寻优过程中早熟收敛问题，快速精确确定最优核函数参数，采用该算法的支持向量机具有更好的性能.

1 支持向量机的混合核函数

1.1支持向量机算法原理

SVM基本原理是通过某种非线性变换函数φ(x)，将样本空间中{(xi,yi)}(i=1,2,…m)输入量xi∈Rn映射到某一高维特征空间Z，在Z空间中搜索支持向量，并用支持向量构造最优分类超平面[8].在高维空间构造的分类决策最优线性函数为：

f(x)=sign(ωT·φ(x)+b)

(1)

根据最小化结构风险原则，参数ω,b可通过式(2)最小化得到最初问题为:

(2)

式中C是参数可调的惩罚因子，其取值越大表示对错误分类惩罚越大.对式(2)的问题求解可以通过拉格朗日公式转化成式(3)的对偶求解问题：

(3)

式中ai为非负拉格朗日因子，其中所应用的非线性变换函数称为核函数K，可定义为：

K(x,xk)=φ(xi)T·φ(xi)

(4)

通过选择合适的核函数，联立式(3)和(4)，对偶问题化为

(5)

再通过对偶问题(3)的求解，可得到

(6)

于是，最终可以得到最优线性决策函数为：

(7)

1.2混合核函数

支持向量机的核心即是核函数的确定和选择.通常把能够满足Mercer定理的对称函数K(x,xi)定义为核函数.

Mercer定理：要保证任意的对称函数K(u,v)能以正的系数ak>0展开成：

(8)

(10)

多项式核函数(Poly)：

(11)

径向基核函数(RBF)：

(12)

反正切核函数：

(13)

在实际应用中，为了兼顾改善学习能力和泛化能力，常常选择两种单核函数按特定的权重构建出混合核函数如式(14)所示：

Kmix=ρKpoly+(1-ρ)KRBF

(14)

2 基于量子粒子群优化参数的支持向量机

2.1量子粒子群算法

为了优化支持向量机的性能，必须采用合理的智能算法对混合核函数的参数进行优选[10].针对传统粒子群算法(PSO)在样本空间进行寻优迭代时易发生早熟收敛，不能精准搜索到全局最优值的问题，本文提出将兼容性极强且易于和其它进化计算方法结合的量子进化算法融合进粒子群算法，构造出量子粒子群算法(Quantum Particle Swarms Optimization, QPSO)应用于混合核函数的参数优化选择，该算法特点是采用量子位编码定义粒子的当前位置，再由量子旋转门搜索确定粒子最优位置，其算法具体操作如下：

首先利用量子位概率幅Qi进行粒子初始位置的编码:

(15)

(16)

通过上述变换即实现了从粒子位置到问题最优解的转换，因此每一个量子位对应优化问题的两个解.

设粒子qi当前空间寻优求解所经历的最优位置为余弦位置，即：

Qil=(cos(θil1),cos(θil2),…,cos(θiln))

(17)

种群全部粒子所经历的最优位置也记为余弦位置：

Qg=(cos(θg1),cos(θg2),…,cos(θgn))

(18)

由式(17)和(18)得到粒子Qi上量子幅角变化量如下式(19)所示：

Δθij(t+1)=ωΔθij(t)+c1(Δθl)+c2(Δθg)

(19)

由此推出量子旋转门如下式为：

(20)

同理通过基于量子旋转门幅角更新公式最终求得采用于量子粒子算法的粒子Qi的两个更新位置分别为：

(21)

(22)

上述基本量子粒子群算法流程如图1所示，分析可知，在QPSO中，一个量子粒子对应于解空间中两个解，即可同时实现解空间中两个位置移动，因此在支持向量机核函数参数优选中采用量子粒子群算法能够优化种群粒子寻址空间搜索效率，提高算法优化参数能力[11].

图1 量子粒子群算法流程图

2.2采用量子粒子群优化核函数参数的支持向量机

为了发挥最佳的机器学习能力和达到更好的预测效果，本文采用基于混合核函数的支持向量机模型进行分类预测仿真实验，并将量子粒子群算法应用于核函数最佳参数寻优，得到基于量子粒子群的混合核函数支持向量(GAPSO-CSVM)，通过红酒分类识别实验来检测采用GAPSO-CSVM的性能.为检验本文提出的量子粒子群算法最优核函数优点和特性，分别对采用BP算法、传统粒子群算法和量子粒子群算法核函数的三种支持向量机进行红酒分类问题仿真实验，实验的数据集中共有178个样本，每个样本中包含14个数据，其中输入数据为13维，依次代表着红酒的酒精浓度、苹果酸含量、杂质含量百分百等，而输出数据只有一个，既红酒种类的标识码.实验首先采取5个样本作为训练集，然后将整个数据集的178个样本全部作为测试集，设定种群含有20个粒子，每个粒子都为5维，其所包含的数据分别为：混合核函数权重系数ρ，RBF核函数的参数δ，PLOY函数的参数d、γ和ζ.分别采用上述三种不同算法对红酒种类识别问题进行20次仿真实验，实验过程中采取每做完5次实验就暂停1次，然后将训练样本重新随机选择，保持训练集大小不变,最后得到采用三种参数优化算法支持向量机的分类实验准确率[12]，结果如图2和表1所示.

图2 BP、SVM、QPSO-SVM算法仿真结果图

算 法最高准确率最低准确率平均准确率迭代终止次数BP89.33%87.63%88.60%30PSO-SVM91.01%89.32%90.20%35QPSO-CSVM94.38%92.70%93.57%20

分析图2和表1可以看出，基于QPSO参数优选算法的支持向量机的最高、最低和平均分类准确率都高于另外两种算法，同时，由于量子算法的优点和特性，采用该算法终止迭代次数明显减少，其具有更好的学习能力和泛化能力.说明相较于另外两种参数优选算法，量子粒子群算法可以进一步提高了参数优化效率，得到预测精度和稳定性更高的最优核函数.分析上述实验结果可以得知，量子粒子群参数优选算法在小样本数训练集具备高准确率和更少迭代次数的优点，而实际应用中可能遇到大样本空间参数优化求解问题，针对寻址空间样本数增加时，量子粒子群算法是否依然能够延续优异的性能，下面依次增加训练集样本数，进行仿真实验.实验将训练集样本数量依次定为99，135和178.利用QPSO-CSVM算法拟合出函数模型，进行与前面完全一致的实验，结果如图3所示.

图3 增加训练集样本数时，量子粒子群算法支持向量机的分类准确率

分析对比图2和图3中采用量子粒子群算法核函数的支持向量机分类准确率可知，随着训练集样本数由55依次增加大95、130和177过程中，最高分类准确率与最低分类准确率差值也逐渐由0.56%升高到1.12%，即随训练集样本数的加大，算法分类准确率呈下降趋势，这表明采用QPSO算法对核函数参数进行优选时，种群粒子陷入早熟收敛问题.

3 基于收敛因子改进量子粒子群

为了消除QPSO早熟收敛，可将收敛因子应用于QPSO，通过收敛因子优化调整PSO中粒子状态的更新，提高收敛速度和全局搜索能力[13].收敛因子表达式如下式(23)所示：

(23)

式中：κ∈[0,1]，φ=φ1+φ2，φ的取值对于算法的收敛具有至关重要的作用.通过收敛因子得到粒子速度、位置更新公式如下式(24)所示：

Vi(t+1)=χ(Vi(t)+φ1c1(Pi-Xi(t))+φ2c2(Pg-Xi(t)))
Xi(t+1)=Xi(t)+Vi(t+1)

(24)

式中，pi(t)-φ1c1(Pi-Xi(t))+φ2c2(Pg-Xi(t))为第i个粒子的局部吸引因子，粒子在全局寻优搜索过程中，会持续快速的向着局部吸引子靠近.

3.1早熟收敛的评价准则

引入收敛因子克服早熟收敛，可以提高量子粒子群算法优化核函数参数的效率，因此要进行参数优化效果评价就必须先定义相应的早熟收敛的评价准则[14]：

在QPSO算法寻优迭代过程中，当迭代次数为k次，仍没有搜索到全局最优值，且种寻址空间内所有粒子位置和速度都满足下式(25)：

(25)

式中，e1>0,e2>0i=1，2，…，m；j=1，2，…n.

就判定算法陷入了早熟收敛.

3.2基于收敛因子改进量子粒子群算法

3.2.1 基于全新寻址搜索模式克服早熟收敛的优化策略

利用QPSO算法进行参数寻优求解时，种群多样性的减少是造成算法无法准确搜索到全局最优解的重要原因.因此可以采取在算法出现早熟收敛时，立即重新初始化粒子种群、Pil和Pg，对种群进行重新搜索[15].针对QPSO算法中粒子速度和位置更新都在每一维进行操作，将量子粒子的每一维的幅角都在[-2π,2π)]区间上进行独立且均匀分布的初始化操作，以m个边长为r的子空间组成初始化空间，

(26)

式中，j=1，2，…m，θmax=2π，θmin=0.01π.早熟收敛一旦出现，即对粒子在寻址空间搜索到的最优位置重新初始化，使种群在寻优空间重新搜索最优解，直到满足收敛条件，判定搜索到全局最优解，迭代终止,此为改进的量子粒子群算法QPSO1.

3.2.2 基于全干扰交叉模式克服早熟收敛策略

利用量子粒子优化求解过程可以采用量子交叉门，根据每个量子粒子不同下标，对种群进行概率交叉操作，进而对整个量子粒子种群进行重新排列.设交叉概率为ρc，在迭代过程中，产生随机数r，若r>ρc,则依照表2所示对种群粒子进行交叉操作，否则不进行交叉.

表2 量子全干扰交叉

分析表2可知，在进行交叉操作时，整个粒子种群数量和数据保持不变，仅仅是量子粒子排列顺序发生变化，其变化规律可归纳为下式(27)所示：

(27)

式中i′和j′分别表示新的量子种群中，粒子新的横、纵坐标，i和j分别表示原量子种群中，粒子的横、纵坐标，n表示染色体种群的纵坐标最大值.具体操作为，一旦概率超过设定值时，就通过进行交叉操作得到新的量子种群.由此得到新的寻优算法定义为QPSO2.

3.2.3 两种改进量子粒子群算法的仿真实验

为了检验本文所述基于克服早熟收敛策略所产生的核函数优化算法的性能，分别利用QPSO算法和改进的QPSO1、QPSO2算法对Griewank函数进行定义域xi∈(-5.25,5.25)上的最小值点及其对应的函数值的求解仿真实验，Griewank函数的表达式如下所示

(28)

Griewank函数在三维空间中的特征如图4所示，该函数是一个多极值函数，在定义域xi∈(-5.25,5.25)中，具有多个极大值点和极小值点.因此在作用域对该函数求解，会有多个局部最优解，而全局最优解为一个“0”向量.基于此，该函数可作为检验算法性能的指标.

分别采用QPSO算法、QPSO1和QPSO2对Griewank函数在10维空间中进行50次求解，粒子种群都取20，优化迭代上限次数为2 000次，设定当f(x)≤0.01时，迭代终止，分析表3所示仿真结果可知，在50次的仿真过程中，QPSO1和QPSO2算法相较于QPSO算法可以更大概率地求解出最优解.表明QPSO1算法和QPSO2算法具有较好的避免早熟收敛的能力，同时具有更好的搜索能力.进一步分析比较算法QPSO1和QPSO2可以发现，QPSO1算法相对QPSO2算法有一定的概率可以更快的搜索到最优值，而QPSO2算法则能够搜索到更精准全局最优解，且所用的平均时间会相对较小.

图4 Griewank函数三维空间特征

4 基于改进QPSO优化核函数参数的支持向量机仿真实验

将QPSO、QPSO1和QPSO2算法应用到混合核函数支持向量机，分别采用这三种算法对混合核函数参数进行寻优，利用优化参数的CSVM进行和上文相同的红酒分类实验，并以支持向量机最终分类准确率作为核函数参数性能评价指标.

QPSO-CSVM、QPSO1-CSVM以及QPSO2-CSVM的仿真实验参数与前文相同，样本数分别为55、95、130、178，采用三种不同算法共进行20次迭代，得到面对不同训练集时的分类能力如图5(a)、(b)、(c)、(d)所示.分析图5所示算法分类准确率可知，首先，当增加训练集样本数时，三种算法的分类准确率都有所提高.而当训练集样本为整个数据集时，QPSO1-CSVM和QPSO2-CSVM的分类准确率甚至达到了100%.其次，分析单独一种训练集下三种算法的分类准确率可知，基于QPSO的CSVM算法的分类准确率最差的；QPSO2-CSVM算法的分类准确率最好的，最后，对比分析基于QPSO1和QPSO2的CSVM分类准确率结果可以发现，采用QPSO1算法的支持向量机总体具有较好的分类准确率，但分析整个20次仿真实验数据，可发现其分类准确率并不相同.

综上分析可知，在对混合核函数参数进行寻优的过程中，两种基于改进的QPSO算法相较于传统QPSO算法更容易收敛到全局最优解，提高核函数参数优选效率，优化支持向量机学习能力和泛化能力.并且基于QPSO2支持向量机，相较于基于QPSO1支持向量机性能更好，说明QPSO2参数优化算法比QPSO1算法参数寻优搜索时间更短，求解到更优核函数.

表3 QPSO、QPSO1、QPSO2仿真结果

图5 不同训练集，三种算法的性能对比

5 结语

本文提出一种将量子进化算法和粒子群算法相结合的量子粒子群算法，并将其应用到支持向量机参数优化中，该算法发挥QPSO(量子粒子群算法)的函数优化功能，对支持向量机核函数参数寻优求解，快速准确地搜寻并求解得到最优核函数，使支持向量机在小样本数集具有更好的性能.

由于传统量子粒子群算法具有算法发散和早熟收敛的缺陷，在训练集样本数增加时，核函数参数优选不能准确搜索到最优解，本文又提出两种基于收敛因子改进量子粒子群算法QPSO1和QPSO2，并将两种改进量子粒子群算法应用于的支持向量机核函数参数优选，利用基于QPSO1和QPSO2的支持向量机对红酒酒类识别进行了仿真实验，并与传统QPSO支持向量机进行了对比，结果表明，两种基于改进的QPSO算法相较于传统QPSO算法更容易收敛到全局最优解，提高核函数参数优选效率，优化支持向量机学习能力和泛化能力.并且，基于QPSO2支持向量机相较于基于QPSO1支持向量机性能更好，说明QPSO2参数优化算法比QPSO1算法参数寻优搜索时间更短，求解到更优核函数.

[1]Rodger J A. A fuzzy nearest neighbor neural network statistical model for predicting demand for natural gas and energy cost savings in public bulidings[J].Expert Syst，2014,41(4)：1813-1829.

[2]Wang Q,Zhu H,Wu W,et al. Inshore ship detection using high-resoution synthetic aperture radar images based on maximally stable extremal region[J]. Journal of Applied Remote Sensing,2015,9(1):94-95.

[3]高艳云，庞敏.基于最小流形类内离散度的支持向量机[J].计算机应用研究，2015,32(9):2639-2642.

[4]Singh A K,Shukla V P,Tiwari S,et al. Wavelet based histogram feature descriptors for classification of partially occluded object[J]. International Journal of Intelligent Systems and Applications,2015,7(3):54-61.

[5]单黎黎，张宏军，王杰，等.一种改进粒子群算法的混合核ε -SVM 参数优化及应用[J].计算机应用研究，2013,30(6)：1636-1639.

[6]Wang X,P ardalos P M. A survey of support vector machines with uncertainties[J].Annals of Data Science,2015,1(4):293-309.

[7]栾咏红,刘全.Twin-SVM 和 Twin-KSVC标志物检测与分类方法[J].计算机工程与设计, 2016,37(12): 3306-3310.

[8]Rani S,Syed D. Categorization of video using viola jones and fisher linear discriminant function[J].Biometrics and Bioinformatics ,2015,7(4):110-113.

[9]Yin S,Ouyang P,Liu L, et al. Fast traffic sign recognition with a rotation invariant binary pattern based feature[J].Sensors,2015,15(1):2161-2180.

[10]Shamshirband S,Petkovic D,Hashim R,et al. An appraisal of wind turbine wake models by adaptive neuro-fuzzy methodology[J].Int J Elect Power Energy Syst,2014,63(5):618-624.

[11]苗超维，秦品乐.基于多分类SVM和Hd的目标跟踪算法[J].计算机工程与设计，2016,37(11):3118-3123.

[12]马家辰，武冠群 ，马立勇，等.基于细菌觅食算法和支持向量机的表情识别[J].计算机工程与设计, 2015,36(7): 1881-1885.

[13]蔡世清，周杰.基于支持向量机的多传感器数据融合算法[J].计算机工程与设计, 2016,37(5): 1352-1356.

[14]丁胜锋，孙劲光.基于混合模糊隶属度的模糊双支持向量机研究[J].计算机应用研究，2013,30(2):432-435.

[15]Nouaouria N，Boukadoum M． Improved global-best particle swarm optimization algorithm with mixed-attribute data classification capability[J].Applied Soft Computing，2014，21: 554-567．

ResearchonParameterOptimizationAlgorithmofHybridKernelFunctionSupportVectorMachines

XU Shao-rong

(Department of Cultural Creativity, Fuzhou Polytechnic, Fuzhou Fujian 350108, China)

This paper studies the parameter selection of hybrid kernel function of support vector machines. A new hybrid kernel function support vector machine parameter optimization algorithm is proposed by combining quantum evolutionary algorithm with particle swarm optimization. It puts forward two improved quantum particle swarm optimization algorithm based on convergence factor and avoids the problem of premature convergence to ensure that the quantum particle swarm algorithm can accurately search the global optimal kernel function parameters. Simulation test results show that the optimization algorithm can effectively avoid premature convergence and improve the prediction accuracy of vector machines.

support vector machine; hybrid kernel function; parameter optimization; quantum particle swarm algorithm

1673-2103(2017)05-0020-09

2017-04-06

许少榕(1982-)，女，福州闽侯人，硕士，实验师.研究方向：计算机技术及实验室管理.

TP18

A