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

王建建，何楓

（北京科技大學東凌經濟管理學院，北京100083）

0 引言

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

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

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

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

1.1 相關定義

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 訓練時間復雜度分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 生成二叉樹的結構

步驟5：算法結束。

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

2 實驗仿真與結果分析

2.1 人工模擬實驗結果與分析

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

圖6 人工模擬數據集

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

圖7 人工模擬數據訓練樣本集

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

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

表1 對模擬數據集的各類方法的比較

圖8 人工模擬數據訓練樣本集第一次分類

圖9 人工模擬數據訓練樣本集第二次分類

2.2 UCI數據集上的實驗結果與分析

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

表2 實驗所用的UCI數據集

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

表3 對各個數據集的各類方法的比較

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

3 結論

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

[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] 唐發明，王仲東，陳綿云.支持向量機多類分類算法研究[J].控制與決策，2005,20（7）.

[10] 唐發明，王仲東，陳綿云.一種新的二叉樹多類支持向量機算法[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).