宋曉婉 黃樹成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

支持向量機(jī)（SVM）［1-2］是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的用于解決兩類分類問(wèn)題的機(jī)器學(xué)習(xí)方法，由VAPNIK 和CORTES 于1995 年提出。支持向量機(jī)（SVM）在解決小樣本、非線性及高維向量空間中有很好的性能。支持向量機(jī)的提出是為了解決兩類分類問(wèn)題，但是實(shí)際的應(yīng)用中，更多的是對(duì)多類分類問(wèn)題的解決，因此，如何運(yùn)用支持向量機(jī)解決多類分類問(wèn)題是當(dāng)前支持向量機(jī)研究的方向之一。SVM解決多類分類問(wèn)題的思路主要有以下兩種：第一種是一次性求解［3］，對(duì)多類分類問(wèn)題通過(guò)一個(gè)公式求解；第二種是構(gòu)造多個(gè)二值分類器，并根據(jù)不同的組合方式來(lái)解決不同的多類分類問(wèn)題。常用的多類分類支持向量機(jī)算法有：“一對(duì)一”、“一對(duì)多”、“有向無(wú)環(huán)圖”和“二叉樹”［4］等。根據(jù)研究表明，第二種方法總體性能較優(yōu)，能更好地解決多類分類問(wèn)題。

“一對(duì)一”算法［5］是在兩類樣本間訓(xùn)練出一個(gè)兩類分類器使其中一個(gè)類為正，另一個(gè)類為負(fù)。該算法訓(xùn)練速度快，但若某個(gè)子分類器存在誤差，就會(huì)導(dǎo)致整個(gè)分類器出現(xiàn)過(guò)學(xué)習(xí)，并且存在隨著類別的增加兩類分類器的數(shù)量急劇上升及不可分區(qū)域的缺點(diǎn)。

“一對(duì)多”算法［6］是在所有類樣本間訓(xùn)練出一個(gè)兩類分類器使其中一個(gè)類樣本為正，其余的類樣本為負(fù)。該算法所需的兩類分類器的數(shù)量較少，但由于在兩類分類器的訓(xùn)練過(guò)程中會(huì)涉及到全部的類樣本，因此分類速度較慢。

“二叉樹”算法是每次將最容易分離出來(lái)的類首先分離出來(lái)，以此類推直到只剩下一個(gè)類為止。二叉樹多類分類算法的分類速度會(huì)受到二叉樹結(jié)構(gòu)的影響，完全二叉樹的分類速度較高，因此構(gòu)造完全二叉樹結(jié)構(gòu)能大大提高二叉樹多類分類算法的分類速度。同時(shí)，“二叉樹”算法存在誤差累計(jì)，因此應(yīng)該先將最容易分離的類分離出來(lái)，減少誤差的積累。

“有向無(wú)環(huán)圖”算法［7-8］是在“一對(duì)一”算法的基礎(chǔ)上提出的一種新的學(xué)習(xí)架構(gòu)，它將多個(gè)“一對(duì)一”兩類分類器組合成多元分類器。該算法具有冗余性，不同的DAG 結(jié)構(gòu)會(huì)造成部分樣本的分類路徑的不同，從而對(duì)分類效果產(chǎn)生影響。

“二叉樹”算法在多類分類中有著很好的擴(kuò)展性，在多類分類算法中綜合性能較優(yōu)。但存在“誤差累計(jì)”及對(duì)二叉樹結(jié)構(gòu)依賴的缺點(diǎn)，因此本文主要針對(duì)二叉樹結(jié)構(gòu)及分類順序兩個(gè)方面改進(jìn)“二叉樹”算法。

2 基于二叉樹的SVM多類分類算法

2.1 二叉樹SVM算法介紹

二叉樹SVM 算法［9-10］主要思路：先將所有的類分成兩個(gè)子類，再將這兩個(gè)子類分別劃分成兩個(gè)次子類，以此類推，直到所有節(jié)點(diǎn)只包含一個(gè)類為止。二叉樹多類分類算法的分類速度會(huì)受到二叉樹結(jié)構(gòu)的影響，完全二叉樹的分類速度較高，因此構(gòu)造完全二叉樹結(jié)構(gòu)能大大提高二叉樹多類分類算法的分類速度?，F(xiàn)有的二叉樹多類分類算法只是隨機(jī)的生成二叉樹結(jié)構(gòu)，所以，合理的構(gòu)建二叉樹結(jié)構(gòu)是提高二叉樹SVM算法分類速度的關(guān)鍵。

二叉樹SVM 算法存在“誤差累計(jì)”的缺點(diǎn)，上層節(jié)點(diǎn)的分類結(jié)果對(duì)整個(gè)算法分類性能有著極大的影響，有效的分類順序是提高二叉樹SVM 分類精確度的關(guān)鍵。常用的二叉樹生成思路有以下兩種：1）根據(jù)類中樣本的分布情況進(jìn)行劃分，先將類中樣本分布范圍較廣的類分離出來(lái)，主要通過(guò)計(jì)算各類的超球體的體積來(lái)衡量類樣本分布情況，超球體體積越大，分布范圍越廣。2）根據(jù)兩類間的距離進(jìn)行相似度判斷，一般利用歐氏距離來(lái)計(jì)算兩類之間的距離，距離越小，相似度越大，應(yīng)該最先分離出來(lái)。

2.2 相關(guān)定義

超球體SVM［12～13］主要思想：在非線性系統(tǒng)中，通過(guò)映射函數(shù)將低維空間的特征向量映射到高維空間進(jìn)行類的劃分。在高維空間中，以盡可能小的超球體半徑包含更多的樣本，考慮到散落在球面附近的樣本，引入松弛變量§m，i，并計(jì)算覆蓋樣本的最小超球體的半徑及球心。

定義2：歐氏距離［14］。也稱歐幾里得距離，主要用于計(jì)算兩點(diǎn)之間的真實(shí)距離，m 維空間中點(diǎn)i和j的距離為

在判別兩類之間的分離程度時(shí)，可以使用歐氏距離法、超球體SVM 或者兩種方法的結(jié)合，但都不能準(zhǔn)確地反映類的分布情況。單獨(dú)使用歐氏距離法進(jìn)行類的相似度的判斷沒(méi)有考慮類中樣本的分布情況，單一使用超球體SVM 方法只是考慮類的樣本的分布情況卻忽略類間的相似度的判斷。采用歐氏距離和超球體SVM 方法結(jié)合進(jìn)行類的相似度判斷在精確度上有了一定的提升，但是依然存在一定的問(wèn)題。為了解決這一問(wèn)題，本文對(duì)類內(nèi)和類間相似方向進(jìn)行了改進(jìn)提出了類間相似度量數(shù)的概念。同時(shí)，提出了一種二叉樹結(jié)構(gòu)生成算法，使二叉樹在總體上為偏二叉樹，在局部為完全二叉樹或者近似完全二叉樹，從而提高二叉樹分類效率及分類精度。

3 改進(jìn)的二叉樹SVM多類分類算法

3.1 相關(guān)定義

其中，xˉ是根據(jù)文獻(xiàn)［15］中式（10）、（15）得到的每類樣本所在最小超球體的中心。

定義4：類間相似度量數(shù)。假設(shè)類i 和類j 的最小超球體半徑分別為ri和rj，那么類i 和類j 的類間相似度量數(shù)為

其中，|di，j|為從類i 中心向量到類j 中心向量的歐氏距離，C 為參數(shù)值，其值根據(jù)樣本的分布情況進(jìn)行調(diào)整，默認(rèn)情況下取值1，F(xiàn)i，j越大越不相似，應(yīng)該最先分離出來(lái)。

對(duì)圖1 中的兩個(gè)圖的情況進(jìn)行觀察可以發(fā)現(xiàn)：左圖的類間距較小，但類之間的分布較遠(yuǎn)；而右圖的類間距較大，但類之間的分布較近。采用距離或類間相似方向來(lái)進(jìn)行兩類之間的相似度判斷，都不能達(dá)到比較好的效果，而采用本文提出的類間相似度量數(shù)能在類間距和類的分布情況兩種因素上綜合考慮，從而獲得更有效的分類順序，提高分類精確度。

圖1 左右兩圖表示兩類間距離及類間相似方向

3.2 算法步驟

定義類平均類間相似度量數(shù)：

1）對(duì)于N 類問(wèn)題，定義集合G、G1、G2、G3、G4和G5，NG、NG1、NG2、NG3、NG4、NG5（NG、NG1、NG2、NG3、NG4、NG5分別表示集合G、G1、G2、G3、G4和G5中的類編號(hào)的個(gè)數(shù)）。首先對(duì)所有類樣本從編號(hào)1 到編號(hào)N 進(jìn)行編號(hào)，并放到集合G 中。然后根據(jù)式（1）～（3）計(jì)算所有類樣本的類間相似度量數(shù)Fi，j（i=1，2，…N，j=1，2，…N，i≠j）和Fˉi,j。

2）如若NG=2，那么把類編號(hào)較小的類作為左子樹，類編號(hào)較大的類作為右子樹，算法結(jié)束。

3）根據(jù)式（1）～（2）計(jì)算集合G中的每一個(gè)類到其他類的Fi，j，并統(tǒng)計(jì)每一個(gè)類的Fi，j小于 λFˉi,j的個(gè)數(shù)（λ根據(jù)樣本分布情況進(jìn)行值的調(diào)整，是一個(gè)大于零的參數(shù)），記作Sumi（i=1，2，…N）。

4）找出最大的Sumi，如果存在相同的Sumi，則選擇類編號(hào)較小的類樣本。如果Sumi=NG，則將集合G 中的所有類編號(hào)放到集合G3中，轉(zhuǎn)5）。否則，將類編號(hào)i 放到集合G1中，并將滿足Fi,j＜ λFˉi,j(j=1,2,…N,i ≠j)的類編號(hào)放到集合G1中作為二叉樹的左子樹，將剩下的類編號(hào)放到集合G2中作為二叉樹的右子樹，并將集合G1中的所有類編號(hào)放到集合G3中，轉(zhuǎn)5）。

5）若NG3=2，那么把類編號(hào)較小的類作為左子樹，類編號(hào)較大的類作為右子樹，算法結(jié)束。

6）找出Fi，j值最小的兩個(gè)類i 和j，并將它們按照類編號(hào)的大小放到集合G4中。在剩下的類中找出與集合G4中各類的Fi，j和最大的類標(biāo)號(hào)，并將其放到集合G5中，令G3=G3-（G4∪G5）。若NG3=0 則轉(zhuǎn)8）。

7）計(jì)算集合G3中的各類到集合G5的各類的Fi，j和，找出最小Fi，j和的類編號(hào)，并將其放到集合G5中，令G3=G3-（G4∪G5）。若NG3=0則轉(zhuǎn)8）。否則，若NG3=1，計(jì)算集合G3中的類與集合G4和G5中各類的Fi，j和，將其放到Fi，j和較小的集合，比較NG4和NG5大小，若NG4＞NG5，則將集合G4和G5中的類編號(hào)進(jìn)行交換，轉(zhuǎn)8）。否則，計(jì)算集合G3中的各類與集合G4中各類的Fi，j和，找出最小Fi，j和的類編號(hào)，并將其放到集合G4中，令G3=G3-（G4∪G5）。

8）重復(fù)7）。

9）集合G4和G5分別作為二叉樹的左右子樹，并將左子樹進(jìn)一步劃分為兩個(gè)次子類，令G3=G4，轉(zhuǎn)5）。

10）對(duì)右子樹劃分為兩個(gè)次子類，令G3=G5，轉(zhuǎn)5）。

11）若NG2=1則算法結(jié)束，否則將集合G2中的類編號(hào)放到集合G中，轉(zhuǎn)2）。

經(jīng)過(guò)以上實(shí)驗(yàn)步驟，可以使更容易分離出來(lái)的類首先分離出來(lái)，提高分類精確度，同時(shí)使生成的二叉樹結(jié)構(gòu)根據(jù)樣本數(shù)據(jù)分布情況的變化而變化，在總體上是一顆偏二叉樹結(jié)構(gòu)，局部是一顆完全或近似完全二叉樹結(jié)構(gòu)，具有較高的分類速度。

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)采用的數(shù)據(jù)集包括UCI 數(shù)據(jù)庫(kù)中的Glass Identification 和Optdigits，以 及Statlog 數(shù) 據(jù) 庫(kù) 中 的Satimage 和Letter，實(shí)驗(yàn)數(shù)據(jù)集信息見(jiàn)表1。算法采用Matlab 和VC++混合編程，并且是在LIBSVM 工具包的基礎(chǔ)上進(jìn)行修改的。實(shí)驗(yàn)采用RBF核函數(shù)，固定的最優(yōu)參數(shù)（C，r）是經(jīng)過(guò)網(wǎng)格搜索法得到的推廣精度最高的C和r參數(shù)。為了證明本文所提出的算法具有較好的分類性能，選取一對(duì)多SVM（One-versus-rest，OVR）和一對(duì)一SVM（One-versus-one，OVO）在四個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見(jiàn)表2和表3。

表1 數(shù)據(jù)集信息表

表2 分類速度比較表/s

表3 分類精度比較表/%

通過(guò)以上實(shí)驗(yàn)得出結(jié)論：在相同的測(cè)試條件下，不同的分類算法會(huì)得到不同的分類結(jié)果。由表2 可知，本文算法的分類速度較OVR 和OVO 算法快，原因是：二叉樹多類分類算法構(gòu)造的兩類分類器較少，且在訓(xùn)練過(guò)程中所涉及的樣本數(shù)量也逐漸減少。同時(shí)，本文算法使生成的二叉樹結(jié)構(gòu)總體上是一顆偏二叉樹，局部是一顆完全或近似完全二叉樹結(jié)構(gòu)，大大減少所需計(jì)算的二值分類器數(shù)量，進(jìn)一步提升分類速度。通過(guò)表3 可以看出，本文算法在分類精度方面也有了一定的提升，文中提出的類間相似度量數(shù)能更準(zhǔn)確地將更容易分離出的類分離出來(lái)。

5 結(jié)語(yǔ)

本文介紹了當(dāng)前支持向量機(jī)解決多類分類問(wèn)題的一般思路及二叉樹SVM 多類分類算法的原理，并分析現(xiàn)有二叉樹SVM 存在的問(wèn)題。并針對(duì)存在的問(wèn)題提出了一種改進(jìn)的二叉樹SVM 多類分類算法，該算法能大大減少“誤差累計(jì)”，提高分類精度。同時(shí)，使生成的二叉樹總體上是一顆偏二叉樹，局部是一顆完全或近似完全二叉樹結(jié)構(gòu)，提高分類速度。通過(guò)在四個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文算法在分類速度及精度上都有了一定的提升，具有一定的可行性。