多類SVM分類算法的研究

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

(山西大同大學數學與計算機科學學院，山西大同 037009)

機器學習從早期Fisher分類器到人工神經網絡都是基于傳統的經驗風險最小化原則進行的，即采用在訓練樣本集上的學習能力，作為衡量一個學習機性能好壞的標準.這種機器學習存在著過擬合問題，使得學習機的泛化能力差.支持向量機(SVM)是一種建立在統計學習理論基礎之上的機器學習方法,其最大的特點是根據Vapnik結構風險最小化原則[1],即在函數復雜性和樣本復雜性之間進行折中，盡量提高學習機的泛化能力，具有優良的分類性能.

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

1 支持向量機原理[2]

1.1 線性可分問題

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

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

滿足式(1)條件且使｜w｜2最小的分類面就是最優分類面.過兩類樣本中離分類面最近的點且平行于最優分類面的超平面上的訓練樣本就是式(1)中使等號成立的那些樣本，它們叫做支持向量(Support Vectors).因為它們支撐了最優分類面.

1.2 線性不可分問題

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

尋優目標函數式(2)變為式(4)：

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

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

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

1.3 非線性問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 有向無環圖支持向量機(DAG-SVM)

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

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

圖1 DAG算法分類示意圖

3 結論

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

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

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

[3]趙金鳳,張日權.比例可加模型參數估計的相合性[J].山西大同大學學報:自然科學版,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.