基于bab+算法的最優(yōu)特征選擇

基于bab+算法的最優(yōu)特征選擇

0特征選擇方法在模式識(shí)別系統(tǒng)中，資源選擇起著非常重要的作用，因?yàn)橘Y源選擇的質(zhì)量對(duì)后續(xù)排序的影響起著非常重要的作用。由于在實(shí)際應(yīng)用中,包括顏色、形狀、紋理等特征的數(shù)量非常大,沒有必要也不可能用所有這些特征進(jìn)行分類,因此有必要對(duì)不同的特征組合進(jìn)行評(píng)價(jià),從而選出對(duì)分類最有效的一組特征。特征選擇是從n個(gè)特征中選擇d(n>d)個(gè)特征,使判決函數(shù)值J達(dá)到最大值。在原坐標(biāo)系中依據(jù)某些規(guī)則直接選擇特征的方法分為兩大類:次優(yōu)搜索法和最優(yōu)搜索法。常用的次優(yōu)搜索法有:單獨(dú)最優(yōu)法、順序前進(jìn)法(SFS)、順序后退法(SBS)。單獨(dú)最優(yōu)法的基本思想是計(jì)算各特征單獨(dú)使用時(shí)的判據(jù)值并以遞減排序,選取前d個(gè)分類效果最好的特征。順序前進(jìn)法每次從未選入的特征中選擇一個(gè)特征,使它與已選入的特征組合在一起時(shí)J值最大。順序后退法是從全部特征開始每次剔除一個(gè)特征,所剔除的特征應(yīng)使余下特征組合的J值最大。然而,所有的次優(yōu)算法都不能保證所選擇的特征對(duì)某一判決函數(shù)來說是最優(yōu)的,因?yàn)樽詈玫奶卣鹘M合不一定包含最好的單個(gè)特征。最優(yōu)特征的搜索方法是窮舉法和分支定界法。窮舉法是對(duì)所有的特征組合計(jì)算J值,選出使J最大的那一組特征作為最優(yōu)特征。由于特征組合的數(shù)量隨著特征個(gè)數(shù)的增加而迅速增長,因此在實(shí)際應(yīng)用過程中使用窮舉法是不現(xiàn)實(shí)的。1基于刪除特征的篩選分支定界的搜索過程是通過搜索樹來表示的。總的搜索過程是沿著樹自上而下、從右到左進(jìn)行搜索。包括以下幾個(gè)部分:向下搜索、更新界值、向上回溯、停止回溯再向下搜索。分支定界算法使用的判決函數(shù)具有單調(diào)性。例如S1是S2的子集,則J(S1)<J(S2)。假如從原始特征集(1,2,3,4,5,6)中選出兩個(gè)特征,搜索樹如圖1所示,由于每層刪除一個(gè)特征,因此層數(shù)m=6-2=4。節(jié)點(diǎn)上的數(shù)字表明刪除的特征。例如節(jié)點(diǎn)X表明刪除特征(2,3),也就是剩下特征集(1,4,5,6)。開始時(shí)界值為0,從根節(jié)點(diǎn)開始沿最右邊的一支自上而下搜索,到達(dá)葉節(jié)點(diǎn)時(shí),計(jì)算J值,更新界值,令B=J,并記錄此時(shí)剩余的特征;然后向上回溯。一旦遇到有分支的節(jié)點(diǎn),則停止回溯向下搜索,如果該節(jié)點(diǎn)的J值小于界值,則向上回溯,否則向下一直搜索到葉節(jié)點(diǎn)。如果葉節(jié)點(diǎn)的J值大于界值,則更新界值令B=J,同時(shí)記下此時(shí)剩余的特征;否則向上回溯,一直到所有的節(jié)點(diǎn)搜索完畢或沒有比當(dāng)前界值更大的J值為止。由于樹的每個(gè)節(jié)點(diǎn)代表一種特征組合,于是所有可能的組合都被考慮到。分支定界所采用的可分性判據(jù)具有單調(diào)性,因此如果某個(gè)節(jié)點(diǎn)的J值小于界值,那么它的后繼節(jié)點(diǎn)可以不必搜索同時(shí)又不影響全局尋優(yōu)。例如假設(shè)節(jié)點(diǎn)X的J值小于界值B,則X的子節(jié)點(diǎn)4,5,以及4,5的子節(jié)點(diǎn)都可以不必考慮。同時(shí)由于搜索是從結(jié)構(gòu)簡單的右邊開始,所以這種選擇算法效率很高。如圖1所示,對(duì)于一個(gè)節(jié)點(diǎn)來說,它的最右邊的子樹總是1度節(jié)點(diǎn)(只含有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫1度節(jié)點(diǎn))或0度節(jié)點(diǎn)(葉節(jié)點(diǎn)),由于可能的解節(jié)點(diǎn)只在這個(gè)子樹的葉節(jié)點(diǎn)上,因此當(dāng)對(duì)最右邊的子樹進(jìn)行搜索時(shí),可以不必每次去掉一個(gè)特征,而可以直接到達(dá)葉節(jié)點(diǎn),此算法稱為BAB+算法。剪切最右邊1度節(jié)點(diǎn)后所得到的樹,稱為最小解樹。圖1的最小解樹如下圖所示。2改進(jìn)的分支機(jī)構(gòu)定界算法在圖2中,假設(shè)節(jié)點(diǎn)X的J值小于當(dāng)前界值,由于X是去除特征(2,3),或者說保留特征(1,4,5,6),在BAB和BAB+算法中,節(jié)點(diǎn)Z仍然要計(jì)算。然而,根據(jù)單調(diào)性可以知道節(jié)點(diǎn)Z根本不用考慮。由于節(jié)點(diǎn)X去除的特征集(2,3)是節(jié)點(diǎn)Z去除特征集(1,2,3)的子集,換句話說節(jié)點(diǎn)Z剩余的特征集(4,5,6)是節(jié)點(diǎn)X剩余特征集(1,4,5,6)的子集。因此節(jié)點(diǎn)Z的判據(jù)值J值必小于節(jié)點(diǎn)X的J值,而節(jié)點(diǎn)X的判據(jù)值J值小于當(dāng)前界值,因此節(jié)點(diǎn)Z的J值也必定小于當(dāng)前界值。在改進(jìn)的分支定界算法中,定義了部分路徑這一概念。部分路徑是由節(jié)點(diǎn)個(gè)數(shù)小于層數(shù)m并且判據(jù)值J值小于界值B的節(jié)點(diǎn)組成的(例如路徑(2,3))。一旦找到了部分路徑,改進(jìn)的分支定界算法就不必計(jì)算所有以部分路徑為子集的路徑,稱這些路徑為父路徑(例如(1,2,3))。當(dāng)在第L(L<m)層的節(jié)點(diǎn)N的判據(jù)值J值小于當(dāng)前界值B(假如該節(jié)點(diǎn)在某一部分路徑上),那么在改進(jìn)的分支定界算法中,節(jié)點(diǎn)N的所有后繼節(jié)點(diǎn)以及所有的父路徑都可以不必分析,這樣就可以節(jié)省很大的計(jì)算。3轉(zhuǎn)移平臺(tái)型ss-ls-qssn是原始特征的個(gè)數(shù),d是所要選擇的特征個(gè)數(shù),s表示深度,anti＿Xs表示舍棄s個(gè)特征以后余下的特征,Ws表示可供第s級(jí)當(dāng)前節(jié)點(diǎn)的下一級(jí)選擇舍棄的特征集,rs表示這個(gè)集合中元素的個(gè)數(shù),qs表示當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù),Stack存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn),Sub＿node(s)存儲(chǔ)第s級(jí)子節(jié)點(diǎn)的個(gè)數(shù)。Full表示父路徑,Partial表示部分路徑,B表示界值。Qs表示第s級(jí)當(dāng)前節(jié)點(diǎn)的qs個(gè)子節(jié)點(diǎn)所舍棄的特征。初始化:anti＿X0=W0,B=0,s=0,r0=n步驟1:用公式qs=rs-(n-d-s-1)計(jì)算qs。步驟2:判斷當(dāng)前路徑是否是父路徑,如果是,則轉(zhuǎn)步驟13;否則進(jìn)入步驟3。步驟3:判斷當(dāng)前路徑是否是單分支節(jié)點(diǎn),如果否,進(jìn)入步驟4;如果是,則包括該節(jié)點(diǎn)所有的后繼節(jié)點(diǎn),進(jìn)入步驟4。步驟4:計(jì)算J值,并按升序排列求出Qs=(x1s+1,x2s+1,…,xqss+1)。步驟5:把Qs中的特征按順序放入Stack中最后一個(gè)非空元素的后面,從Ws中去掉Qs,并修改rs,同時(shí)記錄下該層的子節(jié)點(diǎn)數(shù)。即步驟6:如果qs大于0,轉(zhuǎn)步驟11。否則,Sub＿node(s+1)減1,如果Sub＿node(s+1)=0,轉(zhuǎn)步驟7;否則,轉(zhuǎn)步驟10。步驟7:該節(jié)點(diǎn)為單分支節(jié)點(diǎn),向上回溯。即s=s-1;anti＿Xs=anti＿Xs+1+xqss+1。同時(shí)把Stack中的特征xqss+1去掉。如果s=-1,轉(zhuǎn)步驟9;否則轉(zhuǎn)步驟13。步驟9:如果Stack為空,退出。否則令s=1;把特征xqss+1從anti＿Xs中刪掉,即anti＿Xs+1=anti＿Xs-xqss+1,轉(zhuǎn)步驟1。步驟10:該節(jié)點(diǎn)有分支,把已經(jīng)擴(kuò)展過的節(jié)點(diǎn)放入anti＿Xs中,并把該節(jié)點(diǎn)從Stack中刪掉。然后把最接近該節(jié)點(diǎn)的左節(jié)點(diǎn)從anti＿Xs中去掉并向下擴(kuò)展,s=s+1;轉(zhuǎn)步驟1。步驟11:如果當(dāng)前J<B并且節(jié)點(diǎn)個(gè)數(shù)小于n-d,則把當(dāng)前路徑作為部分路徑加入Partial中,轉(zhuǎn)步驟13;如果J<B,但節(jié)點(diǎn)個(gè)數(shù)等于n-d,轉(zhuǎn)步驟13;否則轉(zhuǎn)步驟12。步驟12:把特征xqss+1從anti＿Xs中刪掉。如果s+1=n-d,更新界值,B=J(Xn-d),把J(Xn-d)作為當(dāng)前選擇的最好特征組。轉(zhuǎn)步驟13;否則s=s+1,轉(zhuǎn)步驟1。步驟13:Ws=Ws+1+xqss+1;rs=rs+1+1;qs=0;轉(zhuǎn)步驟6。4特征變量及判決函數(shù)為了驗(yàn)證改進(jìn)的分支定界算法,選用大臺(tái)芒、小臺(tái)芒、紅象牙、白象牙4芒果圖像共128個(gè)樣本,每個(gè)樣本有12個(gè)特征,包括顏色、形狀、面積、周長、長寬比等。判決函數(shù)J=|SW+SB|/|SW|=|ST|/|SW|,SW是總的類內(nèi)離差矩陣,SB是總的類間離差矩陣,ST是總體離差矩陣。由圖3可見,BAB+算法比BAB算法有一定程度的改進(jìn),而IBAB算法比BAB、BAB+算法更有效,而且隨著選取特征個(gè)數(shù)的增加,有效性越來越明顯。5改進(jìn)分支機(jī)構(gòu)定界算法分