粒子群算法優(yōu)化混合核函數(shù)SVM及應(yīng)用*

崔國(guó)恒 李京書(shū) 張 軍

(1.海軍工程大學(xué) 武漢 430033)(2.空軍裝備研究院 北京 100000)

粒子群算法優(yōu)化混合核函數(shù)SVM及應(yīng)用*

崔國(guó)恒1李京書(shū)1張 軍2

(1.海軍工程大學(xué) 武漢 430033)(2.空軍裝備研究院 北京 100000)

相比于單一核函數(shù)支持向量機(jī)，混合核函數(shù)的引入使支持向量機(jī)多了一個(gè)可調(diào)參數(shù)，而這個(gè)可調(diào)參數(shù)一般是根據(jù)人為隨機(jī)選取或者依據(jù)經(jīng)驗(yàn)選取，并不能保證參數(shù)最優(yōu)。針對(duì)此問(wèn)題，提出了以懲罰系數(shù)、核函數(shù)參數(shù)和可調(diào)參數(shù)為尋優(yōu)對(duì)象，用動(dòng)態(tài)粒子群對(duì)其進(jìn)行尋優(yōu)的方法，以獲取最優(yōu)參數(shù)組合，從而提高支持向量機(jī)的分類性能。通過(guò)對(duì)UCI數(shù)據(jù)庫(kù)中的IRIS數(shù)據(jù)集進(jìn)行分類實(shí)驗(yàn)，結(jié)果表明：相比于單一核函數(shù)支持向量機(jī)，混合核函數(shù)支持向量機(jī)泛化能力更好，分類精度更高；動(dòng)態(tài)粒子群算法能夠搜索到更優(yōu)的支持向量機(jī)參數(shù)。

支持向量機(jī)；動(dòng)態(tài)粒子群；核函數(shù)參數(shù)；尋優(yōu)；分類精度

(1. Naval University of Engineering, Wuhan 430033)(2. Equipment Research Department of Air Force, Beijing 100000)

Class Number TP393

1 引言

支持向量機(jī)(Support Vector Machine，SVM)是統(tǒng)計(jì)學(xué)習(xí)理論的具體體現(xiàn)，統(tǒng)計(jì)學(xué)習(xí)理論是從小樣本出發(fā)的學(xué)習(xí)理論，最早是由Vapnik于20世紀(jì)60年代提出的，自20個(gè)世紀(jì)90年代逐漸受到越來(lái)越多的關(guān)注[1]。一般的機(jī)器學(xué)習(xí)如神經(jīng)網(wǎng)絡(luò)，在訓(xùn)練的過(guò)程中目標(biāo)函數(shù)通常遵循最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)，但真實(shí)風(fēng)險(xiǎn)不一定最小，這也是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則的弊端。而SVM放棄了傳統(tǒng)的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則，采用的是結(jié)構(gòu)風(fēng)險(xiǎn)最小化(Structure Risk Minimization，SRM)，SVM對(duì)于問(wèn)題的求解實(shí)際上是求一個(gè)二次規(guī)劃問(wèn)題的最優(yōu)解。在SVM中，采用核函數(shù)構(gòu)建非線性映射很好地解決了線性不可分問(wèn)題[2]。SVM已經(jīng)在如基因分析、手寫(xiě)體數(shù)字識(shí)別、人臉識(shí)別等很多領(lǐng)域取得了成功應(yīng)用[3]。

SVM作為一種較為新穎的機(jī)器學(xué)習(xí)方法，目前存在的主要問(wèn)題是核函數(shù)的選取和參數(shù)的優(yōu)化。對(duì)于一些數(shù)據(jù)集，不同的核函數(shù)選取方式對(duì)分類結(jié)果的影響較為相近；而對(duì)另一些數(shù)據(jù)集來(lái)說(shuō)，選取不同的核函數(shù)對(duì)分類結(jié)果的影響很大。對(duì)于不同的數(shù)據(jù)集，需要選取什么樣的核函數(shù)并沒(méi)有統(tǒng)一的解決方法。另外，SVM參數(shù)的選取也沒(méi)有確定的參考標(biāo)準(zhǔn)。因此，核函數(shù)的選取以及參數(shù)的優(yōu)化對(duì)提高SVM性能就顯得尤為重要。粒子群(Particle Swarm Optimization，PSO)算法是基于群體中粒子間的合作和競(jìng)爭(zhēng)而進(jìn)行參數(shù)優(yōu)化、搜索的，它是一種較為有效的全局尋優(yōu)算法[4]。但是，PSO算法容易早熟、陷入局部最優(yōu)，導(dǎo)致最終搜索到的參數(shù)最優(yōu)解不是全局最優(yōu)解[5]。考慮以上因素，本文提出混合核函數(shù)SVM，并用動(dòng)態(tài)粒子群(DPSO)算法對(duì)其參數(shù)進(jìn)行尋優(yōu)。

2 混合核函數(shù)

核函數(shù)是指非線性映射函數(shù)K(·)，它能將低維空間中的線性不可分問(wèn)題轉(zhuǎn)化到高維空間中，從而變?yōu)榫€性可分問(wèn)題。核函數(shù)的引入極大的提高了SVM對(duì)非線性問(wèn)題的處理能力。SVM主要有全局和局部?jī)煞N核函數(shù)類型，主要分為四種[6]：

1) 多項(xiàng)式(Polynomial，POLY)核：

K(x,xi)=(xxi+1)d

2) RBF(Radial Basis Function)核：

3) 線性核

K(x,xi)=xxi

4) Sigmoid核

K(x,xi)=tanh(k(xxi)+θ)

RBF核函數(shù)屬于局部核函數(shù)，其學(xué)習(xí)能力強(qiáng)，泛化能力弱，它是一般的SVM最常用的核函數(shù)；與RBF核函數(shù)不同，線性核函數(shù)、POLY核函數(shù)、Sigmoid核函數(shù)屬于全局核函數(shù)，其學(xué)習(xí)能力弱，泛化能力強(qiáng)[7]。當(dāng)數(shù)據(jù)之間距離較遠(yuǎn)的點(diǎn)對(duì)SVM分類效果影響較大時(shí)，此時(shí)應(yīng)選用全局核函數(shù)；當(dāng)數(shù)據(jù)之間距離較近的點(diǎn)對(duì)SVM分類影響較大時(shí)，此時(shí)應(yīng)選用局部核函數(shù)。來(lái)源于神經(jīng)網(wǎng)絡(luò)的Sigmoid全局核函數(shù)只有在它的參數(shù)達(dá)到特定條件的要求時(shí)，才符合對(duì)稱、半正定的核函數(shù)條件，它在解決實(shí)際問(wèn)題的過(guò)程中常受到限制[8～9]。所以，考慮將局部核RBF核函數(shù)和全局核POLY核函數(shù)組合起來(lái)，形成一種新的核函數(shù)以達(dá)到同時(shí)兼顧學(xué)習(xí)能力和泛化能力的目的，本文提出一種新的混合核函數(shù)為

Kmix=(λ/2)2·KRBF+[1-(λ/2)2]·KPOLY

其中參數(shù)λ用來(lái)調(diào)節(jié)RBF核函數(shù)和POLY核函數(shù)在混合核函數(shù)所占的比重，它決定了RBF核函數(shù)和POLY核函數(shù)所發(fā)揮的作用的大小。因?yàn)镵RBF、KPOLY滿足對(duì)稱、半正定，可以證明，Kmix滿足對(duì)稱、半正定的Mercer條件。當(dāng)λ=0時(shí)，混合核函數(shù)變?yōu)镻OLY核函數(shù)；當(dāng)λ=2時(shí)，混合核函數(shù)變?yōu)镽BF核函數(shù)。這里確定參數(shù)λ的取值范圍為[0，2]。則混合核SVM需要優(yōu)化的參數(shù)有可調(diào)參數(shù)l、RBF核參數(shù)γ、POLY核參數(shù)d以及懲罰系數(shù)C。

3 動(dòng)態(tài)粒子群算法(DPSO)

(1)

(2)

其中，d=1，2，，K；i=1，2，，N分別為搜索空間維數(shù)和種群規(guī)模；r1，r2是介于(0，1)之間的隨機(jī)數(shù)；c1，c2為學(xué)習(xí)因子常數(shù)，ω為慣性權(quán)重。

針對(duì)PSO算法運(yùn)行過(guò)程中，粒子群多樣性下降較快及算法容易陷入局部最優(yōu)的問(wèn)題，劉建華等根據(jù)粒子之間的相似度對(duì)算法進(jìn)行改進(jìn)，使粒子群算法能夠在運(yùn)行過(guò)程中動(dòng)態(tài)地調(diào)整自身的搜索能力，提高收斂速度和搜索精度，以達(dá)到更好的性能[11]。定義1、定義2分別是劉建華等給出的粒子間相似度定義和慣性權(quán)重ω′的計(jì)算公式，定義3是本文給出的慣性權(quán)重ω計(jì)算公式。

定義1 兩個(gè)粒子i，j的相似度s(i,j)滿足如下條件[12]：

1)s(i,i)=1；2)當(dāng)d(i,j)→∞時(shí)，s(i,j)=0；3)對(duì)任意兩個(gè)粒子i、j，都有s(i,j)∈[0,1]。則粒子之間的相似度s(i,j)滿足如下等式：

(3)

其中，d(i,j)為粒子i，j在空間里的歐幾里得距離，dmax、dmin分別為粒子間距離的最大、最小值。

定義2 慣性權(quán)重ω′的計(jì)算公式如下[12]：

(4)

(5)

本文在劉建華等給出的粒子相似度定義的基礎(chǔ)上重新定義權(quán)重ω，如定義3所示。

定義3 慣性權(quán)重ω的計(jì)算公式如下：

(6)

其中，s(i,g)為第i個(gè)粒子與最優(yōu)粒子g之間的相似度；ωmax、ωmin分別為慣性權(quán)重取得的最大、最小值；tmax為最大進(jìn)化代數(shù)；t為當(dāng)前進(jìn)化代數(shù)。由式(6)可知，隨進(jìn)化代數(shù)t和粒子i與最優(yōu)粒子間相似度s(i,g)的變化，慣性權(quán)重ω∈(ωmin,ωmax)，且在算法在運(yùn)行前期，大部分粒子與最優(yōu)粒子的距離大于或等于dmax，此時(shí)慣性權(quán)重大，算法的全局搜索能力強(qiáng)；在運(yùn)行過(guò)程中，隨著粒子逐漸向最優(yōu)粒子靠近，慣性權(quán)重隨著進(jìn)化代數(shù)非線性減小，模擬粒子的非線性運(yùn)動(dòng)過(guò)程；在運(yùn)行后期，粒子越來(lái)越接近最優(yōu)粒子(最優(yōu)解)，此時(shí)令慣性權(quán)重等于較小的值，進(jìn)一步保證了算法在較小范圍內(nèi)搜索的精度。劉建華等提出的動(dòng)態(tài)粒子群算法記為DPSO1，本文提出的動(dòng)態(tài)粒子群算法記為DPSO2。

4 DPSO優(yōu)化混合核函數(shù)SVM方法

應(yīng)用DPSO算法優(yōu)化SVM的流程圖如圖1所示。DPSO算法適應(yīng)度函數(shù)為SVM分類準(zhǔn)確率的最大值，這樣DPSO算法就會(huì)將使SVM具有最大分類能力的參數(shù)組合作為搜索目標(biāo)。

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 數(shù)據(jù)來(lái)源

本文采用UCI數(shù)據(jù)庫(kù)中的IRIS數(shù)據(jù)集進(jìn)行分類實(shí)驗(yàn)，IRIS數(shù)據(jù)集是以鳶尾花的特征作為數(shù)據(jù)來(lái)源，包含150個(gè)數(shù)據(jù)樣本，分為Iris-setosa、Iris-versicolor、Iris-virginica等3類，每類有50個(gè)樣本，每個(gè)樣本包括4個(gè)屬性：萼片長(zhǎng)度、萼片寬度、花瓣長(zhǎng)度、花瓣寬度[13]。

5.2 實(shí)驗(yàn)結(jié)果與分析

模型中，設(shè)置混合核函數(shù)SVM參數(shù)范圍為λ∈[0,2]；C∈[2-10,210]；γ∈[2-10,210]；d∈[1,10]。設(shè)置DPSO算法參數(shù)范圍為c1=1.5，c2=1.5；ω∈[0.2,1]；種群大小為25；進(jìn)化代數(shù)為50。實(shí)驗(yàn)中，隨機(jī)選擇IRIS數(shù)據(jù)集中Iris-setosa樣本25組、Iris-versicolor樣本25組、Iris-virginica樣本25組作為訓(xùn)練集，剩下的作為測(cè)試集，以檢驗(yàn)SVM的分類性能和泛化能力。分別利用劉建華等提出的DPSO1算法和本文提出的DPSO2算法搜索SVM的最優(yōu)參數(shù)，實(shí)驗(yàn)重復(fù)進(jìn)行20次，得到混合核函數(shù)SVM算法、RBF核函數(shù)SVM的分類正確率及算法運(yùn)行時(shí)間分別如圖2、圖3所示。

同時(shí)，由仿真實(shí)驗(yàn)可以得出，當(dāng)可調(diào)參數(shù)λ的取值范圍為(1.5，2)時(shí)，混合核函數(shù)SVM具有更好的分類準(zhǔn)確率。

從圖2、圖3可以看出，混合核函數(shù)DPSO-SVM的分類準(zhǔn)確率/運(yùn)行時(shí)間總體上比單一RBF核函數(shù)DPSO-SVM的分類準(zhǔn)確率/運(yùn)行時(shí)間高/長(zhǎng)，計(jì)算出20次實(shí)驗(yàn)混合核函數(shù)DPSO1-SVM、混合核函數(shù)DPSO2-SVM的分類準(zhǔn)確率的平均值分別為96.0667%和97.4667%；運(yùn)行時(shí)間平均值分別為24.2711s和24.1817s。計(jì)算出單一RBF核函數(shù)DPSO1-SVM、單一RBF核函數(shù)DPSO2-SVM的分類準(zhǔn)確率平均值分別為91.8000%和92.7333%；運(yùn)行時(shí)間平均值分別為1.7219s和1.7100s。不同算法的分類準(zhǔn)確率均值和運(yùn)行時(shí)間均值如表1所示。

圖1 DPSO-SVM算法流程圖

圖2 20次實(shí)驗(yàn)不同算法準(zhǔn)確率對(duì)比

圖3 20次實(shí)驗(yàn)不同算法運(yùn)行時(shí)間對(duì)比

表1 不同算法分類準(zhǔn)確率、運(yùn)行時(shí)間均值

從表1中的數(shù)據(jù)可以看出，在核函數(shù)一致的情況下，DPSO2算法優(yōu)化的SVM平均分類精度/運(yùn)行速度要比DPSO1算法優(yōu)化的SVM平均分類精度/運(yùn)行速度高/快，這說(shuō)明了本文提出的DPSO2算法要比劉建華等提出的DPSO1算法搜索精度更高，收斂速度更快。在優(yōu)化算法一致的情況下，混合核函數(shù)DPSO-SVM算法的平均分類精度要比單一RBF核函數(shù)DPSO-SVM的平均分類精度高，經(jīng)POLY核和RBF核混合而成的混合核函數(shù)使得SVM的分類能力有所提高，推廣能力也有所增強(qiáng)。但混合核函數(shù)DPSO-SVM算法平均運(yùn)行時(shí)間大約是單一RBF核函數(shù)DPSO-SVM算法平均運(yùn)行時(shí)間的14倍。經(jīng)過(guò)以上分析，雖然混核函數(shù)DPSO-SVM的分類準(zhǔn)確率比單一RBF核函數(shù)DPSO-SVM分類準(zhǔn)確率高，但是其運(yùn)行時(shí)間要更長(zhǎng)。這是因?yàn)榛旌虾撕瘮?shù)SVM的待優(yōu)化參數(shù)除了懲罰系數(shù)C和核函數(shù)參數(shù)γ外，還增加了權(quán)重參數(shù)l和POLY核參數(shù)d，使得算法的復(fù)雜性增加，計(jì)算量增大，算法運(yùn)行起來(lái)更加耗時(shí)。另外，由表1還可以看出，在相同條件下，不同算法的平均運(yùn)行時(shí)間差異并不是很大，犧牲適當(dāng)?shù)倪\(yùn)行時(shí)間來(lái)實(shí)現(xiàn)算法分類精度的較大提升是完全可以接受的。所以，混合核函數(shù)DPSO-SVM算法也是可行、有效的。

6 結(jié)語(yǔ)

本文提出了一種新的混合核函數(shù)SVM算法，并在DPSO1算法基礎(chǔ)上，提出了DPSO2算法，用于搜索SVM的參數(shù)。實(shí)驗(yàn)結(jié)果表明: 1) 相比于DPSO1算法，DPSO2算法的搜索精度更高，收斂速度更快； 2) 相比于RBF核函數(shù)SVM，混合核函數(shù)SVM的分類性能有所提高。

[1] Theodoros Evgeniou,Massimiliano Pontil,Tomaso Poggio. Statistical Learning Theory: A Primer[J]. International Journal of Computer Vision, 2000, 381.

[2] Jawad S. Alagha,Md Azlin Md Said,Yunes Mogheir. Modeling of nitrate concentration in groundwater using artificial intelligence approach—a case study of Gaza coastal aquifer[J]. Environmental Monitoring and Assessment, 2014, 1861:.

[3] 丁世飛,齊丙娟,譚紅艷.支持向量機(jī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報(bào),2011,01:2-10.

[4] 黃少榮.粒子群優(yōu)化算法綜述[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,08: 1977-1980.

[5] 聶立新,張?zhí)靷b,趙攸.粒子群算法優(yōu)化雙核支持向量機(jī)及應(yīng)用[J].振動(dòng)、測(cè)試與診斷,2014(3):565-569.

[6] Christopher K. I Williams. Learning With Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[J]. Journal of the American Statistical Association, 2003, 98462.

[7] Zheng S, Liu J, Tian J W. An SVM-based small target segmentation and clustering approach[C]//Machine Learning and Cybernetics, 2004. Proceedings of 2004 International Conference on. IEEE, 2004, 6: 3318-3323.

[8] 王行甫,俞璐.混合核函數(shù)中權(quán)重求解方法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,04:129-133.

[9] Smits G F, Jordaan E M. Improved SVM regression using mixtures of kernels[C]//Neural Networks, 2002. IJCNN'02. Proceedings of the 2002 International Joint Conference on. IEEE,2002,3:2785-2790.

[10] 魯峰,黃金泉,陳煜,等.基于SPSO-SVR的融合航空發(fā)動(dòng)機(jī)傳感器故障診斷[J].航空動(dòng)力學(xué)報(bào),2009,08:1856-1865.

[11] 劉建華,樊曉平,瞿志華.一種慣性權(quán)重動(dòng)態(tài)調(diào)整的新型粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007, 07: 68-70.

[12] 劉建華.粒子群算法的基本理論及其改進(jìn)研究[D].長(zhǎng)沙:中南大學(xué),2009.

[13] 劉春衛(wèi),羅健旭.基于混合核函數(shù)的PSO-SVM分類算法[J]. 華東理工大學(xué)學(xué)報(bào) (自然科學(xué)版), 2014, 1: 017.

Particle Swarm Algorithm to Optimize the Kernel Function SVM and Its Application

CUI Guoheng1LI Jingshu1ZHANG Jun2

Compared to single kernel function of support vector machine (SVM), the introduction of the mixed kernel function of SVM has one more adjustable parameters. And the adjustable parameter is usually selected on the basis of human or experience, which does not guarantee the optimal parameters. In order to find the optimal parameters and improve ability of classification of SVM, the parameters of the mixed kernel of SVM are selected by dynamic particle swarm optimization. The classification experiment results show that compared to a single kernel of SVM, the hybrid kernelof SVM has better generalization ability and higher classification accuracy, dynamic particle swarm algorithm can search better parameters of SVM.

support vector machine, dynamic particle swarm, kernel function parameter, optimizing, classification accuracy

2016年6月7日,

2016年7月19日

崔國(guó)恒,男,博士,講師,研究方向:無(wú)線電技術(shù)及研究。

TP393

10.3969/j.issn.1672-9730.2016.12.011