摘 要：分支界定算法是目前為止惟一既能保證全局最優(yōu)，又能避免窮盡搜索的算法。他自上而下進(jìn)行搜索，同時(shí)具有回溯功能，可使所有可能的特征組合都被考慮到。對(duì)分支界定算法進(jìn)行研究，并對(duì)其做了一些改進(jìn)；最后對(duì)改進(jìn)前后的算法在特征選擇領(lǐng)域進(jìn)行比較，選擇效率有了明顯的提高。

關(guān)鍵詞：分支界定算法；特征選擇；特征集；最小決策樹(shù)；局部預(yù)測(cè)

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2008)10-142-03

Study of BranchBound Algorithm and Application of Feature Selection

WANG Sichen，YU Lu，LIU Shui，TANG Jinyuan

(Qingdao Branch，Naval Aeronautical Engineering Institute，Qingdao，266041，China)

Abstract：BranchBound Algorithm is the only method which can ensure best of all the vectors，and it can avoid endless searching.It searches from top to bottom and has the function that from bottom to top，so it can include all of the feature vectors.The BranchBound Algorithm is studied in the paper，and it is improved，the two algorithms are compared by the feature seclection，the efficiency of seclection is improved greatly.

Keywords：branchbound algorithm;feature selection;feature vector;minimum solution tree;partial prediction

隨著科學(xué)技術(shù)的發(fā)展，信息獲取技術(shù)的不斷提高和生存能力的提升，對(duì)于目標(biāo)特征能夠獲得的數(shù)據(jù)量越來(lái)越大，維數(shù)越來(lái)越高，一方面可以使信息更充分，但在另一方面數(shù)據(jù)中的冗余和無(wú)關(guān)部分也會(huì)相應(yīng)的增多。特征選擇^[1，2]就是為了篩選出那些對(duì)于分類來(lái)說(shuō)最相關(guān)的特征，而去掉冗余和無(wú)關(guān)的特征。

分支界定算法^{[1，3，4]}是一種行之有效的特征選擇方法，由于合理地組織搜索過(guò)程，使其有可能避免計(jì)算某些特征組合，同時(shí)又能保證選擇的特征子集是全局最優(yōu)的。但是如果原始特征集的維數(shù)與要選擇出來(lái)的特征子集的維數(shù)接近或者高很多，其效率就不夠理想?；诖?，本文對(duì)分支界定算法做了一定的改進(jìn)，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，與改進(jìn)前相比其效率有明顯的提高。

1 分支界定算法的基本原理

分支界定算法針對(duì)的特征選擇問(wèn)題是這樣定義的^[1]：在原來(lái)的D 個(gè)特征的集合中選擇一個(gè)d 個(gè)特征的子集，d

其中X代表一個(gè)特征子集，J(X)是所采取的評(píng)價(jià)函數(shù)。單調(diào)性保證了分支界定算法能在保證全局最優(yōu)的前提下大大減少搜索的復(fù)雜度。分支界定算法的搜索空間是一棵樹(shù)，稱為搜索樹(shù)^[2](Search Tree)。他是在算法運(yùn)行過(guò)程中自上而下(top-bottom)按照深度優(yōu)先(depth-first)的次序動(dòng)態(tài)生成的。以D=5，d=2為例，其中D 為總的特征維數(shù)，d 為預(yù)期選定的特征子集的維數(shù)。搜索樹(shù)的拓?fù)浣Y(jié)構(gòu)如圖1所示。分支界定算法的搜索樹(shù)總共有Cd+1D+1個(gè)節(jié)點(diǎn)，其中有Cd+1D－1個(gè)度數(shù)為1的節(jié)點(diǎn)，有CdD個(gè)葉子節(jié)點(diǎn)數(shù)。

圖1 從5維中選擇2維的搜索樹(shù)

該算法中用到的一些符號(hào)說(shuō)明如下：總的特征維數(shù)為D；預(yù)期選定的特征子集Xg的維數(shù)為d 。X 為當(dāng)前要展開(kāi)以擴(kuò)展搜索樹(shù)的節(jié)點(diǎn)；Num_features是X 中的特征數(shù)目；X→q為節(jié)點(diǎn)X 在搜索樹(shù)中的子節(jié)點(diǎn)個(gè)數(shù)(在動(dòng)態(tài)生成搜索樹(shù)中很重要)；XD為所有特征組成的集合；X*是當(dāng)前最優(yōu)節(jié)點(diǎn)；bound是當(dāng)前最優(yōu)節(jié)點(diǎn)X*的評(píng)價(jià)函數(shù)值；J(X)為評(píng)價(jià)函數(shù)；該算法的具體步驟如下^[3，5]：

（1） 令X=XD，X→q=d+1，即讓X 指向根節(jié)點(diǎn)，并設(shè)置根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)為d+1；bound=0；

（2） 展開(kāi)節(jié)點(diǎn)X： 即調(diào)用函數(shù)ExpandNode(X)；

（3） 輸出全局最優(yōu)節(jié)點(diǎn)X*。

其中第（2）步中函數(shù)ExpandNode(X)是一個(gè)遞歸過(guò)程，他具體的實(shí)現(xiàn)步驟如下：

① 如果X 是終止節(jié)點(diǎn)，轉(zhuǎn)到第⑤步。否則，如果J(X)≥bound，繼續(xù)執(zhí)行，如果J(X)

② 令n=Num_features(X)，在X 中依次去掉一個(gè)特征，產(chǎn)生子節(jié)點(diǎn)，共n 個(gè)，記為X1，X2，…，Xn；

③ 計(jì)算這n 個(gè)子節(jié)點(diǎn)的的評(píng)價(jià)函數(shù)值J(Xi)，i=1，2，…，n。按升序排列：J(Xj1)≤J(Xj2)≤…≤J(Xjn) ；

④令p=X→q；取上式中的前p 個(gè)節(jié)點(diǎn)，作為搜索樹(shù)中X 的后繼節(jié)點(diǎn)。對(duì)于這p個(gè)節(jié)點(diǎn)中的每個(gè)節(jié)點(diǎn)Xji(i=p－1，p－2，…，1)，令Xji→q=p－i+1。依次執(zhí)行ExpandNode(Xji)(i=p－1，p－2，…，1)執(zhí)行完p 個(gè)節(jié)點(diǎn)的后續(xù)展開(kāi)后，轉(zhuǎn)到第⑥步；

⑤若X優(yōu)于當(dāng)前最優(yōu)節(jié)點(diǎn)（即J(X)>bound），令bound=J(X)，X*=X；

⑥結(jié)束。

在d<

2 最小決策樹(shù)

上面的搜索樹(shù)中每個(gè)節(jié)點(diǎn)的最右一個(gè)節(jié)點(diǎn)后面連接了一長(zhǎng)串度數(shù)為1的節(jié)點(diǎn)。在這一串節(jié)點(diǎn)中，其實(shí)只有葉子節(jié)點(diǎn)的評(píng)價(jià)值是真正需要計(jì)算的。因此，如果將每個(gè)節(jié)點(diǎn)的最右節(jié)點(diǎn)用葉子節(jié)點(diǎn)代替，可以簡(jiǎn)化樹(shù)的拓?fù)浣Y(jié)構(gòu)。同時(shí)不會(huì)破壞搜索全局最優(yōu)的特性。簡(jiǎn)化后稱為“最小決策樹(shù)”^[2，3](Minimum Solution Tree)。圖2所示為最小決策樹(shù)示意圖。

圖2 最小決策樹(shù)

根據(jù)上面的算法描述，在展開(kāi)一個(gè)節(jié)點(diǎn)時(shí)，將評(píng)價(jià)值小的后繼節(jié)點(diǎn)放在樹(shù)的左邊，評(píng)價(jià)值大的后繼節(jié)點(diǎn)放在樹(shù)的右邊。由于搜索過(guò)程是從右邊往左邊進(jìn)行的，所以這種排序可以帶來(lái)2個(gè)好處：bound值快速增大，使一個(gè)節(jié)點(diǎn)處發(fā)生剪枝的概率增大(該節(jié)點(diǎn)評(píng)價(jià)值小于bound值的概率增大)；剪枝更多地發(fā)生在樹(shù)的左邊，因?yàn)樽筮叺墓?jié)點(diǎn)評(píng)價(jià)值小，發(fā)生剪枝的概率大，而樹(shù)的左邊的節(jié)點(diǎn)有更多的子節(jié)點(diǎn)數(shù)，因此可以刪除掉更多的節(jié)點(diǎn)。最小決策樹(shù)正是去掉了這些節(jié)點(diǎn)，所以在原始的分支界定算法的基礎(chǔ)上大大提高了搜索效率。

3 局部預(yù)測(cè)分支界定算法及其改進(jìn)

局部預(yù)測(cè)分支界定算法^{[3，5，6]}（BranchBound Algorithm with Partial Prediction，BBPP）是用預(yù)測(cè)節(jié)點(diǎn)的評(píng)價(jià)值來(lái)代替真實(shí)的評(píng)價(jià)值。對(duì)于每一個(gè)特征xi，保存一個(gè)特征對(duì)評(píng)價(jià)值的貢獻(xiàn)Axi。Axi在運(yùn)行過(guò)程中不斷地更新，用來(lái)預(yù)測(cè)節(jié)點(diǎn)的評(píng)價(jià)值。可以把Axi理解為從子集中去掉xi所帶來(lái)的評(píng)價(jià)值下降的平均值。其計(jì)算公式是：

Axi=Axi#8226;Sxi+J(X)－J(X－{xi})Sxi+1(1)

Sxi=Sxi+1(2)

其中Sxi是一個(gè)計(jì)數(shù)器，記錄Axi被更新的次數(shù)。局部預(yù)測(cè)分支界定算法在滿足一定條件的情況下預(yù)測(cè)節(jié)點(diǎn)的評(píng)價(jià)值，預(yù)測(cè)公式是：

J(X－{xi})=J(X)－γ#8226;Axi(3)

其中γ是一個(gè)預(yù)先給定的數(shù)，用來(lái)調(diào)整預(yù)測(cè)的精確程度。只有在確實(shí)需要知道節(jié)點(diǎn)的真實(shí)評(píng)價(jià)值的時(shí)候，才計(jì)算其真實(shí)值，由于預(yù)測(cè)比計(jì)算真實(shí)值快得多，所以節(jié)省了時(shí)間。

通過(guò)上面對(duì)局部預(yù)測(cè)分支界定算法的研究，作者對(duì)該算法做的改進(jìn)為：在最小決策樹(shù)中，最右一個(gè)節(jié)點(diǎn)可以直接變?yōu)槿~子節(jié)點(diǎn)，所以可以直接計(jì)算這個(gè)葉子節(jié)點(diǎn)的評(píng)價(jià)值，這樣在每一次展開(kāi)一個(gè)節(jié)點(diǎn)的時(shí)候就能節(jié)省一次可能的評(píng)價(jià)值運(yùn)算；在局部預(yù)測(cè)分支界定算法中，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)是按照預(yù)測(cè)值進(jìn)行排序的，在計(jì)算了子節(jié)點(diǎn)的真實(shí)評(píng)價(jià)后，將子節(jié)點(diǎn)按照真實(shí)評(píng)價(jià)值重新排序。

改進(jìn)之后的算法與改進(jìn)之前相比的優(yōu)點(diǎn)為：每展開(kāi)一個(gè)節(jié)點(diǎn)，改進(jìn)后的算法比改進(jìn)前少了一次評(píng)價(jià)值的運(yùn)算。因此節(jié)省的次數(shù)就是最小決策樹(shù)的中間節(jié)點(diǎn)的個(gè)數(shù)；在展開(kāi)一個(gè)節(jié)點(diǎn)時(shí)，改進(jìn)前是按照預(yù)測(cè)值對(duì)子節(jié)點(diǎn)進(jìn)行排序的，一般來(lái)說(shuō)和真實(shí)排序不一致。改進(jìn)后在計(jì)算子節(jié)點(diǎn)的真實(shí)評(píng)價(jià)值后，按真實(shí)值進(jìn)行排序，并依次放入最小決策樹(shù)。這樣可以減少評(píng)價(jià)次數(shù)和搜索時(shí)間。

改進(jìn)前后的算法的實(shí)現(xiàn)步驟不變，不同的是遞歸函數(shù)ExpandNode(X)的實(shí)現(xiàn)，具體實(shí)現(xiàn)步驟如下：

(1） 如果X是終止節(jié)點(diǎn)，轉(zhuǎn)到第（5）步。否則，如果J(X)≥bound，繼續(xù)執(zhí)行下面的步驟，如果J(X)

(2） 令n=Num_features(X)，在X中依次去掉一個(gè)特征，產(chǎn)生子節(jié)點(diǎn)，共有n 個(gè)，記為X1，X2，…，Xn；

(3） 根據(jù)預(yù)測(cè)公式Jρ(X－{fi})=J(X)－γ#8226;Afi預(yù)測(cè)這n 個(gè)子節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值J(X)，i=1，2，…，n。將這n個(gè)評(píng)價(jià)值按升序排列：

J(Xj1)≤J(Xj2)≤…≤J(Xjn)

(4） 令p=X→q；取上式中的前p 個(gè)節(jié)點(diǎn)，作為搜索樹(shù)中X的后繼節(jié)點(diǎn)。將最右節(jié)點(diǎn)Xjp直接變成終止節(jié)點(diǎn)Xi，然后計(jì)算其評(píng)價(jià)值J(Xi)，如果J(Xi)≥bound，令bound=J(Xi)，X*=X。計(jì)算其余p-1個(gè)子節(jié)點(diǎn)的真實(shí)評(píng)價(jià)值J(Xji) (i=p-1，p-2，…，1)，并根據(jù)式（1）和式（2）更新特征對(duì)評(píng)價(jià)值的貢獻(xiàn)Axi以及Sxi，然后將他們按照升序排序?yàn)椋篔(Xk1)≤J(Xk2)≤…≤J(Xk(p－1))。對(duì)于這p-1個(gè)節(jié)點(diǎn)中的每個(gè)節(jié)點(diǎn)Xki(i=p-l，p-2，…，1)，令Xki→q＝p－i+1。依次執(zhí)行ExpandNode(Xji) (i=p-1，p-2，…，1)執(zhí)行完p-1個(gè)節(jié)點(diǎn)的后續(xù)展開(kāi)后，轉(zhuǎn)到（6）；

(5） 如果X優(yōu)于當(dāng)前最優(yōu)節(jié)點(diǎn)（即J(X)>bound，則令bound=J(X)，X*=X；

（6） 結(jié)束。

4 實(shí)驗(yàn)結(jié)果及結(jié)論

在本實(shí)驗(yàn)中，所用的特征集是從某型低分辨雷達(dá)獲取的實(shí)驗(yàn)數(shù)據(jù)，共提取了27個(gè)特征，組成特征集。這里對(duì)改進(jìn)前后消耗的時(shí)間（這里消耗的時(shí)間是在Core(TM)2，CPU主頻1.86 GHz，內(nèi)存2 GB的電腦上的運(yùn)行時(shí)間）做比較。具體實(shí)驗(yàn)情況如下：對(duì)1架、2架和4架目標(biāo)，分別選1 000組數(shù)據(jù)，其中500組用于分類器學(xué)習(xí)，500組用于目標(biāo)識(shí)別。用局部預(yù)測(cè)分支界定算法在原始的27維特征中，改進(jìn)的局部預(yù)測(cè)分支界定算法選擇9個(gè)特征。對(duì)于不同的組合順序，改進(jìn)之前需要13~20 min，改進(jìn)之后只需要11~17 min。

從理論的角度分析，改進(jìn)之后的局部預(yù)測(cè)分支界定算法與改進(jìn)前相比，減少了一次評(píng)價(jià)值的計(jì)算。因此節(jié)省的次數(shù)就是最小決策樹(shù)的中間節(jié)點(diǎn)的個(gè)數(shù)，則減少的運(yùn)算次數(shù)就是最小決策樹(shù)的總節(jié)點(diǎn)數(shù)減去葉子節(jié)點(diǎn)數(shù)Cd+1D+1－CdD－1－CdD，其中Cd+1D+1－Cd+1D－1是最小決策樹(shù)的總節(jié)點(diǎn)數(shù)；CdD是葉子節(jié)點(diǎn)數(shù)。所以改進(jìn)后的局部預(yù)測(cè)分支界定算法可以使評(píng)價(jià)值的運(yùn)算量減少Cd+1D+1－Cd－1D+1－CdD2×(Cd+1D+1－Cd－1D+1)－CdD×100%。這里分析的是沒(méi)有剪枝的最小決策樹(shù)的情況，實(shí)際運(yùn)算中由于進(jìn)行了剪枝，運(yùn)算次數(shù)會(huì)有所不同，但是改進(jìn)之后的局部預(yù)測(cè)分支界定算法的運(yùn)算次數(shù)一定小于改進(jìn)之前的運(yùn)算次數(shù)。

參 考 文 獻(xiàn)

［1］邊肇祺，張學(xué)工.模式識(shí)別[M].北京：清華大學(xué)出版社，2001.

［2］Yu B，Yuan B.A More Efficient Branch and Bound Algorithm for Feature Seclection[J].Patern Recognition，1993，26:883-889.

［3］王振曉.分類器設(shè)計(jì)中特征選擇問(wèn)題的研究[D].上海：上海交通大學(xué)，2003.

［4］虞華.基于雷達(dá)回波的特征選擇與分類識(shí)別方法研究[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2003.

［5］李國(guó)正.特征選擇若干新方法的研究[D].上海：上海交通大學(xué)，2004.

［6］賈沛.特征選擇技術(shù)研究[D].武漢：華中科技大學(xué)，2003.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。