一種改進(jìn)的二叉樹多分支持向量機(jī)算法*

周愛武,吳國(guó)進(jìn),崔丹丹

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

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

1 BT-SVM多類分類思想

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

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

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

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

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

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

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

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

3 改進(jìn)的二叉樹生成算法

3.1 相似度量函數(shù)

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

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

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

3.2 改進(jìn)算法

定義類平均距離：

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

[2]鄧乃揚(yáng)，田英杰.支持向量機(jī).北京：科學(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ī)算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(7):24-26.

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

[8]唐發(fā)明，王仲東，陳綿云.支持向量機(jī)多類分類算法研究[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ī)多類分類二叉樹生成算法[J].機(jī)械工程與自動(dòng)化,2007(3):1-3.

[11]謝志強(qiáng),高麗,楊靜.基于球結(jié)構(gòu)的完全二叉樹SVM多類分類算法[J].計(jì)算機(jī)應(yīng)用研究,2008，25(11):3268-3274.