侯大軍，朱偉興

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

0 引言

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

1 特征選擇建模與分類

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

圖1 特征選擇建?？蚣蹻ig 1 Modeling of feature selection

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

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

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

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

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

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

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

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

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

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

1.1.2 問題解的建立

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

1.1.3 適應度函數(shù)［6］

粒子優(yōu)劣性能評定標準定義如下

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

1.1.4 算法步驟

改進的PSO算法的流程:

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

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

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

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

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

1.2 支持向量機識別分類

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

2 實驗結果

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

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

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

2)離散二進制PSO算法的適應度一直小于改進后的離散二進制PSO，這是因為離散二進制PSO算法陷入局部極值點;同樣從迭代次數(shù)上離散二進制PSO算法迭代了43次，根據(jù)文獻［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算法從特征樣本中提取一組最優(yōu)特征子空間;之后利用LSSVM分類器來驗證此方法的可行性。此算法雖然克服了算法收斂性慢和易引入陷入局部極值點的缺點，迭代次數(shù)比離散PSO和文獻［10］中的方法要小，但也引入了新問題(如增加了算法的空間復雜度和當原始數(shù)據(jù)大于1000維以上需要調整適應度函數(shù))，它們在后期的工作中有待解決。

［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］.系統(tǒng)仿真學報，2008，20(14):3853－3863.