溫海標

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

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

DOIDOI：10.11907/rjdk.171267

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）005002103

0引言

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

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

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

1相關(guān)概念

1.1支持向量機

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

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

1.2PSO算法

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

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

1.3GA算法

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

2PGS算法

2.1粒子設(shè)計

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

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

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

2.2染色體構(gòu)成

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

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

算法的目標是提高SVM的分類準確率，盡可能降低所選特征數(shù)目。PGS算法是PSO算法和GA算法的結(jié)合，把PSO中的個體和GA中的個體組合，稱之為PGS算法個體。若PGS算法個體能使SVM分類器分類精度提高，選定的特征數(shù)目減少，則算法個體的適應(yīng)值就高。評價PGS算法個體的適應(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中的種群。本文隨機產(chǎn)生一組初始值，該初始值是PSO的速度和位置及種群個體的二進制串值。在空間Rn中隨機產(chǎn)生n個粒子x1，x2，...，xN，組成初始種群X（t）；隨機產(chǎn)生各粒子的初始速度v1，v2，...，vN，組成速度矩陣V（t）；每個粒子的個體最優(yōu)值f（Pbest，i）的初始值為xi的初始值。

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

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

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

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

當vi>vmax時，vi=vmax；當vi<-vmax時，vi=-vmax。

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

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

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

（7）以一定的概率c作交叉運算，每兩個基因個體執(zhí)行單點交叉。

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

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

3實驗

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

實驗結(jié)果的評價標準采用分類準確率，準確率值越大分類器性能越好。公式如下：

A=nN（10）

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

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

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

4結(jié)語

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

參考文獻參考文獻：

[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].計算機科學(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é)任編輯：杜能鋼）