一種改進的二叉樹多分支持向量機算法*

周愛武,吳國進,崔丹丹

(安徽大學 計算機科學與技術學院,安徽 合肥230039)

支持向量機 (SVM)[1-2]是一種基于統計學理論的機器學習方法，由VAPNIK和CORTES于1995年首先提出。在解決小樣本、非線性及高維向量空間的模式識別中具有良好的性能。支持向量機的思想是：如果是線性不可分，則通過某種非線性映射，將輸入向量x映射到一高維特征空間Z，在這個空間中構造最優超平面，把不同的類分開；如果是線性可分，就可以直接構造最優超平面。但是傳統的支持向量機分類方法是針對兩類問題的二分方法，而實際應用中，更多的是多類問題，如何將一個兩類分類方法擴展到多類的分類方法一直是人們研究的重點，目前SVM多類分類方法應用得較為廣泛的有：“一對一”OVO(One-Versus-One)[3]、“一對多”OVR(One-Versus-Rest)[4]、“有向無環圖”(DAG)[5]。 這些方法都是通過構造一系列的SVM二分器并將它們組合起來實現的多類分類。但是都存在不足之處，前兩種方法存在線性不可分區域，第三種方法雖然解決了不可分區域問題，但各子類分類器在有向無環圖中的位置會影響整個分類器的性能。所以人們又提出一種利用二叉樹構造SVM的多類分類方法。

1 BT-SVM多類分類思想

BT-SVM的思想是：首先將所有類別分成兩子類，再將子類進一步劃分成兩個次級子類，如此循環下去，直到所有的節點只包含一個單獨的類別為止，這些節點也是二叉樹的葉子節點，這樣就得到了一棵二叉樹。該方法將一個多類分類問題轉化為一系列的兩類分類問題，其中每個子類間的分類器都是SVM二值分類器，對于一個K類問題只需要構造K-1個分類器，這樣相對于“一對一”、“一對多”及“有向無環圖”方法構造所需的分類器都要少。另外，二叉樹方法可以克服傳統方法遇到的不可分問題。

二叉樹結構的生成：例如，對于一個四類問題,可以有圖1中的兩種二叉樹結構 (還有其他的結構沒有列出)。對于不同的二叉樹，會得到不同的分類模型，它們的推廣性能也會不同。不同的層次結構對分類精度有一定影響，并且這種影響有可能產生“誤差累積”現象，既若在某個節點上發生分類錯誤，將會把錯誤延續下去，該節點的后續下一級節點上的分類就失去了意義。越是上層節點的子分類器的分類性能對整個分類模型的推廣性影響越大，因此，二叉樹的結構生成問題是許多學者研究的重點。目前已經有大量此類論文研究分類相同的模型。

2 幾種常用的二叉樹生成算法

2.1 構造偏二叉樹

由于上層節點的SVM子分類器的分類性能對整個分類模型的推廣性影響最大，所以在二叉樹的生成過程中，應該讓與其他類別相差最大的類首先分割出來。此分類的基本思想是：利用聚類分析中的類距離作為二叉樹的生成算法，讓與其他類距離最遠的類最先分割出來。圖2為四類樣本數據的二維空間分布圖，所以應該先把與其他三類距離最遠的第1類分割出來。在剩下的三個類中，第3類與其他兩類的距離最遠，所以再把第3類分割出來。剩下的第2類與第4類構造最后的二值分類器。這樣就得到了一棵類似于圖1(a)所示的二叉樹。

定義類距離[6]：把類Sa與類Sb中兩個最近樣本向量之間的歐式距離作為兩類之間的距離，即：

2.2 構造完全或近似完全二叉樹

上面簡單介紹了兩種構造二叉樹的方法，現在分析這兩種方法的優缺點。第一種方法每次把與其他類距離之和最大的類分割出來，這樣分類的準確性較高，但是，如果對于一個N類分類問題，其中有一個類別K，有可能在第一次就被分離出來，也有可能在第N-1次才被分離出來，這樣分類的效率就會比較低，而且訓練時間也比較慢。第二種方法，采用完全或近似完全二叉樹，所以分類和訓練的效率比較高，但是，在構造這顆二叉樹時,每次都會把集合中的元素平均地分成兩類，這是不現實的，因為，不能保證每個集合中的任一元素相對于所屬集合的相似度大于另一個集合的相似度，這樣分類的準確性就會較低。分類的準確性和分類的效率是一對矛盾，本文提出一種改進算法，既考慮分離的準確性，又能保證分類的效率。

3 改進的二叉樹生成算法

3.1 相似度量函數

第2節定義的類距離，是將兩類樣本的最短距離作為兩類的距離，這種方法雖然簡單，但是沒有考慮類樣本的分布情況。本文采用球結構的距離計算方法[8]，該方法在定義類距離時既考慮了類中心又考慮了類的樣本分布，是一種比較科學的方法。如圖3所示的兩類，它們的類中心距離相等，但是樣本分布不同。圖3(a)為兩類相交，圖 3(b)為兩類相離。顯然圖3(a)比圖 3(b)具有更高的相似性。因此，不能只以類中心的歐氏距離作為相似性度量函數，還需要考慮類樣本的分布情況。球結構的SVM能構造出半徑最小且盡可能包含該類所有樣本的球體,因此球體的半徑可以用來度量類樣本的分布。

根據上述分析，可以用下面的距離計算公式作為類i與j間的相似性度量：

其中：ai，aj，Ri，Rj分別是第 i類和第 j類的中心和半徑。 當dij≥0時，說明第i類與第j類沒有相交區域。dij越大，說明第i類與第j類可分性越強，dij越小，說明兩類的相似度越高。

3.2 改進算法

定義類平均距離：

其中：N為總類別數，dij為(2)式定義的類 i與類 j的距離，當 i=j時，定義 dij=0。 另定義集合 S、S1和 S2，Ns、Ns1、Ns2分別表示 S、S1、S2集合中類標號的個數。算法具體描述如下：

(1)對于一個N類問題，首先對N個類進行標號，標號為1,2,3…，N,并將這些類標號置入集合S中。由參考文獻[9]中的式(10)和式(15)可得到每一類樣本所在超球體的中心ai和半徑 Ri(i=1,2,3,…,N)。根據式(2)和式(3)計算出 dij和 d。

(2)如果Ns=2，則把其中的一個類標號的類作為左子類，另一個類作為右子類，結束。

(3)計算集合S中的每一類到其他類的距離dij，統計每個類到其他類距離小于λd類的個數 (λ是一個大于零的參數，對于不同的樣本分布情況，通過調整λ值來提高分類的精度)，記作：Numi(i=1,2,3,…,N)。例如第 i類，統計這個類到其他N-1個類的距離小于λd的類個數，計入Numi。找出最大的Numi(如果存在不唯一，任意選擇其中一個)，如果 Numi=Ns，則轉入(4)，否則，將標號i 置入集合 S1，并將滿足 dij＜λd(j=1,2,3,…,Ns,j≠i)的類的標號置入S1，將 S剩下的類的標號置入S2。S1中類標號對應的類就作為二叉樹的左之類，S2中類標號對應的類作為二叉樹的右子類。轉到(5)。

(4)如果出現這種情況，說明類之間的相似度比較高，可以根據參考文獻[11]中提出的二叉樹生產算法，構造一顆完全或近似完全二叉樹。結束。

(5)經過步驟(3)，集合S1中的類別相似度比較高，可以根據參考文獻[11]中提出的二叉樹生產算法，以集合S1對應的左子類作為頂層節點構造一顆完全或近似完全二叉樹。

(6)如果 Ns2=1，則結束。否則將集合 S2中的類別號置入S，將得到的右子類作為頂層節點，回到步驟(2)。

經過上面的步驟，可以構造出一棵二叉樹，這個二叉樹可能是一個偏二叉樹，也可能是一個完全二叉樹，但是這兩種都是極端的情況。更多的情況下構造的二叉樹總體上是一棵偏二叉樹，局部是一棵完全或近似完全二叉樹。這樣做的好處是，既保證了分類的準確性，又保證了分類的速度。

4 實驗分析

下面以N=9的情況分析本文提出的算法構造的二叉樹，并與參考文獻[11]中構造的完全二叉樹做比較。圖4是9類樣本的球結構在二維空間分布情況，圖5是球心坐標,圖6是根據式(2)計算出的各類間的距離。由圖6中的數據可以計算出d=2.966，λ取0.5。根據本文提出的算法，構造出圖 7(a)所示的二叉樹，圖 7(b)圖是根據參考文獻[11]算法構造的二叉樹(構造的偏二叉樹在這里沒有畫出)。

從圖4的樣本分布圖可以看出，圖 7(a)所示的二叉樹分類更符合樣本的分布情況。而圖7(b)所示的二叉樹把原本相似度非常高的 E、F、G三個類拆分成了 EF和 G，這顯然是不合理的，出現這種情況的原因是因為此算法要求構造一個完全二叉樹，左子樹和右子樹包含的類別個數只能相差0或1，所以有些相似度高的類就被拆分開了。這樣就會產生分類誤差，而且本實驗在一開始就出現這種誤差會影響后面的分類結果，出現誤差累積的現象。而本文提出的算法，首先把相似度高的ABC先分割出來，再把EFG分割出來，最后把HI和D分開，這樣的結果符合樣本的真實分布，所以具有比較高的分類精度。

再把圖7(a)構造的二叉樹與偏二叉樹作一下比較，偏二叉樹每次只有一個類被分離出來，所以訓練速度比較慢，而且在后面分類時效率也比較低。而本文構造的二叉樹每次會把相似度比較高的一些類先分出來，再將這些類構造一個完全或近似完全二叉樹，所以訓練的時間會比偏二叉樹低而分類的速度要更快。

本文結合偏二叉樹和完全二叉樹的構造思想，提出了一種基于球結構的二叉樹生產算法，利用該算法構造出的二叉樹更接近樣本的真實分布，具有較高的分類精度和分類速度。但是算法還存在一些沒有解決的問題，例如：在算法中要求 dij＜λd，本文參數λ取 0.5，對于其他樣本λ值可能會取不同的值，所以λ的取值問題是今后研究的重點。

[1]VAPNIK V.Statistical learning theory[M].New York:Wiley,1988.

[2]鄧乃揚，田英杰.支持向量機.北京：科學出版社，2009.

[3]BOTTOU L,CORTES,DENKER J.Comparison of classifier Methods:a case study in handwriting digit recognition[C]//Proceedings of the 12th IAPR International Conferenceon Pattern Recognition,Jerusalerm:IEEE,1994.

[4]KREBERL U.Pair wise classification and support vector machines[C]//Advances In Kernel Methods-Support Vector Learnning,Cambrige:MIT Press,1999:255-268.

[5]PLATT J C,CRISTIANINI N,SHAWE～TAY-LOR J.Large Margin DAGs for multiclass classification[C]//Advances in Neural Information Processing systems,Cambridge:Mtt Press,2000:547-268.

[6]唐發明，王仲東，陳綿云.一種新的二叉樹多類支持向量機算法[J].計算機工程與應用,2005,41(7):24-26.

[7]張貝貝，何中市.基于支持向量機數據描述算法的SVM多分類別新方法[J].計算機應用研究,2007,24(11):46-48.

[8]唐發明，王仲東，陳綿云.支持向量機多類分類算法研究[J].控制與決策,2005,20(7):746-749.

[9]Hao Peiyi,LIN Y H.A new multi-class support vector machine with multi-sphere in the feature Space[C].Lecture Notes in Computer Science.BerLin,Heidelberg:Springer-Verlag,2007:756-765.

[10]張曉平,楊潔明.一種新的支持向量機多類分類二叉樹生成算法[J].機械工程與自動化,2007(3):1-3.

[11]謝志強,高麗,楊靜.基于球結構的完全二叉樹SVM多類分類算法[J].計算機應用研究,2008，25(11):3268-3274.