粒子群算法優化混合核函數SVM及應用*

崔國恒 李京書 張 軍

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

粒子群算法優化混合核函數SVM及應用*

崔國恒1李京書1張 軍2

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

相比于單一核函數支持向量機，混合核函數的引入使支持向量機多了一個可調參數，而這個可調參數一般是根據人為隨機選取或者依據經驗選取，并不能保證參數最優。針對此問題，提出了以懲罰系數、核函數參數和可調參數為尋優對象，用動態粒子群對其進行尋優的方法，以獲取最優參數組合，從而提高支持向量機的分類性能。通過對UCI數據庫中的IRIS數據集進行分類實驗，結果表明：相比于單一核函數支持向量機，混合核函數支持向量機泛化能力更好，分類精度更高；動態粒子群算法能夠搜索到更優的支持向量機參數。

支持向量機；動態粒子群；核函數參數；尋優；分類精度

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

Class Number TP393

1 引言

支持向量機(Support Vector Machine，SVM)是統計學習理論的具體體現，統計學習理論是從小樣本出發的學習理論，最早是由Vapnik于20世紀60年代提出的，自20個世紀90年代逐漸受到越來越多的關注[1]。一般的機器學習如神經網絡，在訓練的過程中目標函數通常遵循最小化經驗風險，但真實風險不一定最小，這也是經驗風險最小化準則的弊端。而SVM放棄了傳統的經驗風險最小化準則，采用的是結構風險最小化(Structure Risk Minimization，SRM)，SVM對于問題的求解實際上是求一個二次規劃問題的最優解。在SVM中，采用核函數構建非線性映射很好地解決了線性不可分問題[2]。SVM已經在如基因分析、手寫體數字識別、人臉識別等很多領域取得了成功應用[3]。

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

2 混合核函數

核函數是指非線性映射函數K(·)，它能將低維空間中的線性不可分問題轉化到高維空間中，從而變為線性可分問題。核函數的引入極大的提高了SVM對非線性問題的處理能力。SVM主要有全局和局部兩種核函數類型，主要分為四種[6]：

1) 多項式(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核函數屬于局部核函數，其學習能力強，泛化能力弱，它是一般的SVM最常用的核函數；與RBF核函數不同，線性核函數、POLY核函數、Sigmoid核函數屬于全局核函數，其學習能力弱，泛化能力強[7]。當數據之間距離較遠的點對SVM分類效果影響較大時，此時應選用全局核函數；當數據之間距離較近的點對SVM分類影響較大時，此時應選用局部核函數。來源于神經網絡的Sigmoid全局核函數只有在它的參數達到特定條件的要求時，才符合對稱、半正定的核函數條件，它在解決實際問題的過程中常受到限制[8～9]。所以，考慮將局部核RBF核函數和全局核POLY核函數組合起來，形成一種新的核函數以達到同時兼顧學習能力和泛化能力的目的，本文提出一種新的混合核函數為

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

其中參數λ用來調節RBF核函數和POLY核函數在混合核函數所占的比重，它決定了RBF核函數和POLY核函數所發揮的作用的大小。因為KRBF、KPOLY滿足對稱、半正定，可以證明，Kmix滿足對稱、半正定的Mercer條件。當λ=0時，混合核函數變為POLY核函數；當λ=2時，混合核函數變為RBF核函數。這里確定參數λ的取值范圍為[0，2]。則混合核SVM需要優化的參數有可調參數l、RBF核參數γ、POLY核參數d以及懲罰系數C。

3 動態粒子群算法(DPSO)

(1)

(2)

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

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

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

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

(3)

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

定義2 慣性權重ω′的計算公式如下[12]：

(4)

(5)

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

定義3 慣性權重ω的計算公式如下：

(6)

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

4 DPSO優化混合核函數SVM方法

應用DPSO算法優化SVM的流程圖如圖1所示。DPSO算法適應度函數為SVM分類準確率的最大值，這樣DPSO算法就會將使SVM具有最大分類能力的參數組合作為搜索目標。

5 仿真實驗與結果分析

5.1 數據來源

本文采用UCI數據庫中的IRIS數據集進行分類實驗，IRIS數據集是以鳶尾花的特征作為數據來源，包含150個數據樣本，分為Iris-setosa、Iris-versicolor、Iris-virginica等3類，每類有50個樣本，每個樣本包括4個屬性：萼片長度、萼片寬度、花瓣長度、花瓣寬度[13]。

5.2 實驗結果與分析

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

同時，由仿真實驗可以得出，當可調參數λ的取值范圍為(1.5，2)時，混合核函數SVM具有更好的分類準確率。

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

圖1 DPSO-SVM算法流程圖

圖2 20次實驗不同算法準確率對比

圖3 20次實驗不同算法運行時間對比

表1 不同算法分類準確率、運行時間均值

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

6 結語

本文提出了一種新的混合核函數SVM算法，并在DPSO1算法基礎上，提出了DPSO2算法，用于搜索SVM的參數。實驗結果表明: 1) 相比于DPSO1算法，DPSO2算法的搜索精度更高，收斂速度更快； 2) 相比于RBF核函數SVM，混合核函數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].電子科技大學學報,2011,01:2-10.

[4] 黃少榮.粒子群優化算法綜述[J].計算機工程與設計,2009,08: 1977-1980.

[5] 聶立新,張天俠,趙攸.粒子群算法優化雙核支持向量機及應用[J].振動、測試與診斷,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] 王行甫,俞璐.混合核函數中權重求解方法[J].計算機系統應用,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的融合航空發動機傳感器故障診斷[J].航空動力學報,2009,08:1856-1865.

[11] 劉建華,樊曉平,瞿志華.一種慣性權重動態調整的新型粒子群算法[J]. 計算機工程與應用, 2007, 07: 68-70.

[12] 劉建華.粒子群算法的基本理論及其改進研究[D].長沙:中南大學,2009.

[13] 劉春衛,羅健旭.基于混合核函數的PSO-SVM分類算法[J]. 華東理工大學學報 (自然科學版), 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日

崔國恒,男,博士,講師,研究方向:無線電技術及研究。

TP393

10.3969/j.issn.1672-9730.2016.12.011