基于改進(jìn)SFS特征選擇BP識(shí)別算法

朱旭東等

摘 要： 特征選擇在BP神經(jīng)網(wǎng)絡(luò)算法中起著重要作用，順序前向選擇算法（SFS算法）利用前向搜索疊加的方式，從眾多的原始特征中獲得對(duì)分類識(shí)別算法最有效的主要特征，實(shí)現(xiàn)樣本特征維數(shù)壓縮。提出一種改進(jìn)SFS特征選擇算法，設(shè)計(jì)了加權(quán)判別函數(shù)和測(cè)試反饋停止準(zhǔn)則。實(shí)驗(yàn)證明，改進(jìn)算法能有效壓縮樣本特征維數(shù)，提高BP網(wǎng)絡(luò)收斂速度和正確識(shí)別率。

關(guān)鍵詞： 特征選擇； SFS； BP網(wǎng)絡(luò)； 收斂速度

中圖分類號(hào)： TN911?34； TP391.4 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）12?0001?04

0 引 言

一個(gè)完善的BP神經(jīng)網(wǎng)絡(luò)識(shí)別系統(tǒng)中，特征選擇是不可缺少的一個(gè)重要技術(shù)環(huán)節(jié)，它一般處于樣本特征數(shù)據(jù)采集和識(shí)別算法兩大環(huán)節(jié)之間，與后續(xù)的BP神經(jīng)網(wǎng)絡(luò)分類算法的性能息息相關(guān)，是模式識(shí)別領(lǐng)域研究的核心內(nèi)容之一。

近幾年來，在數(shù)據(jù)挖掘的機(jī)器學(xué)習(xí)領(lǐng)域所涉及的維數(shù)都比較高，所提取的特征不能滿足不同類的樣本差別較大，而同類的樣本差別較小的特點(diǎn)，或者提取的特征彼此相關(guān)性很大，并且存在很多冗余的特征。另外，當(dāng)樣本特征維數(shù)增加到一定值以后若是再繼續(xù)增加，反而會(huì)導(dǎo)致分類識(shí)別算法識(shí)別率變差，這些不足嚴(yán)重影響到分類識(shí)別算法性能。特征選擇的任務(wù)就是從原始特征中挑選出對(duì)識(shí)別算法最有效且數(shù)目最少的特征，去除噪音特征和冗余不相關(guān)的特征，實(shí)現(xiàn)樣本特征空間維數(shù)的簡(jiǎn)化，減少識(shí)別算法運(yùn)算復(fù)雜度和系統(tǒng)運(yùn)算時(shí)間，提高網(wǎng)絡(luò)收斂速度。因此，特征選擇在BP神經(jīng)網(wǎng)絡(luò)算法中起著重要作用。一般情況下，一個(gè)完整的特征選擇算法包括4個(gè)要素：搜索起點(diǎn)和方向，搜索策略，特征評(píng)估函數(shù)和算法停止準(zhǔn)則。

文獻(xiàn)[1?4]提出了SFS特征選擇的算法，文獻(xiàn)[5]提出了基于一種特征判別函數(shù)的SFS特征選擇算法，并在BP網(wǎng)絡(luò)和向量機(jī)識(shí)別系統(tǒng)中進(jìn)行了驗(yàn)證；本文在此基礎(chǔ)上，設(shè)計(jì)了加權(quán)判別函數(shù)和測(cè)試反饋停止準(zhǔn)則等改進(jìn)方法，使特征選擇算法更為合理、規(guī)范，選出的優(yōu)秀特征子集更為有效和精簡(jiǎn)。

1 SFS算法模型和缺陷分析

順序前向選擇算法（SFS）是一種簡(jiǎn)單的自下而上的搜索方法[5]，首先把目標(biāo)特征集初始化為空集合，然后根據(jù)所設(shè)立的評(píng)價(jià)規(guī)則函數(shù)處理原始特征集合中的每一個(gè)特征，比較每個(gè)特征的函數(shù)值，選擇其中函數(shù)值最大的對(duì)應(yīng)特征加入目標(biāo)特征子集。然后在保留這個(gè)入選特征的基礎(chǔ)上重復(fù)上面的過程，從原始特征集剩余的特征中循環(huán)選擇剩余的特征與入選的特征匹配，比較組合特征所得到的函數(shù)值，選擇與入選特征組合所得到的評(píng)價(jià)函數(shù)值最大的特征加入目標(biāo)特征子集。按照順序前向選擇方式重復(fù)以上的選擇步驟，直到維數(shù)達(dá)到規(guī)定的最大維數(shù)[6]。作為一種最基本的貪心算法，該算法要求每次選擇的特征都能使加入后的新特征子集最優(yōu)[7]。

具體的算法描述如下：

假設(shè)原始特征集有n個(gè)特征，表示為：{fd ，1≤d≤n}，設(shè)立特征評(píng)估準(zhǔn)則函數(shù)為：

[FDR=jMi≥jMμi-μj2σi2-σj2] （1）

式中：[M]表示樣本所含的類別；[μi]和[μj]分別表示第[i]類和第[j]類的類內(nèi)特征向量均值；[σi2]和[σj2]分別表示第[i]類和第[j]類的類內(nèi)方差[5]。

Step1： 將目標(biāo)特征子集Xk初始化為空，即Xk=[?]。

Step2： 計(jì)算原始特征集F[（f1，f2，…，fn）]中每一個(gè)特征[fd]的函數(shù)評(píng)價(jià)函數(shù)值[FDR（fd）]，找到其中最大的函數(shù)值[FDR（fa）]=max{[FDR（fd）]}，將[FDR（fa）]所對(duì)應(yīng)的特征[fa]加入目標(biāo)特征子集Xk；

Step3：將其余未入選的n-1個(gè)特征依次與已入選特征[fa]匹配，得到匹配后的組合特征的準(zhǔn)則函數(shù)值[FDR]的大小按照升序排序，如果：

[FDR（Xk?{F1}）>FDR（Xk?{F2}）>…>FDR（Xk?{Fn-1}）] （2）

則將能使[FDR]值最大的特征加入到目標(biāo)特征子集[Xk]中，得到更新后的目標(biāo)特征子集：

[Xk=Xk?F1] （3）

Step4：按照Step3的思想，依次增加能使[FDR]值最大的的特征到目標(biāo)特征子集Xk中，每次只增加一個(gè)特征，直到目標(biāo)特征子集的數(shù)量達(dá)到設(shè)定的最大的L值的水平，從而得到更新后最終的目標(biāo)特征子集Xk。

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

針對(duì)以上問題，需要在原SFS算法的基礎(chǔ)上進(jìn)行必要的改進(jìn)。

2 改進(jìn)算法

2.1 SFS判別函數(shù)公式加權(quán)改進(jìn)

式（1）給出的判別函數(shù)FDR是類與類之間的差異性和類內(nèi)一致性的比值，F(xiàn)DR值越大表示兩類之間的差別性越大。分子[μi]和[μj]分別表示第[i]類和第[j]類的類內(nèi)特征向量均值，[μi-μj2]代表各類別之間的差異性，[μi-μj2]越大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)負(fù)數(shù)的情況，并且顯然沒有考慮到各類別的類內(nèi)方差可能存在個(gè)別偏大的情況。因此，可以通過改進(jìn)判別函數(shù)FDR的公式來解決上述這些問題。改進(jìn)的判別公式[FDR′]如下所示：

[FDR′=jMi≥jMμi-μj2aσi2+bσj2] （4）

式中：[M]表示樣本所含的類別；[μi]和[μj]分別表示第[i]類和第[j]類的類內(nèi)特征向量均值；[σi2]和[σj2]分別表示第[i]類和第[j]類的類內(nèi)方差[2]，[a，b∈（0，1]]。

式（4）[FDR′]是在原有式（1）FDR的基礎(chǔ)上把公式的分母進(jìn)行了一些改進(jìn)。如果想FDR值很大，就要求公式分母上各類別的類內(nèi)方差[σi2]和[σj2]的值都要很小，要求各類別的類內(nèi)一致性要很高，但是在實(shí)際的工程實(shí)驗(yàn)時(shí)，不能保證所有數(shù)據(jù)樣本類別的類內(nèi)方差都能符合要求，總是存在少部分類別的類內(nèi)方差可能偏大。因此，在判別公式分母各類別的類內(nèi)方差[σi2]和[σj2]前分別加個(gè)取值在[（0，1]]的系數(shù)，當(dāng)出現(xiàn)個(gè)別類內(nèi)方差[σi2]和[σj2]過大的情況時(shí)，適當(dāng)?shù)販p小相應(yīng)類別方差系數(shù)的取值，這樣就能保證判別公式[FDR′]的值很大；另外，將判別公式分母[σi2]和[σj2]之間由“[-]”變成“[+]”更能準(zhǔn)確地表達(dá)判別函數(shù)的函數(shù)值大小與各類別的類內(nèi)一致性的關(guān)系。判別公式要求只有各類別的類內(nèi)一致性同時(shí)很高，即各類別的類內(nèi)方差[σi2]和[σj2]的值同時(shí)很小，函數(shù)值[FDR′]才能最大。綜上所述，改進(jìn)后的[FDR′]判別函數(shù)能更好地描述各類別之間的區(qū)別性，判別函數(shù)[FDR′]值越大，各類別的差別性就越大。判別函數(shù)[FDR′]為選擇最優(yōu)特征組合提供了更科學(xué)、更合理和更準(zhǔn)確的衡量標(biāo)尺。

2.2 基于測(cè)試反饋的SFS算法停止準(zhǔn)則改進(jìn)

原SFS算法停止準(zhǔn)則是憑借經(jīng)驗(yàn)預(yù)先設(shè)置特征子集最大維數(shù)，當(dāng)目標(biāo)特征子集的特征數(shù)量達(dá)到預(yù)先設(shè)置的最大維數(shù)時(shí)，強(qiáng)行停止搜索運(yùn)算。這樣的停止準(zhǔn)則武斷性強(qiáng)，沒有考慮到實(shí)際數(shù)據(jù)的差異性和實(shí)驗(yàn)環(huán)境的復(fù)雜性，算法的預(yù)期效果會(huì)受到影響，得到的最優(yōu)特征子集的有效性和科學(xué)性往往會(huì)打折扣。針對(duì)這個(gè)缺陷，本文提出了一種基于分類正確率反饋的SFS算法的停止準(zhǔn)則，根據(jù)入選特征子集的特征依次用BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練所有樣本，在測(cè)試集上用對(duì)應(yīng)的特征測(cè)試，如果在特征選擇測(cè)試中前后幾次的分類正確率差值平均值小于設(shè)定的閾值，說明特征子集的測(cè)試正確率進(jìn)入了峰值，可以停止搜索算法。

具體基于分類正確率反饋的SFS停止準(zhǔn)則算法如下：

Step1：設(shè)置正確率浮動(dòng)門限閾值為[β0]，初始化目標(biāo)特征子集[Xk]為空，即[Xk=?]；

Step2：利用SFS算法依次從原始特征集[F={Fj，j=1，2，…，N}]中遴選出與[Xk]中特征匹配的判別函數(shù)值最大的特征加入特征子集[Xk]，得到更新后的最優(yōu)特征子集[Xk={s1，s2，…，sm：1≤m

Step3：將匹配更新后最優(yōu)特征子集[Xk]的訓(xùn)練樣本送入BP網(wǎng)絡(luò)訓(xùn)練，當(dāng)訓(xùn)練次數(shù)大于500次時(shí)，停止訓(xùn)練，得到與最優(yōu)特征子集[Xk]中維數(shù)相對(duì)應(yīng)的m個(gè)訓(xùn)練模型[M={Mode1，Mode2，…，Modem}]。將訓(xùn)練模型[M]在測(cè)試集上得到m個(gè)對(duì)應(yīng)特征的分類準(zhǔn)確度[R={α1，α2，…，αm}]；用[αm]，[αm+1]和[αm+2]分別表示特征子集[Xk={s1，s2，…，sm}]，[Xk={s1，s2，…，sm，sm+1}]和[Xk={s1，s2，…，][sm，sm+1，sm+2}]時(shí)經(jīng)測(cè)試集得到的與[Xk]特征維數(shù)相對(duì)應(yīng)的BP網(wǎng)絡(luò)分類準(zhǔn)確度；

Step4：如果[Maxam+1-ai，am+2-am+1<β0]，算法停止搜索。否則，轉(zhuǎn)到Step2。

基于測(cè)試反饋的算法停止準(zhǔn)則是將選擇的最優(yōu)特征送入BP網(wǎng)絡(luò)測(cè)試所選特征相對(duì)應(yīng)的分類準(zhǔn)確度，并將結(jié)果反饋回SFS算法，SFS算法根據(jù)反饋的情況決定是否繼續(xù)搜索。基于測(cè)試反饋的算法停止準(zhǔn)則更加科學(xué)、規(guī)范和合理，能根據(jù)不同的實(shí)驗(yàn)數(shù)據(jù)采取智能的算法停止策略，泛化性更強(qiáng)，準(zhǔn)確性更好，應(yīng)用性更廣泛。

3 實(shí)驗(yàn)結(jié)果及分析

仿真平臺(tái)主要利用Matlab軟件，針對(duì)給定的數(shù)據(jù)樣本建立BP神經(jīng)網(wǎng)絡(luò)識(shí)別系統(tǒng)，用Matlab語言編寫應(yīng)用程序，通過比較改進(jìn)前和改進(jìn)后算法的仿真結(jié)果，分析改進(jìn)算法的優(yōu)劣，證實(shí)了改進(jìn)算法的可行性和有效性。

為了對(duì)改進(jìn)算法進(jìn)行檢驗(yàn)，保證數(shù)據(jù)的真實(shí)性，實(shí)驗(yàn)采用醫(yī)學(xué)顯微鏡醫(yī)學(xué)檢驗(yàn)樣本對(duì)算法進(jìn)行了驗(yàn)證，數(shù)據(jù)庫(kù)為尿沉渣細(xì)胞，共14類，形狀、紋理、顏色等特征共90維，從2萬多個(gè)樣本中，選出了1 212個(gè)訓(xùn)練樣本和151個(gè)測(cè)試樣本。

實(shí)驗(yàn)選用3層的BP網(wǎng)絡(luò)結(jié)構(gòu)，輸入層節(jié)點(diǎn)的數(shù)量是根據(jù)每個(gè)樣本提取的維數(shù)來確定；中間的隱含層節(jié)點(diǎn)數(shù)根據(jù)經(jīng)驗(yàn)選擇為2×輸入特征維數(shù)+2；輸出層節(jié)點(diǎn)數(shù)根據(jù)分類的數(shù)量選擇為14，代表14類細(xì)胞。這是典型的3層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。隱含層的激活函數(shù)和輸出層的輸出函數(shù)都采用tansig，訓(xùn)練函數(shù)選擇trainrp函數(shù)，輸出層傳輸函數(shù)采用purelin，訓(xùn)練步數(shù)為500，目標(biāo)誤差精度是0.001。

建立好實(shí)驗(yàn)環(huán)境后，根據(jù)特征選擇相應(yīng)的維數(shù)將訓(xùn)練樣本送入BP網(wǎng)絡(luò)進(jìn)行訓(xùn)練構(gòu)造與選擇最優(yōu)特征維數(shù)相對(duì)應(yīng)的模型，利用特征選擇相對(duì)應(yīng)維數(shù)的模型對(duì)測(cè)試集進(jìn)行測(cè)試得到相應(yīng)的BP識(shí)別正確率，其性能曲線如圖1所示。圖中橫坐標(biāo)表示最優(yōu)特征選擇的維數(shù)，縱坐標(biāo)表示與選擇最優(yōu)特征維數(shù)相對(duì)應(yīng)的BP算法識(shí)別正確率。圖1為原始全部特征、原SFS、改進(jìn)SFS特征選擇維數(shù)與相應(yīng)BP網(wǎng)絡(luò)識(shí)別正確率對(duì)比。

與相對(duì)應(yīng)BP網(wǎng)絡(luò)識(shí)別正確率對(duì)比

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

實(shí)驗(yàn)中分別記錄全部特征?BP算法、原SFS特征選擇?BP算法和改進(jìn)SFS特征選擇?BP算法的最終結(jié)果，將各算法數(shù)據(jù)結(jié)果分別在樣本特征選擇維數(shù)、迭代步數(shù)和正確識(shí)別率進(jìn)行對(duì)比，對(duì)比結(jié)果見表1。

根據(jù)圖1和圖2，改進(jìn)SFS特征選擇的最優(yōu)特征是42維，比全部特征90維少了38，但是比原SFS算法40維多了2維特征；在正確率的對(duì)比上，改進(jìn)SFS特征選擇BP識(shí)別率比全部特征BP識(shí)別率略低一點(diǎn)，但是比原SFS識(shí)別率高。由圖2和表1可知，改進(jìn)的SFS特征選擇BP算法的迭代步數(shù)是100次，比全部特征?BP網(wǎng)絡(luò)的迭代步數(shù)少20次，比原SFS?BP算法迭代步數(shù)120次少了20次；在正確率方面，改進(jìn)的SFS特征選擇的BP算法正確識(shí)別率比全部特征?BP算法正確識(shí)別率少了0.613 2%，基本接近全部特征?BP算法識(shí)別率，比原SFS?BP算法的識(shí)別率高0.657 3%。

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

4 結(jié) 語

本文通過設(shè)計(jì)加權(quán)判別函數(shù)和測(cè)試反饋停止準(zhǔn)則等方法改進(jìn)SFS特征選擇算法，充分考慮到各類別樣本的類內(nèi)方差可能存在個(gè)別偏大的情況，采取判別函數(shù)系數(shù)加權(quán)的方法來調(diào)整類內(nèi)方差值，又提出了基于測(cè)試反饋的SFS算法停止準(zhǔn)則，克服了原來的預(yù)先設(shè)定閾值的缺陷。實(shí)驗(yàn)證明，改進(jìn)算法能有效壓縮樣本特征維數(shù)，提高BP網(wǎng)絡(luò)收斂速度和正確識(shí)別率。

參考文獻(xiàn)

[1] MENEGATTI E， PRETTO A， PAGELLO E. Testing onmidirectional 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： 2487?2493.

[2] 計(jì)智偉，胡珉，尹建新.特征選擇算法綜述[J].電子設(shè)計(jì)工程，2011（5）：45?51.

[3] 姚旭，王曉丹，張玉璽，等.特征選擇方法綜述[J].控制與決策，2012（2）：161?165.

[4] 李敏，卡米力·木依丁.特征選擇方法與算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013（12）：16?21.

[5] REZATOFIGHIA Seyed Hamid， SOLTANIAN?ZADEH Hamid. Automatic recognition of five types of white blood cells in peripheral blood [J]. Computerized Medical Imaging and Graphics， 2011， 35： 333?343.

[6] PUDIL P， NOVOVICOVA J， KITTLER J. Floating search methods in feature selection [J]. Pattern Recognition Letters 1994， 15： 1119?1125.

[7] GUYON I. An introduction to variable and feature selection [J]. Journal of Machine Learning Research， 2003， 3： 1157?1182.

[8] 易超群，李建平，朱成文.一種基于分類精度的特征選擇支持向量機(jī)[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2010（7）：119?121.