改進(jìn)的基于粒子群優(yōu)化的支持向量機(jī)特征選擇和參數(shù)聯(lián)合優(yōu)化算法

張進(jìn) 丁勝 李波

摘要：針對支持向量機(jī)（SVM）中特征選擇和參數(shù)優(yōu)化對分類精度有較大影響，提出了一種改進(jìn)的基于粒子群優(yōu)化（PSO）的SVM特征選擇和參數(shù)聯(lián)合優(yōu)化算法（GPSOSVM），使算法在提高分類精度的同時選取盡可能少的特征數(shù)目。為了解決傳統(tǒng)粒子群算法在進(jìn)行優(yōu)化時易出現(xiàn)陷入局部最優(yōu)和早熟的問題，該算法在PSO中引入遺傳算法（GA）中的交叉變異算子，使粒子在每次迭代更新后進(jìn)行交叉變異操作來避免這一問題。該算法通過粒子之間的不相關(guān)性指數(shù)來決定粒子之間的交叉配對，由粒子適應(yīng)度值的大小決定其變異概率的大小，由此產(chǎn)生新的粒子進(jìn)入到群體中。這樣使得粒子跳出當(dāng)前搜索到的局部最優(yōu)位置，提高了群體的多樣性，在全局范圍內(nèi)尋找更優(yōu)值。在不同數(shù)據(jù)集上進(jìn)行實驗，與基于PSO和GA的特征選擇和SVM參數(shù)聯(lián)合優(yōu)化算法相比，GPSOSVM的分類精度平均提高了2%～3%，選擇的特征數(shù)目減少了3%～15%。實驗結(jié)果表明，所提算法的特征選擇和參數(shù)優(yōu)化效果更好。

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

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

Abstract：In view of feature selection and parameter optimization in Support Vector Machine （SVM） have great impact on the classification accuracy， an improved algorithm based on Particle Swarm Optimization （PSO） for SVM feature selection and parameter optimization （GPSOSVM） was proposed to improve the classification accuracy and select the number of features as little as possible. In order to solve the problem that the traditional particle swarm algorithm was easy to fall into local optimum and premature maturation， the crossover and mutation operator were introduced from Genetic Algorithm （GA） that allows the particle to carry out cross and mutation operations after iteration and update to avoid the problem in PSO. The cross matching between particles was determined by the noncorrelation index between particles and the mutation probability was determined by the fitness value， thereby new particles was generated into the group. By this way， the particles jump out of the previous search to the optimal position to improve the diversity of the population and to find a better value. Experiments were carried out on different data sets， compared with the feature selection and SVM parameters optimization algorithm based on PSO and GA， the accuracy of GPSOSVM is improved by an average of 2% to 3%， and the number of selected features is reduced by 3% to 15%. The experimental result show that the features selection and parameter optimization of the proposed algorithm are better.

Key words：Support Vector Machine （SVM）； feature selection； parameter optimization； Particle Swarm Optimization （PSO） algorithm； Genetic Algorithm （GA）； no correlation index

0 引言

支持向量機(jī)（Support Vector Machine，SVM）用于高維數(shù)據(jù)分類具有較好的分類性能。由于高維數(shù)據(jù)中不可避免地存在與其他特征相冗余的特征，不僅降低SVM分類精度，而且增加算法的時間和空間復(fù)雜度。通過特征選擇算法實行降維[1-4]能有效消除冗余特征，提高算法性能。此外，在SVM分類問題中，參數(shù)設(shè)置對分類器的性能有較大的影響，合適的參數(shù)能提高分類器的性能。SVM的參數(shù)選擇問題，其實質(zhì)就是一個優(yōu)化問題?，F(xiàn)有參數(shù)優(yōu)化的方法中，交叉驗證[5]是目前應(yīng)用較為普遍的一種方法，該方法易于實現(xiàn)，但是計算量大，尤其對于大樣本問題。近幾年來，進(jìn)化計算算法成為參數(shù)優(yōu)化的新型優(yōu)化算法，文獻(xiàn)[6]提出了基于蟻群算法的支持向量機(jī)參數(shù)選取算法；文獻(xiàn)[7]提出了采用遺傳算法優(yōu)化最小二乘支持向量機(jī)參數(shù)的方法。上述算法僅對特征子集或?qū)VM參數(shù)單獨進(jìn)行優(yōu)化。實際上，特征選擇與參數(shù)優(yōu)化在提高SVM分類精度上相互影響。如何將兩者聯(lián)合優(yōu)化以獲得最優(yōu)分類性能，是目前SVM分類問題研究領(lǐng)域的一個熱點。文獻(xiàn)[8]提出了基于蜜蜂算法的SVM特征選擇和參數(shù)優(yōu)化，文獻(xiàn)[9]提出了應(yīng)用遺傳算法（Genetic Algorithm，GA）同步進(jìn)行特征選擇和參數(shù)優(yōu)化的方法（GASVM）。其中，遺傳算法是一種全局優(yōu)化算法，雖然克服了一般迭代方法中容易陷入局部最優(yōu)的缺點，但是搜索速度較慢。粒子群優(yōu)化 （Particle Swarm Optimization，PSO） 算法是一種新興的優(yōu)化算法，近年來在許多領(lǐng)域得到應(yīng)用，如用粒子群算法用于圖像處理[10]、優(yōu)化問題[11]和分類問題[12]。近年來，出現(xiàn)基于PSO的特征選擇和參數(shù)同步優(yōu)化的（PSOSVM）算法[13]。PSO算法雖然搜索速度較快，但是存在容易陷入局部最優(yōu)和早熟的問題。針對這一情況，可以將遺傳算法和粒子群算法結(jié)合起來，用于特征選擇和SVM參數(shù)同步優(yōu)化。

本文將GA的交叉和變異機(jī)制引入到PSO中，提出了一種改進(jìn)的基于PSO的SVM特征選擇和參數(shù)聯(lián)合優(yōu)化算法（GPSOSVM）。

2 GPSOSVM算法

傳統(tǒng)粒子群優(yōu)化算法對于位置與速度的更新具有很好的導(dǎo)向性，對空間最優(yōu)解的逼近能力較強(qiáng)，但是存在容易陷入局部最優(yōu)解、搜索精度較低、后期迭代效率不高等缺點。而遺傳算法（GA）的交叉和變異操作，都缺乏明確的導(dǎo)向性，對空間最優(yōu)解的逼近能力不足，但是能擴(kuò)大搜索空間，對空間最優(yōu)解的搜索能力相對較強(qiáng)，不容易陷入局部最優(yōu)。本文把兩種算法進(jìn)行結(jié)合，將遺傳算法的交叉和變異機(jī)制引入到粒子群優(yōu)化算法中，提出了GPSOSVM算法，在粒子每次迭代更新后通過交叉和變異操作產(chǎn)生出新的個體，對當(dāng)前適應(yīng)度較低的個體進(jìn)行替換，拓展粒子群在迭代中不斷縮小的搜索空間，使粒子跳出當(dāng)前搜索到的局部最優(yōu)值位置，在更大的空間搜索，尋找更優(yōu)值。

2.1 粒子編譯碼

2.3 慣性權(quán)重

慣性權(quán)重w是粒子保持原來速度的系數(shù)，體現(xiàn)的是繼承當(dāng)前速度的程度，較大的值利于全局搜索，而較小的值利于局部搜索。一般情況下，w設(shè)為1。為了更好地平衡算法的全局搜索與局部搜索能力，采用動態(tài)慣性權(quán)重，在迭代初期設(shè)置較大的慣性權(quán)重搜索較大的區(qū)域，而迭代后期設(shè)置較小的慣性權(quán)重進(jìn)行更精細(xì)的局部搜索。和一般線性遞減慣性權(quán)重的方式不同，本文采用一種慣性權(quán)重非線性遞減方式，使慣性權(quán)重前期下降較慢，后期下降較快，進(jìn)行更精確的搜索。慣性權(quán)重更新公式如下：

2.4.2 交叉方式

本文中粒子是由懲罰參數(shù)C、核參數(shù)γ和特征子集三段組成，在選擇交叉點時，對三部分位串都進(jìn)行交叉，保證交叉操作作用到三部分位串上。懲罰參數(shù)C和核參數(shù)γ位串采用單點交叉法，即在該位串上只選擇一個交叉點。交叉點的位置決定了子代基因的組成方式，如果交叉點選取得不合適，則交叉后很可能產(chǎn)生和父代一樣的個體，特別是在迭代后期由于粒子群中粒子逐漸趨于一致，每個粒子基因趨于相同，導(dǎo)致出現(xiàn)無效交叉操作的可能性更大。如下所例，由于交叉點位置選取得不合適導(dǎo)致出現(xiàn)和父代一樣的子代。

2.6 算法流程

算法輸入 數(shù)據(jù)集D，參數(shù)C的最大值Cmax和最小值Cmin，參數(shù)γ的最大值γmax和最小值γmin，適應(yīng)度函數(shù)權(quán)重Wa和Wf，粒子長度num，粒子群數(shù)目group，最大迭代次數(shù)Dmax，學(xué)習(xí)因子c1和c2，初始慣性權(quán)重wstart，迭代至最大次數(shù)時的慣性權(quán)重wend。

算法輸出 最優(yōu)個體及其適應(yīng)度值，優(yōu)化的特征子集，支持向量的參數(shù)C、γ和對應(yīng)的分類精度。

步驟1 對數(shù)據(jù)集D進(jìn)行規(guī)范化處理，將全部特征值都變換到[0，1]區(qū)間上，并將數(shù)據(jù)集分為訓(xùn)練集D1和測試集D2。

步驟2 設(shè)定輸入各參數(shù)，初始化粒子群X。

步驟3 把粒子的二進(jìn)制碼根據(jù)式（7）轉(zhuǎn)換成支持向量機(jī)的參數(shù)C、γ和數(shù)據(jù)特征子集，利用SVM進(jìn)行學(xué)習(xí)和訓(xùn)練，得出分類精度。最后由式（8）計算出粒子群中每個粒子的適應(yīng)度值。

步驟4 根據(jù)粒子適應(yīng)度，更新每個粒子個體歷史最優(yōu)位置Pbesti以及整個粒子群的群體歷史最優(yōu)位置Gbest。

步驟5 根據(jù)式（9）更新慣性權(quán)重w（k），再根據(jù)式（1）和（2）更新種群X的速度和位置，計算得出這一代粒子的適應(yīng)度值。

步驟6 新建粒子群Y，令Y=X。

步驟7 根據(jù)本文提出的交叉操作方法（見2.4節(jié)），對種群Y進(jìn)行交叉操作。

步驟8 根據(jù)本文提出的變異操作方法（見2.5節(jié)），對種群Y進(jìn)行變異操作。

步驟9 對新種群Y求取適應(yīng)度值，對比X和Y中對應(yīng)個體的適應(yīng)度值，對Y中適應(yīng)度值比X高的個體對X進(jìn)行替換，并更新X中的Pbesti和Gbest。

步驟10 判斷是否達(dá)到最大迭代次數(shù)：若已經(jīng)達(dá)到，則輸出最優(yōu)個體；如果沒有達(dá)到，則跳轉(zhuǎn)到步驟5繼續(xù)運行。

步驟11 通過最優(yōu)個體得到參數(shù)C、γ和特征子集，構(gòu)造GPSOSVM分類器，得出最終的分類精度。

3 實驗研究

3.1 實驗環(huán)境和實驗數(shù)據(jù)

算法用Matlab編程實現(xiàn)，計算機(jī)配置為雙核，內(nèi)存4GB，CPU速度為3.50GHz，SVM采用LIBSVM[15]。為驗證算法的有效性，采用多個UCI數(shù)據(jù)集進(jìn)行研究，如表1所示。

3.2 實驗評價方法

為了驗證算法的效果，實驗采用K折交叉驗證求取分類精度，以減小SVM分類的誤差。把表1中每個數(shù)據(jù)集隨機(jī)分成n個子集，每次取一個作為測試集，其余n-1個合并為訓(xùn)練集。每個子集分別做一次測試，連續(xù)運行n次，然后取n次實驗結(jié)果的算術(shù)平均值作為運行一次所得到的分類精度。本實驗中n值取10。

表2是GPSOSVM算法同SVM算法，PSOSVM算法和GASVM算法在相同數(shù)據(jù)集上所達(dá)到分類精度的比較。其結(jié)果是算法在某一數(shù)據(jù)集上連續(xù)運行10次所得出精度的平均值。表3是GPSOSVM算法同PSOSVM算法和GASVM算法在相同數(shù)據(jù)集上所選出的特征選擇數(shù)目比較。其結(jié)果是算法在數(shù)據(jù)集上連續(xù)運行10次所得出的平均值。

3.5 實驗分析

從圖2看出，相比PSOSVM算法和GASVM算法，本文提出的GPSOSVM算法得到的最佳適應(yīng)度值最高，能找到最優(yōu)的個體，其參數(shù)優(yōu)化和特征選擇能力更強(qiáng)。GPSOSVM算法與另外兩種算法對比，GASVM算法過早陷入了成熟，PSOSVM算法最佳適應(yīng)度值相對不高，GPSOSVM算法在迭代過程中能找到適應(yīng)度更高的個體。從圖3可以看出，GPSOSVM算法迭代中的平均適應(yīng)度值的震蕩范圍更大，也就是說在解空間中搜索范圍更大，不易陷入局部最優(yōu)解。

從表2看出，SVM算法的分類精度明顯低于另外三種算法，可以證明進(jìn)行特征選擇和參數(shù)優(yōu)化后的SVM分類器分類效果會更好。在三種優(yōu)化算法中，GPSOSVM算法的分類精度同PSOSVM算法和GASVM算法相比更高。比如對于二分類數(shù)據(jù)集Sonar，GPSOSVM算法總命中率為88.7500%，PSOSVM算法總命中率為83.8462%，GASVM算法總命中率為84.5192%。GPSOSVM算法比PSOSVM算法提高4.9038個百分點，比GASVM算法提高4.2308個百分點。

對于多分類數(shù)據(jù)集Air，GPSOSVM算法比PSOSVM算法提高2.0612個百分點，比GASVM算法提高2.6741個百分點。此外，GPSOSVM算法同另外三種算法相比，得到的正命中率和反命中率相差最小，因此，均衡性更好。

由于SVM算法沒有特征選擇能力，故對其他三種算法所選出特征子集的數(shù)目進(jìn)行比較。從表3可以看出，GPSOSVM算法同PSOSVM算法和GASVM算法相比，GPSOSVM算法所選出特征子集的數(shù)目要少于PSOSVM算法和GASVM算法所選的數(shù)目。以特征數(shù)目較多的數(shù)據(jù)集Sonar（特征數(shù)目為60）為例，GPSOSVM算法選出特征數(shù)目的平均值為19.6，而PSOSVM算法和GASVM算法選出特征數(shù)目的平均值分別為25和26，是前者的1.28倍和1.33倍。可以得出，GPSOSVM算法相比PSOSVM算法和GASVM算法選出特征子集的數(shù)目最少，同時分類精度更高。

在算法效率上，因為不需要進(jìn)行特征選擇和參數(shù)優(yōu)化，SVM算法的運行時間最短，但得到的分類精度較低。另外在數(shù)據(jù)集的數(shù)據(jù)量比較大，特征維數(shù)比較多的情況下，特征選擇的缺失不僅使得分類的精度降低，而且過多的特征數(shù)目使得運行速率變慢。這樣來看，SVM算法的效率較差。在GPSOSVM算法中，由于在PSO中引入了交叉和變異機(jī)制，在每次交叉變異操作后每個個體要進(jìn)行一次分類，使得算法的時間復(fù)雜度相對增加。但實驗結(jié)果證明，該算法有較強(qiáng)的SVM特征選擇和參數(shù)優(yōu)化能力，最終得到的分類精度更高且均衡性更好。另一方面，優(yōu)化所需的時間雖然增加，但對于同一類型的數(shù)據(jù)，分類器可以一次優(yōu)化，多次使用。由于該算法的特征選擇能力較強(qiáng)，在使用階段只需選擇較小的特征維數(shù)，這樣減少了運行時間，提高了使用階段的運行效率。

綜合以上分析，本文提出的GPSOSVM算法無論在提高分類精度、均衡性還是特征選擇能力方面表現(xiàn)都最好。

4 結(jié)語

針對SVM特征選擇和參數(shù)進(jìn)行優(yōu)化提高分類精度的問題，本文提出了一種改進(jìn)的基于PSO的SVM特征選擇和參數(shù)聯(lián)合優(yōu)化算法（GPSOSVM）。該算法通過在PSO中引入GA的交叉和變異算子以提高算法的性能，同時避免了GPSOSVM中出現(xiàn)早熟和陷入局部最優(yōu)的問題。實驗表明該算法能得到更高的適應(yīng)度值，精確得到待分類數(shù)據(jù)的特征子集和SVM參數(shù)，從而得到更高的分類精度而且均衡性更好。但是該算法仍然有改進(jìn)的空間，例如在迭代過程中如何動態(tài)縮小參數(shù)取值范圍以提高搜索精度等，這將是下一步研究的方向。

參考文獻(xiàn)：

[1]BING X， ZHANG M， BROWNE W N. Particle swarm optimization for feature selection in classification： a multiobjective approach[J]. IEEE Transactions on Cybernetics， 2013， 43（6）：1656-1671.

[2]BOLNCANEDO V， SNCHEZMAROO N， ALONSOBETANZOS A. A review of feature selection methods on synthetic data[J]. Knowledge & Information Systems， 2013， 34（3）：483-519.

[3]RONDING J， HAHN T， DE O L， et al. SCoRS — a method based on stability for feature selection and mapping in neuroimaging[J].IEEE Transactions on Medical Imaging， 2013， 33（1）：85-98.

[4]ZHAO Z， ZHANG R， COX J， et al. Massively parallel feature selection： an approach based on variance preservation[J]. Machine Learning， 2013， 92（1）：195-220.

[5]ZHANG W， LI C， ZHONG B. LSSVM parameters optimizing and nonlinear system prediction based on cross validation[C]// Proceedings of the 2009 5th International Conference on Natural Computation. Piscataway， NJ： IEEE， 2009：531-535.

[6]莊嚴(yán)，白振林，許云峰. 基于蟻群算法的支持向量機(jī)參數(shù)選擇方法研究[J].計算機(jī)仿真，2011，28（5）：216-219.（ZHUANG Y， BAI Z L， XU Y F. Research on parameters of support vector machine based on ant colony algorithm[J].Computer Simulation，2011， 28（5）：216-219.）

[7]王克奇，楊少春，戴天虹， 等. 采用遺傳算法優(yōu)化最小二乘支持向量機(jī)參數(shù)的方法[J].計算機(jī)應(yīng)用與軟件，2009，26（7）：109-111.（WANG K Q， YANG S C， DAI T H， et al. Method of optimizing parameter of least squares support vector machine by genetic algorithm[J].Computer Applications and Software，2009， 26（7）：109-111.）

[8]陳淵，馬宏偉. 基于蜜蜂算法的支持向量機(jī)特征選擇和參數(shù)優(yōu)化[J]. 組合機(jī)床與自動化加工技術(shù)，2013（11）：41-43.（CHEN Y， MA H W. Feature selection and parameter optimization of support vector machine based on the bees algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique， 2013（11）：41-43.）

[9]HUANG C L， WANG C J. A GAbased feature selection and parameters optimization for support vector machines[J]. Expert Systems with Applications， 2006， 31（2）：231-240.

[10]王維真，熊義軍，魏開平， 等. 基于粒子群算法的灰度相關(guān)圖像匹配技術(shù)[J]. 計算機(jī)工程與應(yīng)用，2010，46（12）：169-171.（WANG W Z， XIONG Y J， WEI K P， et al. Grey intensity correlated imagematching technology based on PSO[J]. Computer Engineering and Applications，2010， 46（12）：169-171.）

[11]石曉艷，劉淮霞，于水娟. 鯰魚粒子群算法優(yōu)化支持向量機(jī)的短期負(fù)荷預(yù)測[J]. 計算機(jī)工程與應(yīng)用，2013，49（11）：220-223.（SHI X Y， LIU H X， YU S J. Shorttime load prediction based on support vector machine optimized by catfish particle swarm optimization algorithm[J]. Computer Engineering and Applications， 2013， 49（11）：220-223.）

[12]段曉東，王存睿，王楠楠，等. 一種基于粒子群算法的分類器設(shè)計[J]. 計算機(jī)工程，2005，31（20）：107-109. （DUAN X D， WANG C R， WANG N N， et al. Design of classifier based on particle swarm algorithm[J]. Computer Engineering， 2005， 31（20）： 107-109.）

[13]LIN S W， YING K C， CHEN S C， et al. Particle swarm optimization for parameter determination and feature selection of support vector machines[J].Expert Systems with Applications，2008，35（4）：1817-1824.

[14]蔡良偉， 李霞. 遺傳算法交叉操作的改進(jìn)[J]. 系統(tǒng)工程與電子技術(shù)， 2006， 28（6）：925-928. （CAI L W， LI X. Improvement on crossover operation of genetic algorithms[J]. Systems Engineering and Electronics， 2006， 28（6）：925-928.）

[15]CHANG C C， LIN C J. LIBSVM： a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology， 2011， 2（3）：389-396.