基于粒子群優(yōu)化算法的支持向量機(jī)參數(shù)選擇①

賀心皓， 羅 旭

(成都信息工程大學(xué) 通信工程學(xué)院，成都 610225)

引言

支持向量機(jī)(Support Vector Machines，SVM)是一種應(yīng)用廣泛的機(jī)器學(xué)習(xí)方法，具有理論知識(shí)清晰完備，適應(yīng)性和泛化能力良好的優(yōu)點(diǎn)，核心思想是在特征空間中尋找到一個(gè)最優(yōu)超平面將兩類樣本盡可能大的分開，能夠較好的處理小樣本、非線性和克服“維數(shù)災(zāi)難”問(wèn)題，并且表現(xiàn)出優(yōu)秀的分類能力和泛化能力而被廣泛應(yīng)用于分類和回歸等領(lǐng)域. 但是SVM對(duì)核函數(shù)的參數(shù)選取對(duì)分類效果影響很大，不合適的參數(shù)可能使得分類器性能大大降低.

針對(duì)SVM核參數(shù)的選取問(wèn)題，目前尚沒(méi)有統(tǒng)一有效的方法. 傳統(tǒng)的參數(shù)選擇方法如實(shí)驗(yàn)法、網(wǎng)格搜索法等由于耗時(shí)過(guò)長(zhǎng)和不必要的驗(yàn)證流程等缺點(diǎn)，更常用的方法是群智能算法如蟻群算法、遺傳算法和粒子群算法等優(yōu)化支持向量機(jī)核參數(shù).

粒子群算法由于算法結(jié)構(gòu)簡(jiǎn)單、尋優(yōu)能力相對(duì)較好，近年來(lái)選擇粒子群算法優(yōu)化SVM參數(shù)成為研究熱點(diǎn)之一. 如文獻(xiàn)[1]用標(biāo)準(zhǔn)粒子群算法對(duì)SVM參數(shù)進(jìn)行優(yōu)化，并將該模型應(yīng)用于聚丙烯腈生產(chǎn)的軟測(cè)量模型中，通過(guò)與標(biāo)準(zhǔn)SVM比較，證明了所提方案有效性;隨著研究深入，標(biāo)準(zhǔn)PSO算法在應(yīng)用過(guò)程中暴露出不少的缺點(diǎn)，如易陷入局部最優(yōu)值、后期收斂的速度較慢等缺點(diǎn)，因此研究者也對(duì)其提出不少改進(jìn)方法，如文獻(xiàn)[2-4]等通過(guò)改進(jìn)慣性權(quán)值，或者改變學(xué)習(xí)機(jī)制等方法以提高粒子群算法性能.

本文通過(guò)引入非線性慣性權(quán)值遞減和異步線性變化的學(xué)習(xí)因子策略改進(jìn)粒子群算法，并且通過(guò)機(jī)器學(xué)習(xí)公開數(shù)據(jù)集UCI數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)證明了其有效性.

1 支持向量機(jī)基本思想和參數(shù)

支持向量機(jī)是由Vapnik等人在1995年提出的基于統(tǒng)計(jì)學(xué)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的機(jī)器學(xué)習(xí)方法，其基本思想是找到一個(gè)分類面將兩類樣本分開. 當(dāng)線性可分時(shí)，其最優(yōu)的分類面要求正確地將樣本分開且分類間隔最大; 當(dāng)線性不可分時(shí)，尋找一個(gè)多維超平面從而將樣本分開.

對(duì)于訓(xùn)練樣本集：(x1,y1),(x2,y2),···,(xN,yN),x∈Rn,y∈(-1,1)最優(yōu)分類超平面的二次規(guī)劃問(wèn)題如下：

其Lagrange函數(shù)為：

式中，λi≥0,i=1,2,···,N. 式(1)的對(duì)偶問(wèn)題可表示為：

可得決策函數(shù)為：

對(duì)線性不可分的對(duì)偶函數(shù)為：

式中，φxi×φxj=K(xi,xj)即為核函數(shù)，其決策函數(shù)為：

不同的核函數(shù)可以生成不同的支持向量機(jī)分類器，SVM中常用的核函數(shù)有線性核、多項(xiàng)式核、徑向基核和Sigmoid核函數(shù)等. 本文選擇徑向基核函數(shù)作為SVM的核函數(shù)，即：

影響核函數(shù)的參數(shù)有懲罰銀子C和核函數(shù)σ，懲罰因子C是對(duì)錯(cuò)分的樣本的懲罰程度的控制，越大表示懲罰越重，但其泛化能力也會(huì)同時(shí)降低. σ是核函數(shù)的寬度參數(shù)，表示對(duì)徑向范圍的控制. 懲罰因子C和核函數(shù)σ的選取對(duì)SVM分類器影響至關(guān)重要，因此要獲得優(yōu)秀的支持向量機(jī)的分類性能，需要選取合適的C和σ[5].

2 改進(jìn)粒子群算法優(yōu)化SVM

2.1 粒子群算法概述

粒子群算法是基于對(duì)鳥類的捕食過(guò)程進(jìn)行模擬的一種新型智能仿生優(yōu)化算法. 該算法把群體中的個(gè)體視為多維空間中的一個(gè)沒(méi)有質(zhì)量和體積的點(diǎn)，且以一定的速度飛行，在此迭代過(guò)程中根據(jù)自身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)對(duì)自身的飛行速度進(jìn)行動(dòng)態(tài)調(diào)整以修正前進(jìn)方向和速度大小. 粒子群算法就是通過(guò)每個(gè)粒子由適應(yīng)度函數(shù)調(diào)整粒子至較優(yōu)的區(qū)域以搜尋到問(wèn)題的最優(yōu)解.

PSO初始化一群隨機(jī)粒子(粒子不考慮質(zhì)量和體積)，粒子在N維空間位置表示為矢量xi=(x1,x2,···,xn)，飛行速度表示為矢量vi=(v1,v2,···,vn)，每個(gè)粒子都有一個(gè)由目標(biāo)函數(shù)確定的適應(yīng)值(fitness value)，其個(gè)體最好位置pbest值和整個(gè)群體中發(fā)現(xiàn)的最好的位置gbest值以及當(dāng)前位置，通過(guò)迭代找到最優(yōu)解，在每次迭代中粒子通過(guò)pbest值和gbest值來(lái)更新自己.

式中，pbest表示粒子i是個(gè)體最優(yōu)值，gbest表示粒子群的全局最優(yōu)值; C1和C2是兩個(gè)常數(shù)，稱為學(xué)習(xí)因子;r1，r2是0到1的隨機(jī)數(shù); w被稱為慣性因子，w的值越大，全局尋優(yōu)能力越強(qiáng)，收斂越慢，w值越小，局部尋優(yōu)能力越強(qiáng)，收斂較快.

2.2 粒子群優(yōu)化算法和支持向量機(jī)參數(shù)選擇

慣性權(quán)重是粒子群算法中一個(gè)重要的參數(shù)之一，它控制了全局搜索能力和局部搜索能力的平衡. 傳統(tǒng)的粒子群算法有一些缺點(diǎn)，如容易陷入局部最優(yōu)值和后期震蕩和收斂速度慢等，國(guó)內(nèi)外學(xué)者對(duì)算法的改進(jìn)展開了研究. 文獻(xiàn)[6]提出慣性權(quán)重進(jìn)行了研究，提出慣性權(quán)重w從0.9至0.4的線性遞減的策略能夠保證有更好的全局搜索能力和后期的局部搜索能力; 文獻(xiàn)[7]在遞減的慣性權(quán)值的基礎(chǔ)上，提出了拋物線和指數(shù)曲線的非線性的權(quán)值遞減策略; 文獻(xiàn)[8]提出一種慣性權(quán)重線性遞增的粒子群算法; 文獻(xiàn)[9]提出一種慣性權(quán)重先增后減的粒子群算法; 文獻(xiàn)[10]提出一種非線性遞減的慣性權(quán)重粒子群算法; 文獻(xiàn)[11，12]提出了慣性權(quán)重指數(shù)遞減和余弦遞減的粒子群算法; 文獻(xiàn)[13]提出了一種慣性權(quán)值隨粒子的位置和目標(biāo)函數(shù)性質(zhì)變化的動(dòng)態(tài)改變慣性權(quán)重的粒子群算法等.

1) 具有非線性遞減慣性權(quán)重粒子群算法

本文使用非線性遞減權(quán)值策略將慣性權(quán)值w設(shè)置為變量，通過(guò)非線性遞減權(quán)值實(shí)現(xiàn)粒子的調(diào)整，(當(dāng)n=1時(shí)，即Shi提出的線性遞減慣性權(quán)重策略)，其公式如下：

式中，wini、wend分別為w的最大值和最小值，i表示當(dāng)前迭代次數(shù)，imax表示最大迭代次數(shù)，n是指數(shù)值.

2) 異步線性改變學(xué)習(xí)因子策略

由標(biāo)準(zhǔn)粒子群算法公式(8)可知，C1控制了“自我認(rèn)知”部分，即粒子自身之前的飛行經(jīng)驗(yàn)對(duì)之后飛行方向的影響，C2控制了“社會(huì)認(rèn)知”部分，即種群中所有粒子的飛行經(jīng)驗(yàn)對(duì)每個(gè)粒子之后飛行方向的影響. 在標(biāo)準(zhǔn)粒子群算法中，Shi等建議C1和C2都取值為2，在其他文獻(xiàn)中有學(xué)者也提出C1和C2可以取不同的值，其取值也基本在0至4之間.

學(xué)習(xí)因子在過(guò)程中采用不同的變化策略稱之為異步變化. A.Ratnawecra等提出了一種異步線性改變學(xué)習(xí)因子的策略[14]，該策略是在算法早期階段C1取值較大而C2取值較小，使粒子能夠更多地向自我的學(xué)習(xí)以此加強(qiáng)全局搜尋能力; 在搜尋的后期階段C2取值較大，使粒子能夠快速收斂到全局最優(yōu)解. 學(xué)習(xí)因子的更新公式如下：

式中，c1ini、c2ini分別表示學(xué)習(xí)因子的初始值; c1fin、c2fin分別表示學(xué)習(xí)因子的迭代最終值; t和Tmax分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù).

綜上所述，本文引入非線性遞減慣性權(quán)重和異步線性改變學(xué)習(xí)因子的粒子群優(yōu)化算法，用以尋找SVM模型中的懲罰因子C 和核函數(shù)參數(shù)σ最優(yōu)解，每個(gè)粒子的位置代表為(C，σ).

其算法流程如下，

① 初始化參數(shù)設(shè)置，包括設(shè)置粒子種群規(guī)模、粒子維數(shù)、最大迭代次數(shù)、慣性權(quán)重最大值和最小值和指數(shù)值、加速因子初始值和迭代最終值、隨機(jī)產(chǎn)生粒子初始位置和速度、個(gè)體極值和全局極值.

② 根據(jù)式(8)～式(10) 更新每個(gè)粒子的速度和位置.

③ 根據(jù)適應(yīng)度函數(shù)計(jì)算粒子的適應(yīng)度值.

④ 將粒子的當(dāng)前適應(yīng)度值和粒子個(gè)體極值進(jìn)行比較，若優(yōu)于粒子個(gè)體極值，則進(jìn)行替換.

⑤ 若當(dāng)前粒子的適應(yīng)度值優(yōu)于全局極值的適應(yīng)度值，則用當(dāng)前粒子適應(yīng)度值替換全局極值.

⑥ 若達(dá)到最大迭代次數(shù)，則輸出迭代出的最優(yōu)解(C，σ)，輸出; 否則返回至步驟② .

⑦ 將優(yōu)化后的C和σ利用SVM分類器進(jìn)行訓(xùn)練，并用文本測(cè)試集進(jìn)行測(cè)試.

本算法優(yōu)化過(guò)程圖如圖1所示.

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)所用硬軟件環(huán)境信息如下，AMD A6-3420M APU with Radeon (tm)，RAM 4 GB (含一2 GB samsung內(nèi)存條)，Windows 8 64位，平臺(tái)為Matlab R2014a.

為了驗(yàn)證本文提出的粒子群優(yōu)化的支持向量機(jī)分類模型的有效性，本文選取了機(jī)器學(xué)習(xí)公開數(shù)據(jù)集UCI的4組數(shù)據(jù)進(jìn)行測(cè)試，下載地址如下：http：//archive.ics. uci.edu/ml/datasets.html.

圖1 粒子群優(yōu)化算法的過(guò)程

3.1 實(shí)驗(yàn)參數(shù)設(shè)定

在參考大量文獻(xiàn)之后[1，5-7，15]，本文對(duì)粒子群參數(shù)作出如下合理設(shè)置. 種群規(guī)模N=20，最大迭代次數(shù)Tmax=100，懲罰因子C最小值Cmin=2-5，最大值Cmax=215，誤差閾值為10-3，核參數(shù)σ的最小值σmin=2-15，最大值σmax=23，慣性因子最小值wend=0.4，慣性因子最大值wini=0.9，非線性遞減慣性權(quán)重粒子群算法中的指數(shù)n=1.2，C1ini=2，C1fin=0.5，C2ini=0.5，C2fin=2; 標(biāo)準(zhǔn)粒子群算法的w=0.9，C1=C2=2;

3.2 實(shí)驗(yàn)結(jié)果

在表1的數(shù)據(jù)集通過(guò)采用K折交叉驗(yàn)證法(Kfold cross validation)，即把表1中的每個(gè)樣本數(shù)據(jù)隨機(jī)地分為K個(gè)子樣本集，每次都去一個(gè)子樣本集作為測(cè)試集，剩余K-1個(gè)樣本集作為訓(xùn)練集，以此進(jìn)行驗(yàn)證.

表1 實(shí)驗(yàn)數(shù)據(jù)信息

如下表2所示，通過(guò)標(biāo)準(zhǔn)粒子群優(yōu)化支持向量機(jī)算法[1]和本文提出粒子群優(yōu)化算法在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，表中的最大值、最小值和平均值表示經(jīng)過(guò)了10-fold CV交叉驗(yàn)證后的分類準(zhǔn)確率的最大值、最小值和平均值. 圖2為兩種算法在數(shù)據(jù)集上的準(zhǔn)確率平均值對(duì)比圖.

表2 兩種算法在數(shù)據(jù)集上的交叉驗(yàn)證結(jié)果對(duì)比

圖2 兩種算法的準(zhǔn)確率均值對(duì)比圖

4 結(jié)論

支持向量機(jī)模型的分類精確率很大程度上由關(guān)鍵參數(shù)的選取決定，本文引入非線性遞減慣性權(quán)重和異步線性變化的學(xué)習(xí)因子策略. 隨著迭代次數(shù)增加，學(xué)習(xí)因子C1的值減小而C2值增加，保證了前期個(gè)體最優(yōu)質(zhì)影響和后期全局最優(yōu)解的影響，加快后期的收斂; 而非線性遞減慣性權(quán)重在保證粒子在迭代初期對(duì)整個(gè)搜索空間能進(jìn)行快速搜索，隨著慣性權(quán)重非線性減小能使大部分搜索范圍集中于最優(yōu)值鄰域中，使搜索速度和精度都有提高. 實(shí)驗(yàn)結(jié)果表明，非線性遞減慣性權(quán)重和異步線性改變學(xué)習(xí)因子粒子群算法優(yōu)化支持向量機(jī)比標(biāo)準(zhǔn)粒子群優(yōu)化的支持向量機(jī)有更高的分類精確度和效率.