分支界定算法及其在特征選擇中的應用研究

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

關鍵詞：分支界定算法；特征選擇；特征集；最小決策樹；局部預測

中圖分類號：TP31 文獻標識碼：A

文章編號：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

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

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

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

分支界定算法針對的特征選擇問題是這樣定義的^[1]：在原來的D 個特征的集合中選擇一個d 個特征的子集，d

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

圖1 從5維中選擇2維的搜索樹

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

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

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

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

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

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

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

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

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

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

⑥結(jié)束。

在d<

2 最小決策樹

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

圖2 最小決策樹

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

3 局部預測分支界定算法及其改進

局部預測分支界定算法^[3，5，6]（BranchBound Algorithm with Partial Prediction，BBPP）是用預測節(jié)點的評價值來代替真實的評價值。對于每一個特征xi，保存一個特征對評價值的貢獻Axi。Axi在運行過程中不斷地更新，用來預測節(jié)點的評價值。可以把Axi理解為從子集中去掉xi所帶來的評價值下降的平均值。其計算公式是：

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

Sxi=Sxi+1(2)

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

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

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

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

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

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

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

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

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

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

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

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

（6） 結(jié)束。

4 實驗結(jié)果及結(jié)論

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

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

參 考 文 獻

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

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

［3］王振曉.分類器設計中特征選擇問題的研究[D].上海：上海交通大學，2003.

［4］虞華.基于雷達回波的特征選擇與分類識別方法研究[D].長沙：國防科技大學，2003.

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

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

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