一種改進(jìn)型PSO算法在SVM參數(shù)尋優(yōu)中的應(yīng)用

房樂(lè)楠，何騰鵬，劉宇紅

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025)

20世紀(jì)90年代，Vapnik等人首提支持向量機(jī)(Support Machine Vector，SVM)算法，該算法在小樣本、非線性和高維模式分類(lèi)中表現(xiàn)出特有的優(yōu)勢(shì)，因此得到了廣泛的應(yīng)用[1]。SVM作為一種機(jī)器學(xué)習(xí)算法的主要優(yōu)勢(shì)是泛化能力強(qiáng)，預(yù)測(cè)精度高，由于其獨(dú)特的核函數(shù)機(jī)制，對(duì)非線性問(wèn)題有著良好的逼近能力，但核函數(shù)對(duì)參數(shù)選取十分敏感，如何選取最優(yōu)參數(shù)決定了SVM分類(lèi)器的性能，針對(duì)SVM算法參數(shù)尋優(yōu)問(wèn)題，目前引入了諸多仿生算法如遺傳算法、粒子群(Particle Swarm Optimization，PSO)算法、蟻群算法等[2]。

本文基于對(duì)PSO算法的研究，針對(duì)PSO算法在粒子搜索過(guò)程中易陷入局部最優(yōu)的缺點(diǎn)，提出一種應(yīng)用非線性慣性權(quán)重策略并引入雙變異算子(邊緣變異算子和全局變異算子)的改進(jìn)型PSO算法，并將其應(yīng)用于SVM參數(shù)尋優(yōu)中。

1 SVM算法理論

SVM算法的主要思想是以統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ)，可以概括為兩點(diǎn)：(1)努力結(jié)構(gòu)風(fēng)險(xiǎn)最小化，尋找最大化分類(lèi)間隔以控制VC維，并使之最小，因而具有很強(qiáng)的泛化能力；(2)引入核函數(shù)和松弛變量技術(shù)，處理樣本線性不可分問(wèn)題[3]。

SVM算法解決樣本線性不可分問(wèn)題的主要思想是：通過(guò)非線性映射將低維線性不可分樣本映射到高維特征空間，進(jìn)而在高維特征空間進(jìn)行線性分類(lèi)。假設(shè)訓(xùn)練樣本是Di=(xi,yi)其中：xi∈Rn,yi∈{-1,1},i=1,2,3…m,定義一個(gè)樣本點(diǎn)到超平面的距離：

L=y1[(wx1+b)]

(1)

SVM分類(lèi)可表示為：

f(x)=sgn[∑wφ(x)+b]

(2)

其中，sgn(·)是符號(hào)函數(shù),w∈Rn,b∈R。

在高維空間進(jìn)行線性分類(lèi)是一個(gè)尋找最大化幾何間隔的過(guò)程，其數(shù)學(xué)實(shí)質(zhì)是求解凸優(yōu)化問(wèn)題[4]，即

(3)

yi[(wxi+b)]≥1-ξi

(4)

ξi≥0

(5)

其中，i=1,2,3,…,m是樣本數(shù)；c是懲罰因子；ξi是松弛變量。

方程(2)可以轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題，所以分類(lèi)函數(shù)可以寫(xiě)成

(6)

其中，αi為凸二次規(guī)劃問(wèn)題中的朗格朗日乘子，是滿足Mercer條件的核函數(shù)，本文采用RBF核函數(shù)，公式如下

(7)

對(duì)于采用RBF核函數(shù)的SVM分類(lèi)器來(lái)說(shuō)，如何選取合適的c和σ值是至關(guān)重要的問(wèn)題，其中懲罰因子值c的大小決定著樣本對(duì)離群點(diǎn)的重視程度[5]，參數(shù)σ與輸入空間的樣本寬度和范圍相關(guān)。

2 改進(jìn)型PSO算法

PSO算法是一種全局進(jìn)化算法，由Eberhart博士等人提出，源于對(duì)鳥(niǎo)群捕食行為的研究，利用個(gè)體之間信息共享使整個(gè)群體產(chǎn)生從無(wú)序到有序的演化過(guò)程，從而獲取最優(yōu)解，因此該算法是一類(lèi)基于群體智能的仿生算法[6]。

2.1 標(biāo)準(zhǔn)PSO算法

在N維空間初始化一群粒子，其中第i個(gè)粒子的位置和速度信息可以用N維向量Xi和Vi表示：Xi=(Xi1,Xi2,Xi3,…,XiN)T，Vi=(Vi1,Vi2,Vi3,…,ViN)T。在找到個(gè)體極值P和全局極值G后，粒子根據(jù)如下公式更新自身的速度和位置

(8)

(9)

2.2 慣性權(quán)重策略

PSO算法的搜索過(guò)程是一種不斷迭代收縮，初期快后期慢的過(guò)程，Eberhart等人提出線性慣性權(quán)重法以調(diào)整粒子的全局與局部搜索能力[7]，但粒子群搜索是一個(gè)復(fù)雜的過(guò)程，W值線性減小并不能反映出粒子實(shí)際的搜索過(guò)程，本文引入非線性慣性權(quán)重法[8]，遞減策略為指數(shù)曲線，公式為

(10)

其中：Wmax和Wmin是W的最大值和最小值，iter和itermax是粒子當(dāng)前迭代次數(shù)和最大迭代次數(shù)，a是調(diào)整因子，其作用是控制曲線的下降效果。為取得合理的下降效果a取10，實(shí)驗(yàn)表明：采用指數(shù)曲線的遞減策略在搜索前期W值快速減小，后期遞減速度明顯變慢，符合粒子群前期收斂快后期慢的特點(diǎn)，且前期快速收斂可以使粒子更快進(jìn)入精細(xì)的局部搜索。

2.3 雙變異算子PSO算法

實(shí)驗(yàn)研究表明，粒子無(wú)論在進(jìn)行全局搜索或是局部搜索時(shí)，都會(huì)出行“聚集”現(xiàn)象，此時(shí)種群的多樣性十分欠缺，PSO算法過(guò)早收斂陷入局部最優(yōu)正是由于種群多樣性匱乏所致[9]。

2.3.1 邊緣變異算子

隨機(jī)產(chǎn)生一群粒子P，粒子的位置：Xi={Xmin,Xmax}，當(dāng)一部分粒子收斂到位置的邊緣或是粒子的位置超過(guò)最大范圍而被限制在邊緣時(shí)，此時(shí)邊緣位置粒子(如：Xi=Xmax)的適應(yīng)度值恰是當(dāng)前群體的最佳適應(yīng)度值，粒子便會(huì)向此邊緣位置“聚集”，從而使算法陷入邊緣局部最優(yōu)。實(shí)驗(yàn)表明：初始化的粒子群是隨機(jī)產(chǎn)生的，多數(shù)粒子因超出位置的限定范圍而被限制在邊緣位置，算法陷入邊緣局部最優(yōu)的概率增大，因此引入邊緣變異粒子r1，公式為

(11)

2.3.2 全局變異算子

在粒子群搜索過(guò)程中出行“聚集”現(xiàn)象，粒子多樣性十分匱乏時(shí)，粒子群迭代產(chǎn)生的全局最優(yōu)解會(huì)出現(xiàn)停止更新現(xiàn)象，而該全局最優(yōu)解極有可能是局部最優(yōu)解，如果是則算法陷入局部最優(yōu)[10]。因此針對(duì)全局最優(yōu)解G引入全局變異算子r2，改變此解以改變當(dāng)前粒子的前進(jìn)方向，使粒子重新進(jìn)入極值更新搜索過(guò)程，產(chǎn)生更為優(yōu)秀的全局最優(yōu)解。公式如下

Gk+1=(g1(g2-g1)×r2)×Gk

(12)

其中，g1和g2是限制范圍，一般范圍控制得較小，不會(huì)使已迭代產(chǎn)生的全局最優(yōu)解發(fā)生大幅度變動(dòng)，本文g1取0.8，g2取1.2。Gk和Gk+1是當(dāng)代和次代的全局最優(yōu)解，r2是服從正態(tài)分布的隨機(jī)變量。

2.3.3 雙變異算子PSO算法流程

所提算法流程可描述如下：(1)隨機(jī)產(chǎn)生一群粒子，并初始化粒子的速度和位置；(2)根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度值；(3)根據(jù)式(8)和式(9)更新粒子的位置和速度，根據(jù)式(10)對(duì)慣性權(quán)重W進(jìn)行非線性調(diào)整；(4)迭代過(guò)程中，根據(jù)粒子的位置和邊緣適應(yīng)度值判斷其是否陷入邊緣局部最優(yōu)，如果是，根據(jù)式(11)調(diào)整粒子的位置；(5)迭代過(guò)程中，如果全局最優(yōu)解停止更新(一般約為10次不發(fā)生明顯變化)，如果是，根據(jù)式(12)對(duì)最優(yōu)解進(jìn)行小范圍調(diào)整；(6)根據(jù)迭代條件停止迭代。

3 SVM參數(shù)尋優(yōu)仿真實(shí)驗(yàn)

針對(duì)SVM參數(shù)尋優(yōu)進(jìn)行仿真實(shí)驗(yàn)，在Windows10和Matlab R2015b軟件平臺(tái)下利用工具箱Libsvm軟件[11]進(jìn)行訓(xùn)練預(yù)測(cè)，其中分類(lèi)類(lèi)型為C-SVC，核函數(shù)為RBF核函數(shù)。電腦硬件平臺(tái)為Core-i3雙核處理器，運(yùn)行內(nèi)存4 GB。

實(shí)驗(yàn)所用的Segment數(shù)據(jù)集來(lái)自于UCI公共數(shù)據(jù)庫(kù)，其中包含了7個(gè)類(lèi)型、19個(gè)特征、2 310個(gè)數(shù)據(jù)。實(shí)驗(yàn)采用K-fold交叉驗(yàn)證法，將數(shù)據(jù)分為K組(本實(shí)驗(yàn)K取3)，其中一組作為測(cè)試集，K-1組作為訓(xùn)練集，循環(huán)K次驗(yàn)證，取K次結(jié)果均值作為最終結(jié)果，K-fold交叉驗(yàn)證法可以最大程度的利用樣本，有效的避免過(guò)學(xué)習(xí)以及欠學(xué)習(xí)狀態(tài)的發(fā)生[12]。

3.1 仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中應(yīng)用3種算法：(1)線性慣性權(quán)重標(biāo)準(zhǔn)PSO算法；(2)非線性慣性權(quán)重標(biāo)準(zhǔn)PSO算法；(3)非線性慣性權(quán)重改進(jìn)型PSO算法，進(jìn)行SVM參數(shù)尋優(yōu)。實(shí)驗(yàn)對(duì)比結(jié)果如表1所示。

表1 3類(lèi)算法實(shí)驗(yàn)結(jié)果對(duì)比表

以上3類(lèi)實(shí)驗(yàn)中，粒子的最佳適應(yīng)度和平均適應(yīng)度迭代圖如下。

圖1 算法(1)適應(yīng)度值迭代圖

圖2 算法(2)適應(yīng)度值迭代圖

圖3 算法(3)適應(yīng)度值迭代圖

3.2 實(shí)驗(yàn)分析

圖1～圖3是最佳適應(yīng)度值與平均適應(yīng)度值迭代變化曲線(x軸是迭代數(shù)，y軸是適應(yīng)度)，最佳適應(yīng)度值是根據(jù)全局極值G和目標(biāo)函數(shù)得出，其更新情況可以反映全局極值的變化，若保持不變或無(wú)明顯變化，則算法陷入局部最優(yōu)[13]。平均適應(yīng)度值計(jì)算公式為

(13)

其中：argfitness(i)是當(dāng)代平均適應(yīng)度值， fitness(j)當(dāng)前粒子的適應(yīng)度，N是種群粒子數(shù)。分析公式得出：相似的粒子有著近似的適應(yīng)度值，在迭代前期粒子多樣

性豐富，平均適應(yīng)度迭代曲線會(huì)產(chǎn)生較大幅度的振蕩，后期曲線收斂變慢，粒子多樣性減少[14]。

圖1是采用線性遞減慣性權(quán)重的標(biāo)準(zhǔn)PSO算法，最佳適應(yīng)度曲線在迭代初期跳動(dòng)之后一直保持不變，算法陷入局部最優(yōu)；平均適應(yīng)度曲線在收斂到一定值之后振蕩幅度變化不明顯，平均適應(yīng)度值趨向近似，表明粒子已出現(xiàn)“聚集”現(xiàn)象，種群多樣性減少。圖2是采用非線性遞減慣性權(quán)重的標(biāo)準(zhǔn)PSO算法，平均適應(yīng)度曲線迭代初期收斂速度較快，但同樣出現(xiàn)圖1迭代后期值趨于平穩(wěn)的現(xiàn)象。圖3是采用非線性遞減慣性權(quán)重的改進(jìn)型PSO算法，如圖所示，最佳適應(yīng)度曲線每隔一定的代數(shù)增加，表明雙變異算子的引入，改變了其易陷入局部收斂的情況，平均適應(yīng)度曲線初期振蕩明顯，后期振蕩變得微弱，但值仍保持遞增趨勢(shì)。從表1也可以看出采用改進(jìn)型PSO算法進(jìn)行分類(lèi)的平均準(zhǔn)確率明顯優(yōu)于采用標(biāo)準(zhǔn)PSO算法，但是由于改進(jìn)PSO算法增加了運(yùn)算量，耗時(shí)相對(duì)較長(zhǎng)。

4 結(jié)束語(yǔ)

SVM算法以其獨(dú)特優(yōu)勢(shì)已廣泛應(yīng)用于數(shù)據(jù)挖掘、文本分類(lèi)等諸多領(lǐng)域[15]。本文針對(duì)該算法核函數(shù)參數(shù)最優(yōu)化問(wèn)題提出一種采用非線性遞減慣性權(quán)重策略，引入雙變異算子的改進(jìn)型PSO算法，實(shí)驗(yàn)證明所提算法在SVM參數(shù)尋優(yōu)中有著良好的效果，所確定的SVM分類(lèi)器在分類(lèi)中有著良好的性能。

[1] Keerthi S S, Shevade S K.SMO algorithm for least-squares SVM formulations[J].Neural Computation, 2014,15(2):487-507.

[2] 張東東.基于遺傳算法的支持向量機(jī)分類(lèi)算法[J].電子科技,2015,28(12):32-35.

[3] 梁禮明,鐘震,陳召陽(yáng).支持向量機(jī)核函數(shù)選擇研究與仿真[J].計(jì)算機(jī)工程與科學(xué),2015,37(2):1135-1141.

[4] 陸星家,王玉金,陳志榮,等.基于隱性SVM和混合高斯模型的目標(biāo)檢測(cè)算法[J].計(jì)算機(jī)工程,2016,42(6):287-292.

[5] 王道明,魯昌華,蔣薇薇,等.基于粒子群算法的決策樹(shù)SVM多分類(lèi)方法研究[J].電子測(cè)量與儀器學(xué)報(bào),2015(4):611-615.

[6] Moradi M H,Abedini M.A combination of genetic algorithm and particle swarm optimization for optimal DG location and sizing in distribution systems[J]. International Journal of Electrical Power & Energy Systems, 2012, 34(1):66-74.

[7] Fan H.A modification to particle swarm optimization algorithm[J].Engineering Computations,2013,19(8):970-989.

[8] 敖永才,師奕兵,張偉,等.自適應(yīng)慣性權(quán)重的改進(jìn)粒子群算法[J].電子科技大學(xué)學(xué)報(bào),2014,43(6):874-880.

[9] 夏學(xué)文,王博建,金暢,等.一種自適應(yīng)多種群的PSO算法[J].系統(tǒng)仿真學(xué)報(bào),2016,28(12):2887-2895.

[10] 周利軍,彭衛(wèi),鄒芳,等.自適應(yīng)變異粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(7):50-55.

[11] 韓兆洲,林少萍,鄭博儒.多類(lèi)支持向量機(jī)分類(lèi)技術(shù)及實(shí)證[J].統(tǒng)計(jì)與決策,2015(19):10-13.

[12] 楊靜,王瑞波,李濟(jì)洪.一種均衡的RHS交叉驗(yàn)證[J].南京大學(xué)學(xué)報(bào):自然科學(xué)版,2015(4):842-849.

[13] 吳潤(rùn)秀,孫輝,朱德剛,等.具有高斯擾動(dòng)的最優(yōu)粒子引導(dǎo)粒子群優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(1):146-151.

[14] 黃明,張春蕾,武耀旭,等.一種多樣性反饋高斯粒子群算法[J].大連交通大學(xué)學(xué)報(bào), 2015,36(1):105-108.

[15] 魏芳芳,段青玲,肖曉琰,等.基于支持向量機(jī)的中文農(nóng)業(yè)文本分類(lèi)技術(shù)研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2015(s1):174-179.