多類SVM分類算法的研究

郭顯娥,武 偉,劉春貴,張景安

(山西大同大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西大同 037009)

機(jī)器學(xué)習(xí)從早期Fisher分類器到人工神經(jīng)網(wǎng)絡(luò)都是基于傳統(tǒng)的經(jīng)驗(yàn)風(fēng)險最小化原則進(jìn)行的，即采用在訓(xùn)練樣本集上的學(xué)習(xí)能力，作為衡量一個學(xué)習(xí)機(jī)性能好壞的標(biāo)準(zhǔn).這種機(jī)器學(xué)習(xí)存在著過擬合問題，使得學(xué)習(xí)機(jī)的泛化能力差.支持向量機(jī)(SVM)是一種建立在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)之上的機(jī)器學(xué)習(xí)方法,其最大的特點(diǎn)是根據(jù)Vapnik結(jié)構(gòu)風(fēng)險最小化原則[1],即在函數(shù)復(fù)雜性和樣本復(fù)雜性之間進(jìn)行折中，盡量提高學(xué)習(xí)機(jī)的泛化能力，具有優(yōu)良的分類性能.

支持向量機(jī)在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出了許多特有的優(yōu)勢，基于支持向量的分類越來越受到廣泛的關(guān)注與重視.支持向量機(jī)的出現(xiàn)最初是為了解決兩類模式識別問題.當(dāng)它在兩類問題中展現(xiàn)出其卓越的性能之后，人們自然而然地想到了利用它來解決機(jī)器學(xué)習(xí)等領(lǐng)域中的其它難題.對于我們所處的客觀世界來說，許多問題所需要面對的事物類別遠(yuǎn)遠(yuǎn)不止兩類，例如語音識別，手寫體數(shù)字識別問題等.因此如何將SVM方法有效的應(yīng)用于多類分類問題迅速成為SVM研究熱點(diǎn).針對多類分類問題的經(jīng)典SVM算法主要有一對一方法(1-vs-1)，一對多方法(1-vs-all)，有向無環(huán)圖方法(DAG-SVM)和二叉樹法(BT-SVM)等幾種.下面將對這些主要的多類SVM算法以及優(yōu)缺點(diǎn)進(jìn)行全面的討論.

1 支持向量機(jī)原理[2]

1.1 線性可分問題

SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來的，所謂最優(yōu)分類面就是要求分類面不但能將兩類樣本正確分開 (訓(xùn)練錯誤率為0)，而且使分類間隔最大.設(shè)有n個樣本xi及其所屬類別yi表示為:

超平面W·X+b=0方程，能將兩類樣本正確區(qū)分，并使分類間隔最大的優(yōu)化問題可表示為在式(1)的約束下求式(2)的最小值.

滿足式(1)條件且使｜w｜2最小的分類面就是最優(yōu)分類面.過兩類樣本中離分類面最近的點(diǎn)且平行于最優(yōu)分類面的超平面上的訓(xùn)練樣本就是式(1)中使等號成立的那些樣本，它們叫做支持向量(Support Vectors).因?yàn)樗鼈冎瘟俗顑?yōu)分類面.

1.2 線性不可分問題

最優(yōu)分類面是在線性可分的前提下討論的，在線性不可分的情況下，就是某些訓(xùn)練樣本不能滿足式 (1)的條件，因此可以在條件中增加一個松弛項(xiàng)ξi≥0(i=1,…,n)，此時約束條件式(1)變?yōu)槭?3)：

尋優(yōu)目標(biāo)函數(shù)式(2)變?yōu)槭?4)：

(4)式中的C為某個指定的常數(shù)，起到對錯分樣本懲罰程度控制的作用，實(shí)現(xiàn)在錯分樣本的比例和算法復(fù)雜程度之間的“折衷”．該問題可轉(zhuǎn)化為其對偶問題．即在式(5)和式(6)的約束條件下求式(7)的最大值．

這是一個不等式約束下二次函數(shù)極值問題，存在唯一解．求解出上述各系數(shù)α、W、b對應(yīng)的最優(yōu)解α*、W*、b*后，得到最優(yōu)分類函數(shù)為式(8)．

其中：sgn()為符號函數(shù)，b*為分類的域值．

1.3 非線性問題

現(xiàn)實(shí)問題幾乎都是非線性可分的，對非線性問題，可以通過非線性變換轉(zhuǎn)化為某個高維空間中的線性問題[3]，在變換空間求最優(yōu)分類面．根據(jù)泛函的有關(guān)理論，只要一種核函數(shù)k(x,xi)滿足Mercer條件，它就對應(yīng)某一變換空間中的內(nèi)積．因此，在最優(yōu)分類面中用適當(dāng)?shù)膬?nèi)積核函數(shù)k(x,xi)就可以實(shí)現(xiàn)從低維空間向高維空間的映射，從而實(shí)現(xiàn)某一非線性變換后的線性分類，而計算復(fù)雜度卻沒有增加．

2 多類SVM分類算法分析與研究

2.1 一對一支持向量機(jī)(1-vs-1 SVM)

一對一支持向量機(jī)(1－vs－1 SVM)[2]是利用兩類SVM算法在每兩類不同的訓(xùn)練樣本之間都構(gòu)造一個最優(yōu)決策面．如果面對的是一個k類問題，那么這種方法需要構(gòu)造k(k－1)/2個分類平面(k＞2)．這種方法的本質(zhì)與兩類SVM并沒有區(qū)別，它相當(dāng)于將多類問題轉(zhuǎn)化為多個兩類問題來求解．具體構(gòu)造分類平面的方法如下：

從樣本集中取出所有滿足yi=s與yi=t(其中1≤s,t≤k,s≠t)通過兩類SVM算法構(gòu)造最優(yōu)決策函數(shù)：

用同樣的方法對k類樣本中的每一對構(gòu)造一個決策函數(shù)，又由于fst(x)=－fts(x)，容易知道一個k類問題需要k(k－1)/2個分類平面．

根據(jù)經(jīng)驗(yàn)樣本集構(gòu)造出決策函數(shù)以后，接下來的問題是如何對未知樣本進(jìn)行準(zhǔn)確的預(yù)測．通常的辦法是采取投票機(jī)制：給定一個測試樣本x，為了判定它屬于哪一類，該機(jī)制必須綜合考慮上述所有k(k－1)/2個決策函數(shù)對x所屬類別的判定：有一個決策函數(shù)判定x屬于第s類,則意味著第s類獲得了一票，最后得票數(shù)最多的類別就是最終x所屬的類別．

1－vs－1 SVM方法，優(yōu)點(diǎn)在于每次投入訓(xùn)練的樣本相對較少，因此單個決策面的訓(xùn)練速度較快，同時精度也較高．但是由于k類問題需要訓(xùn)練k(k－1)/2個決策面，當(dāng)k較大的時候決策面的總數(shù)將過多，因此會影響后面的預(yù)測速度．這是一個有待改進(jìn)的地方．在投票機(jī)制方面，如果獲得的最高票數(shù)的類別多于一類時，將產(chǎn)生不確定區(qū)域；另外在采用該機(jī)制的時候，如果某些類別的得票數(shù)已經(jīng)使它們不可能成為最終的獲勝者，那么可以考慮不再計算以這些類中任意兩類為樣本而產(chǎn)生的決策函數(shù)，以此來減小計算復(fù)雜度．

2.2 一對多支持向量機(jī)(1-vs-all SVM)

一對多支持向量機(jī)(1－vs－all SVM)[4]是在一類樣本與剩余的多類樣本之間構(gòu)造決策平面，從而達(dá)到多類識別的目的．這種方法只需要在每一類樣本和對應(yīng)的剩余樣本之間產(chǎn)生一個最優(yōu)決策面，而不用在兩兩之間都進(jìn)行分類．因此如果仍然是一個k類問題的話，那么該方法僅需要構(gòu)造k個分類平面(k＞2)．該方法其實(shí)也可以認(rèn)為是兩類SVM方法的推廣．實(shí)際上它是將剩余的多類看成一個整體，然后進(jìn)行k次兩類識別．具體方法如下：

假定將第j類樣本看作正類 (j=1,2,…,k)，而將其他k－1類樣本看作負(fù)類，通過兩類SVM方法求出一個決策函數(shù)這樣的決策函數(shù)fj(x)一共有k個．給定一個測試輸入x，將其分別帶入k個決策函數(shù)并求出函數(shù)值，若在k個fj(x)中fs(x)最大，則判定樣本x屬于第s類．

1－vs－all SVM 方法和 1－vs－1 SVM 相比，構(gòu)造的決策平面數(shù)大大減少，因此在類別數(shù)目k較大時，其預(yù)測速度將比1－vs－1 SVM方法快．但是由于它每次構(gòu)造決策平面的時候都需要用上全部的樣本集，因此它在訓(xùn)練上花的時間并不比1－vs－1 SVM少.同時由于訓(xùn)練的時候總是將剩余的多類看作一類，因此正類和負(fù)類在訓(xùn)練樣本的數(shù)目上極不平衡，這很可能影響到預(yù)測時的精度.另外，與1-vs-1方法類似，當(dāng)同時有幾個j能取到相同的最大值fj(x)時，將產(chǎn)生不確定區(qū)域。

2.3 二叉樹支持向量機(jī)(BT-SVM)[5]

對于k類的訓(xùn)練樣本,訓(xùn)練k-1個SVM,第1個SVM以第1類樣本為正的訓(xùn)練樣本，將第2,3,…,k類訓(xùn)練樣本作為負(fù)的訓(xùn)練樣本訓(xùn)練SVM1，第i個支持向量機(jī)以第i類樣本為正的訓(xùn)練樣本，將第i+1,i+2,…,k類訓(xùn)練樣本作為負(fù)的訓(xùn)練樣本訓(xùn)練SVMi，直到第k-1個支持向量機(jī)將以第k-1類樣本作為正樣本，以第k類樣本為負(fù)樣本訓(xùn)練SVM(k-1).可以看出二叉樹方法可以避免傳統(tǒng)方法的不可分情況，并且只需構(gòu)造k-1個SVM分類器，測試時并不一定需要計算所有的分類器判別函數(shù)，從而可節(jié)省測試時間，同時提高了訓(xùn)練和測試的速度.該思想也給它帶來了問題：假設(shè)共有k類訓(xùn)練樣本，根據(jù)類別號碼的排列次序訓(xùn)練樣本，不同的排列直接影響生成的二叉樹結(jié)構(gòu)，如果某個節(jié)點(diǎn)上發(fā)生分類錯誤，則錯誤會沿樹結(jié)構(gòu)向后續(xù)節(jié)點(diǎn)擴(kuò)散，從而影響分類器的性能.因此選擇合適的二叉樹生成算法，構(gòu)造合理的二叉樹結(jié)構(gòu)以提高分類器的推廣能力是值得進(jìn)一步研究的問題.

2.4 有向無環(huán)圖支持向量機(jī)(DAG-SVM)

DAG-SVMS是由Platt提出的決策導(dǎo)向的無環(huán)圖DAG導(dǎo)出的，是針對1-vs-1 SVMS存在誤分、拒分現(xiàn)象提出的[6]，該方案訓(xùn)練階段和一對一相同,如果有n類,則要訓(xùn)練n(n-1)/2個分類器,但在預(yù)測階段則要先構(gòu)造一個有向無環(huán)圖,該圖共有n(n-1)/2節(jié)點(diǎn)和n個葉,每個節(jié)點(diǎn)代表一個分類器,每個葉為一個類別.當(dāng)對測試樣本預(yù)測時,先用根節(jié)點(diǎn)的分類器預(yù)測,根據(jù)結(jié)果選擇下一層中的左節(jié)點(diǎn)或右節(jié)點(diǎn)繼續(xù)預(yù)測,直到最后到達(dá)葉就得到測試樣本所屬類別.

該方法和1-vs-1 SVM一樣，訓(xùn)練的時候,首先需要構(gòu)造k(k-1)/2個分類決策面.然而和1-vs-1 SVM方法不同的是，由于在每個節(jié)點(diǎn)預(yù)測的時候同時排除了許多類別的可能性，因此預(yù)測的時候用到的總分類平面只有k-1個，比1-vs-1 SVM要少很多，預(yù)測速度自然提高不少.但DAGSVM算法也有其不足之處.正由于它采取的是排除策略，那么最開始的判定顯得尤為重要，如果在開始階段就決策錯誤的話，那么后面的步驟都沒有意義了.因此如何選取判定的順序和得到令人信服的開始階段的判定,是值得進(jìn)一步研究的問題.圖1給出了使用DAG算法解決一個九類問題的分類示意圖.

圖1 DAG算法分類示意圖

3 結(jié)論

從分類器的復(fù)雜度方面分析，一對多和二叉樹算法對n類問題分別需要構(gòu)造n和n-1分類面；構(gòu)造分類面最多的是一對一和DAG算法，對n類問題需要構(gòu)造n(n-1)/2個分類面.從分類精度方面分析，一對一和DAG算法比一對多和二叉樹算法高，可以看出由于在目標(biāo)分類問題中,分類精度和分類器復(fù)雜度常為一對互相矛盾的指標(biāo),因此在解決實(shí)際問題中究竟采用那種分類器,應(yīng)根據(jù)用戶的要求而定,對分類精度要求較高的問題可使用一對一和DAG算法，如果需將分類精度與分類速度綜合考慮,則可以使用一對多和二叉樹算法；也可以將不同分類器組合成混合的分類器來協(xié)調(diào)二者間的需求矛盾.

[1]Vapnik V N.The nature of statistical learning theory[M].New York:Springer Verlag,1995:4-80.

[2]王亮申,歐宗瑛.基于SVM的圖像分類[J].計算機(jī)應(yīng)用與軟件,2005,22(5):98-99.

[3]趙金鳳,張日權(quán).比例可加模型參數(shù)估計的相合性[J].山西大同大學(xué)學(xué)報:自然科學(xué)版,2009,25(1):3-7.

[4]Burges C J C.A tutorial on Support Vector Machines for Pattern Recognition[J].Knowledge Discovery and Data Mining,1998,2(2):121-167.

[5]Weston J,Watkins C.Support vector machines for multi-class pattern recogni-tion[D].In Proceedings of 7th European Symposium on Artificial Neural Networks,1999:219-224.

[6]Platt J,Cristianini N,Shawe-Taylor J.Large margin DAGs for multiclass classification[A].Leen T K,Mu¨ller K R.Advancesin Neural Information Processing Systems 12[C].S A Solla:The MIT Press,2000:547-553.