基于類間相似方向數(shù)的二叉樹支持向量機

王建建，何楓

（北京科技大學東凌經(jīng)濟管理學院，北京100083）

0 引言

支持向量機（SVM）是在統(tǒng)計學的理論上發(fā)展的一種新的機器學習方法[1]，起初是針對二分類問題而提出的，目前的研究重點是如何將其推廣到多分類問題。目前解決該問題的方法主要分為兩類：第一類是直接構(gòu)造多分類問題的支持向量機模型，在一個最優(yōu)化模型中求解多個分類面的參數(shù)，來“一次性”的實現(xiàn)求解多分類[2]。第二類是間接法，將多分類問題轉(zhuǎn)化成二分類問題，即把多個不同的二分類器合并成一個多分類器。這類方法主要有四種：一對多方法（1-a-r）、一對一方法（1-a-1）、DDAG方法（決策導向非循環(huán)圖法）和二叉樹分類法。其中“一對多”方法[3]得到了廣泛的應用，原因是其簡單易實現(xiàn)，但也存在許多缺點，該方法會造成訓練集不均勻，對小樣本的類別識別精度低，并且存在不可識別區(qū)域；“一對一”方法[4]存在不可識別域，并且需要建立較多的支持向量機，對于很多類別的分類問題，導致訓練時間加長，分類速度降低，且類別數(shù)的擴大引起預測函數(shù)增加，導致預測速度變慢；DDAG法采用了有向無環(huán)圖的組合策略[5]，分類時雖不用經(jīng)過所有的分類器，但增加了支持向量機的數(shù)目，隨類別數(shù)的增加，訓練時間也會很長，速度較低。

基于二叉樹支持向量機[6]的分類方法避免上述問題，并解決了以下三個問題：（1）訓練一個k分類問題，只要訓練二分類向量機k-1個即可；（2）消除了以上方法存在的不可識別的區(qū)域；（3）與“一對多”的方法相比，訓練時總的訓練樣本數(shù)目減少了很多。

采用二叉樹的方法，首先，其結(jié)構(gòu)較大的影響了整體的分類精度。不同結(jié)構(gòu)的二叉樹，由于分類順序不同導致節(jié)點處的分類精度不同，進而影響最終的分類結(jié)果。其次，“誤差累積”的影響，使得錯誤分類發(fā)生在越靠近根節(jié)點的地方，從而分類性能變差，因此在二叉樹的結(jié)構(gòu)產(chǎn)生過程中，應確保分離出最容易分離出來的一類。為解決這一問題，目前國內(nèi)外研究二叉樹生成的算法已經(jīng)有很多[7-11]。本文在已有研究的基礎上提出了一種類間相似方向數(shù)來作為生成偏二叉樹支持向量機的準則。采用圖示法和數(shù)值實驗表明本文的方法具有一定的優(yōu)越性。

1 基于類間相似方向數(shù)的二叉樹多類分類算法

1.1 相關(guān)定義

定義1：中心向量[11]。一個類別的中心即為該類別所有訓練樣本向量的平均值，中心向量為：

為了研究三分類問題的分類順序影響分類精度的問題，在文獻[11]提出的類間相似方向的基礎上，本文改進了類內(nèi)和類間相似方向，再考慮到類間的距離，提出了類間相似方向數(shù)的相關(guān)定義如下：

令類i的類內(nèi)相似方向為：

定義3：改進的類間相似方向。用Pi，j表示第i類訓練樣本集Si與第j類訓練樣本集Sj的相似方向，用di，j（dj，i）表示由類別i中心到類別j中心的向量（表示由類別j中心到類別i中心的向量），令：

此時當Pi，j=qi+qj取得-2時，即qi，qj均取-1時，可使得i，j兩類最不相似（即類間分離性最大），當Pi，j越小時也就是越容易分離,如圖1所示。

圖1 改進的類間相似方向

定義4：類間相似方向數(shù)。定義類別i和類別j的類半徑為ri，rj（即訓練樣本中距離中心點最遠的點與中心之間的距離），定義類間相似方向數(shù)為：|di，j|為類中心距離，即向量di，j的長度，C＞0為合適的參數(shù)，一般取1即可，可根據(jù)樣本點分布情況調(diào)整C的值，越大則越容易分離。

1.2 圖示法比較本文方法與其他二叉樹改進方法的優(yōu)勢

在判別兩類之間的分離程度時，歐式距離是普遍使用的分離度，但距離并不能準確反映類的分布情況，如圖2所示。

圖2 中心距離相等的分離度的比較

圖2中左右兩圖的兩類別之間中心距離是相同的，顯然右圖兩個類比左圖的兩個類更容易分開，所以這種情況下只依賴距離不能做出正確的判斷。而按照本文定義的類間相似方向數(shù)=||di，j-C(qiri+qjrj)，則彌補了只依照距離的這方面的不足，能判斷出右邊的兩個類更容易分離。

按照文獻[11]提出的類間相似方向，不能正確的反映類與類間的分離程度，如圖3所示。

圖3 左右兩圖表示兩類間方向均相反的情況

圖3中左圖的兩個類比右圖的兩個類更容易分開，但按照文獻[11]的方法判斷時把方向相反的即類間相似方向夾角余弦為-1時是最好分的，當分布情況類似為左圖時，采用其方法可以很好地將兩類分離出來，若分布為右圖情況時，其類間相似方向夾角余弦也是-1，卻不能采用這類方法將兩類更好地分開。因此本文重新定義了新的類間相似方向數(shù)，避免了此種錯誤，按照本文的方法能判斷出左邊的兩類更容易分離。

圖4 左右兩圖表示兩類間距離與類間相似方向的情況

比較圖4中左右兩圖的情況可以發(fā)現(xiàn)，右圖的類間距離雖然比左圖的距離大，但是類與類之間的分布比較近，不容易分離；若只是按照距離的分離度來分類則應該先將右圖的這類情況先分，但是按照距離來分類將不能更好地反映類之間的分布，當這種情況出現(xiàn)時，應按照距離并結(jié)合類間相似方向的方法來判斷分類順序，可避免這種錯誤的分類。

當上述圖2至圖4的情況出現(xiàn)時，單獨靠距離或者類間相似方向不能較好地判別出正確的分類順序，因此采用本文提出的方法，能更好地反映類之間的分布，確定出更加有效的分類順序，從而有利于分類。通過以上圖示之間比較可見，采用本文提出的類間相似方向數(shù)的二叉樹支持向量機具有一定優(yōu)勢。

1.3 訓練時間復雜度分析

引理1：訓練時間復雜度的定律[12]

支持向量機求解的實質(zhì)是二次規(guī)劃問題，其訓練時間隨著樣本數(shù)量的增大呈超線性關(guān)系，由如下能量守恒定律[12]描述：

式中，T為訓練時間，γ為能量指數(shù)，m為樣本的規(guī)模，c為比例常數(shù)。并且當采取SMO分析訓練算法時，γ≈2。

假設訓練樣本集中共有m個樣本點，有N類樣本，每一類的數(shù)目相同，均為個，有引理1可得：

（1）一對多方法（1-a-r）需要構(gòu)造N個分類器，每個及節(jié)點的樣本分類數(shù)目為m，則整個分類器所需要的總的訓練時間為：

其中當γ=2時，T1-a-r=cNm2。

（2）一對一方法（1-a-1）需要構(gòu)造N(N-1) 2個分類器，每個及節(jié)點的樣本分類數(shù)目為，則整個分類器所需要的總的訓練時間為：

其中當γ=2時，T1-a-1=2cm2。DDAG方法進行訓練分類時與一對一的方法相同，因此分類器所需要的訓練時間與一對一方法（1-a-1）一樣，即TDDAG=T1-a-1。

（3）本文二叉樹方法需要構(gòu)造N-1個分類器，每個及節(jié)點的樣本分類數(shù)目為，其中i為分類的次數(shù)，則整個分類器所需要的總的訓練時間為：

其中當γ=2時，TBT-SVM≈cNm23。

由以上分析可以得出，在分類的類別數(shù)目N較大時，本文二叉樹算法的訓練時間比一對一的時間要長，但是時間遠小于一對多的情況。本文采用的實驗數(shù)據(jù)類別為3類或4類，計算的時間也比一對一的要短。

1.4 以類間相似方向數(shù)作為生成二叉樹支持向量機的多分類算法

步驟2：對于第i類，存在k-1個與其他各類的類間相似方向數(shù)，將這k-1個數(shù)按照從小到大的順序排列起來，類似于第i類，計算(j=1，2，...，k，j≠i)按照由小到大的順序進行排列為≤≤...≤。

步驟4：采用二分類的SVM算法建立二叉樹各節(jié)點的最優(yōu)超平面。根據(jù)類別標號的排序，從訓練樣本集中選第n1類樣本為正類樣本，其他剩余幾類樣本為負類樣本，在根節(jié)點處建立第1個子分類器，并將第n1類樣本刪除，然后將第n2類樣本作為正類樣本在第二個節(jié)點處，其他為負類樣本，構(gòu)造第2個二值SVM子分類器，依次迭代之后，最終可得到基于二叉樹的多類分類模型，如圖5所示。

圖5 生成二叉樹的結(jié)構(gòu)

步驟5：算法結(jié)束。

針對多分類問題，根據(jù)本算法由Matlab編程可以判別哪一類最先分出來能達到最優(yōu)，給出合理的分類順序，減少“誤差積累”效應，使得最終的分類精度達到較高水平。

2 實驗仿真與結(jié)果分析

2.1 人工模擬實驗結(jié)果與分析

實驗中所有訓練樣本與測試樣本是在數(shù)據(jù)總量上隨機選取，因此采用三倍交叉驗證方法來進行實驗，選取實驗結(jié)果的平均值作為最終的實驗結(jié)果。其中計算SVM的方法是采用工具箱OUS-SVM3.0，核函數(shù)則選取高斯徑向基核函數(shù)，參數(shù)的選擇固定。為驗證本文提出的類間相似方向數(shù)生成二叉樹結(jié)構(gòu)的模型，隨機生成一組模擬人工數(shù)據(jù)組，實驗時其中的懲罰參數(shù)C采取1000，r取值為3。數(shù)據(jù)樣本為600個，被分成三類，每類共有200個，如圖6所示。（“×”記為1類，“+”記為2類，“○”記為3類）

圖6 人工模擬數(shù)據(jù)集

隨機選出每類當中的一半作為訓練樣本，如圖7所示。

圖7 人工模擬數(shù)據(jù)訓練樣本集

進而訓練剩余兩類會得到第二個分類模型，如下頁圖9所示。

將測試集代入第一個分類模型判斷其屬性，把不屬于第三類的點再代入第二個分類模型判斷其屬性，經(jīng)過這兩個分類模型得到測試集的屬性，并與原本數(shù)據(jù)的真實屬性相比較，得到錯分點的個數(shù)為48個，求得分類正確率84%。本文方法與一對一和一對多及其他二叉樹的方法進行比較如表1所示的逼近精度及訓練時間。

表1 對模擬數(shù)據(jù)集的各類方法的比較

圖8 人工模擬數(shù)據(jù)訓練樣本集第一次分類

圖9 人工模擬數(shù)據(jù)訓練樣本集第二次分類

2.2 UCI數(shù)據(jù)集上的實驗結(jié)果與分析

本文所用的實驗數(shù)據(jù)均來自UCI數(shù)據(jù)庫，所有的樣本個數(shù)、屬性及類別均為已知的，所需要的實驗數(shù)據(jù)如表2所示。其中iris（鳶尾花植物）的數(shù)據(jù)集共有150個樣本，每個樣本有4個特征屬性，分別為：萼片長度和寬度，花瓣長度和寬度，數(shù)據(jù)被分成三類，分別為I:setosa,II:versicolor和III:virginica，每類樣本是50個。Shuttle（航天飛機）的數(shù)據(jù)集有58000個樣本，每個樣本有9個屬性，分別為時間（time）、拉德流（Rad Flow）、Fpv關(guān)閉（Fpv Close）、Fpv開放（Fpv Open）、高（High）、支路（Bypass）、Bpv關(guān)閉（Bpv Close）、Bpv開放（Bpv Open）、類別屬性(Class Attribute)，由于其中的2、3、6、7類別個數(shù)較少，為了試驗簡便，因此實驗時將這幾類合并為一類，從而將樣本分為了四類。Yeast（酵母）數(shù)據(jù)集有CYT,ERL,EXC,MEI,ME2，ME3,MIT,NUC,POX,UAX 10個類別,每個樣本有8個屬性，分為mcg(信號序列識別麥吉奧赫的方法)、gvh(信號序列識別馮海涅的方法)、alm（Alom預測得分）、mit（判別線非線粒體蛋白質(zhì)的N端氨基酸含量得分）、erl(“HDEL”子串作為某信號保留在內(nèi)質(zhì)網(wǎng)腔的狀態(tài)，二進制屬性)、pox(定位末端的過氧化物酶體信號)、vac(評分判別分析的氨基酸含量的液泡和胞外蛋白)、nuc(核與非核蛋白核定位信號判別分析)，但是類別VAC,ERL,POX,EXC的個別屬性未知且樣本個數(shù)極少，因此把這些樣本點刪除，并將ME1,ME2,ME3這三類樣本數(shù)較少的標記為一類，從而原始數(shù)據(jù)的1481個樣本變?yōu)?394個樣本點，由10類刪減合并成4類問題。Auto_mpg（車輛MPG）數(shù)據(jù)集原始數(shù)據(jù)有406個樣本點，刪掉其中的個別屬性未知的某些樣本點，數(shù)據(jù)集變?yōu)?92個，數(shù)據(jù)樣本分成三類，每個樣本點共有7個屬性，分別為cylinders(汽缸)、displacement（排量）、horsepower（馬力）、weight（體重）、acceleration（加速度）、model year（年份）、origin（產(chǎn)地）。Wine數(shù)據(jù)集共有178個數(shù)據(jù)點，分為1、2、3類,對應的樣本點的個數(shù)分別為59、71、48個，每個樣本點有13個屬性特征,如alcohol（酒精）、malic acid（蘋果酸）、ash（火山灰）、alcalinity of ash（灰分堿度）、magnesium（鎂）等13個屬性。

表2 實驗所用的UCI數(shù)據(jù)集

數(shù)據(jù)樣本進行實驗時，為了避免數(shù)據(jù)中屬性值范圍大的比屬性范圍小的更具有影響力，故對所有樣本數(shù)據(jù)進行歸一化到[-1,1]上。實驗時，采用RBF核函數(shù)，文中每一組實驗所固定的最優(yōu)參數(shù)(C，r)是經(jīng)過網(wǎng)格搜索法來得到的推廣精度最高的C與r參數(shù)。計算SVM的方法是采用工具箱OUS-SVM3.0，選用MATLAB工具編程來實現(xiàn)本文所有的算法，利用式（1）至式（7）給出分類順序，通過SVM用Matlab編程計算可得數(shù)據(jù)實驗結(jié)果如表3所示的逼近精度及訓練時間。

表3 對各個數(shù)據(jù)集的各類方法的比較

實驗結(jié)果表明，由表2、表3結(jié)果分析可以得出采用本文方法與按距離生成二叉樹的方法、一對一、一對多方法比較可知，本文方法得到的分類精度相對較高。與一對多方法相比，在分類精度接近的同時，明顯分類速度要比一對多方法快出很多。因此進行多分類實驗時，與其他方法相比，采用類間相似方向數(shù)來生成偏二叉樹支持向量機能夠使最容易分離出來的類最早分離出來，使得分類精度和分類效率都得到一定的提高。最后的數(shù)值實驗驗證了基于本文方法的二叉樹支持向量分類機可以取得更優(yōu)的分類精度。

3 結(jié)論

對于多分類當中的三分類問題，本文主要采用多分類的方法之一的二叉樹支持向量機的方法研究，其分類效果與二叉樹結(jié)構(gòu)有很大關(guān)系。針對二叉樹結(jié)構(gòu)的分類順序影響分類精度的問題，改進一種類間相似方向，并結(jié)合距離，提出了類間相似方向數(shù)作為二叉樹結(jié)構(gòu)生成的多分類方法，彌補了距離不能很好地反映類分離度的缺陷。采用本文提出的生成二叉樹結(jié)構(gòu)的方法進行數(shù)據(jù)實驗分析，實驗結(jié)果證明該方法具有較高的分類精度和分類效率。

[1] Vapnik V N.The Nature of Statistical Learning Theory[M]NewYork:Springer Verlag,1995.

[2] Madzarov G,Gjorgjevikj D,Chorbev I.A Multi-class SVM Classifier Utilizing Binary Decision Tree[J].Informatica,2009,33(2).

[3] Hill S I,Doucet A.A Framework for Kernel-Based Multi-Category Classification[J].Artif.Intell.Res.(JAIR),2007,(30).

[4] He X,Wang Z,Jin C,et al.A Simplified Multi-Class Support Vector Machine With Reduced Dual Optimization[J].Pattern Recognition Letters,2012,33(1).

[5] Martínez J,Iglesias C,Matías J M,et al.Solving the Slate Tile Classifi?cation Problem Using a DAGSVM Multiclassification Algorithm Based on SVM binary Classifiers With A One-Versus-All Approach[J].Applied Mathematics and Computation,2014,(230).

[6] Du P,Tan K,Xing X.A Novel Binary Tree Support Vector Machine for Hyperspectral Remote Sensing Image Classification[J].Optics Communications,2012,285(13).

[7] Cheong S,Oh S H,Lee S Y.Support Vector Machines With Binary Tree Architecture for Multi-Class Classification[J].Neural Informa?tion Processing-Letters and Reviews,2004,2(3).

[8] 孟媛媛，劉希玉.一種新的基于二叉樹的SVM多類分類分法[J].計算機應用，2005,25（11）.

[9] 唐發(fā)明，王仲東，陳綿云.支持向量機多類分類算法研究[J].控制與決策，2005,20（7）.

[10] 唐發(fā)明，王仲東，陳綿云.一種新的二叉樹多類支持向量機算法[J].計算機工程與應用，2005,20（7）.

[11] 汪洋,陳友利,劉軍等.基于相似方向的二叉樹支持向量機多類分類算[J].四川師范大學學報:自然科學版,2008,31(6).

[12] Platt J C,Cristianini N,Shawe-Taylor J.Large Margin DAGs for Multiclass Classification[C].nips,1999,(12).