SVM算法原理及其Matlab應(yīng)用

SVM算法及其Matlab應(yīng)用TOC\o"1-2"\h\z\u一、SVM算法21.1、線性分類器及其求解21.2、核函數(shù)71.3、松弛變量8二、SVM在多類分類中的應(yīng)用132.1、一對其余法132.2、一對一142.3、DAG方法〔有向無環(huán)圖〕142.4、決策樹方法152.5、糾錯輸出編碼法〔ECOC〕15三、SVM在Matlab中的應(yīng)用163.1、libsvm工具箱和Matlab自帶svm算法差異163.2、libsvm訓(xùn)練函數(shù)及結(jié)果參數(shù)說明163.3、libsvm使用技巧18一、SVM算法SVM(SupportVectorMachine，支持向量機(jī)〕是一種有監(jiān)督的機(jī)器學(xué)習(xí)方法，可以學(xué)習(xí)不同類別的樣本的特點(diǎn)，進(jìn)而對未知的樣本進(jìn)行預(yù)測。支持向量機(jī)的目標(biāo)就是要根據(jù)結(jié)構(gòu)風(fēng)險最小化原理,構(gòu)造一個目標(biāo)函數(shù)將兩類模式盡可能地區(qū)分開。1.1、線性分類器及其求解下面以線性分類器為例，來引入SVM算法的一些概念和處理流程。如圖1所示，C1和C2是要區(qū)分的兩個類別，在二維平面中它們的樣本如圖。中間的直線就是一個線性分類函數(shù)，它可以將兩類樣本完全分開，就稱這些數(shù)據(jù)是線性可分的，否那么稱為非線性可分的。設(shè)圖中線性函數(shù)為g(x)=wx+b〔x是樣本的向量表示〕，那么當(dāng)有一個樣本xi需要判別的時候，就可以看g(xi)的值，假設(shè)g(xi)>0，就判別為類別C1，假設(shè)g(xi)<0，那么判別為類別C2〔等于的時候就拒絕判斷〕。此時也等價于給函數(shù)g(x)附加一個符號函數(shù)sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數(shù)。中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個函數(shù)叫做分類面。從圖可知，中間那條分界線并不是唯一的，把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯，仍然可以到達(dá)上面說的效果，稍微平移一下，也可以。那么哪一個函數(shù)更好呢？顯然必須要先找一個指標(biāo)來量化“好〞的程度，通常使用的都是叫做“分類間隔〞的指標(biāo)。設(shè)每一個樣本由一個向量〔樣本特征所組成的向量〕和一個標(biāo)記〔標(biāo)示出這個樣本屬于哪個類別〕組成。如下：Di=(xi,yi)，xi是特征向量〔維數(shù)很高〕，yi是分類標(biāo)記。在二元的線性分類中，這個表示分類的標(biāo)記只有兩個值，1和-1〔用來表示屬于還是不屬于這個類〕。有了這種表示法，我們就可以定義一個樣本點(diǎn)到某個超平面的間隔：δi=yi(wxi+b)首先注意到如果某個樣本屬于該類別的話，那么wxi+b>0，而yi也大于0；假設(shè)不屬于該類別的話，那么wxi+b<0，而yi也小于0，這意味著yi(wxi+b)總是大于0的，而且它的值就等于|wxi+b|〔也就是|g(xi)|〕現(xiàn)在把w和b進(jìn)行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成這就是解析幾何中點(diǎn)xi到直線g(x)=0的距離公式，當(dāng)用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離〞。以上是單個點(diǎn)到某個超平面的距離〔就是間隔，后面不再區(qū)別這兩個詞〕定義，同樣可以定義一個點(diǎn)的集合〔就是一組樣本〕到某個超平面的距離為此集合中離超平面最近的點(diǎn)的距離。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實(shí)含義：H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。幾何間隔與樣本的誤分次數(shù)間存在關(guān)系：其中的δ是樣本集合到分類面的間隔，R=max||xi||i=1,...,n，即R是所有樣本中〔xi是以向量表示的第i個樣本〕向量長度最長的值。誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，誤分次數(shù)的上界由幾何間隔決定，而幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓(xùn)練階段的目標(biāo)。根據(jù)以上分析知，間隔：δ=y(wx+b)=|g(x)|，幾何間隔：可以看出δ=||w||δ幾何。注意到幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||在δ固定時完全是一回事。而我們常用的方法也是固定間隔〔例如固定為1〕，尋找最小的||w||。這是一個尋優(yōu)問題〔也叫作一個規(guī)劃問題〕，而一個尋優(yōu)問題最重要的局部是目標(biāo)函數(shù)，我們的目標(biāo)即找到也可以用來代替。接下來回想一下，我們的問題是有一堆點(diǎn)，可以被分成兩類，我們要找出最好的分類面，且||w||≠0因此需要有約束條件，我們前文提到過把間隔固定為1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，即yi[(w·xi)+b]≥1(i=1,2,…,l)〔l是總的樣本數(shù)〕，也可以寫成：yi[(w·xi)+b]-1≥0(i=1,2,…,l)〔l是總的樣本數(shù)〕因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個帶約束的最小值的問題：在這個問題中，自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)〔哎，千萬不要把xi當(dāng)成變量，它代表樣本，是的〕，這種規(guī)劃問題有個很有名氣的稱呼——二次規(guī)劃〔QuadraticProgramming，QP〕，而且可以更進(jìn)一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。而且對SVM來說，可行域邊界上的點(diǎn)有其特殊意義，實(shí)際上是它們唯一的決定了分類超平面，這些點(diǎn)〔想象他們就是以前的圖中恰好落在H1和H2上的點(diǎn)〕就被稱為支持向量。根據(jù)以上分析知，樣本確定了w，即w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn式子中的αi是數(shù)〔又稱拉格朗日乘子〕，而xi是樣本點(diǎn)，n是總樣本點(diǎn)的個數(shù)。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：g(x)=<w,x>+b但是上面的式子還不夠好，想像一下列圖中正樣本和負(fù)樣本的位置，假設(shè)不動所有點(diǎn)的位置，而只是把其中一個正樣本點(diǎn)定為負(fù)樣本點(diǎn)，三條直線都必須移動。這說明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)〔也就是和樣本的“標(biāo)簽〞有關(guān)〕。因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn〔式1〕其中的yi就是第i個樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的那一堆拉格朗日乘子中，只有很少的一局部不等于0〔不等于0才對w起決定作用〕，這局部不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這局部樣本〔而不需要全部樣本〕唯一確實(shí)定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說，這些樣本的一局部就可以確定，因為例如確定一條直線，只需要兩個點(diǎn)就可以，即便有三五個都落在上面，我們也不是全都需要。這局部我們真正需要的樣本點(diǎn)，就叫做支持向量！式1也可以用求和符號簡寫一下：因此原來的g(x)表達(dá)式可以寫為：注意式子中x才是變量，即需要測試的樣本x，而所有的xi統(tǒng)統(tǒng)都是的樣本。還注意到式子中只有xi和x是向量，因此一局部可以從內(nèi)積符號中拿出來，得到g(x)的式子為：因此尋優(yōu)問題從求w變成了求α。這使優(yōu)化問題少了很大一局部不等式約束。接下來先跳過線性分類器求解的局部，來看看SVM在線性分類器上所做的重大改良——核函數(shù)。之前一直在討論的線性分類器,只能對線性可分的樣本做處理。如果提供的樣本線性不可分，那線性分類器將失效，是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？有！下面用一個二維平面中的分類問題作例子。如下列圖：橫軸上端點(diǎn)a和b之間紅色局部里的所有點(diǎn)為正類，兩邊的黑色局部里的點(diǎn)為負(fù)類。顯然找不到符合條件的直線將兩類點(diǎn)分開，但可以找到一條曲線，例如下列圖中這條來判斷點(diǎn)的所屬類別，它的函數(shù)表達(dá)式可以寫為：但它不是一個線性函數(shù)，不過，假設(shè)新建一個向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，即：g(x)=f(y)=ay在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)，因為自變量y的次數(shù)不大于1。這樣，原來在二維空間中一個線性不可分的問題，映射到四維空間后？，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的根本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。而轉(zhuǎn)化最關(guān)鍵的局部就在于找到x到y(tǒng)的映射方法。遺憾的是，假設(shè)x’是由x變換得到的高維變量，在此維度下，問題先行可分，那么只需計算f(x’)=<w’,x’>+b的值來進(jìn)行分類，即只關(guān)心高維空間里內(nèi)積<w’,x’>的值。而從理論上說，x’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)，而w’是常量，它是一個低維空間里的常量w經(jīng)過x與x’之間相同的變換得到的，所以給了一個w和x的值，就有一個確定的f(x’)值與其對應(yīng)。那么是否能有這樣一種函數(shù)K(w,x),它接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>？如果有這樣的函數(shù)，那么當(dāng)給了一個低維空間的輸入x以后，使g(x)=K(w,x)+b和f(x’)=<w’,x’>+b這兩個函數(shù)的計算結(jié)果就完全一樣，也就不用費(fèi)力找映射關(guān)系了。1.2、核函數(shù)上述的K(w,x)確實(shí)存在，它被稱作核函數(shù)〔核，kernel〕，而且只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的根本作用就是接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。回想我們上節(jié)說的求一個線性分類器，它的形式應(yīng)該是：現(xiàn)在這個就是高維空間里的線性函數(shù)，就可以用以下低維空間里的函數(shù)來代替。由以上分析又引出兩個問題：1．既然有很多的核函數(shù)，針對具體問題該怎么選擇？2．如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？對第一個問題，即核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原那么！通常而言，徑向基核函數(shù)〔RBF〕核是合理的首選。這個核函數(shù)將樣本非線性地映射到一個更高維的空間，與線性核不同，它能夠處理分類標(biāo)注和屬性的非線性關(guān)系。并且，線性核是RBF的一個特例〔KeerthiandLin2003〕。同時，Sigmoid核的表現(xiàn)很像一定參數(shù)的RBF核〔LinandLink2003〕。第二個原因，超參數(shù)的數(shù)量會影響到模型選擇的復(fù)雜度,而多項式核比RBF核有更多的超參數(shù)。最后，RBF核有更少的數(shù)值復(fù)雜度。當(dāng)然，也存在一些情形RBF核是不適用的。特別地，當(dāng)特征維數(shù)非常大的時候，很可能只能適用線性核。1.3、松弛變量對上述第二個問題，可以用松弛變量來解決，下面對松弛變量進(jìn)行詳細(xì)描述。現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就像下列圖這樣：圓形和方形的點(diǎn)各有成千上萬個，現(xiàn)在想象我們有另一個訓(xùn)練集，只比原先這個訓(xùn)練集多了一個樣本，映射到高維空間以后，也就多了一個樣本點(diǎn)，但是這個樣本的位置如下列圖，就是圖中黃色那個點(diǎn)，它是方形的，因而它是負(fù)類的一個樣本，這單獨(dú)的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題〔僅有少數(shù)點(diǎn)線性不可分〕叫做“近似線性可分〞的問題。以我們?nèi)祟惖某ＷR來判斷，這個樣本點(diǎn)很可能是噪聲，我們會簡單的忽略這個樣本點(diǎn)，仍然使用原來的分類器，其效果絲毫不受影響。但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)，在此根底上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實(shí)也叫做“硬間隔〞分類法，因為他硬性的要求所有樣本點(diǎn)都滿足和分類平面間的距離必須大于某個值。因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制。但解決方法也很明顯，就是允許一些點(diǎn)到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔〔而不是幾何間隔〕來衡量有利于我們表達(dá)形式的簡潔。我們原先對樣本點(diǎn)的要求是：意思是說離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許因為松弛變量是非負(fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時〔這些點(diǎn)也叫離群點(diǎn)〕，意味著我們放棄了對這些點(diǎn)的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點(diǎn)也帶來了好處，那就是使分類面不必向這些點(diǎn)的方向移動，因而可以得到更大的幾何間隔〔在低維空間看來，分類邊界也更平滑〕。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多?；貞浳覀冊嫉挠查g隔分類對應(yīng)的優(yōu)化問題：||w||2就是我們的目標(biāo)函數(shù)〔當(dāng)然系數(shù)可有可無〕，希望它越小越好，因而損失就必然是一個能使之變大的量〔能使它變小就不叫損失了，我們本來就希望目標(biāo)函數(shù)值越小越好〕。那如何來衡量損失，有兩種常用的方式，有人喜歡用而有人喜歡用其中l(wèi)都是樣本的數(shù)目。兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失參加到目標(biāo)函數(shù)里的時候，就需要一個懲罰因子〔cost，也就是libSVM的諸多參數(shù)中的C〕，原來的優(yōu)化問題就變成了下面這樣：這個式子有這么幾點(diǎn)要注意：〔1〕并非所有的樣本點(diǎn)都有一個松弛變量與其對應(yīng)。實(shí)際上只有“離群點(diǎn)〞才有，或者也可以這么看，所有沒離群的點(diǎn)松弛變量都等于0〔對負(fù)類來說，離群點(diǎn)就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點(diǎn)，對正類來說，就是跑到H1左側(cè)的那些正樣本點(diǎn)〕?！?〕松弛變量的值實(shí)際上標(biāo)示出了對應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)?！?〕懲罰因子C決定了你有多重視離群點(diǎn)帶來的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時，你定的C越大，對目標(biāo)函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點(diǎn)，最極端的情況是你把C定為無限大，這樣只要稍有一個點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題?！?〕懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器。〔5〕盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題〔汗，這不廢話么〕，解它的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直線〔你可以看到，分類的直線位置如果移動了，有些原來離群的點(diǎn)會變得不再離群，而有的本來不離群的點(diǎn)會變成離群點(diǎn)〕，再把目標(biāo)函數(shù)的值算一算，如此往復(fù)〔迭代〕，直到最終找到目標(biāo)函數(shù)最小時的w。至此一個比擬完整的支持向量機(jī)框架就有了，簡單說來，支持向量機(jī)就是使用了核函數(shù)的軟間隔線性分類法。接下來討論一下懲罰因子C?；仡^看一眼引入了松弛變量以后的優(yōu)化問題：注意其中C表征了你有多么重視離群點(diǎn)，C越大越重視，越不想丟掉它們。這個式子是以前做SVM的人寫的，但沒有任何規(guī)定說必須對所有的松弛變量都使用同一個懲罰因子，我們完全可以給每一個離群點(diǎn)都使用不同的C，這時就意味著你對每個樣本的重視程度都不一樣。當(dāng)然實(shí)際使用的時候并沒有這么極端，但一種很常用的變形可以用來解決分類問題中樣本的“偏斜〞問題。樣本的偏斜問題，也叫數(shù)據(jù)集偏斜〔unbalanced〕，它指的是參與分類的兩個類別〔也可以指多個類別〕樣本數(shù)量差異很大。比方說正類有10000個樣本，而負(fù)類只給了100個，這會引起的問題顯而易見，可以看看下面的圖：方形的點(diǎn)是負(fù)類。H，H1，H2是根據(jù)給的樣本算出來的分類面，由于負(fù)類的樣本很少很少，所以有一些本來是負(fù)類的樣本點(diǎn)沒有提供，比方圖中兩個灰色的方形點(diǎn)，如果這兩個點(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ù)類更大的懲罰因子，表示我們重視這局部樣本〔本來數(shù)量就少，再拋棄一些，那人家負(fù)類還活不活了〕，因此我們的目標(biāo)函數(shù)中因松弛變量而損失的局部就變成了：其中i=1…p都是正樣本，j=p+1…p+q都是負(fù)樣本。libSVM這個算法包在解決偏斜問題的時候用的就是這種方法。二、SVM在多類分類中的應(yīng)用從SVM的那幾張圖可以看出來，SVM是一種典型的兩類分類器，即它只答復(fù)屬于正類還是負(fù)類的問題。而現(xiàn)實(shí)中要解決的問題，往往是多類的問題。如何由兩類分類器得到多類分類器，就是一個值得研究的問題。SVM多類分類方法的實(shí)現(xiàn)根據(jù)其指導(dǎo)思想大致有兩種：通過對前面所述支持向量分類機(jī)中的原始最優(yōu)化問題的適當(dāng)改變，使得它能同時計算出所有多類分類決策函數(shù)，從而“一次性〞地實(shí)現(xiàn)多類分類。原始問題可以改寫為：將多類問題分解為一系列SVM可直接求解的兩類問題，基于這一系列SVM求解結(jié)果得出最終判別結(jié)果。雖然第(1)種指導(dǎo)思想看起來簡單，但由于它的最優(yōu)化問題求解過程太復(fù)雜，計算量太大，實(shí)現(xiàn)起來比擬困難，因此未被廣泛應(yīng)用。而基于第(2)種指導(dǎo)思想的SVM多類分類方法主要有5種。2.1、一對其余法一對余類法(Oneversusrest，OVR)是最早出現(xiàn)也是目前應(yīng)用最為廣泛的方法之一，其步驟是構(gòu)造k個兩類分類機(jī)(設(shè)共有k個類別)，其中第i個分類機(jī)把第i類同余下的各類劃分開，訓(xùn)練時第i個分類機(jī)取訓(xùn)練集中第i類為正類，其余類別點(diǎn)為負(fù)類進(jìn)行訓(xùn)練。判別時，輸入信號分別經(jīng)過k個分類機(jī)共得到k個輸出值fi(x)=sgn(gi(x))，假設(shè)只有一個+1出現(xiàn)，那么其對應(yīng)類別為輸入信號類別；實(shí)際情況下構(gòu)造的決策函數(shù)總是有誤差的，假設(shè)輸出不只一個+1，或者沒有一個輸出為+1，那么比擬g(x)輸出值，最大者對應(yīng)類別為輸入的類別。這種方法的優(yōu)點(diǎn)是，對k類問題，只需要訓(xùn)練k個兩類分類支持向量機(jī)，故其所得到的分類函數(shù)的個數(shù)較少，其分類速度相對較快，但容易出現(xiàn)樣本偏斜問題。2.2、一對一該方法在每兩類間訓(xùn)練一個分類器，因此對于一個k類問題，將有k(k-1)／2個分類函數(shù)。當(dāng)對一個未知樣本進(jìn)行分類時，每個分類器都對其類別進(jìn)行判斷．并為相應(yīng)的類別“投上一票〞，最后得票最多的類別即作為該未知樣本的類別。決策階段采用投票法，可能存在多個類的票數(shù)相同的情況，從而使未知樣本同時屬于多個類別，影響分類精度。2.3、DAG方法〔有向無環(huán)圖〕

DAG-SvMS是由PIatt提出的決策導(dǎo)向的循環(huán)圖DAG導(dǎo)出的，是針對“一對一"SvMS存在誤分，拒分現(xiàn)象提出的。這種方法的訓(xùn)練過程類似于“一對一〞方法，k類別問題需要求解k(k-1)／2個支持向量機(jī)分類器，這些分類器構(gòu)成一個有向無環(huán)圖。該有向無環(huán)圖中含有k(k-1)／2個內(nèi)部節(jié)點(diǎn)和k個葉結(jié)點(diǎn)，每個節(jié)點(diǎn)對應(yīng)一個二類分類器。DAG-SVMS簡單易行，只需要使用k-1個決策函數(shù)即可得出結(jié)果，較“一對一"方法提高了測試速度，而且不存在誤分、拒分區(qū)域；另外，由于其特殊的結(jié)構(gòu)，故有一定的容錯性，分類精度較一般的二叉樹方法高。然而，由于存在自上而下的“誤差積累〞現(xiàn)象是層次結(jié)構(gòu)固有弊端，故DAG-SVMS也逃脫不掉。即如果在某個結(jié)點(diǎn)上發(fā)生了分類錯誤，那么會把分類錯誤延續(xù)到該結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)上.2.4、決策樹方法決策樹的根本思想是從根節(jié)點(diǎn)開始，采用某種方法將該節(jié)點(diǎn)所包含的類別劃分為兩個子類，然后再對兩個子類進(jìn)一步劃分，如此循環(huán)，直到子類中只包含一個類別為止，這樣，就得到了一個倒立的二叉樹。最后，在二叉樹各決策節(jié)點(diǎn)訓(xùn)練支持向量機(jī)分類器，實(shí)現(xiàn)對識別樣本的分類。決策樹支持向量機(jī)多分類方法有很多種，不同方法的主要區(qū)別在于設(shè)計樹結(jié)構(gòu)的方法不同。完全二叉樹結(jié)構(gòu)分類時使用的平均分類器數(shù)目為log2k，偏二叉樹使用的平均分類器數(shù)為(k+1)／2-1／k，具有其他層次結(jié)構(gòu)的二叉樹使用的分類器平均值介于二者之間。完全二叉樹分類時所需要的分類器數(shù)目最少，因此具有較少支持向量的完全二叉樹的分類器速度也是較快的。2.5、糾錯輸出編碼法〔ECOC〕對于K類分類問題，可以根據(jù)不同方法構(gòu)造一系列的兩類分類問題，對于每個兩類分類問題可以建立一決策函數(shù)。共得到L個決策函數(shù)，如果這些決策函數(shù)完全正確，K類中的每一類都對應(yīng)一個元素為-1或+1的長度為L的數(shù)列，按照K類中的第一類、第二類，...，第K類的順序，把這些數(shù)列排列起來，便可得到一個K行L列的編碼矩陣，假設(shè)要判斷一個測試輸入點(diǎn)的歸屬，首先用所得到的L個決策函數(shù)，得到一個元素為-l或l的長度為L的數(shù)列，然后將此數(shù)列與先前得到矩陣比擬，相應(yīng)于矩陣中有一行且僅有一行向與此數(shù)列相同，這個行數(shù)就是輸入點(diǎn)的歸屬類；假設(shè)矩陣中沒有一行與該數(shù)列相同，可以通過計算漢明距離找出最近的一行，改行對應(yīng)的類別即為該點(diǎn)的類別。三、SVM在Matlab中的應(yīng)用Matlab有自帶的支持向量機(jī)算法，但存在一定的局限性，因此安裝了臺灣大學(xué)林智仁(LinChih-Jen)教授等開發(fā)的SVM模式識別與回歸的軟件包libsvm。3.1、libsvm工具箱和Matlab自帶svm算法差異下面先比照一下libsvm工具箱和Matlab自帶的svm算法的差異：(1)MATLAB自帶的svm實(shí)現(xiàn)函數(shù)僅有的模型是C-SVC(C-supportvectorclassification)；而libsvm工具箱有C-SVC〔正負(fù)樣本采用不同的代價權(quán)值〕,nu-SVC(nu-supportvectorclassification),one-classSVM(distributionestimation),epsilon-SVR(epsilon-supportvectorregression),nu-SVR(nu-supportvectorregression)等多種模型可供使用。(2)MATLAB自帶的svm實(shí)現(xiàn)函數(shù)僅支持分類問題，不支持回歸問題；而libsvm不僅支持分類問題，亦支持回歸問題。(3)MATLAB自帶的svm實(shí)現(xiàn)函數(shù)僅支持二分類問題，多分類問題需按照多分類的相應(yīng)算法編程實(shí)現(xiàn)；而libsvm采用1v1算法支持多分類。(4)MATLAB自帶的svm實(shí)現(xiàn)函數(shù)采用RBF核函數(shù)時無法調(diào)節(jié)核函數(shù)的參數(shù)gamma，貌似僅能用默認(rèn)的；而libsvm可以進(jìn)行該參數(shù)的調(diào)節(jié)。(5)libsvm中的二次規(guī)劃問題的解決算法是SMO；而MATLAB自帶的svm實(shí)現(xiàn)函數(shù)中二次規(guī)劃問題的解法有三種可以選擇：經(jīng)典二次方法；SMO；最小二乘。3.2、libsvm訓(xùn)練函數(shù)及結(jié)果參數(shù)說明libsvm在訓(xùn)練model的時候，需要用到svmtrain函數(shù)，調(diào)用方法如下：m=svmtrain(y,x,'-s0-t2-c1-g1')；其中Y為訓(xùn)練樣本的類別，X為對應(yīng)的訓(xùn)練樣本，'-s0-t2-c1-g1'是對參數(shù)的設(shè)置，下面進(jìn)行詳細(xì)說明：〔1〕-ssvm類型：SVM設(shè)置類型(默認(rèn)0)0--C-SVC1--v-SVC2–一類SVM3--e-SVR4--v-SVR〔2〕-t核函數(shù)類型：核函數(shù)設(shè)置類型(默認(rèn)2)0–線性：u'v1–多項式：(r*u'v+coef0)^degree2–RBF函數(shù)：exp(-gamma|u-v|^2)3–sigmoid：tanh(r*u'v+coef0)〔3〕-ddegree：核函數(shù)中的degree設(shè)置(針對多項式核函數(shù))(默認(rèn)3)-gr(gama)：核函數(shù)中的gamma函數(shù)設(shè)置(針對多項式/rbf/sigmoid核函數(shù))(默認(rèn)1/k)-rcoef0：核函數(shù)中的coef0設(shè)置(針對多項式/sigmoid核函數(shù))((默認(rèn)0)-ccost：設(shè)置C-SVC，e-SVR和v-SVR的參數(shù)(損失函數(shù))(默認(rèn)1)-nnu：設(shè)置v-SVC，一類SVM和v-SVR的參數(shù)(默認(rèn)0.5)-pp：設(shè)置e-SVR中損失函數(shù)p的值(默認(rèn)0.1)-mcachesize：設(shè)置cache內(nèi)存大小，以MB為單位(默認(rèn)40)-eeps：設(shè)置允許的終止判據(jù)(默認(rèn)0.001)-hshrinking：是否使用啟發(fā)式，0或1(默認(rèn)1)-wiweight：設(shè)置第幾類的參數(shù)C為weight*C(C-SVC中的C)(默認(rèn)1)-vn:n-fold交互檢驗?zāi)Ｊ?，n為fold的個數(shù)，必須大于等于2其中-g選項中的k是指輸入數(shù)據(jù)中的屬性數(shù)。option-v隨機(jī)地將數(shù)據(jù)剖分為n部。通過訓(xùn)練得到的模型m中包含參數(shù)的意義如下：structsvm_model{structsvm_parameterparam;/*parameter*/intnr_class;/*numberofclasses,=2inregression/oneclasssvm*/intl;/*total#S