支持向量機(jī)算法推導(dǎo)及其分類的算法實(shí)現(xiàn)

1、支持向量機(jī)算法推導(dǎo)及其分類的算法實(shí)現(xiàn)摘要：本文從線性分類問題開始逐步的敘述支持向量機(jī)思想的形成，并提供相應(yīng) 的推導(dǎo)過程。簡(jiǎn)述核函數(shù)的概念，以及kernel在SVM算法中的核心地位。介紹 松弛變量引入的SVM算法原因，提出軟間隔線性分類法。概括SVM分別在一 對(duì)一和一對(duì)多分類問題中應(yīng)用。基于SVM在一對(duì)多問題中的不足，提出SVM 的改進(jìn)版本DAG SVM。Abstract: This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivati

2、on. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM short

3、age in one-to-many problems, an improved version which called DAG SVM was put forward.關(guān)鍵字：SVM、線性分類、核函數(shù)、松弛變量、DAG SVM1. SVM的簡(jiǎn)介支持向量機(jī)（Support Vector Machine）是 Cortes 和 Vapnik于 1995 年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠 推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí) 理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型 的復(fù)雜性（即對(duì)特定訓(xùn)練

4、樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無錯(cuò)誤地 識(shí)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力。對(duì)于SVM的基本特點(diǎn)，小樣本，并不是樣本的絕對(duì)數(shù)量少，而是與問題的 復(fù)雜度比起來，SVM算法要求的樣本數(shù)是相對(duì)比較少的。非線性，是指SVM擅 長(zhǎng)處理樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量和核函數(shù)實(shí)現(xiàn)，是SVM 的精髓。高維模式識(shí)別是指樣本維數(shù)很高，通過SVM建立的分類器卻很簡(jiǎn)潔， 只包含落在邊界上的支持向量。線性分類器及其求解線性分類器，是最簡(jiǎn)單也很有效的分類器形式。在一個(gè)線性分類器中，可以 看到SVM形成的思路，并接觸很多SVM的核心概念。用一個(gè)二維空間里僅有兩類樣本的

5、分類問題來舉例。如圖1所示圖1兩類樣本分類C1和C2是要區(qū)分的兩個(gè)類別，在二維平面中它們的樣本如圖1所示。中間 的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性 函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性 可分的。很容易看出來，圖1中間那條分界線并不是唯一的，旋轉(zhuǎn)一下，只要不把兩 類數(shù)據(jù)分錯(cuò)，仍然可以達(dá)到分類的效果，稍微平移一下，也可以。對(duì)同一個(gè)問題 存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？必須要先找一個(gè)指標(biāo)來量化“好” 的程度，通常使用分類間隔來衡量。設(shè)平面中的直線方程為：g （x） = wx + b（1）設(shè)七是一個(gè)有某一對(duì)象抽取出的n維向

6、量，七為分類標(biāo)記，則可以定義點(diǎn)到某一超平面的 間隔：6 = y （w 工 + b）（2）用二和替代（2）式中的w和b得：II W II II W III g (x )Ii 將（3）式得到的間隔稱為幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的歐氏 距離，以上是單個(gè)點(diǎn)到某個(gè)超平面的距離定義，同樣可以定義一個(gè)點(diǎn)的集合（就是一組樣本）到某個(gè)超平面的距離為此集合中離超平面最近的點(diǎn)的距離。圖2 更加直觀的展示出了幾何間隔的含義。圖2分割超平面圖2中，H是分類面，H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。幾何間隔與樣本的誤分次數(shù)間存 在關(guān)系：其中的是樣本集合

7、到分類面的間隔，R = max|xJ，i - 1,.,n，即r是所有 樣本中向量長(zhǎng)度最長(zhǎng)的值。從上式可以看出，誤分次數(shù)的上界由幾何間隔決定。 因此選擇幾何間隔來作為評(píng)價(jià)一個(gè)解優(yōu)劣的指標(biāo)，幾何間隔越大的解，它的誤差 上界越小。因此最大化幾何間隔成了我們訓(xùn)練階段的目標(biāo)。從（3）式可知，幾何間隔與I Iwl I是成反比的，因此最大化幾何間隔與最小化I Iwll 等價(jià)。通常不是固定I IwI I的大小而尋求最大幾何間隔，而是固定間隔（例如固定 為1），尋找最小的I IwII。此時(shí)變成一個(gè)最優(yōu)化問題，若想尋找一個(gè)小IIwII，就可以用下面的式子表示:但實(shí)際上對(duì)于這個(gè)目標(biāo)，常常使用另一個(gè)完全等價(jià)的目標(biāo)函數(shù)

8、來代替，如下:min | w 1122如果直接來解這個(gè)求最小值問題，很容易看出當(dāng)Ilwll=0的時(shí)候就得到了目標(biāo) 函數(shù)的最小值。反映在圖2中，就是Hi與H2兩條直線間的距離無限大，這個(gè)時(shí) 候，所有的樣本點(diǎn)都位于H1和H 2中間，而我們?cè)镜囊鈭D是，H1右側(cè)的被分為 正類，H2左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類。這樣，所有樣 本點(diǎn)都進(jìn)入了無法分類的灰色地帶。造成這種結(jié)果的原因是在描述問題的時(shí)候只 考慮了目標(biāo)，而沒有加入約束條件，于是可以添加約束條件：平（W.? + b l（i =l，2，.，n）（n 是總的樣本數(shù)）于是可以將兩類分類轉(zhuǎn)化成數(shù)學(xué)形式，如下：f 1min II w II2

9、 0（i = 1,2,.,n）（4）在這個(gè)問題中，自變量就是可，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條 件都是w的線性函數(shù)，這種規(guī)劃問題就是二次規(guī)劃（Quadratic Programming， QP），由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。樣本確定了可，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合：w = a % +a % +.+ a %1 12 2n n（5）式子中的氣是拉格朗日乘子，而%是樣本點(diǎn)，也是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。 為了方便描述，以下開始嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會(huì)用a x*. r.曰 , x /i i表示數(shù)字和向量的乘積，而用i j表示向量

10、i j的內(nèi)積。因此（1）式 嚴(yán)格的形式應(yīng)該是：（6）g (x) = + bw不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)。因此用下面這個(gè)式子表 示w：w = a yx +a yx +.+ a y x111222n n n(7)其中的y就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的拉格朗 日乘子氣，,氣中，只有很少的一部分不等于0，這部分不等于0的拉格朗 日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在氣和H 2上，也正是這部分樣本唯一的確 定了分類函數(shù)。這部分可以確定分類的樣本點(diǎn)，就叫做支持向量。因此原來的 g(x)表達(dá)式可以寫為：g (x) = + b= +bi=1 i i i，(8)w = (a

11、y x )其中，i =1 E 上式可以變形為:(9)g (x) = E a y +bi=1此時(shí)消去了上式中的w，問題從求w變成了求以。這樣就簡(jiǎn)化了原問題的求 解，以這樣的形式描述問題以后，優(yōu)化問題少了很大一部分不等式約束。接下來 看看SVM在線性分類器上所做的重大改進(jìn)一一核函數(shù)。SVM中的核函數(shù)根據(jù)模式識(shí)別理論，低維空間線性不可分的模式通過非線性映射到高維特征 空間則可能實(shí)現(xiàn)線性可分，但是如果直接采用這種技術(shù)在高維空間進(jìn)行分類或回 歸，則存在確定非線性映射函數(shù)的形式和參數(shù)、特征空間維數(shù)等問題，而最大的 障礙則是在高維特征空間運(yùn)算時(shí)存在的“維數(shù)災(zāi)難”。采用核函數(shù)技術(shù)可以有效 地解決這樣問題。如圖

12、3所示，當(dāng)分類問題在低緯空間無法用線性分類方法解決時(shí)，可以通過8將低緯空間的數(shù)據(jù)映射到高緯特征空間中，從而達(dá)到線性可分的目的。p mapping （jj? R、改.功 r=2 土）=孺、明甚，K ,k iz/ciiturc HK圖3低緯度向高緯度空間映射從低緯度向高緯度轉(zhuǎn)化關(guān)鍵在于尋在一個(gè)。函數(shù)，但對(duì)目前沒有一個(gè)系統(tǒng)的方法。對(duì)映射過程推導(dǎo)如下：= TOC o 1-5 h z 1212123123=11 221122=X2XT2 + 2XX XT XT + X 2X T2(偵)=(X XT + X XT )2 1122= ()2=K ( x, xt )從上式可以得出，我們只關(guān)心高維空間里內(nèi)積的值

13、，而核函數(shù)就是接受低空 間的輸入，并計(jì)算出在高緯空間的內(nèi)積值。K(X,XT)，就是我們要找的核函數(shù)。如圖4fcnlurc nLLpF】i)g*R*=：,也藥如牙；,閔,也點(diǎn)；,矛；勺)= jc)3 + 2x2aj|Xj + x2x2+=() k(x,x) kernel fiinctinn圖4在映射過程中的核函數(shù)g (x) = Y a y K (x , x) + b于是上式，可以表示為i 1 。盡管給的問題是線性不可分的，但凡是要求內(nèi)積的時(shí)候我們就選定的核函數(shù)來算。這樣求出來的a再和你 選定的核函數(shù)一組合，就可以得到線性分類器。但是任然存在以下兩個(gè)問題：既然有很多的核函數(shù)，針對(duì)具體問題該怎么選擇

14、？如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么 辦？第一個(gè)問題：對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果 的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講， 徑向基核函數(shù)是不會(huì)出太大偏差的一種，首選。對(duì)第二個(gè)問題的解決則引出了 SVM中的另一個(gè)概念：松弛變量。SVM中的松弛變量假設(shè)有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一個(gè)樣本，映射到高維空間 以后，也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的，如圖5：口圖5新增加了一個(gè)樣本后分類的結(jié)果就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類的一個(gè)樣本，這單獨(dú)的一 個(gè)樣本，使得原本線性可分的問題變成了線

15、性不可分的。這樣類似的問題（僅有 少數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問題。對(duì)于人類思維，在大量的樣本基礎(chǔ)上，可能會(huì)認(rèn)為圖5中的黃點(diǎn)是錯(cuò)誤的， 是噪聲，會(huì)自動(dòng)的剔除掉。人的思維對(duì)于噪聲數(shù)據(jù)具有容錯(cuò)性，可程序沒有。由 于我們?cè)镜膬?yōu)化問題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)，在此基礎(chǔ)上尋找 正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面 這種有噪聲的情況會(huì)使得整個(gè)問題無解。這種解法其實(shí)也叫做“硬間隔”分類法， 因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值。說明 硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制。針對(duì)硬間隔的問題，解決方法也很明顯，就是仿照人的思

16、路，允許一些點(diǎn)到 分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一 樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達(dá)形式的簡(jiǎn)潔。原先對(duì) 樣本點(diǎn)的要求是：（11）y.（心.）+ b 1（i = 1,2,.,n）（n是樣本數(shù)）該式說明，離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就 給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許：（12）y（wx） + b 1 & （i = 1,2,., n）（n是樣本數(shù)）M 0i i因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某 些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著放棄了對(duì)這些 點(diǎn)的精確分

17、類，而這對(duì)分類器來說是種損失。但是放棄這些點(diǎn)也帶來了好處，那 就是使分類面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的幾何間隔。顯然必 須權(quán)衡這種損失和好處。得到的分類間隔越大，好處就越多。原始的硬間隔分類 對(duì)應(yīng)的優(yōu)化問題：min II w 1|22（13）S:T. y （w-尤）+ b-1 0 （i = 1,2,.,n）II w II2就是目標(biāo)函數(shù)，希望它越小越好，因而損失就必然是一個(gè)能使之變大的量。 那如何來衡量損失，有兩種常用的方式，t饋 i s心 或者7兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間 隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標(biāo)函數(shù)里的時(shí)候

18、， 就需要一個(gè)懲罰因子，原來的優(yōu)化問題就變成了下面這樣：1“ “min II w II22 , 、ST. y （w-x） + b T （i = 1,2,.,n）（14）4 0 1這個(gè)式子有這么幾點(diǎn)要注意：一是并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才 有，沒離群的點(diǎn)松弛變量都等于0。二是松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就 越遠(yuǎn)。三是懲罰因子C決定了你有多重視離群點(diǎn)帶來的損失，顯然當(dāng)所有離群點(diǎn)的 松弛變量的和一定時(shí)，定的C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著 不愿意放棄這些離群點(diǎn)，最極端的情況是你把C定為無限大，這樣只要稍有一 個(gè)點(diǎn)離群，目

19、標(biāo)函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了 硬間隔問題。四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問題在解的時(shí)候，C是一個(gè)你必須 事先指定的值。五是盡管加了松弛變量這么一說，但這個(gè)優(yōu)化問題仍然是一個(gè)優(yōu)化問題，解 的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前 面圖中的三條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算 一算，再換一組三條直線，再把目標(biāo)函數(shù)的值算一算，如此往復(fù)（迭代），直到 最終找到目標(biāo)函數(shù)最小時(shí)的w。松弛變量也就是個(gè)解決線性不可分問題的方法罷了，核函數(shù)的引入不也是為 了解決線性不可

20、分的問題么？為什么要為了一個(gè)問題使用兩種方法呢？其實(shí)兩者還有微妙的不同。一般的情況下，在原始的低維空間中，樣本相當(dāng) 的不可分，無論怎么找分類平面，總會(huì)有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空 間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分 的狀態(tài)，此時(shí)再用松弛變量處理那些少數(shù)“冥頑不化”的離群點(diǎn)，就簡(jiǎn)單有效得多 了。至此一個(gè)比較完整的支持向量機(jī)框架就有了，簡(jiǎn)單說來，支持向量機(jī)就是使 用了核函數(shù)的軟間隔線性分類法。懲罰因子和數(shù)據(jù)偏斜偏斜問題，也叫數(shù)據(jù)集偏斜（unbalanced），它指的是參與分類的兩個(gè)類別 （也可以指多個(gè)類別）樣本數(shù)量差異很大。比如說正類有10，000個(gè)樣本

21、，而負(fù) 類只給了100個(gè)，這會(huì)引起的問題顯而易見，如圖7：圖6數(shù)據(jù)集偏斜現(xiàn)象方形的點(diǎn)是負(fù)類。H, HI, H2是根據(jù)給的樣本算出來的分類面，由于負(fù)類的 樣本很少很少，所以有一些本來是負(fù)類的樣本點(diǎn)沒有提供，比如圖7中兩個(gè)灰色 的方形點(diǎn)，如果這兩個(gè)點(diǎn)有提供的話，那算出來的分類面應(yīng)該是H，H2和H1， 他們顯然和之前的結(jié)果有出入，實(shí)際上負(fù)類給的樣本點(diǎn)越多，就越容易出現(xiàn)在灰 色點(diǎn)附近的點(diǎn)，算出的結(jié)果也就越接近于真實(shí)的分類面。但現(xiàn)在由于偏斜的現(xiàn)象 存在，使得數(shù)量多的正類可以把分類面向負(fù)類的方向“推”，因而影響了結(jié)果的 準(zhǔn)確性。解決數(shù)據(jù)集偏斜問題的方法之一就是在懲罰因子上作文章，那就是給樣 本數(shù)量少的負(fù)類

22、更大的懲罰因子，表示我們重視這部分樣本，因此我們的目標(biāo)函 數(shù)中因松弛變量而損失的部分就變成了：（15）c+：L + C_ 匚, i=1j=P+1g - o其中i=1p都是正樣本，j=p+1p+q都是負(fù)樣本。那和C怎么確定呢？它 們的大小是試出來的（參數(shù)調(diào)優(yōu)），但是他們的比例可以有些方法來確定。但是 這樣并不夠好，如圖6,發(fā)現(xiàn)正類之所以可以“欺負(fù)”負(fù)類，其實(shí)并不是因?yàn)樨?fù) 類樣本少，真實(shí)的原因是負(fù)類的樣本分布的不夠廣（沒擴(kuò)充到負(fù)類本應(yīng)該有的區(qū) 域）。比如，現(xiàn)在想給政治類和體育類的文章做分類，政治類文章很多，而體育 類只提供了幾篇關(guān)于籃球的文章，這時(shí)分類會(huì)明顯偏向于政治類，如果要給體育 類文章增加樣

23、本，但增加的樣本仍然全都是關(guān)于籃球的。雖然體育類文章在數(shù)量 上可以達(dá)到與政治類一樣多，但過于集中了，結(jié)果仍會(huì)偏向于政治類！所以給C 和C確定比例更好的方法應(yīng)該是衡量他們分布的程度。比如可以算算他們?cè)诳?間中占據(jù)了多大的體積，例如給負(fù)類找一個(gè)超球，它可以包含所有負(fù)類的樣本， 再給正類找一個(gè)超球，比比兩個(gè)球的半徑，就可以大致確定分布的情況。顯然半 徑大的分布就比較廣，就給小一點(diǎn)的懲罰因子。6.SVM 的改進(jìn) DAG SVMSVM是一種典型的兩類分類器，而現(xiàn)實(shí)中要解決的問題，往往是多類的問題， 比如文本分類，數(shù)字識(shí)別。如何由兩類分類器得到多類分類器，就是一個(gè)值得研 究的問題。以文本分類為例，現(xiàn)成的方

24、法有很多，其中一種一勞永逸的方法，就 是真的一次性考慮所有樣本，并求解一個(gè)多目標(biāo)函數(shù)的優(yōu)化問題，一次性得到多 個(gè)分類面，就像下圖這樣：圖7對(duì)任意兩個(gè)類構(gòu)建一個(gè)分類器多個(gè)超平面把空間劃分為多個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)類別，給一篇文章， 看它落在哪個(gè)區(qū)域就知道了它的分類。這樣一次性求解的方法計(jì)算量實(shí)在太大， 大到無法實(shí)用的地步?！耙活悓?duì)其余”的方法，就是每次仍然解一個(gè)兩類分類的問題。比如有5 個(gè)類別，第一次就把類別1的樣本定為正樣本，其余2, 3, 4, 5的樣本合起來 定為負(fù)樣本，這樣得到一個(gè)兩類分類器，它能夠指出一篇文章是還是不是第1 類的；第二次我們把類別2的樣本定為正樣本，把1，3, 4,5

25、的樣本合起來定 為負(fù)樣本，得到一個(gè)分類器，如此下去，可以得到5個(gè)這樣的兩類分類器。這種 方法的好處是每個(gè)優(yōu)化問題的規(guī)模比較小，而且分類的時(shí)候速度很快。但有時(shí)也 會(huì)出現(xiàn)兩種很尷尬的情況，例如拿一篇文章每一個(gè)分類器都說它是屬于它那一類 的，或者每一個(gè)分類器都說它不是它那一類的，前者叫分類重疊現(xiàn)象，后者叫不 可分類現(xiàn)象。對(duì)于分類重疊倒，隨機(jī)選一個(gè)結(jié)果都不至于太離譜，或者看看這篇 文章到各個(gè)超平面的距離，哪個(gè)遠(yuǎn)就判給哪個(gè)。不可分類現(xiàn)象就著實(shí)難辦了，只 能把它分給第6個(gè)類別了，本來各個(gè)類別的樣本數(shù)目是差不多的，但“其余”的 那一類樣本數(shù)總是要數(shù)倍于正類，這就人為的造成了 “數(shù)據(jù)集偏斜”問題。再退一步，還

26、是解兩類分類問題，還是每次選一個(gè)類的樣本作正類樣本，而 負(fù)類樣本則變成只選一個(gè)類，這就避免了偏斜。因此過程就是算出這樣一些分類 器，第一個(gè)只回答“是第1類還是第2類”，第二個(gè)只回答“是第1類還是第3 類”，第三個(gè)只回答“是第1類還是第4類”，如此下去，可以馬上得出，這樣 的分類器應(yīng)該有5 X 4/2=10個(gè)。雖然分類器的數(shù)目多了，但是在訓(xùn)練階段所用 的總時(shí)間卻比“一類對(duì)其余”方法少很多，在真正用來分類的時(shí)候，把一篇文章 扔給所有分類器，第一個(gè)分類器會(huì)投票說它是“ 1”或者“2”，第二個(gè)會(huì)說它是 “1”或者“3”，讓每一個(gè)都投上自己的一票，最后統(tǒng)計(jì)票數(shù)，如果類別“1” 得票最多，就判這篇文章屬于

27、第1類。這種方法顯然也會(huì)有分類重疊的現(xiàn)象，但 不會(huì)有不可分類現(xiàn)象，因?yàn)榭偛豢赡芩蓄悇e的票數(shù)都是0。這還是類別數(shù)為5 的時(shí)候，類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會(huì)上升至約500,000個(gè)。再退一步，還是像一對(duì)一方法那樣來訓(xùn)練，只是在對(duì)一篇文章進(jìn)行分類之前， 先按照?qǐng)D8的樣子來組織分類器圖8 DAG SVM訓(xùn)練方法這樣在分類時(shí)，就可以先問分類器“1對(duì)5”，如果它回答5,就往左走，再 問“2對(duì)5”這個(gè)分類器，如果它還說是“5”，就繼續(xù)往左走，這樣一直問下去， 就可以得到分類結(jié)果。優(yōu)點(diǎn)是，只調(diào)用了4個(gè)分類器，分類速度快，且沒有分類 重疊和不可分類現(xiàn)象！缺點(diǎn)是，假如最一開始的分類器回答錯(cuò)誤，那么

28、后面的分 類器是無論如何也無法糾正它的錯(cuò)誤的，其實(shí)對(duì)下面每一層的分類器都存在這種 錯(cuò)誤向下累積的現(xiàn)象。DAG方法好于它們的地方就在于，累積的上限，不管是大 是小，總是有定論的，有理論證明。而一對(duì)其余和一對(duì)一方法中，盡管每一個(gè)兩 類分類器的泛化誤差限是知道的，但是合起來做多類分類的時(shí)候，誤差上界是多 少，無法知道，這意味著準(zhǔn)確率低到0也是有可能的。而且現(xiàn)在DAG方法根節(jié)點(diǎn) 的選取，也有一些方法可以改善整體效果，我們總希望根節(jié)點(diǎn)少犯錯(cuò)誤為好，因 此參與第一次分類的兩個(gè)類別，最好是差別特別特別大，大到以至于不太可能把 他們分錯(cuò)；或者就總?cè)≡趦深惙诸愔姓_率最高的那個(gè)分類器作根節(jié)點(diǎn)，或者我 們讓兩類分

29、類器在分類的時(shí)候，不光輸出類別的標(biāo)簽，還輸出一個(gè)類似“置信 度”等。參考文獻(xiàn). Bahlmann C, Haasdonk B, Burkhardt H. Online handwriting recognition with support vector machines-a kernel approachC/Frontiers in Handwriting Recognition, 2002. Proceedings. Eighth International Workshop on. IEEE, 2002: 49-54. Mandel M I, Ellis D P W. Song-leve

30、l features and support vector machines for music classificationC/ISMIR 2005: 6th International Conference on Music Information Retrieval: Proceedings: Variation 2: Queen Mary, University of London & Goldsmiths College, University of London, 11-15 September, 2005. Queen Mary, University of London, 2005: 594-599. Chen P, Liu S. An improved dag-svm for multi-class classificationC/Natural Computation, 2009. ICNC09. Fifth International Con