基于PSO與GA的SVM特征選擇與參數(shù)優(yōu)化算法

溫海標(biāo)

摘要摘要：支持向量機(jī)（SVM）在處理大樣本特征維數(shù)較多的數(shù)據(jù)集時(shí)，算法消耗時(shí)間長(zhǎng)而且容易陷入局部最優(yōu)解，選擇不合適的SVM算法參數(shù)會(huì)影響SVM模型分類性能。為了提高SVM性能，提出了基于粒子群算法（PSO）和遺傳算法（GA）相結(jié)合的SVM特征選擇與參數(shù)同步優(yōu)化算法PGS。在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，PGS算法能有效地找出合適的特征子集及SVM算法參數(shù)，提高收斂速度并能在較小的特征子集獲得較高的分類準(zhǔn)確率。

關(guān)鍵詞關(guān)鍵詞：粒子群算法；遺傳算法；支持向量機(jī)；特征選擇；參數(shù)優(yōu)化

DOIDOI：10.11907/rjdk.171267

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）005002103

0引言

分類問(wèn)題主要是分類器模型的選擇、分類樣本的特征選擇以及分類器參數(shù)優(yōu)化等問(wèn)題，是模式識(shí)別領(lǐng)域的基礎(chǔ)問(wèn)題。Vapnik等[1]在1995年提出一種新型有監(jiān)督的統(tǒng)計(jì)學(xué)習(xí)方法——支持向量機(jī)（Support Vector Machines，SVM），在文本分類、圖像分類、人臉識(shí)別等諸多領(lǐng)域得到了成功應(yīng)用，成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。研究表明，SVM分類器的參數(shù)例如核函數(shù)參數(shù)、懲罰參數(shù)C與SVM 的分類性能有很大關(guān)系[2]，選擇合適的參數(shù)能顯著提高SVM的分類精度。特征選擇是根據(jù)某種評(píng)估標(biāo)準(zhǔn)從樣本的原始特征中選擇部分特征作為特征子集[3]。大數(shù)據(jù)時(shí)代下，樣本冗余特征不斷出現(xiàn)，如何從大樣本特征中去除冗余、選取有利特征是機(jī)器學(xué)習(xí)的重要研究課題。樣本特征選擇合理，不但可以消除冗余，而且可以降低算法時(shí)間復(fù)雜度，加快算法運(yùn)行速度，提高分類器的準(zhǔn)確率。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是根據(jù)鳥(niǎo)群撲食行為產(chǎn)生的仿生設(shè)計(jì)算法，屬于一種簡(jiǎn)單有效的全局優(yōu)化算法，已在許多領(lǐng)域得到應(yīng)用，如用于參數(shù)選擇[4]。遺傳算法（Genetic Algorithm，GA）是根據(jù)遺傳變異論和“適者生存”原理啟發(fā)設(shè)計(jì)的算法，經(jīng)過(guò)一系列的選擇、交叉、變異操作，使個(gè)體不斷進(jìn)化，越來(lái)越適應(yīng)環(huán)境，即越來(lái)越接近問(wèn)題的最優(yōu)解。GA算法不依賴于求解問(wèn)題的具體領(lǐng)域，有較強(qiáng)的魯棒性，主要用于解決優(yōu)化問(wèn)題。

一般通過(guò)大量實(shí)驗(yàn)獲得較優(yōu)的參數(shù)和特征子集，但這種方法要消耗大量的時(shí)間，而且獲得的參數(shù)和特征子集不一定好。本文提出一種特征選擇和參數(shù)同步優(yōu)化算法，該算法使用了PSO、GA 和SVM算法，簡(jiǎn)稱為PGS算法。

1相關(guān)概念

1.1支持向量機(jī)

支持向量機(jī)（SVM）是一種機(jī)器學(xué)習(xí)過(guò)程，基本原理是將樣本數(shù)據(jù)映射到一個(gè)高維空間，并在高維空間中尋找一個(gè)最大間隔超平面，將不同類別的樣本數(shù)據(jù)隔離，使間隔最大，從而正確分類樣本數(shù)據(jù)。

e是元素全為1的向量，ξ為誤差，C > 0為懲罰參數(shù)，該參數(shù)的作用是調(diào)整誤差。式（3）最小化問(wèn)題取決于參數(shù)C和核函數(shù)的參數(shù)選擇。選擇合適的參數(shù)可以提升SVM分類性能。

1.2PSO算法

Kennedy等[5]通過(guò)觀察鳥(niǎo)群捕食行為得到啟發(fā)，于1995 年提出粒子群優(yōu)化算法（PSO）。PSO屬于啟發(fā)式算法，與遺傳算法不同，它不是根據(jù)個(gè)體自然進(jìn)化規(guī)律設(shè)計(jì)，而是以生物群體的社會(huì)行為啟發(fā)設(shè)計(jì)。鳥(niǎo)群的個(gè)體與個(gè)體、個(gè)體與群體間相互作用、相互影響，通過(guò)鳥(niǎo)群個(gè)體之間的協(xié)作和信息共享為群體進(jìn)化提供幫助。PSO中粒子追隨當(dāng)前最優(yōu)的粒子在整個(gè)解空間進(jìn)行搜索，通過(guò)協(xié)作和信息共享機(jī)制尋找最優(yōu)解。算法具有調(diào)節(jié)參數(shù)少、收斂速度快、對(duì)特征變化不敏感等優(yōu)點(diǎn)。PSO 算法將每個(gè)個(gè)體看作是在n 維搜索空間中具有一定飛行速度的微粒，該飛行速度可由微粒的飛行經(jīng)驗(yàn)和所有微粒飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。算法描述如下：

式（5）中，w是非負(fù)常數(shù)，稱為慣性因子；c1，c2稱為學(xué)習(xí)因子，一般取非負(fù)常數(shù)，分別用來(lái)調(diào)節(jié)粒子向個(gè)體最優(yōu)粒子和群體最優(yōu)粒子方向飛行的步長(zhǎng)。合適的學(xué)習(xí)因子參數(shù)值可加快算法的收斂速度且不易陷入局部最優(yōu)，通常取[0，2]之間的值；參數(shù)r1和r2是介于[0，1]之間的隨機(jī)數(shù)。

1.3GA算法

HollandJ[6]教授于1975年提出遺傳算法，算法基于生物學(xué)的進(jìn)化論和遺傳變異理論，自然界的物種不斷進(jìn)化以適應(yīng)自然環(huán)境，不斷迭代更新個(gè)體基因。每一次迭代根據(jù)設(shè)定的適應(yīng)度函數(shù)計(jì)算群體所有個(gè)體的適應(yīng)值，然后根據(jù)適應(yīng)值計(jì)算被選中的概率，根據(jù)概率選擇一部分個(gè)體。被選中的個(gè)體一部分直接進(jìn)入下一代，一部分經(jīng)過(guò)交叉變異操作產(chǎn)生下一代。通過(guò)種群初始化、選擇、交叉、變異操作，產(chǎn)生新的一群更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到待求解問(wèn)題空間中越來(lái)越好的區(qū)域，最后得到最適應(yīng)環(huán)境的個(gè)體，也就是問(wèn)題的最優(yōu)解。

2PGS算法

2.1粒子設(shè)計(jì)

當(dāng)缺乏先驗(yàn)知識(shí)時(shí)，SVM分類器選擇高斯核函數(shù)通常比選擇其它核函數(shù)有更好的分類結(jié)果[7]。因此，本文采用RBF徑向基函數(shù)作為核函數(shù)。RBF核函數(shù)為：

ψ（x，xi）=exp-||x-xi||22σ2（7）

式（7）中，σ為徑向基函數(shù)的寬度，為待定優(yōu)化參數(shù)。另外一個(gè)待優(yōu)化參數(shù)是式（2）中的C。因此，粒子包括兩個(gè)部分，即參數(shù)C和參數(shù)σ。

2.2染色體構(gòu)成

遺傳算法中每個(gè)個(gè)體的染色體采用二進(jìn)制編碼方式編碼，每一個(gè)二進(jìn)制位對(duì)應(yīng)特征集中的一個(gè)特征，使用特征長(zhǎng)度為N的0、1二進(jìn)制字符串（x1，x2，...，xN）表示一個(gè)個(gè)體。這個(gè)個(gè)體對(duì)應(yīng)N維特征向量。xi=1代表第i項(xiàng)對(duì)應(yīng)的特征選入特征子集中，反之xi=0代表第i項(xiàng)對(duì)應(yīng)的特征排除于特征子集之外。

2.3適應(yīng)度函數(shù)

算法的目標(biāo)是提高SVM的分類準(zhǔn)確率，盡可能降低所選特征數(shù)目。PGS算法是PSO算法和GA算法的結(jié)合，把PSO中的個(gè)體和GA中的個(gè)體組合，稱之為PGS算法個(gè)體。若PGS算法個(gè)體能使SVM分類器分類精度提高，選定的特征數(shù)目減少，則算法個(gè)體的適應(yīng)值就高。評(píng)價(jià)PGS算法個(gè)體的適應(yīng)度函數(shù)定義為：

fitness=A1+Nm（8）

其中A為分類器的分類精度，N的選定的特征數(shù)目，m為平衡特征數(shù)目和分類精度權(quán)重的參數(shù)，本文m的取值范圍是：0≤m≤1。

2.4PGS算法描述

PGS算法步驟如下：

（1）初始化PSO的粒子群和GA中的種群。本文隨機(jī)產(chǎn)生一組初始值，該初始值是PSO的速度和位置及種群個(gè)體的二進(jìn)制串值。在空間Rn中隨機(jī)產(chǎn)生n個(gè)粒子x1，x2，...，xN，組成初始種群X（t）；隨機(jī)產(chǎn)生各粒子的初始速度v1，v2，...，vN，組成速度矩陣V（t）；每個(gè)粒子的個(gè)體最優(yōu)值f（Pbest，i）的初始值為xi的初始值。

（2）根據(jù)粒子所包含的參數(shù)σ、參數(shù)C 和種群個(gè)體特征子集，調(diào)用LIBSVM算法進(jìn)行學(xué)習(xí)和訓(xùn)練，測(cè)試并記錄分類精度。根據(jù)式（8）計(jì)算粒子適應(yīng)度。

（3）對(duì)每個(gè)PGS組合個(gè)體進(jìn)行適應(yīng)度函數(shù)值f（xi）和自身的最優(yōu)值f（Pbest，i）比較，如果f（xi）>f（Pbest，i），則更新組合個(gè)體的最優(yōu)值，將當(dāng)代適應(yīng)值作為自身的最優(yōu)值。

（4）將每個(gè)組合個(gè)體最好的適應(yīng)值f（xi）與所有組合個(gè)體的最優(yōu)適應(yīng)值f（Gbest）進(jìn)行比較，如果f（xi）>f（Gbest），更新全局最優(yōu)，即用該組合個(gè)體的最好適應(yīng)值取代原全局最優(yōu)適應(yīng)值。

（5）根據(jù)式（5）和式（6），更新粒子的速度和位置，速度調(diào)整規(guī)則如下：

當(dāng)vi>vmax時(shí)，vi=vmax；當(dāng)vi<-vmax時(shí)，vi=-vmax。

（6）每個(gè)基因個(gè)體根據(jù)適應(yīng)值，計(jì)算各自被選中的概率P，P的計(jì)算公式如下：

P（i）=f（i）∑Nj=1f（j）（9）

根據(jù)每個(gè)個(gè)體的概率P，從群體中選擇一部分個(gè)體。

（7）以一定的概率c作交叉運(yùn)算，每?jī)蓚€(gè)基因個(gè)體執(zhí)行單點(diǎn)交叉。

（8）每個(gè)基因個(gè)體發(fā)生變異的概率為m，若某個(gè)個(gè)體發(fā)生變異，則將它包含的二進(jìn)制串中隨機(jī)選取一位取反。

（9）檢查是否滿足設(shè)定的終止條件。如果滿足，則算法結(jié)束，返回目前最優(yōu)的特征子集、參數(shù)C、參數(shù)σ及分類精度；否則T=T+1，轉(zhuǎn)至步驟（2）。設(shè)定終止條件為算法達(dá)到最大迭代次數(shù)T或組合個(gè)體適應(yīng)值大于等于給定值。

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

為了驗(yàn)證基于PSO與GA的SVM特征選擇與參數(shù)優(yōu)化算法的有效性，選取UCI[8]機(jī)器學(xué)習(xí)知識(shí)庫(kù)中的部分?jǐn)?shù)據(jù)集進(jìn)行實(shí)驗(yàn)，見(jiàn)表1。

實(shí)驗(yàn)結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)采用分類準(zhǔn)確率，準(zhǔn)確率值越大分類器性能越好。公式如下：

A=nN（10）

式（10）中N為測(cè)試樣本的樣本總數(shù)，n為正確分類的樣本總數(shù)。

算法采用Matlab編程實(shí)現(xiàn)。Matlab軟件版本為2014a，系統(tǒng)平臺(tái)為AMD Athlon（tm）Ⅱ X2 B24 processor 3.0 GHz，Windows 7旗艦版，4GB內(nèi)存。實(shí)驗(yàn)采用k 折交叉驗(yàn)證法進(jìn)行評(píng)價(jià)。數(shù)據(jù)集隨機(jī)分成k 個(gè)子集，第一次實(shí)驗(yàn)將第一個(gè)子集作為測(cè)試集，其余的子集作為訓(xùn)練集。本文實(shí)驗(yàn)k取10，表1中的每個(gè)數(shù)據(jù)集分別用PGS算法進(jìn)行10次實(shí)驗(yàn)，每次取一個(gè)子集作為測(cè)試集，其余9個(gè)子集作為訓(xùn)練集，取10次實(shí)驗(yàn)所得的準(zhǔn)確率均值加上標(biāo)準(zhǔn)差作為該數(shù)據(jù)集的分類結(jié)果，如圖1所示。

從表2中可以看出，PGS算法的分類準(zhǔn)確率比傳統(tǒng)SVM算法有較大的提高。在每個(gè)數(shù)據(jù)集上，前者的分類準(zhǔn)確率都高于后者，運(yùn)行效率優(yōu)于SVM。從標(biāo)準(zhǔn)差的值可以看出PGS算法比SVM算法有更好的穩(wěn)定性，從圖1可更直觀看出PGS的優(yōu)越性能，也證實(shí)了PGS算法比SVM具有更好的分類性能。

4結(jié)語(yǔ)

本文提出了一種PSO算法與GA算法組合同步優(yōu)化SVM算法參數(shù)和樣本特征的選擇算法，解決了支持向量機(jī)用于學(xué)習(xí)時(shí)，選擇合適算法參數(shù)和樣本特征的問(wèn)題。理論分析和實(shí)驗(yàn)表明，本文算法可有效找出合適的特征子集和SVM參數(shù)，取得了較好的分類效果。

參考文獻(xiàn)參考文獻(xiàn)：

[1]CORTES C，VAPNIK V.Supportvector networks[J].Machine Learning，1995，20（3）：273297.

[2]ZHANG L，WANG L，LIN W.Semisupervised biased maximum margin analysis for interactive image retrieval[J].IEEE Transactions on Image Processing，2012，21（4）：22942308.

[3]孟軍，尉雙云.基于近鄰傳播聚類的集成特征選擇方法[J].計(jì)算機(jī)科學(xué)，2015，42（3）：241244.

[4]徐海龍，王曉丹，廖勇，等.一種基于PSO的RBFSVM模型優(yōu)化新方法[J].控制與決策，2010，25（3）：367370.

[5]KENNEDY J，EBERHART R.Particle swarm optimization[C].IEEE International Conference on Neural Networks，1995：19421948.

[6]GOLDBERG D E.Genetic algorithm in search，optimization，and machine learning[J].Addisonwesley Pub.co，1989（7）：21042116.

[7]ZHANG Y，DAI M，JU Z.Preliminary discussion regarding SVM kernel function selection in the twofold rock slope prediction model[J].Journal of Computing in Civil Engineering，2015（6）：155158.

[8]UCI repository of machine learning datasets[EB/OL].http：//archive.ics.uci.edu/m.

責(zé)任編輯（責(zé)任編輯：杜能鋼）