基于自適應(yīng)遺傳算法的SVM參數(shù)優(yōu)化

孟 滔,周新志,雷印杰

(四川大學(xué) 電子信息學(xué)院，成都 610065)

?

基于自適應(yīng)遺傳算法的SVM參數(shù)優(yōu)化

孟 滔,周新志,雷印杰

(四川大學(xué) 電子信息學(xué)院，成都 610065)

針對(duì)基于遺傳算法支持向量機(jī)(SVM)訓(xùn)練時(shí)間較長(zhǎng)以及分類精度較網(wǎng)格搜索法有所降低等問(wèn)題,通過(guò)重新定義遺傳算法參數(shù)的尋優(yōu)范圍，提出一種自適應(yīng)遺傳算法；該算法根據(jù)網(wǎng)格搜索法得到遺傳算法參數(shù)的最佳尋優(yōu)范圍，然后遺傳算法在這個(gè)范圍內(nèi)進(jìn)行參數(shù)的精確尋優(yōu)，最后得到分類的結(jié)果；這樣不僅可以有效縮短訓(xùn)練時(shí)間，而且擁有更高的分類正確率；通過(guò)UCI中的10組經(jīng)典數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可知，自適應(yīng)遺傳算法較之網(wǎng)格搜索法、 常規(guī)遺傳算法、粒子群算法在訓(xùn)練時(shí)間上有較大的提升，并且擁有較高的分類準(zhǔn)確率。

支持向量機(jī)；參數(shù)優(yōu)化；遺傳算法；網(wǎng)格搜索法

0 引言

支持向量機(jī)(SVM)是Corters和Vapnik等人[1]于1995年提出的一種新的機(jī)器學(xué)習(xí)方法，其根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，最大程度地提高了其泛化能力[2]，在解決小樣本、非線性和高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。但是支持向量機(jī)只是一個(gè)二分類器，實(shí)際應(yīng)用中的問(wèn)題大多數(shù)是多分類問(wèn)題，如何將其推廣到多分類，同時(shí)提高分類準(zhǔn)確度與分類計(jì)算速度一直是機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。

SVM進(jìn)行多分類時(shí)，主要包括兩個(gè)階段，訓(xùn)練階段即參數(shù)尋優(yōu)階段以及利用分類模型進(jìn)行分類階段。參數(shù)尋優(yōu)主要包括核函數(shù)參數(shù)和分類模型參數(shù)的尋優(yōu)，實(shí)際使用中核函數(shù)選用使用最廣泛的徑向基核函數(shù)，分類模型常選用C-支持向量分類機(jī)(C-SVC)支持向量機(jī)，其中核參數(shù)g和懲罰參數(shù)C是決定徑向基核函數(shù)和C-SVC的關(guān)鍵。g表示樣本映射特征空間的復(fù)雜程度，C是對(duì)錯(cuò)分樣本比例和算法復(fù)雜度的折衷，這兩個(gè)參數(shù)是可以人為調(diào)節(jié)的，取值不同，對(duì)應(yīng)的分類器性質(zhì)以及推廣識(shí)別率也將有很大差別[3]。這兩個(gè)階段中分類階段耗時(shí)很少一般在毫秒級(jí)，而參數(shù)尋優(yōu)階段耗費(fèi)的時(shí)間卻遠(yuǎn)遠(yuǎn)大于其分類時(shí)間，一般是分類階段的上萬(wàn)倍以上。故找到最佳核參數(shù)g和懲罰參數(shù)C，是提高分類準(zhǔn)確度有效途徑。而快速找到這組參數(shù)則是提高參數(shù)尋優(yōu)速度的有效途徑。針對(duì)SVM的這兩個(gè)參數(shù)，國(guó)內(nèi)外部分學(xué)者從多個(gè)方面提出了解決方法。例如XL Liu等人[4]提出基于網(wǎng)格搜索最佳核參數(shù)g和懲罰參數(shù)C，該方法通過(guò)遍歷網(wǎng)格中所有的點(diǎn)來(lái)尋找最優(yōu)解，由于尋找的點(diǎn)多，故得到的分類準(zhǔn)確率高，但分類的時(shí)間較長(zhǎng)。Chen P W等人[5]提出使用遺傳算法優(yōu)化核參數(shù)g和懲罰參數(shù)C，該方法屬于啟發(fā)式算法，不必遍歷網(wǎng)格內(nèi)所有的參數(shù)點(diǎn)，也能找到全局最優(yōu)解。然而在實(shí)際應(yīng)用中，存在SVM模型參數(shù)尋優(yōu)范圍不確定的問(wèn)題，參數(shù)的尋優(yōu)范圍設(shè)置過(guò)大時(shí)，訓(xùn)練的時(shí)間過(guò)長(zhǎng)，參數(shù)的尋優(yōu)范圍設(shè)置過(guò)小時(shí)，分類的準(zhǔn)確率難以得到保證。Eberhart R等人[6]提出使用粒子群算法來(lái)對(duì)這兩個(gè)參數(shù)進(jìn)行尋優(yōu)，雖然分類的準(zhǔn)確率較遺傳算法有所提升，但由于復(fù)雜度提升了反而訓(xùn)練時(shí)間比遺傳算法長(zhǎng)。

本文優(yōu)化了現(xiàn)有遺傳算法對(duì)核參數(shù)g和懲罰參數(shù)C的尋優(yōu)范圍，首先在大范圍中快速找到最佳參數(shù)組的粗值，然后通過(guò)縮小和放大這個(gè)參數(shù)組的粗值，得到遺傳算法參數(shù)的最小尋優(yōu)范圍，這樣不僅可以快速得到最佳的參數(shù)組，而且對(duì)不同的數(shù)據(jù)集不必每次都重新設(shè)定遺傳算法參數(shù)的尋優(yōu)范圍。并且由于通過(guò)網(wǎng)格搜索法得到的是最佳參數(shù)的最小值范圍，所以得到的懲罰參數(shù)C值較小，具有較好的泛化能力。實(shí)驗(yàn)表明該算法比網(wǎng)格搜索法、常規(guī)遺傳算法、粒子群算法具有更好的訓(xùn)練速度，并且分類精度較常規(guī)遺傳算法有所提升。

1 支持向量機(jī)SVM

支持向量機(jī)是由尋找線性可分情況下的最優(yōu)分類平面發(fā)展而來(lái)的[7]，主要思想是建立一個(gè)分類超平面作為決策面，使得正例和反例之間的隔離邊緣被最大化。其中分類超平面就是求函數(shù)：

(1)

s.t yi(w·xi+b)≥1,?i=1,2,...,n的最小值。其中w是超平面的法向量，b是超平面的常數(shù)項(xiàng)，xi為訓(xùn)練樣本，yi為樣本的類別。

支持向量機(jī)進(jìn)行多分類時(shí)，數(shù)據(jù)集往往是非線性且不可分的，需要在約束條件中引入松弛因子，在目標(biāo)函數(shù)中加入懲罰參數(shù)C以及引入核函數(shù)將樣本映射到一個(gè)新的空間，使其在新的空間里可以實(shí)現(xiàn)線性可分來(lái)解決這一問(wèn)題。其中，懲罰參數(shù)C用于控制模型復(fù)雜度和逼近誤差的折中。若C過(guò)大，就會(huì)引起過(guò)學(xué)習(xí)，影響分類器的泛化能力。

目前實(shí)際工程中廣泛使用的核函數(shù)主要有線性核函數(shù)(Linear)，多項(xiàng)式核函數(shù)(Poly)，徑向基核函數(shù)(Radial Basis Function,RBF),兩層感知器核函數(shù)(Sigmoid)四類[8]。其中徑向基核函數(shù)是目前應(yīng)用最廣泛的核函數(shù)，文中也將采用此核函數(shù)。其形式如下：

(2)

其中，g為核函數(shù)中的重要參數(shù)，影響著SVM分類算法的復(fù)雜程度。

2 自適應(yīng)遺傳算法尋優(yōu)方法

遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，經(jīng)過(guò)數(shù)代選擇、遺傳、變異，最后得到最適應(yīng)環(huán)境的種群[9]。將遺傳算法引入到SVM參數(shù)尋優(yōu)當(dāng)中，較之傳統(tǒng)的網(wǎng)格搜索法具有更高的分類速度，且當(dāng)參數(shù)的尋優(yōu)范圍設(shè)置恰當(dāng)時(shí)，其分類準(zhǔn)確度也比較高。

2.1 傳統(tǒng)遺傳算法

傳統(tǒng)的遺傳算法對(duì)參數(shù)的尋優(yōu)范圍往往是基于學(xué)者的自身經(jīng)驗(yàn)進(jìn)行設(shè)定的。收斂速度慢且容易出現(xiàn)種群早熟現(xiàn)象或陷入局部極值點(diǎn),不能保證收斂到全局最優(yōu)解。在最大進(jìn)化代數(shù)和總?cè)簲?shù)相同的情況下，尋優(yōu)的范圍越小得到的結(jié)果越好，且尋優(yōu)的時(shí)間也越短。而當(dāng)尋優(yōu)的范圍足夠小但最佳的參數(shù)不在這個(gè)范圍時(shí)，得到的結(jié)果卻不是最佳的。故如何確定這個(gè)范圍是提高遺傳算法尋優(yōu)的關(guān)鍵問(wèn)題。并且針對(duì)不同的數(shù)據(jù)集，尋優(yōu)范圍如果是固定在一個(gè)范圍，得到的結(jié)果不一定是最佳的。故能自適應(yīng)的設(shè)置參數(shù)尋優(yōu)的范圍是解決此問(wèn)題的關(guān)鍵。

2.2 自適應(yīng)遺傳算法

通過(guò)網(wǎng)格搜索法對(duì)wine數(shù)據(jù)(來(lái)自UCI)進(jìn)行預(yù)測(cè)，可以得到圖1。由圖1可知，懲罰參數(shù)C和核函數(shù)參數(shù)g只有在一定的范圍內(nèi)對(duì)應(yīng)的訓(xùn)練集分類準(zhǔn)確率很高，但是絕大部分的范圍內(nèi)，分類準(zhǔn)確率都比較低。如能先定位出比較好的參數(shù)尋優(yōu)區(qū)間，再進(jìn)行精確搜索，就能夠減少不必要的計(jì)算，提高尋優(yōu)的速度。針對(duì)以上問(wèn)題，提出一種自適應(yīng)遺傳算法。首先，網(wǎng)格搜索法在較大范圍內(nèi)采用較大步距進(jìn)行粗搜，選擇使分類準(zhǔn)確率最高的一組C和g。如果參數(shù)選擇過(guò)程中有多組的C和g對(duì)應(yīng)于最高的驗(yàn)證分類準(zhǔn)確率，則選擇能夠達(dá)到最高驗(yàn)證分類準(zhǔn)確率中參數(shù)C最小的這組C和g做為粗搜的基準(zhǔn)值。因?yàn)镃過(guò)大時(shí)會(huì)導(dǎo)致過(guò)學(xué)習(xí)狀態(tài)發(fā)生，即訓(xùn)練集分類準(zhǔn)確率很高而測(cè)試集分類準(zhǔn)確率很低，故選擇C最小的那組參數(shù)做為最佳的選擇對(duì)象，這樣就解決了參數(shù)尋優(yōu)范圍的問(wèn)題。圖2就是利用該方法后同樣通過(guò)網(wǎng)格搜索法得到的結(jié)果，可以看到參數(shù)的尋優(yōu)范圍大大縮小了。

圖1 網(wǎng)格搜索法尋優(yōu)結(jié)果

圖2 優(yōu)化后網(wǎng)格搜索法尋優(yōu)結(jié)果

解決了參數(shù)尋優(yōu)的范圍，但如何保證最佳的參數(shù)在這個(gè)區(qū)間內(nèi)。為此首先來(lái)分析參數(shù)C和徑向基核參數(shù)g在SVM中存在的相互影響關(guān)系[10]。當(dāng)C值過(guò)小時(shí)，SVM預(yù)測(cè)精度較低，易出現(xiàn)欠學(xué)習(xí)狀態(tài)；隨著C值增大，預(yù)測(cè)精度逐漸提高，但當(dāng)C超過(guò)一定值時(shí)又會(huì)出現(xiàn)過(guò)學(xué)習(xí)狀態(tài)；若此時(shí)g值亦隨之增大，則可平衡C值產(chǎn)生的影響。同理g值過(guò)大時(shí)，也會(huì)出現(xiàn)過(guò)學(xué)習(xí)或欠學(xué)習(xí)狀態(tài)。因此，參數(shù)C和g共同作用時(shí)，理論上存在一個(gè)有效區(qū)域，在該區(qū)域中存在一對(duì)預(yù)測(cè)結(jié)果最佳的參數(shù)組合。通過(guò)上述可知，這組參數(shù)存在著相互制約的關(guān)系，即可以認(rèn)為這組參數(shù)不會(huì)太大，通過(guò)UCI上10組經(jīng)典測(cè)試得到了驗(yàn)證，一般都小于100。為了更加有效的找到這組參數(shù)，將C和g參數(shù)的粗尋優(yōu)范圍設(shè)置的足夠大,這樣就保證了最佳參數(shù)在粗尋優(yōu)的區(qū)間內(nèi)。

2.3 基于自適應(yīng)遺傳算法的SVM參數(shù)優(yōu)化的具體算法實(shí)現(xiàn)

自適應(yīng)遺傳算法的步驟如下：

圖3 自適應(yīng)遺傳算法過(guò)程圖

1) 載入需要進(jìn)行測(cè)試的數(shù)據(jù)集包括數(shù)據(jù)的特征屬性和分類類別；

2) 隨機(jī)生成指定數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)和預(yù)測(cè)數(shù)據(jù)；

3) 對(duì)訓(xùn)練和預(yù)測(cè)數(shù)據(jù)按照式(3)進(jìn)行歸一化處理。

(3)

其中：xmin表示此列特征維中最小值；xmax表示此列特征維中最大值；y表示x被歸一化后結(jié)果。

4)設(shè)定網(wǎng)格搜索的變量(C，g)的范圍以及搜索的步距。其中C的初始范圍設(shè)置為[2-5,25],g的初始范圍設(shè)置為[2-10,210]。傳統(tǒng)的網(wǎng)格搜索法的步距一般設(shè)置為0.1，而本文方法中采用步距為2，為傳統(tǒng)步距的20倍，大大提升了搜索的時(shí)間。

5) 利用網(wǎng)格搜索法，初步求出變量(C，g)的值即bestc,bestg。此值作為遺傳算法參數(shù)C和g的基準(zhǔn)值。

6) 設(shè)定遺傳算法的參量，其中C的范圍設(shè)定為[0.5*bestc,2*bestc],g的范圍設(shè)定為[0.5*bestg,2*bestg]。傳統(tǒng)的遺傳算法C和g的尋優(yōu)范圍都設(shè)定為[0,100]。

7) 利用遺傳算法求取預(yù)測(cè)數(shù)據(jù)的分類準(zhǔn)確率。

3 仿真結(jié)果分析

實(shí)驗(yàn)使用的計(jì)算機(jī)平臺(tái)為windows 7(64位)系統(tǒng)，處理器為Core(TM)i5,內(nèi)存為8 GB。使用的軟件仿真平臺(tái)為matlab2010b,采用臺(tái)灣大學(xué)林智仁(Chih-Jen Lin)博士等

開(kāi)發(fā)設(shè)計(jì)的LIBSVM工具包進(jìn)行測(cè)試。核函數(shù)采用用于最廣泛的徑向基核函數(shù)(Radial Basis Function,RBF)。分別采用網(wǎng)格搜索法，傳統(tǒng)遺傳算法，粒子群算法，自適應(yīng)遺傳算法進(jìn)行對(duì)UCI上典型的10組數(shù)據(jù)(見(jiàn)表1所示)進(jìn)行測(cè)試。測(cè)試結(jié)果見(jiàn)表2和表3所示。

表1 10組經(jīng)典數(shù)據(jù)集

從時(shí)間效率方面，從表2可以明顯看出，傳統(tǒng)的網(wǎng)格搜索法耗時(shí)最長(zhǎng)，因?yàn)樗潜闅v大范圍的所有點(diǎn)進(jìn)行尋優(yōu)，且在該范圍內(nèi)大多數(shù)點(diǎn)都不是最佳的點(diǎn)，故其尋優(yōu)時(shí)間最長(zhǎng)。而傳統(tǒng)的遺傳算法由于是固定參數(shù)的搜索范圍，往往范圍過(guò)大，導(dǎo)致故其搜索的時(shí)間也較長(zhǎng)。本文提出的自適應(yīng)遺傳算法耗時(shí)最少，因?yàn)槠鋮?shù)的尋優(yōu)范圍大大縮小了，特別是在數(shù)據(jù)集越加復(fù)雜時(shí)，訓(xùn)練的速度更加明顯。

從分類精度方面，從表3可以看出，網(wǎng)格搜索法在數(shù)據(jù)集較簡(jiǎn)單的情況下得到的分類準(zhǔn)確率往往較高，而當(dāng)數(shù)據(jù)集越加復(fù)雜時(shí)自適應(yīng)遺傳算法的分類準(zhǔn)確率較高，且往往比常規(guī)遺傳算法高，因?yàn)槌Ｒ?guī)遺傳算法是基于經(jīng)驗(yàn)設(shè)置的參數(shù)尋優(yōu)范圍，在相同的情況下搜索的不夠精細(xì)，往往搜索到的C值過(guò)大，即容易導(dǎo)致過(guò)學(xué)習(xí)狀態(tài)的發(fā)生，而采用本文提出的自適應(yīng)遺傳算法因?yàn)閺木W(wǎng)格搜索法得到的參數(shù)范圍的值較小，可以有效的減小尋優(yōu)得到的參數(shù)C，從而改善這種情況，即對(duì)分類的準(zhǔn)確率有所提升。

表2 預(yù)測(cè)結(jié)果對(duì)比

表3 預(yù)測(cè)結(jié)果對(duì)比

4 結(jié)論

針對(duì)常規(guī)遺傳算法存在SVM模型參數(shù)搜索范圍不確定，導(dǎo)致參數(shù)搜索時(shí)間過(guò)長(zhǎng)，分類準(zhǔn)確率較網(wǎng)格搜索法有所降低等問(wèn)題，基于核參數(shù)g和懲罰參數(shù)C之間的相互關(guān)系，通過(guò)網(wǎng)格搜索法確定最佳參數(shù)的最小尋優(yōu)范圍，有效地幫助常規(guī)遺傳算法避免陷入局部最優(yōu)解，為遺傳算法的參數(shù)范圍設(shè)置，提供了有效的方法，保證了搜索的效率，并改善了基于常規(guī)遺傳算法得到的懲罰參數(shù)C過(guò)大，導(dǎo)致的分類準(zhǔn)確率較低的問(wèn)題。最后通過(guò)網(wǎng)格搜索法、常規(guī)遺傳算法、粒子群算法以及自適應(yīng)遺傳算法對(duì)比實(shí)驗(yàn)。表明該算法具有更快的尋優(yōu)速度，能較好的解決常規(guī)遺傳算法參數(shù)設(shè)置不確定性導(dǎo)致的尋優(yōu)較慢以及分類精度較網(wǎng)格搜索法有所降低等問(wèn)題。

[1] Cortes C,Vapnic V.Support-vector networks [J].Machine Learning.1995,20(3): 273-297.

[2] Vapnik V,Levin E,Cun Y L.Measuring The VC-dimension of a learning machines[J]. Neural Computation,1994,6(5):851-876.

[3] 王 鵬，朱小燕.基于RBF核的SVM的模型選擇及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2003,39(24):72-73.

[4] Liu Xianglou, Jia Dongxu, Li Hui.Research on Kernel parameter optimization of support vector machine in speaker recognition[J]. Science Technology And Engineering,2010, 10(7):1669-1673.

[5] Chen P W, Wang J Y,Lee H. Model selection of SVMs using GA approach[A].Proc of 2004 IEEE Int Joint Conf on Neural Networks[C].Piscataway,USA,2004:2035-2040.

[6] Eberhart R,Kenney J. A new optimizer using particle swarm theory[A].Proc of the sixth Internation Symposium on Micro Machine and Human Science[C].Piscataway, USA,1995:39-43.

[7] Cevikalp H.New clustering algorithms for the support vector machine based hierarchical classification[J].Pattern Recognition Letters, 2010,31:1285.

[8] 楊志民，劉廣利.不確定性支持向量機(jī)-算法及應(yīng)用[M].北京：科技出版社，2012.

[9] 朱慶生，程 柯.一種基于累積適應(yīng)度遺傳算法的SVM多分類決策樹(shù)[J].計(jì)算機(jī)應(yīng)用研究，2016,33(1):64-67.

[10] Keerthiss,Lin C J.Asymptotic behaviors of support vector machines with Gaussian kernel[J].Neural Computation,2003,15(7): 1667-1689.

A Parameters Optimization Method for an SVM Based on Adaptive Genetic Algorithm

Meng Tao，Zhou Xinzhi，Lei Yinjie

(College of Electronics and Information Engineering,Sichuan University,Chengdu 610065,China)

Aiming at that training needs a long time and classification accuracy worse than grid algorithm which reduced the benefits of support vector machine (SVM) based on genetic algorithm.This paper redefined the optimal range of the parameters of genetic algorithm,and proposed an adaptive genetic algorithm.According to the grid search method to get the best optimization genetic algorithm parameter range, and then the genetic algorithm in this range for accurate optimization of parameters, get the final classification results. It can not only shorten the time effectively, and it has higher classification accuracy.Experimental results on the UCI 10 classical dataset verify that adaptive genetic algorithm is better than the grid search method、traditional genetic algorithm、particle swarm optimization (PSO) algorithm in the aspect of training time,and has higher classification accuracy.

support vector machine;parameter optimization;genetic algorithm; grid search method

2016-03-30；

2016-04-18。

國(guó)家“973計(jì)劃”資助項(xiàng)目(2013CB328903)；國(guó)家自然科學(xué)基金資助項(xiàng)目(61403265)

孟 滔(1987-)，男，四川成都人，碩士研究生，主要從事智能控制方向的研究。

周新志(1966-)，男，四川德陽(yáng)人，教授，碩士研究生導(dǎo)師，主要從事智能控制方向的研究。

1671-4598(2016)09-0215-03

10.16526/j.cnki.11-4762/tp.2016.09.060

TP181

A