摘 要： 二叉樹支持向量機(jī)分類算法主要是構(gòu)造一個偏二叉樹或是構(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)計學(xué)理論的機(jī)器學(xué)習(xí)方法，由VAPNIK和CORTES于1995年首先提出。在解決小樣本、非線性及高維向量空間的模式識別中具有良好的性能。支持向量機(jī)的思想是：如果是線性不可分，則通過某種非線性映射，將輸入向量x映射到一高維特征空間Z，在這個空間中構(gòu)造最優(yōu)超平面，把不同的類分開；如果是線性可分，就可以直接構(gòu)造最優(yōu)超平面。但是傳統(tǒng)的支持向量機(jī)分類方法是針對兩類問題的二分方法，而實(shí)際應(yīng)用中，更多的是多類問題，如何將一個兩類分類方法擴(kuò)展到多類的分類方法一直是人們研究的重點(diǎn)，目前SVM多類分類方法應(yīng)用得較為廣泛的有：“一對一”OVO(One-Versus-One)[3]、“一對多”OVR(One-Versus-Rest)[4]、“有向無環(huán)圖”(DAG)[5]。這些方法都是通過構(gòu)造一系列的SVM二分器并將它們組合起來實(shí)現(xiàn)的多類分類。但是都存在不足之處，前兩種方法存在線性不可分區(qū)域，第三種方法雖然解決了不可分區(qū)域問題，但各子類分類器在有向無環(huán)圖中的位置會影響整個分類器的性能。所以人們又提出一種利用二叉樹構(gòu)造SVM的多類分類方法。
1 BT-SVM多類分類思想
BT-SVM的思想是：首先將所有類別分成兩子類，再將子類進(jìn)一步劃分成兩個次級子類，如此循環(huán)下去，直到所有的節(jié)點(diǎn)只包含一個單獨(dú)的類別為止，這些節(jié)點(diǎn)也是二叉樹的葉子節(jié)點(diǎn)，這樣就得到了一棵二叉樹。該方法將一個多類分類問題轉(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é)點(diǎn)上發(fā)生分類錯誤，將會把錯誤延續(xù)下去，該節(jié)點(diǎn)的后續(xù)下一級節(jié)點(diǎn)上的分類就失去了意義。越是上層節(jié)點(diǎn)的子分類器的分類性能對整個分類模型的推廣性影響越大，因此， 二叉樹的結(jié)構(gòu)生成問題是許多學(xué)者研究的重點(diǎn)。目前已經(jīng)有大量此類論文研究分類相同的模型。
2 幾種常用的二叉樹生成算法
2.1 構(gòu)造偏二叉樹
由于上層節(jié)點(diǎn)的SVM子分類器的分類性能對整個分類模型的推廣性影響最大，所以在二叉樹的生成過程中，應(yīng)該讓與其他類別相差最大的類首先分割出來。此分類的基本思想是：利用聚類分析中的類距離作為二叉樹的生成算法，讓與其他類距離最遠(yuǎn)的類最先分割出來。圖2為四類樣本數(shù)據(jù)的二維空間分布圖，所以應(yīng)該先把與其他三類距離最遠(yuǎn)的第1類分割出來。在剩下的三個類中，第3類與其他兩類的距離最遠(yuǎn)，所以再把第3類分割出來。剩下的第2類與第4類構(gòu)造最后的二值分類器。這樣就得到了一棵類似于圖1(a)所示的二叉樹。
定義類距離[6]：把類Sa與類Sb中兩個最近樣本向量之間的歐式距離作為兩類之間的距離，即：
2.2 構(gòu)造完全或近似完全二叉樹
如果類別個數(shù)N=2e，e為正整數(shù)，這樣就可以構(gòu)造一個滿二叉樹，否則就構(gòu)造一個完全或近似完全二叉樹。該算法同樣需要用到類距離，可以用式(1)定義的類距離。構(gòu)造二叉樹的過程如下：如果有N個類別，將N個類置于集合S中，S1和S2為兩個空集合，Ns、Ns1、Ns2分
上面簡單介紹了兩種構(gòu)造二叉樹的方法，現(xiàn)在分析這兩種方法的優(yōu)缺點(diǎn)。第一種方法每次把與其他類距離之和最大的類分割出來，這樣分類的準(zhǔn)確性較高，但是，如果對于一個N類分類問題，其中有一個類別K，有可能在第一次就被分離出來，也有可能在第N-1次才被分離出來，這樣分類的效率就會比較低，而且訓(xùn)練時間也比較慢。第二種方法，采用完全或近似完全二叉樹，所以分類和訓(xùn)練的效率比較高，但是，在構(gòu)造這顆二叉樹時,每次都會把集合中的元素平均地分成兩類，這是不現(xiàn)實(shí)的，因?yàn)?，不能保證每個集合中的任一元素相對于所屬集合的相似度大于另一個集合的相似度，這樣分類的準(zhǔn)確性就會較低。分類的準(zhǔn)確性和分類的效率是一對矛盾，本文提出一種改進(jìn)算法，既考慮分離的準(zhǔn)確性，又能保證分類的效率。
3 改進(jìn)的二叉樹生成算法
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)造出半徑最小且盡可能包含該類所有樣本的球體,因此球體的半徑可以用來度量類樣本的分布。
(4)如果出現(xiàn)這種情況，說明類之間的相似度比較高，可以根據(jù)參考文獻(xiàn)[11]中提出的二叉樹生產(chǎn)算法，構(gòu)造一顆完全或近似完全二叉樹。結(jié)束。
(5)經(jīng)過步驟(3)，集合S1中的類別相似度比較高，可以根據(jù)參考文獻(xiàn)[11]中提出的二叉樹生產(chǎn)算法，以集合S1對應(yīng)的左子類作為頂層節(jié)點(diǎn)構(gòu)造一顆完全或近似完全二叉樹。
(6)如果Ns2=1，則結(jié)束。否則將集合S2中的類別號置入S，將得到的右子類作為頂層節(jié)點(diǎn)，回到步驟(2)。
經(jīng)過上面的步驟，可以構(gòu)造出一棵二叉樹，這個二叉樹可能是一個偏二叉樹，也可能是一個完全二叉樹，但是這兩種都是極端的情況。更多的情況下構(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)計算出的各類間的距離。由圖6中的數(shù)據(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三個類拆分成了EF和G，這顯然是不合理的，出現(xiàn)這種情況的原因是因?yàn)榇怂惴ㄒ髽?gòu)造一個完全二叉樹，左子樹和右子樹包含的類別個數(shù)只能相差0或1，所以有些相似度高的類就被拆分開了。這樣就會產(chǎn)生分類誤差，而且本實(shí)驗(yàn)在一開始就出現(xiàn)這種誤差會影響后面的分類結(jié)果，出現(xiàn)誤差累積的現(xiàn)象。而本文提出的算法，首先把相似度高的ABC先分割出來，再把EFG分割出來，最后把HI和D分開，這樣的結(jié)果符合樣本的真實(shí)分布，所以具有比較高的分類精度。
再把圖7(a)構(gòu)造的二叉樹與偏二叉樹作一下比較，偏二叉樹每次只有一個類被分離出來，所以訓(xùn)練速度比較慢，而且在后面分類時效率也比較低。而本文構(gòu)造的二叉樹每次會把相似度比較高的一些類先分出來，再將這些類構(gòu)造一個完全或近似完全二叉樹，所以訓(xùn)練的時間會比偏二叉樹低而分類的速度要更快。
本文結(jié)合偏二叉樹和完全二叉樹的構(gòu)造思想，提出了一種基于球結(jié)構(gòu)的二叉樹生產(chǎn)算法，利用該算法構(gòu)造出的二叉樹更接近樣本的真實(shí)分布，具有較高的分類精度和分類速度。但是算法還存在一些沒有解決的問題，例如：在算法中要求dij<?姿d，本文參數(shù)?姿取0.5，對于其他樣本?姿值可能會取不同的值，所以?姿的取值問題是今后研究的重點(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ī)工程與應(yīng)用,2005,41(7):24-26.
[7] 張貝貝，何中市.基于支持向量機(jī)數(shù)據(jù)描述算法的SVM多分類別新方法[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ī)械工程與自動化,2007(3):1-3.
[11] 謝志強(qiáng),高麗,楊靜.基于球結(jié)構(gòu)的完全二叉樹SVM多類分類算法[J].計算機(jī)應(yīng)用研究,2008，25(11):3268-
3274.