基于改進粒子群算法的最優特征子集研究

侯大軍，朱偉興

(江蘇大學電氣信息工程學院，江蘇鎮江212003)

0 引言

特征選擇是模式識別中的關鍵環節，特征選擇質量的好壞直接影響到識別的成敗，因此，受到科研人員的普遍重視。特征選擇中的搜索問題是一個NP難題。窮盡式搜索由于其計算量過大，不可能得到廣泛應用。1978年，Kittler J提出“分支定界算法”，它是一種自上而下方法，但具有回溯功能，可使所有的特征組合都被考慮到，這樣計算量還是很大。此后出現的順序前進法(SFS)，順序后退法(SBS)以及改進的廣義順序前進法(GSFS)，廣義順序后退法(GSBS)等，這些啟發式搜索策略實際上屬于貪心類算法，搜索計算量較小，在原始特征之間相關性較小的情況下，這類算法能夠取得較好的效果。但存在明顯的缺點:特征一旦被加入或剔除，易出現搜索結果陷于局部最優的“筑巢”現象。為克服這些缺陷，出現了增1減r法(PTA)，先順序加入1個特征再依次剔除r個特征，但這種l和r很難確定。Kudo M等人［1］提出了比啟發式搜索更有優勢的隨機搜索策略，如遺傳算法［2］，但出現早收斂、在進化后期搜索效率低的問題。鑒于以上情況 ，本文采用改進粒子群優化(PSO)算法提取出一組最優特征，進而驗證了此方法的可行性。

1 特征選擇建模與分類

在實際問題中，一般情況下在進行特征提取時會存在一些無關或不重要的特征，這些預先并不知道。無關或不重要的特征有可能引入噪聲，甚至對識別的正確率有負面的影響。更進一步說，少量的特征可以減少系統的花費。因此，很有必要通過特征壓縮來尋找一組最佳特征子集。圖1為特征選擇建模框架。

圖1 特征選擇建模框架Fig 1 Modeling of feature selection

1.1 改進的離散二進制PSO算法

1.1.1 離散二進制PSO算法基本原理與改進算法

基本PSO算法［3］是用于實值連續空間，然而，特征選擇是組合優化問題，因而采用離散形式的PSO算法［3～5］。

根據下面2個公式來更新粒子的速度和位置為

其中，vij(k)為粒子在第k次迭代中第j維的速度;r1，r2和 rij都是［0，1］之間的隨機數，c1，c2都是學習因子;w 為加權系數;xij(k)為粒子i在k次迭代中第j維的當前位置;pBestij為粒子i在第j維的個體極值點的位置;gBestj為整個群在第j維的全局極值點的位置，而sig(vij(k))=1/(1+exp(－vij(k)))，為了防止sig(vij(k))函數飽和，將其修改為

其中，vmax一般為［2，4］。

針對經典離散粒子群優化優化算法收斂性差和易陷入局部極值點的缺點，將式(1)改為粒子群a進化方程式(4)和粒子群b進化方程式(5)

以上構造了2個獨立的微粒群a，b，通過式(3)不必對這2個微粒群分別設置不同的速度上限，就可以使2個粒子群以不同的步長在搜索空間并行尋優。其中較大步長的粒子群全局搜索能力較強，可在搜索空間內進行快速尋優，而較小步長的粒子群則具有更好的局部尋優能力。

在群體智能算法計算中，為避免個體因早熟而降低尋優能力，必須在尋優過程中保證種群的多樣性。為此，本文在兩群微粒群算法的基礎上，設計了一種新的變異算子，這種算子在進化前期不采取變異，當種群進化到一定的收斂時，則執行下面式子進行變異

其中，qj表示微粒群中所有粒子的第j維的值(0或1)的個數與所有粒子的個數的比值，qg一般取0.7～0.9。

1.1.2 問題解的建立

假設在一個J維的目標搜索空間中，有m個微粒組成一個種群，其中，第i個微粒表示為一個J維的向量Xi=如果X的第j位為1，則此特征被選中;否則，沒有被選中。

1.1.3 適應度函數［6］

粒子優劣性能評定標準定義如下

式中 F(i)為粒子i生成解的適應度值;p(i)為運用此特征子集進行分類的正確率的均值;n(i)表示此次選擇的特征個數，即n(i)=xi1+xi2+…+xij;λ是特征個數的權重參數，一般取0.01。F越大，表明選擇的特征子集表現越好，即利用較少的特征獲得較高的分類正確率。

1.1.4 算法步驟

改進的PSO算法的流程:

1)初始化微粒群a，b(群體規模為m)，包括隨機位置和速度;并比較最優位置;

2)根據式(2)，式(4)，式(5)調整微粒速度和位置;3)根據式(7)評價每個微粒的適應度;

4)在每個粒子群中，對每個微粒，將其適應值分別與其經過的最好位置pBbest和gBest作比較，如果較好，則將其作為當前的最好位置pBest和gBest;

5)判斷群最優值是否優于前一次，如果是，直接跳至(6);否則，判斷是否滿足變異條件，如果否，則跳至(6)，若滿足，則執行式(6)。

6)如果連續幾代個體的平均適應度不變(其差小于某個具體的閾值)，就認為種群已成熟且不再有進化趨勢，并以此作為算法終止的判定標準。進化結束后，選取末代種群中適應度最大的個體進行解碼，就得到所要求的最優特征子集。否則，轉(2)。

1.2 支持向量機識別分類

支持向量機(SVM)是20世紀90年代Vapnik基于統計學習理論提出的一種新的機器學習方法。本系統用改進后的PSO提取蘋果的最優特征子集作為SVM的輸入向量，對圖像進行分類學習，應用LSSVM［7］分類器來驗證特征選擇的好壞。在這里選用徑向基函數作為內核函數時可得到相對較好的分類效果。在采用LSSVM分類器識別的過程中，參數C和σ的取值對識別率有較大的影響。

2 實驗結果

對于改進離散二進制PSO算法而言，通常取學習因子c1=c2=c3=2.05，w 取為0.7，種群 a 和種群 b大小都為30，設置最大迭代次數為100。實驗樣本共分4大類，每類60個樣本(30個訓練樣本，30個測試樣本)。在蘋果識別系統中，根據蘋果的形狀和顏色特征［8，9］均將蘋果分為特等品，一等品，二等品，等外品4個等級。

蘋果形狀特征包含:蘋果橫徑，果形指數，周長，面積，占空比，等效圓半徑，偏心率，形狀參數，標準積，7個HU距。當懲罰因子C取20，徑向基函數中的σ取1.3438時，形狀識別的正確率最大。通過表1和表2分析實驗結果，可以得到如下結論:

1)可以提取出最優特征子空間——蘋果橫徑，果形指數，周長，面積，HU距1。并將原來16個3維特征壓縮至5維，從而大大壓縮了特征空間。同樣，從平均識別率上看，所有原始特征的平均識別率為95%，而經特征選擇后的平均識別率高達97.9%

2)離散二進制PSO算法的適應度一直小于改進后的離散二進制PSO，這是因為離散二進制PSO算法陷入局部極值點;同樣從迭代次數上離散二進制PSO算法迭代了43次，根據文獻［10］中的方法迭代了23次，而改進后的離散二進制PSO僅為17次，這樣大大提高了算法收斂性。

3)在Celeron21.72 GHz，512 MB，Matlab7.6.0(R2008a)上，從算法的算法運行時間上看，離散二進制PSO算法為450 ms，文獻［10］中的方法運行時間僅為270 ms;但改進后的離散二進制PSO算法為386 ms。

表1 改進的離散二進制PSO10次特征選擇和分類結果Tab 1 10 times feature selection and classification results of modified binary PSO

表2 3種算法比較Tab 2 Comparison of three algorithms

3 結論

本文提出了一種基于改進PSO算法的快速特征選擇方法。該方法運用改進PSO算法從特征樣本中提取一組最優特征子空間;之后利用LSSVM分類器來驗證此方法的可行性。此算法雖然克服了算法收斂性慢和易引入陷入局部極值點的缺點，迭代次數比離散PSO和文獻［10］中的方法要小，但也引入了新問題(如增加了算法的空間復雜度和當原始數據大于1000維以上需要調整適應度函數)，它們在后期的工作中有待解決。

［1］Kudo M，Sklansky J.Comparison of slgorithms that select features for pattern classifiers［J］.Pattern Recognition，2000，33(1):25－41.

［2］Lu Jianjiang，Zhao Tianzhong，Zhang Yafei.Feature selection based on genetic algorithm for image annotation［J］.Knowledge-based Systems，2008，21(8):887－891.

［3］Bergh Frans v d，Engelbrecht A P.A cooperative approach to particle swarm optimization［J］.IEEE Transactionson Evolutionary Computation，2004，8(3):225－239.

［4］Khanesar M A.A novel binary particle swarm optimization［C］∥The15th Mediterranean Conference on Control and Automation，2007.

［5］Kennedy J，Eberhart R C.A discrete binary version of the particle swarm algorithm［C］∥IEEE International Confererce on Systems，Man and Cybernetics，1997:4104－4108.

［6］Pan Li，Zheng Hong.Genetic feature selection for texture classification［J］.Geo-spatial Information Science，2004，7(3):162－166.

［7］Suykens J A K，Vandewalle J.Recurrent least squares support vector machines［J］.IEEE Transaction on Circuits and Systems-I，2000，47(7):1109－1114.

［8］Unay D，Gosselin B.Stem and calyx recognition on ＇Jonagold＇apples by pattern recognition［J］.Journal of Food Engineering，2007，78(2):597－605.

［9］Ji Haiyan，Yuan Jinli.The application study of apple color grading by particle swarm optimization neural networks［C］∥The 6th World Congress on Intelligent Control and Automation，2006:2651－2654.

［10］李勇明.內嵌多準則的遺傳算法用于尿沉渣紅白細胞的特征選擇［J］.系統仿真學報，2008，20(14):3853－3863.