周愛武,吳國進,崔丹丹

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

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

1 BT-SVM多類分類思想

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

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

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

2.1 構(gòu)造偏二叉樹

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

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

2.2 構(gòu)造完全或近似完全二叉樹

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

3 改進的二叉樹生成算法

3.1 相似度量函數(shù)

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

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

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

3.2 改進算法

定義類平均距離：

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

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

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

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

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

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

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

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

4 實驗分析

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

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

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

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

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

[2]鄧乃揚，田英杰.支持向量機.北京：科學(xué)出版社，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]唐發(fā)明，王仲東，陳綿云.一種新的二叉樹多類支持向量機算法[J].計算機工程與應(yīng)用,2005,41(7):24-26.

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

[8]唐發(fā)明，王仲東，陳綿云.支持向量機多類分類算法研究[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]謝志強,高麗,楊靜.基于球結(jié)構(gòu)的完全二叉樹SVM多類分類算法[J].計算機應(yīng)用研究,2008，25(11):3268-3274.