摘 要： 二叉樹支持向量機(jī)分類算法主要是構(gòu)造一個(gè)偏二叉樹或是構(gòu)造一顆完全二叉樹，但是偏二叉樹分類的準(zhǔn)確性雖高而分類的效率低，完全二叉樹分類的效率高但是準(zhǔn)確性不高。本文提出一種算法，結(jié)合了以上兩種二叉樹構(gòu)造方法的優(yōu)點(diǎn)，并且更能反映樣本的真實(shí)分布。實(shí)驗(yàn)結(jié)果表明，新算法具有較高的推廣性能。
關(guān)鍵詞： 二叉樹； 支持向量機(jī)； 多類多分； 球結(jié)構(gòu)
支持向量機(jī)(SVM)[1-2]是一種基于統(tǒng)計(jì)學(xué)理論的機(jī)器學(xué)習(xí)方法，由VAPNIK和CORTES于1995年首先提出。在解決小樣本、非線性及高維向量空間的模式識(shí)別中具有良好的性能。支持向量機(jī)的思想是：如果是線性不可分，則通過某種非線性映射，將輸入向量x映射到一高維特征空間Z，在這個(gè)空間中構(gòu)造最優(yōu)超平面，把不同的類分開；如果是線性可分，就可以直接構(gòu)造最優(yōu)超平面。但是傳統(tǒng)的支持向量機(jī)分類方法是針對(duì)兩類問題的二分方法，而實(shí)際應(yīng)用中，更多的是多類問題，如何將一個(gè)兩類分類方法擴(kuò)展到多類的分類方法一直是人們研究的重點(diǎn)，目前SVM多類分類方法應(yīng)用得較為廣泛的有：“一對(duì)一”OVO(One-Versus-One)[3]、“一對(duì)多”OVR(One-Versus-Rest)[4]、“有向無環(huán)圖”(DAG)[5]。這些方法都是通過構(gòu)造一系列的SVM二分器并將它們組合起來實(shí)現(xiàn)的多類分類。但是都存在不足之處，前兩種方法存在線性不可分區(qū)域，第三種方法雖然解決了不可分區(qū)域問題，但各子類分類器在有向無環(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è)多類分類問題轉(zhuǎn)化為一系列的兩類分類問題，其中每個(gè)子類間的分類器都是SVM二值分類器，對(duì)于一個(gè)K類問題只需要構(gòu)造K-1個(gè)分類器，這樣相對(duì)于“一對(duì)一”、“一對(duì)多”及“有向無環(huán)圖”方法構(gòu)造所需的分類器都要少。另外，二叉樹方法可以克服傳統(tǒng)方法遇到的不可分問題。
二叉樹結(jié)構(gòu)的生成：例如，對(duì)于一個(gè)四類問題,可以有圖1中的兩種二叉樹結(jié)構(gòu)(還有其他的結(jié)構(gòu)沒有列出)。對(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)生成問題是許多學(xué)者研究的重點(diǎn)。目前已經(jīng)有大量此類論文研究分類相同的模型。
2 幾種常用的二叉樹生成算法
2.1 構(gòu)造偏二叉樹
由于上層節(jié)點(diǎn)的SVM子分類器的分類性能對(duì)整個(gè)分類模型的推廣性影響最大，所以在二叉樹的生成過程中，應(yīng)該讓與其他類別相差最大的類首先分割出來。此分類的基本思想是：利用聚類分析中的類距離作為二叉樹的生成算法，讓與其他類距離最遠(yuǎn)的類最先分割出來。圖2為四類樣本數(shù)據(jù)的二維空間分布圖，所以應(yīng)該先把與其他三類距離最遠(yuǎn)的第1類分割出來。在剩下的三個(gè)類中，第3類與其他兩類的距離最遠(yuǎn)，所以再把第3類分割出來。剩下的第2類與第4類構(gòu)造最后的二值分類器。這樣就得到了一棵類似于圖1(a)所示的二叉樹。
定義類距離[6]：把類Sa與類Sb中兩個(gè)最近樣本向量之間的歐式距離作為兩類之間的距離，即：
2.2 構(gòu)造完全或近似完全二叉樹
如果類別個(gè)數(shù)N=2e，e為正整數(shù)，這樣就可以構(gòu)造一個(gè)滿二叉樹，否則就構(gòu)造一個(gè)完全或近似完全二叉樹。該算法同樣需要用到類距離，可以用式(1)定義的類距離。構(gòu)造二叉樹的過程如下：如果有N個(gè)類別，將N個(gè)類置于集合S中，S1和S2為兩個(gè)空集合，Ns、Ns1、Ns2分
上面簡(jiǎn)單介紹了兩種構(gòu)造二叉樹的方法，現(xiàn)在分析這兩種方法的優(yōu)缺點(diǎn)。第一種方法每次把與其他類距離之和最大的類分割出來，這樣分類的準(zhǔn)確性較高，但是，如果對(duì)于一個(gè)N類分類問題，其中有一個(gè)類別K，有可能在第一次就被分離出來，也有可能在第N-1次才被分離出來，這樣分類的效率就會(huì)比較低，而且訓(xùn)練時(shí)間也比較慢。第二種方法，采用完全或近似完全二叉樹，所以分類和訓(xùn)練的效率比較高，但是，在構(gòu)造這顆二叉樹時(shí),每次都會(huì)把集合中的元素平均地分成兩類，這是不現(xiàn)實(shí)的，因?yàn)椋荒鼙ＷC每個(gè)集合中的任一元素相對(duì)于所屬集合的相似度大于另一個(gè)集合的相似度，這樣分類的準(zhǔn)確性就會(huì)較低。分類的準(zhǔn)確性和分類的效率是一對(duì)矛盾，本文提出一種改進(jìn)算法，既考慮分離的準(zhǔn)確性，又能保證分類的效率。
3 改進(jìn)的二叉樹生成算法
3.1 相似度量函數(shù)
第2節(jié)定義的類距離，是將兩類樣本的最短距離作為兩類的距離，這種方法雖然簡(jiǎn)單，但是沒有考慮類樣本的分布情況。本文采用球結(jié)構(gòu)的距離計(jì)算方法[8]，該方法在定義類距離時(shí)既考慮了類中心又考慮了類的樣本分布，是一種比較科學(xué)的方法。如圖3所示的兩類，它們的類中心距離相等，但是樣本分布不同。圖3(a)為兩類相交，圖3(b)為兩類相離。顯然圖3(a)比圖3(b)具有更高的相似性。因此，不能只以類中心的歐氏距離作為相似性度量函數(shù)，還需要考慮類樣本的分布情況。球結(jié)構(gòu)的SVM能構(gòu)造出半徑最小且盡可能包含該類所有樣本的球體,因此球體的半徑可以用來度量類樣本的分布。
(4)如果出現(xiàn)這種情況，說明類之間的相似度比較高，可以根據(jù)參考文獻(xiàn)[11]中提出的二叉樹生產(chǎn)算法，構(gòu)造一顆完全或近似完全二叉樹。結(jié)束。
(5)經(jīng)過步驟(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)過上面的步驟，可以構(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)造的偏二叉樹在這里沒有畫出)。
從圖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先分割出來，再把EFG分割出來，最后把HI和D分開，這樣的結(jié)果符合樣本的真實(shí)分布，所以具有比較高的分類精度。
再把圖7(a)構(gòu)造的二叉樹與偏二叉樹作一下比較，偏二叉樹每次只有一個(gè)類被分離出來，所以訓(xùn)練速度比較慢，而且在后面分類時(shí)效率也比較低。而本文構(gòu)造的二叉樹每次會(huì)把相似度比較高的一些類先分出來，再將這些類構(gòu)造一個(gè)完全或近似完全二叉樹，所以訓(xùn)練的時(shí)間會(huì)比偏二叉樹低而分類的速度要更快。
本文結(jié)合偏二叉樹和完全二叉樹的構(gòu)造思想，提出了一種基于球結(jié)構(gòu)的二叉樹生產(chǎn)算法，利用該算法構(gòu)造出的二叉樹更接近樣本的真實(shí)分布，具有較高的分類精度和分類速度。但是算法還存在一些沒有解決的問題，例如：在算法中要求dij<?姿d，本文參數(shù)?姿取0.5，對(duì)于其他樣本?姿值可能會(huì)取不同的值，所以?姿的取值問題是今后研究的重點(diǎn)。
參考文獻(xià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.