基于改進SFS特征選擇BP識別算法

1、.基于改進SFS特征選擇BP識別算法-電氣論文基于改進SFS特征選擇BP識別算法 朱旭東，梁光明，馮雁（國防科學技術大學電子科學與工程學院，湖南長沙410073）摘要：特征選擇在BP神經(jīng)網(wǎng)絡算法中起著重要作用，順序前向選擇算法（SFS算法）利用前向搜索疊加的方式，從眾多的原始特征中獲得對分類識別算法最有效的主要特征，實現(xiàn)樣本特征維數(shù)壓縮。提出一種改進SFS特征選擇算法，設計了加權判別函數(shù)和測試反饋停止準則。實驗證明，改進算法能有效壓縮樣本特征維數(shù)，提高BP 網(wǎng)絡收斂速度和正確識別率。關鍵詞：特征選擇；SFS；BP網(wǎng)絡；收斂速度中圖分類號：TN911?34；TP391.4 文獻標識碼：A 文章編

2、號：1004?373X（2015）12?0001?04收稿日期：2014?12?25基金項目：湖南省創(chuàng)新基金支持項目（202c26214300674）0 引言一個完善的BP神經(jīng)網(wǎng)絡識別系統(tǒng)中，特征選擇是不可缺少的一個重要技術環(huán)節(jié)，它一般處于樣本特征數(shù)據(jù)采集和識別算法兩大環(huán)節(jié)之間，與后續(xù)的BP神經(jīng)網(wǎng)絡分類算法的性能息息相關，是模式識別領域研究的核心內(nèi)容之一。近幾年來，在數(shù)據(jù)挖掘的機器學習領域所涉及的維數(shù)都比較高，所提取的特征不能滿足不同類的樣本差別較大，而同類的樣本差別較小的特點，或者提取的特征彼此相關性很大，并且存在很多冗余的特征。另外，當樣本特征維數(shù)增加到一定值以后若是再繼續(xù)增加，反而會導致

3、分類識別算法識別率變差，這些不足嚴重影響到分類識別算法性能。特征選擇的任務就是從原始特征中挑選出對識別算法最有效且數(shù)目最少的特征，去除噪音特征和冗余不相關的特征，實現(xiàn)樣本特征空間維數(shù)的簡化，減少識別算法運算復雜度和系統(tǒng)運算時間，提高網(wǎng)絡收斂速度。因此，特征選擇在BP神經(jīng)網(wǎng)絡算法中起著重要作用。一般情況下，一個完整的特征選擇算法包括4個要素：搜索起點和方向，搜索策略，特征評估函數(shù)和算法停止準則。文獻1?4提出了SFS特征選擇的算法，文獻5提出了基于一種特征判別函數(shù)的SFS 特征選擇算法，并在BP 網(wǎng)絡和向量機識別系統(tǒng)中進行了驗證；本文在此基礎上，設計了加權判別函數(shù)和測試反饋停止準則等改進方法，使

4、特征選擇算法更為合理、規(guī)范，選出的優(yōu)秀特征子集更為有效和精簡。1 SFS 算法模型和缺陷分析順序前向選擇算法（SFS）是一種簡單的自下而上的搜索方法5，首先把目標特征集初始化為空集合，然后根據(jù)所設立的評價規(guī)則函數(shù)處理原始特征集合中的每一個特征，比較每個特征的函數(shù)值，選擇其中函數(shù)值最大的對應特征加入目標特征子集。然后在保留這個入選特征的基礎上重復上面的過程，從原始特征集剩余的特征中循環(huán)選擇剩余的特征與入選的特征匹配，比較組合特征所得到的函數(shù)值，選擇與入選特征組合所得到的評價函數(shù)值最大的特征加入目標特征子集。按照順序前向選擇方式重復以上的選擇步驟，直到維數(shù)達到規(guī)定的最大維數(shù)6。作為一種最基本的貪心

5、算法，該算法要求每次選擇的特征都能使加入后的新特征子集最優(yōu)7。具體的算法描述如下：假設原始特征集有n 個特征，表示為：fd ，1dn，設立特征評估準則函數(shù)為： 式中：M 表示樣本所含的類別；i 和j 分別表示第i 類和第j 類的類內(nèi)特征向量均值；i2 和j2 分別表示第i 類和第j 類的類內(nèi)方差5。Step1: 將目標特征子集Xk初始化為空，即Xk= ? 。Step2: 計算原始特征集F ( f1,f2 ,?,fn ) 中每一個特征fd 的函數(shù)評價函數(shù)值FDR( fd ) ，找到其中最大的函數(shù)值FDR( fa ) =max FDR( fd ) ，將FDR( fa ) 所對應的特征fa 加入目標

6、特征子集Xk；Step3：將其余未入選的n-1個特征依次與已入選特征fa 匹配，得到匹配后的組合特征的準則函數(shù)值FDR的大小按照升序排序，如果：FDR(Xk ?F1) FDR(Xk ?F2) ? FDR(Xk ?Fn - 1)（2）則將能使FDR 值最大的特征加入到目標特征子集Xk中，得到更新后的目標特征子集：Xk = Xk ? F1 （3）Step4：按照Step3的思想，依次增加能使FDR 值最大的的特征到目標特征子集Xk 中，每次只增加一個特征，直到目標特征子集的數(shù)量達到設定的最大的L 值的水平，從而得到更新后最終的目標特征子集Xk。通過順序前向選擇算法更新目標特征子集，使目標特征子集幾

7、乎包含原始特征集中的所有最優(yōu)特征，更能準確地代表原始特征集，過濾掉大部分的噪聲和冗余特征，增加了分類的有效性，算法計算量較小。但是，與此同時，SFS 算法也存在著明顯的缺陷：現(xiàn)有的特征評估準則函數(shù)公式區(qū)分度不夠好，還有待進一步完善；傳統(tǒng)的算法停止準則是建立在預先憑借經(jīng)驗設立特征子集最大維數(shù)，當目標特征子集的特征維數(shù)達到預先設定最大維數(shù)時停止搜索運算。該種方法武斷性強，并沒有考慮客觀實驗數(shù)據(jù)的差異性，可以進一步根據(jù)需要進行停止準則的改進；算法沒有充分地考慮目標特征子集已入選的特征與特征之間的相關性。針對以上問題，需要在原SFS算法的基礎上進行必要的改進。2 改進算法2.1 SFS判別函數(shù)公式加權

8、改進式（1）給出的判別函數(shù)FDR 是類與類之間的差異性和類內(nèi)一致性的比值，F(xiàn)DR值越大表示兩類之間的差別性越大。分子i 和j 分別表示第i 類和第j 類的類內(nèi)特征向量均值，(i-j)2代表各類別之間的差異性，(i-j)2越大FDR 值越大；分母i2 和j2 分別表示第i類和第j 類的類內(nèi)方差，i2 - j2 代表的是各自類內(nèi)的分布一致性。i2 和j2 各自的值越小，F(xiàn)DR值就越大。分母i2 - j2 不能很好地表現(xiàn)第i 類和第j 類的各自的類內(nèi)一致性，還可能出現(xiàn)負數(shù)的情況，并且顯然沒有考慮到各類別的類內(nèi)方差可能存在個別偏大的情況。因此，可以通過改進判別函數(shù)FDR 的公式來解決上述這些問題。改進

9、的判別公式FDR 如下所示： 式中：M 表示樣本所含的類別；i 和j 分別表示第i 類和第j 類的類內(nèi)特征向量均值；i2 和j2 分別表示第i類和第j 類的類內(nèi)方差2，a,b (0,1 。式（4）FDR 是在原有式（1）FDR 的基礎上把公式的分母進行了一些改進。如果想FDR 值很大，就要求公式分母上各類別的類內(nèi)方差i2 和j2 的值都要很小，要求各類別的類內(nèi)一致性要很高，但是在實際的工程實驗時，不能保證所有數(shù)據(jù)樣本類別的類內(nèi)方差都能符合要求，總是存在少部分類別的類內(nèi)方差可能偏大。因此，在判別公式分母各類別的類內(nèi)方差i2 和j2 前分別加個取值在(0,1 的系數(shù)，當出現(xiàn)個別類內(nèi)方差i2和j2

10、過大的情況時，適當?shù)販p小相應類別方差系數(shù)的取值，這樣就能保證判別公式FDR 的值很大；另外，將判別公式分母i2 和j2 之間由“ - ”變成“ + ”更能準確地表達判別函數(shù)的函數(shù)值大小與各類別的類內(nèi)一致性的關系。判別公式要求只有各類別的類內(nèi)一致性同時很高，即各類別的類內(nèi)方差i2 和j2 的值同時很小，函數(shù)值FDR 才能最大。綜上所述，改進后的FDR 判別函數(shù)能更好地描述各類別之間的區(qū)別性，判別函數(shù)FDR 值越大，各類別的差別性就越大。判別函數(shù)FDR為選擇最優(yōu)特征組合提供了更科學、更合理和更準確的衡量標尺。2.2 基于測試反饋的SFS算法停止準則改進原SFS 算法停止準則是憑借經(jīng)驗預先設置特征子

11、集最大維數(shù)，當目標特征子集的特征數(shù)量達到預先設置的最大維數(shù)時，強行停止搜索運算。這樣的停止準則武斷性強，沒有考慮到實際數(shù)據(jù)的差異性和實驗環(huán)境的復雜性，算法的預期效果會受到影響，得到的最優(yōu)特征子集的有效性和科學性往往會打折扣。針對這個缺陷，本文提出了一種基于分類正確率反饋的SFS算法的停止準則，根據(jù)入選特征子集的特征依次用BP神經(jīng)網(wǎng)絡訓練所有樣本，在測試集上用對應的特征測試，如果在特征選擇測試中前后幾次的分類正確率差值平均值小于設定的閾值，說明特征子集的測試正確率進入了峰值，可以停止搜索算法。具體基于分類正確率反饋的SFS 停止準則算法如下：Step1：設置正確率浮動門限閾值為0 ，初始化目標特

12、征子集Xk 為空，即Xk = ? ；Step2：利用SFS 算法依次從原始特征集F =Fj ,j = 1,2,N 中遴選出與Xk 中特征匹配的判別函數(shù)值最大的特征加入特征子集Xk ，得到更新后的最優(yōu)特征子集Xk =s1,s2 ,sm :1 m N ；Step3：將匹配更新后最優(yōu)特征子集Xk 的訓練樣本送入BP 網(wǎng)絡訓練，當訓練次數(shù)大于500 次時，停止訓練，得到與最優(yōu)特征子集Xk 中維數(shù)相對應的m 個訓練模型M =Mode1,Mode2 ,Modem 。將訓練模型M 在測試集上得到m 個對應特征的分類準確度R =1,2 ,m ；用m ，m + 1 和m + 2 分別表示特征子集Xk =s1,s

13、2 ,sm ，Xk =s1,s2 ,sm ,sm + 1 和Xk =s1,s2 ,sm ,sm + 1,sm + 2 時經(jīng)測試集得到的與Xk 特征維數(shù)相對應的BP網(wǎng)絡分類準確度；Step4：如果Max| a | m + 1 - ai ,| a | m + 2 - am + 1 0 ，算法停止搜索。否則，轉(zhuǎn)到Step2?；跍y試反饋的算法停止準則是將選擇的最優(yōu)特征送入BP網(wǎng)絡測試所選特征相對應的分類準確度，并將結(jié)果反饋回SFS算法，SFS算法根據(jù)反饋的情況決定是否繼續(xù)搜索?；跍y試反饋的算法停止準則更加科學、規(guī)范和合理，能根據(jù)不同的實驗數(shù)據(jù)采取智能的算法停止策略，泛化性更強，準確性更好，應用性更

14、廣泛。3 實驗結(jié)果及分析仿真平臺主要利用Matlab軟件，針對給定的數(shù)據(jù)樣本建立BP神經(jīng)網(wǎng)絡識別系統(tǒng)，用Matlab語言編寫應用程序，通過比較改進前和改進后算法的仿真結(jié)果，分析改進算法的優(yōu)劣，證實了改進算法的可行性和有效性。為了對改進算法進行檢驗，保證數(shù)據(jù)的真實性，實驗采用醫(yī)學顯微鏡醫(yī)學檢驗樣本對算法進行了驗證，數(shù)據(jù)庫為尿沉渣細胞，共14類，形狀、紋理、顏色等特征共90 維，從2 萬多個樣本中，選出了1 212 個訓練樣本和151個測試樣本。實驗選用3 層的BP 網(wǎng)絡結(jié)構(gòu)，輸入層節(jié)點的數(shù)量是根據(jù)每個樣本提取的維數(shù)來確定；中間的隱含層節(jié)點數(shù)根據(jù)經(jīng)驗選擇為2×輸入特征維數(shù)+2；輸出層節(jié)點

15、數(shù)根據(jù)分類的數(shù)量選擇為14，代表14類細胞。這是典型的3層BP神經(jīng)網(wǎng)絡結(jié)構(gòu)。隱含層的激活函數(shù)和輸出層的輸出函數(shù)都采用tansig，訓練函數(shù)選擇trainrp函數(shù)，輸出層傳輸函數(shù)采用purelin，訓練步數(shù)為500，目標誤差精度是0.001。建立好實驗環(huán)境后，根據(jù)特征選擇相應的維數(shù)將訓練樣本送入BP網(wǎng)絡進行訓練構(gòu)造與選擇最優(yōu)特征維數(shù)相對應的模型，利用特征選擇相對應維數(shù)的模型對測試集進行測試得到相應的BP識別正確率，其性能曲線如圖1所示。圖中橫坐標表示最優(yōu)特征選擇的維數(shù)，縱坐標表示與選擇最優(yōu)特征維數(shù)相對應的BP算法識別正確率。圖1為原始全部特征、原SFS、改進SFS特征選擇維數(shù)與相應BP網(wǎng)絡識別正

16、確率對比。 如圖2 所示是Matlab 程序生成的各類最終識別結(jié)果的混淆矩陣，測試樣本經(jīng)過BP網(wǎng)絡模型測試驗證得到詳細的各類別樣本的正確識別數(shù)據(jù)。數(shù)據(jù)主要分成3部分，分別記錄全部特征、原SFS特征選擇和改進SFS特征選擇BP算法的各類別樣本的正確識別率。原SFS和改進SFS特征選擇最終選擇的最優(yōu)特征子集的數(shù)量分別是40維和42維。各部分表格中加顏色的各區(qū)域是各類別樣本被正確識別的數(shù)量，最右側(cè)一列是各類別被正確識別比例，每個部分的右下角加紅的數(shù)據(jù)是記錄各部分算法的平均正確識別率，可以清楚對比地看出3種算法的各類別樣本的識別情況。實驗中分別記錄全部特征?BP算法、原SFS特征選擇?BP算法和改進S

17、FS特征選擇?BP算法的最終結(jié)果，將各算法數(shù)據(jù)結(jié)果分別在樣本特征選擇維數(shù)、迭代步數(shù)和正確識別率進行對比，對比結(jié)果見表1。 根據(jù)圖1 和圖2，改進SFS 特征選擇的最優(yōu)特征是42維，比全部特征90維少了38，但是比原SFS算法40維多了2維特征；在正確率的對比上，改進SFS特征選擇BP識別率比全部特征BP識別率略低一點，但是比原SFS識別率高。由圖2和表1可知，改進的SFS特征選擇BP算法的迭代步數(shù)是100次，比全部特征?BP網(wǎng)絡的迭代步數(shù)少20次，比原SFS?BP算法迭代步數(shù)120次少了20次；在正確率方面，改進的SFS特征選擇的BP算法正確識別率比全部特征?BP算法正確識別率少了0.613

18、2%，基本接近全部特征?BP算法識別率，比原SFS?BP算法的識別率高0.657 3%。綜上所述，改進SFS特征選擇成功縮減了樣本特征維數(shù)，由全部特征的90維壓縮到了42維，過濾掉了大部分的噪聲和冗余特征，減小了BP神經(jīng)網(wǎng)絡的運算復雜度，并且基本接近全部特征的BP算法識別率，比原始全部特征BP 算法識別率僅少0.613 2%；改進SFS 算法選擇的特征比原SFS 選擇的特征多了2 維，但是改進SFS的BP識別率比原SFS?BP識別率提高了0.659 1%，迭代步數(shù)也少了20次。綜合衡量，不難看出，基于改進SFS特征選擇?BP識別算法比原SFS?BP算法和原始全部特征的BP算法更為科學、合理和可

19、行。4 結(jié)語本文通過設計加權判別函數(shù)和測試反饋停止準則等方法改進SFS特征選擇算法，充分考慮到各類別樣本的類內(nèi)方差可能存在個別偏大的情況，采取判別函數(shù)系數(shù)加權的方法來調(diào)整類內(nèi)方差值，又提出了基于測試反饋的SFS算法停止準則，克服了原來的預先設定閾值的缺陷。實驗證明，改進算法能有效壓縮樣本特征維數(shù)，提高BP網(wǎng)絡收斂速度和正確識別率。作者簡介：朱旭東（1982），男，吉林雙遼人，碩士研究生。主要研究方向為信號處理。梁光明（1970），男，湖南漣源人，副教授，碩士生導師。主要研究方向為信號處理。馮雁（1984），男，廣西貴港人，碩士研究生。主要研究方向為信號處理。參考文獻1 MENEGATTI E，PRETTO A，PAGELLO E. Testing onmidirec? tional vision ? based Mont Carlo localization under occlusion C/ Proceeding of IEEE/RSJ 2004 International Conference on Intelligent Robots and Systems. S.l.：IEEE，2004，3：24