基于鳥(niǎo)群算法的SVM參數(shù)選擇

肖海軍，盧常景，何 凡

(中國(guó)地質(zhì)大學(xué) 數(shù)學(xué)與物理學(xué)院，武漢 430074)

基于鳥(niǎo)群算法的SVM參數(shù)選擇

肖海軍，盧常景*，何 凡

(中國(guó)地質(zhì)大學(xué) 數(shù)學(xué)與物理學(xué)院，武漢 430074)

針對(duì)支持向量機(jī)(SVM)分類(lèi)器參數(shù)選擇問(wèn)題，提出了基于鳥(niǎo)群算法(BSA)的SVM參數(shù)選擇方法(BSA-SVM)，以?xún)?yōu)化SVM懲罰參數(shù)和核參數(shù).鳥(niǎo)群算法具有優(yōu)化精度高、魯棒性好等特點(diǎn),將SVM參數(shù)作為鳥(niǎo)群算法目標(biāo)函數(shù)的優(yōu)化參數(shù)，在搜索到最優(yōu)值的同時(shí)得到最優(yōu)參數(shù).通過(guò)8個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集的MATLAB仿真對(duì)比實(shí)驗(yàn)，驗(yàn)證了BSA-SVM能有效提高分類(lèi)準(zhǔn)確性.實(shí)驗(yàn)結(jié)果表明：BSA-SVM能更加準(zhǔn)確地找到SVM最優(yōu)參數(shù)，從而加強(qiáng)SVM學(xué)習(xí)與泛化能力，是一種有效的SVM參數(shù)優(yōu)化方法.

鳥(niǎo)群算法；支持向量機(jī)；參數(shù)選擇

AbstractAccording to the problem of selecting parameters in support vector machine(SVM), a parameter selection method(BSA-SVM) based on bird swarm algorithm(BSA) for optimizing the SVM penalty parameter and kernel parameter is proposed. BSA is a new optimization algorithm which?possesses the characteristic of high precision and good robustness. Hence, parameters selection problem of SVM can be regarded as a combinatorial optimization problem by setting the objective function in BSA, which can obtain the best value and the optimum parameters at the same time. The simulation comparison experiments on 8 UCI datasets illustrate that the BSA-SVM effectively improves the classification accuracy of SVM. It is shown that the BSA-SVM can find the optimal parameters more accurately and strengthen the learning and generalization ability of SVM, so it′s an effective parameter optimization method of SVM.

Keywordsbird swarm algorithm(BSA); support vector machine(SVM); parameter selection

1995年，Vapnik等在基于統(tǒng)計(jì)學(xué)VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的基礎(chǔ)上提出了支持向量機(jī)[1](SVM).此后，SVM在解決小樣本、非線性和高維識(shí)別問(wèn)題方面展現(xiàn)出了較強(qiáng)的優(yōu)勢(shì)，現(xiàn)今已被廣泛的應(yīng)用于模式識(shí)別、回歸估計(jì)等領(lǐng)域[2-4].

然而，SVM作為一種新穎的機(jī)器學(xué)習(xí)算法，它還有許多需要改進(jìn)的地方.其中如何合理地選擇參數(shù)便是關(guān)鍵問(wèn)題之一，因?yàn)閰?shù)取值將直接影響到預(yù)測(cè)性能的好壞.由于缺乏一定的理論指導(dǎo)，早期的參數(shù)選擇往往依據(jù)網(wǎng)格搜索法[5]、梯度下降法[6]等，這些方法的特點(diǎn)是原理簡(jiǎn)單，實(shí)現(xiàn)容易，但存在著搜索精度不高、計(jì)算量大等問(wèn)題.最近十幾年來(lái)利用優(yōu)化算法優(yōu)化SVM參數(shù)也成為一個(gè)研究熱點(diǎn)，例如Peng提出了基于粒子群算法(PSO)的SVM參數(shù)選擇方法[7]，莊嚴(yán)提出了基于蟻群算法(ACO)的SVM參數(shù)選擇方法[8]，魏峻提出了基于蝙蝠算法(BA)的SVM參數(shù)選擇方法[9]，它們都能有效地尋找到合適的參數(shù)，從而提高SVM分類(lèi)預(yù)測(cè)性能.這幾種優(yōu)化算法都存在著相應(yīng)的特點(diǎn)：PSO算法收斂速度快，全局性能優(yōu)良，但是局部性能較差，很容易陷入局部最優(yōu)；ACO算法具有較強(qiáng)的魯棒性，但收斂速度慢，搜索過(guò)程中容易出現(xiàn)停滯；BA全局性能好，但搜索后期收斂精度差、收斂速度慢且容易陷入局部極值.鳥(niǎo)群算法(BSA)作為一種全新的仿生優(yōu)化算法，相對(duì)于其他優(yōu)化算法具有優(yōu)化精度高、穩(wěn)定性強(qiáng)、收斂速度快等優(yōu)點(diǎn)，能較好地克服傳統(tǒng)優(yōu)化算法容易陷入局部最優(yōu)的缺陷[10].因此，采用鳥(niǎo)群算法來(lái)進(jìn)行SVM參數(shù)選擇也將會(huì)是一種行之有效的方法.

1 SVM分類(lèi)器

1.1 SVM分類(lèi)原理

在二分類(lèi)問(wèn)題中，設(shè)樣本集為{(xi,yi)，i=1,2,…,l}，其中xi∈Rl表示輸入變量，yi∈{+1,-1}表示輸出變量，l為樣本集個(gè)數(shù).通過(guò)引入非線性映射函數(shù)φ(x)，將處于低維空間的輸入變量映射到高維空間，可以構(gòu)造出一個(gè)最優(yōu)分類(lèi)超平面：

f(x)=ω·φ(x)+b=0，

(1)

其中ω表示權(quán)重向量，b表示最優(yōu)超平面位移.

為了最小化結(jié)構(gòu)風(fēng)險(xiǎn)，構(gòu)造出的最優(yōu)超平面需滿足以下約束條件：

yi·(ω·φ(xi)+b)≥1,i=1,2,…,l.

(2)

若構(gòu)造的最優(yōu)分類(lèi)超平面仍存在少量分類(lèi)錯(cuò)誤，那么可以引入非負(fù)松弛變量來(lái)量ζi化分類(lèi)器的這種分類(lèi)誤差.此時(shí)分類(lèi)超平面最優(yōu)化問(wèn)題可表述為：

ζi≥0,i=1,2,…,l，

(3)

其中，C為懲罰系數(shù)，表示對(duì)錯(cuò)誤分類(lèi)的懲罰代價(jià)，C越大，懲罰代價(jià)越大.

對(duì)于該二次規(guī)劃問(wèn)題，采用拉格朗日乘子法將其轉(zhuǎn)化為對(duì)偶形式：

(4)

在(4)中引入核函數(shù)，可轉(zhuǎn)化為：

(5)

其中K(xi,xj)稱(chēng)為核函數(shù)，K(xi,xj)=φ(xi)·φ(xj)，最終得到分類(lèi)超平面：

(6)

采用不同的核函數(shù)會(huì)生成不同的SVM分類(lèi)器，目前SVM中常見(jiàn)的核函數(shù)主要有：線性函數(shù)K(xi,xj)=xi·xj，多項(xiàng)式函數(shù)K(xi,xj)=(xi·xj+1)d，Sigmoid函數(shù)K(xi,xj)=tanh(γxi·xj+r),γ>0，徑向基函數(shù)K(xi,xj)=exp(-‖x-xi‖/2σ2).其中徑向基函數(shù)只需要確定一個(gè)核函數(shù)，并且相關(guān)研究表明，它是一種在分類(lèi)問(wèn)題上表現(xiàn)優(yōu)異的核函數(shù)[11]，因而本文選擇徑向基函數(shù)作為SVM核函數(shù).

1.2 SVM參數(shù)

SVM參數(shù)的選擇對(duì)分類(lèi)器模型的學(xué)習(xí)能力和預(yù)測(cè)能力都有重要影響，因此參數(shù)選擇是SVM一個(gè)關(guān)鍵性問(wèn)題.對(duì)于選用徑向基核函數(shù)的SVM分類(lèi)器，其參數(shù)的選取包括懲罰參數(shù)C與核寬度σ.懲罰參數(shù)C用于調(diào)節(jié)SVM分類(lèi)器置信范圍與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間的比例，以提高其推廣能力.C取值過(guò)小時(shí)稱(chēng)為“欠學(xué)習(xí)”，表示對(duì)經(jīng)驗(yàn)誤差的懲罰小，此時(shí)數(shù)據(jù)擬合程度低.C取值過(guò)大時(shí)稱(chēng)為“過(guò)學(xué)習(xí)”，表示對(duì)經(jīng)驗(yàn)誤差的懲罰大，此時(shí)數(shù)據(jù)擬合程度高，但泛化能力會(huì)降低.核寬度σ的取值大小跟學(xué)習(xí)樣本的輸入空間成正相關(guān)關(guān)系，它體現(xiàn)了特征子空間分布的情況.研究顯示，較小的σ值將導(dǎo)致學(xué)習(xí)樣本過(guò)度擬合，而較大的值將導(dǎo)致學(xué)習(xí)樣本欠擬合，而這都會(huì)影響SVM分類(lèi)器泛化能力[12].因此，懲罰參數(shù)C與核寬度σ的取值過(guò)大或過(guò)小都會(huì)嚴(yán)重影響SVM分類(lèi)器的性能.

2 基于鳥(niǎo)群算法的SVM參數(shù)選擇

2.1鳥(niǎo)群算法原理

鳥(niǎo)群算法(BSA)是Meng等[10]于2015年提出的一種全新仿生優(yōu)化算法.它的靈感來(lái)源于鳥(niǎo)群的三大行為：覓食行為、警戒行為和飛行行為.為了形成該算法，5個(gè)理想化的規(guī)則簡(jiǎn)化如下.

規(guī)則1：每只鳥(niǎo)都可以在警戒行為和覓食行為間隨意切換，是否搜尋食物或保持警戒被描述為一個(gè)隨機(jī)策略.

規(guī)則2：當(dāng)覓食時(shí)，每只鳥(niǎo)都會(huì)及時(shí)記錄并更新自身當(dāng)前最佳經(jīng)驗(yàn)和鳥(niǎo)群當(dāng)前最佳經(jīng)驗(yàn)，并且這些信息能及時(shí)共享.

規(guī)則3：當(dāng)處于警惕時(shí)，每只鳥(niǎo)都會(huì)嘗試移向群體中間，這種行為會(huì)引發(fā)群體競(jìng)爭(zhēng)而使自身受到影響.擁有高儲(chǔ)量食物的鳥(niǎo)比擁有低儲(chǔ)量食物的鳥(niǎo)更可能靠近群體中心.

規(guī)則4：鳥(niǎo)群會(huì)定期飛往另一個(gè)地點(diǎn).當(dāng)飛到另一個(gè)地點(diǎn)時(shí)，每只鳥(niǎo)會(huì)在生產(chǎn)者和乞討者之間切換身份，擁有最高儲(chǔ)量食物的鳥(niǎo)會(huì)成為生產(chǎn)者，而擁有最低儲(chǔ)量食物的鳥(niǎo)成為乞討者，食物儲(chǔ)量介于這兩者之間的鳥(niǎo)隨機(jī)選擇成為生產(chǎn)者或乞討者.

規(guī)則5：生產(chǎn)者積極尋找食物，而乞討者會(huì)隨機(jī)跟從生產(chǎn)者去尋找食物.

覓食行為：規(guī)則1可表示為一個(gè)隨機(jī)策略.隨機(jī)生成一個(gè)服從均勻分布的值，如果該值小于P(P∈(0,1)，其中P為恒定值，那么那只鳥(niǎo)將會(huì)覓食，否則它將保持警戒.規(guī)則2可以表述如下：

(7)

其中j∈[1,…,D]，rand(0,1)表示隨機(jī)生成一個(gè)服從(0,1)均勻分布的值.T和S是兩個(gè)正數(shù)，可分別稱(chēng)為認(rèn)知加數(shù)系數(shù)和社會(huì)加速系數(shù).pi,j是i第只鳥(niǎo)當(dāng)前最佳位置，gj是鳥(niǎo)群當(dāng)前最佳位置.

警戒行為：規(guī)則3下，由于相互競(jìng)爭(zhēng)每只鳥(niǎo)都不會(huì)直接移向群體中間，其位置更新公式可以表述如下：

(8)

(9)

(10)

其中k(k≠i)為正整數(shù)，是從1到N間隨機(jī)選擇的.α1與α2是介于(0,2)之間的兩個(gè)常數(shù)，pFiti表示第i只鳥(niǎo)最佳適應(yīng)度值，sumFit表示鳥(niǎo)群個(gè)體適應(yīng)度值的總和.ε是最小常數(shù)，以避免除0錯(cuò)誤.meanj表示鳥(niǎo)群在j維的平均位置.

飛行行為：由規(guī)則4，鳥(niǎo)群個(gè)體會(huì)分為生產(chǎn)者和乞討者.生產(chǎn)者和乞討者的位置更新公式可表述如下：

(11)

(12)

其中randn(0,1)表示均值為0，標(biāo)準(zhǔn)差為1的高斯分布隨機(jī)數(shù)，k∈(1,…,N)，k≠i.FL(FL∈(0,2))表示乞討者將跟從生產(chǎn)者去尋找食物.另外假設(shè)每只鳥(niǎo)會(huì)在FQ時(shí)間間隔內(nèi)飛往另一個(gè)地方，F(xiàn)Q為正整數(shù).

2.2 BSA-SVM模型

BSA-SVM模型的基本思想為：將懲罰參數(shù)C與核參數(shù)σ作為鳥(niǎo)群個(gè)體位置變量，在這個(gè)二維空間上，通過(guò)適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體所處位置的好壞，由鳥(niǎo)群活動(dòng)時(shí)的三大行為：覓食行為、警戒行為和飛行行為來(lái)更新位置信息，直到迭代結(jié)束時(shí)獲得鳥(niǎo)群最佳位置信息，最終輸出最佳懲罰參數(shù)Cbest與核參數(shù)σbest.BSA-SVM模型實(shí)現(xiàn)步驟可以描述如下.

步驟2：初始化BSA相關(guān)參數(shù).當(dāng)t=0時(shí)，在一定范圍內(nèi)隨機(jī)生成鳥(niǎo)群個(gè)體初始位置，x(i,1)范圍為(Cmin,Cmax)，x(i,2)范圍為(σmin,σmax).同時(shí)設(shè)置鳥(niǎo)群種群規(guī)模N、迭代次數(shù)M、飛行頻率FQ、覓食概率P和常量T、S、α1、α2、FL.

步驟3：計(jì)算適應(yīng)度值.根據(jù)適應(yīng)度函數(shù)計(jì)算每只鳥(niǎo)的適應(yīng)度值，由適應(yīng)度值確定個(gè)體自身最佳位置和群體最佳位置.適應(yīng)度值計(jì)算是根據(jù)x(i,1)與x(i,2)進(jìn)行得到相應(yīng)值.計(jì)算方法為：

其中v表示交叉驗(yàn)證的次數(shù)，c與g分別代表懲罰參數(shù)C與核參數(shù)σ，train_label為訓(xùn)練數(shù)據(jù)集標(biāo)簽，train是訓(xùn)練數(shù)據(jù)集，fitness(i)表示第i只鳥(niǎo)當(dāng)前適應(yīng)度值.

步驟4：迭代尋優(yōu).迭代開(kāi)始，判斷t%FQ是否有余數(shù).

1)若有余數(shù)，則鳥(niǎo)群個(gè)體只進(jìn)行覓食行為或警戒行為.采用規(guī)則1來(lái)判別鳥(niǎo)群個(gè)體進(jìn)行哪種行為，隨機(jī)生成一個(gè)服從均勻分布的值，若該值小于覓食概率P，則該個(gè)體發(fā)生覓食行為，用公式(7)更新位置；否則該個(gè)體保持警戒，用公式(8)更新位置.

2)若沒(méi)有余數(shù)，則將鳥(niǎo)群個(gè)體分為生產(chǎn)者和乞討者.若為生產(chǎn)者，則用公式(11)更新位置；若為乞討者，則用公式(12)更新位置.

步驟5：更新個(gè)體最佳位置和群體最佳位置.若第只鳥(niǎo)當(dāng)前位置優(yōu)于先前自身最佳位置，則將當(dāng)前位置更新為自身最佳位置，同時(shí)更新鳥(niǎo)群當(dāng)前最佳位置.

步驟6：判斷是否達(dá)到最大迭代次數(shù)，若迭代結(jié)束則轉(zhuǎn)至步驟7；否則令t=t+1，轉(zhuǎn)回步驟4.

步驟7：輸出鳥(niǎo)群最佳適應(yīng)度值及鳥(niǎo)群最佳位置所包含的懲罰參數(shù)Cbest與核參數(shù)σbest.

BSA-SVM模型具體流程可歸納為圖1.

圖1 BSA-SVM模型流程圖Fig.1 Flow chart of BSA-SVM model

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

3.1數(shù)據(jù)源

為了驗(yàn)證BSA-SVM模型性能，本文從UCI標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)(http://archive.ics.uci.edu/ml/)選用了8個(gè)數(shù)據(jù)集，與不做參數(shù)選擇的SVM方法、基于粒子群算法的SVM參數(shù)選擇方法[9](PSO-SVM)進(jìn)行MATLAB仿真對(duì)比實(shí)驗(yàn).關(guān)于8個(gè)數(shù)據(jù)集的具體說(shuō)明可見(jiàn)表1.

3.2實(shí)驗(yàn)設(shè)置

SVM懲罰參數(shù)C搜索范圍為[0.1,1000]，核參數(shù)σ搜索范圍為[0.01,100].BSA-SVM模型初始參數(shù)設(shè)置如下：種群規(guī)模N=30，迭代次數(shù)M=200，飛行頻率FQ=10，交叉驗(yàn)證次數(shù)v=10,T=S=1.5，α1=α2=1.PSO-SVM模型初始參數(shù)設(shè)置為：學(xué)習(xí)因子c1=c2=1.5，交叉驗(yàn)證次數(shù)、種群規(guī)模和迭代次數(shù)與鳥(niǎo)群算法均相同.當(dāng)采用不做參數(shù)選擇的SVM方法時(shí)，懲罰參數(shù)C與核參數(shù)σ為默認(rèn)值.

表1 UCI數(shù)據(jù)集

說(shuō)明：訓(xùn)練樣本和測(cè)試樣本在實(shí)驗(yàn)時(shí)均為隨機(jī)選取

本文采用了臺(tái)灣林智仁教授開(kāi)發(fā)的Libsvm3.22工具箱訓(xùn)練和測(cè)試SVM分類(lèi)器.實(shí)驗(yàn)平臺(tái)為Intel奔騰雙核處理器(2.5GHz)，2GB內(nèi)存，Windows 7操作系統(tǒng)，所用軟件為Matlab 2014a.由于模型計(jì)算結(jié)果具有一定的波動(dòng)性，為了公平性與準(zhǔn)確性，所有模型在每個(gè)數(shù)據(jù)集上得到Cbest與σbest后，都會(huì)對(duì)相應(yīng)測(cè)試集進(jìn)行12次預(yù)測(cè)分類(lèi)，在剔除1次最高分類(lèi)準(zhǔn)確率和1次最低分類(lèi)準(zhǔn)確率后，取剩余10次分類(lèi)準(zhǔn)確率的平均值作為最終平均分類(lèi)準(zhǔn)確率.

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

SVM、PSO-SVM與BSA-SVM分類(lèi)測(cè)試結(jié)果如表2所示，其中準(zhǔn)確率指測(cè)試樣本的平均分類(lèi)準(zhǔn)確率.

表2 實(shí)驗(yàn)結(jié)果對(duì)比Tab.2 Comparison of experimental results

由表2可看出，經(jīng)過(guò)PSO算法或BSA優(yōu)化參數(shù)后的SVM分類(lèi)器顯然比未做參數(shù)選擇的SVM分類(lèi)器好，參數(shù)優(yōu)化后的SVM分類(lèi)器能顯著提高分類(lèi)準(zhǔn)確率.此外，BSA-SVM模型與PSO-SVM模型在時(shí)間效率上差不多，但BSA-SVM模型在8個(gè)數(shù)據(jù)集上的分類(lèi)準(zhǔn)確率相對(duì)PSO-SVM模型均有不同程度的提高.

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)方法優(yōu)化SVM參數(shù)存在的問(wèn)題，本文提出使用鳥(niǎo)群算法來(lái)優(yōu)化SVM參數(shù).基于8個(gè)UCI數(shù)據(jù)集的MATLAB仿真對(duì)比實(shí)驗(yàn)表明，BSA-SVM模型加強(qiáng)了分類(lèi)器學(xué)習(xí)能力和泛化能力，能較好地提高分類(lèi)準(zhǔn)確率，是一種有效和可靠的SVM參數(shù)選擇方法.鳥(niǎo)群算法作為一種新穎的優(yōu)化算法，其在SVM參數(shù)選擇中的應(yīng)用才剛剛開(kāi)始，未來(lái)的研究工作除了如何提高優(yōu)化準(zhǔn)確率外，還可以集中于如何改善尋優(yōu)的時(shí)間效率.

[1] Vapnik V N. The nature of statistical learning theory[M].New York: Springer-Verlag,1995:988-999.

[2] 劉洛霞. 基于SVM的多變量函數(shù)回歸分析研究[J]. 電光與控制, 2013, 20(6):50-57.

[3] Huanrui H. New mixed kernel functions of SVM used in pattern recognition[J]. Cybernetics & Information Technologies, 2016,16(5):5-14.

[4] Korpela J, Miyaji R, Maekawa T, et al. Toothbrushing performance evaluation using smartphone audio based on hybrid HMM-recognition/SVM-regression model[J]. Journal of Information Processing, 2016, 24(2):302-313.

[5] Chapelle O, Vapnik V, Bousquet O, et al. Choosing multiple parameters for support vector machines[J]. Machine Learning, 2002, 46(1):131-159.

[6] Keerthi, S S. Efficient tuning of SVM hyperparameters using radius/margin bound and iterative algorithms[J]. Neural Networks IEEE Transactions, 2002,13(5):1225-1229.

[7] Peng, Xiyuan, Hong Xing. Parameter selection method for SVM with PSO[J]. Chinese Journal of Electronics,2006,15(4):638-642.

[8] 莊 嚴(yán),白振林,許云峰. 基于蟻群算法的支持向量機(jī)參數(shù)選擇方法研究[J]. 計(jì)算機(jī)仿真,2011, 28(5):216-219.

[9] 魏 峻. 基于蝙蝠算法的支持向量機(jī)參數(shù)優(yōu)化[J]. 寶雞文理學(xué)院學(xué)報(bào)(自然科學(xué)版),2015,35(3):1-6.

[10] Meng X B, Gao X Z, Lu L, et al. A new bio-inspired optimisation algorithm: Bird Swarm Algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2015,28(4):1-15.

[11] 宋 暉,薛 云,張良均. 基于SVM分類(lèi)問(wèn)題的核函數(shù)選擇仿真研究[J]. 計(jì)算機(jī)與現(xiàn)代化,2011, 2011(8):133-136.

[12] Han S, Cao Q, Han M. Parameter selection in SVM with RBF kernel function[J].Berichte Der Bunsengesellschafz für Physiralische Chemie,2012,85(4):1-4.

ParameterOptimizationofSupportVectorMachineBasedonBirdSwarmAlgorithm

XiaoHaijun,LuChangjing,HeFan

(School of Mathematics & Physics, China University of Geosciences, Wuhan 430074, China)

O235

A

1672-4321(2017)03-0090-05

2017-05-06 *

盧常景，研究方向：數(shù)據(jù)挖掘，E-mail:luchangjing@cug.edu.cn

肖海軍(1965-)，男，教授，博士，研究方向：數(shù)據(jù)挖掘，E-mail: Xiaohj@cug.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目(11301492)；中國(guó)地質(zhì)大學(xué)(武漢)基礎(chǔ)研究基金項(xiàng)目(CUGL140420)