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

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

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

中圖分類號：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

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

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

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

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

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

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

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

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

（2） 展開節點X： 即調用函數ExpandNode(X)；

（3） 輸出全局最優節點X*。

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

① 如果X 是終止節點，轉到第⑤步。否則，如果J(X)≥bound，繼續執行，如果J(X)

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

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

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

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

⑥結束。

在d<

2 最小決策樹

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

圖2 最小決策樹

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

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

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

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

Sxi=Sxi+1(2)

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

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

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

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

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

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

(1） 如果X是終止節點，轉到第（5）步。否則，如果J(X)≥bound，繼續執行下面的步驟，如果J(X)

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

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

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

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

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

（6） 結束。

4 實驗結果及結論

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

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

參 考 文 獻

［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.

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