人工智能大作業(yè)

歷密毛了秤故欣孝

研究報(bào)告

題目支持向量機(jī)學(xué)習(xí)報(bào)告

學(xué)號___________________________

學(xué)生_________________________

支持向量機(jī)學(xué)習(xí)報(bào)告

支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，

根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度）和學(xué)習(xí)能力（即無錯(cuò)

誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力。支持向量機(jī)

SVM（SupportVectorMachine）是AT&TBell實(shí)驗(yàn)室的V.Vapnik提出的針對分類和回歸問題

的統(tǒng)計(jì)學(xué)習(xí)理論。由于SVM方法具有許多優(yōu)點(diǎn)和有前途的實(shí)驗(yàn)性能，該技術(shù)已成為機(jī)器學(xué)

習(xí)研究領(lǐng)域中的熱點(diǎn)，并取得很理想的效果，如人臉識別、手寫體數(shù)字識別和網(wǎng)頁分類等。

1原理及方法

SVM根據(jù)問題的復(fù)雜性可以分為線性可分SVM和非線性可分SVM,其基本原理如下:

在進(jìn)行文本分類的時(shí)候，每一個(gè)樣本由一個(gè)向量（就是那些文本特征所組成的向量）和一個(gè)

標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類別）組成。如下：Di=（xi,yi）xi就是文本向量（維數(shù)很高）,

yi就是分類標(biāo)記。在二元的線性分類中，這個(gè)表示分類的標(biāo)記只有兩個(gè)值，1和-1（用來

表示屬于還是不屬于這個(gè)類）。有了這種表示法，可以定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔：

yi（wxi+b）如果某個(gè)樣本屬于該類別的話，那么wxi+b>0（因?yàn)槲覀兯x的g（x）=wx+b就通過

大于0還是小于0來判斷分類），而yi也大于0；若不屬于該類別的話，那么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,間隔就可以寫成

4=3e叫

11*11

當(dāng)用歸一化的W和b代替原值之后的間隔叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到

超平面的歐氏距離，簡稱幾何間隔為“距離”。同樣一個(gè)點(diǎn)的集合（就是一組樣本）到某個(gè)超

平面的距離為此集合中離超平面最近的點(diǎn)的距離。下面這張圖展示出了幾何間隔的現(xiàn)實(shí)含

義：

H是分類面，而Hl和H2是平行于H,且過離H最近的兩類樣本的直線，H1與H,

H2與H之間的距離就是幾何間隔。

間隔：8=y(wx+b)=|g(x)|

幾何間隔:3而3

可以看出8=||W||^RM?幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||

完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間

隔（例如固定為1）,尋找最小固網(wǎng)|。

而凡是求一個(gè)函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個(gè)規(guī)劃

問題），又由于找最大值的問題總可以通過加一個(gè)負(fù)號變?yōu)檎易钚≈档膯栴}，因此我們下面

討論的時(shí)候都針對找最小值的過程來進(jìn)行。一個(gè)尋優(yōu)問題最重要的部分是目標(biāo)函數(shù)，顧名思

義，就是指尋優(yōu)的目標(biāo)。例如我們想尋找最小的||w||這件事，就可以用下面的式子表示:

但實(shí)際上對于這個(gè)目標(biāo)，常常使用另一個(gè)完全等價(jià)的目標(biāo)函數(shù)來代替，那就是:

當(dāng)||w『到最小時(shí)，||w||也達(dá)到最小，反之亦然（前提當(dāng)然是||w||描述的是向量的長度,

因而是非負(fù)的）。

2

min7Mb111^|I

s.t./）（皿,工⑴4-6）>1,i=1,...,m

將約束條件改寫為：

^i（w）=—/（小工⑴4-6）4-1<0.

從KKT條件得知只有函數(shù)間隔是I（離超平面最近的點(diǎn)）的線性約束式前面的系數(shù)

%>°,也就是說這些約束式防（吟=°,對于其他的不在線上的點(diǎn)的（M<°）,極值不會

在他們所在的范圍內(nèi)取得，因此前面的系數(shù)％=0.

實(shí)線是最大間隔超平面，假設(shè)x號的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間

隔是1的點(diǎn)，那么他們前面的系數(shù)%>°，其他點(diǎn)都是叫二°。這三個(gè)點(diǎn)稱作支持向量。構(gòu)

造拉格朗日函數(shù)如下：

1m

￡（w,6,a）=-||u?||2-52［嚴(yán)（蘇］⑴+b）-1］.

1=1

按照對偶問題的求解步驟來進(jìn)行，

d*=maxmin￡(w,a,/3)

ot,0:ai>Ow

首先求解￡(出，兒。)的最小值，對于固定的，，￡?，b，a)的最小值只與w和

b有關(guān)。對w和b分別求偏導(dǎo)數(shù)。

m

Vu￡(w,b.a)=w-^2=0

i=l

Qm

沅￡(-b,a)=￡a涔⑴=0.

t=i

并得到

m

w=^2⑴工⑴.

t=l

將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值(目標(biāo)函數(shù)是凸

函數(shù))

代入后，化簡過程如下:

m

2(or(x)

￡(w,b,a)=^||w||—ax[y(wx4-h)—1]

i=l

mmm.

rT

=iww—〉:aty^wx?)-W。4《力+〉:%

i=li=li=l

mmmm

)T

=\wr):%丫(')％0—〉:aty^wx^—):ctty^b+):at

t=li=ii=it=i

mmmm

=wr):a?y(i)x")—T>ay(ox(o—W

w￡aty^b+'at

i=lf=l1=1i=l

mmm

T，

—^-w、:%、(，)*(?)—、:aty^b+:ai

i=lt=li=l

mmm

-^WT2。少⑸“⑸一b?a，y")+￡%

i=l4=1￡=1

\Tmmtn

1a.y(，)4(，))2b):a'yG)+):a,

2/i=l4=1i=l

mmmm

=—eaty(O(x(0)r2%〃“)”)~b^,+>.

i=li=lf=li=l

mmm

=—):a?y")(""))「勺yS%5—b):a?y")+):

X=1J=1i=l*=1

mmm

yQ)yO)a?/(x(i))rxS—b):

t=l

最后得到

mATnm

￡(w,b,a)=^27—5^2/)/4%(工⑴V工⑶—6^2。力⑴.

i=lij=li=l

由于最后一項(xiàng)是0,因此簡化為

m1m

￡(w,b.a)=^2I—5y⑴/4%(工⑴),](力.

i=lij=l

梏臼曷內(nèi)和(n"V赤〒%(“")，/)》?

將向室內(nèi)積'，表不為''f

此時(shí)的拉格朗日函數(shù)只包含了變量°、然而我們求出了『才能得到W和b。

d*=maxmin￡(w,a.0]

接著是極大化

a,0-.ai>Qw

m〔m

maxnIV(a)=6-5工^

t=lij=l

a,>0,￡=1,,?,,m

m

⑴=0,

i=l

首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對

于所有的i,d色'）＜°。因此，一定存在w'a*使得k是原問題的解，&?是對偶問題的解。

w=^2

如果求出了%,根據(jù)，-1即可求出w（也是W,原問題的解）。然后

T（,）1

maxi.y（i）=_1w*x+migwiLiw*1⑴

b=--------------------------2------------------------?

即可求出bo即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。

由于前面求解中得到

IB

W=W,嚴(yán)

考慮+根據(jù)求解得到的％,代入前式得到

u^x+b=（＞:62/。）工⑴）x+b

771

=）：6y⑴（了⑴,力+b.

i=i

也就是說，以前新來的要分類的樣本首先根據(jù)W和b做一次線性運(yùn)算，然后看求的

結(jié)果是大于0還是小于0,來判斷正例還是負(fù)例?，F(xiàn)在有了，，我們不需要求出w,只需將新

來的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。我們從KKT條件中得到，只有支持向量

的%>°,其他情況％二°。因此，只需求新來的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。

希望將得到的特征映射后的特征應(yīng)用于SVM分類，而不是最初的特征。這樣，我們需

要將前面A公式中的內(nèi)積從映射到將特征映射到

高維空間后，往往就可分了。將核函數(shù)形式化定義，如果原始特征內(nèi)積是<x,z>,映射后

為那么定義核函數(shù)（Kernel）為

=0（x）p（z）

只需先計(jì)算O（x）,然后計(jì)算OUAqG）即可，然而這種計(jì)算方式是非常低效的。比如最

初的特征是n維的，我們將其映射到n’維，然后再計(jì)算，這樣需要0（屋）的時(shí)間。先看一個(gè)

例子，假設(shè)x和z都是n維的，

K(x,z)=(xTz)2

展開后，得

K(x，z)=GW==￡￡

及工產(chǎn)巧

/\/=1//=!

■n

，=1J=1

可以只計(jì)算原始特征x和z內(nèi)積的平方（時(shí)間復(fù)雜度是O（n））,就等價(jià)與計(jì)算映射后特

征的內(nèi)積。也就是說我們不需要花O（M）時(shí)間了。

如果映射函數(shù)（n=3時(shí)），根據(jù)上面的公式，得到

工112

工同3

工211

。(工)=工212

工213

工311

工312

工313

也就是說核函數(shù)KU*)=只能在選擇這樣的?作為映射函數(shù)時(shí)才能夠等價(jià)于映

射后特征的內(nèi)積。

再看一個(gè)核函數(shù)

K(1,z)=(xTz4-c)2

nn

=￡(工十叼)(2乃)+y^(y/2cxj)(\/2czi)+c2.

ij=li=l

對應(yīng)的映射函數(shù)(n=3時(shí))是

工㈤

W2

工113

1212

工213

M*=工311

工312

13工3

\/2CTI

\/2cr2

\/2C^3

c

(n+d)

更一般地，核函數(shù)KG")=(1'2十°尸對應(yīng)的映射后特征維度為'd二由于計(jì)算的

是內(nèi)積，我們可以想到IR中的余弦相似度，如果x和z向量夾角越小，那么核函數(shù)值越大,

反之，越小。因此，核函數(shù)值是GOO和。G)的相似度。

再看另外一個(gè)核函數(shù)

值一z||）

K（工,z）=exp

2/J-

這時(shí)，如果x和z很相近(11?-1||*0)；那么核函數(shù)值為1,如果X和z相差很大

(||xz||?0),那么核函數(shù)值約等于0。由于這個(gè)函數(shù)類似于高斯分布，因此稱為高斯核

函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡稱RBF)。它能夠把原始特征映射到無窮

維。

既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1,下面的圖說明在低維線性

不可分時(shí)，映射到高維后就可分了，使用高斯核函數(shù)。

注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時(shí)候我們使用SVM學(xué)習(xí)出w和

b,新來樣本x的話，我們使用w'x+占來判斷，如果值大于等于1,那么是正類，小于等

于是負(fù)類。在兩者之間，認(rèn)為無法確定。如果使用了核函數(shù)后，就變成了

wTx+b=($2工+b

m

=￡/嚴(yán)(a?⑴㈤+b.

i=l

只需將(工⑴,*＞替換成

給定m個(gè)訓(xùn)練樣本卜⑴力二力…..7）,每一個(gè)”）對應(yīng)一個(gè)特征向量。那么，將任意兩

個(gè)和X。）帶入K中，計(jì)算得到吊戶K（X（4W>）。i可以從1到m,j可以從1到m,這樣

可以計(jì)算出m*m的核函數(shù)矩陣（KernelMatrix）。

如果假設(shè)K是有效地核函數(shù)，那么根據(jù)核函數(shù)定義

O=K（x?.W）=^（x?Mx^）=0（~）76叼=?2.即）=0

可見，矩陣K應(yīng)該是個(gè)對稱陣。首先使用符號單式0來表示映射函數(shù)@0）的第k維屬性

值。那么對于任意向量z,得

ZTKZ=ZiKijZj

=￡￡Zi0（工⑴）“（工。）區(qū)

=￡￡zt￡0k（工⑴）久（工⑶）Zj

ijk

=￡￡￡為0M]⑴）彌（工⑶）zj

kij

=.（z石"（叫）

>0.

最后一步和前面計(jì)算K（x，z）>時(shí)類似。如果K是個(gè)有效的核函數(shù)（即K（x，z）和

。0尸。（2）等價(jià)），那么，在訓(xùn)練集上得到的核函數(shù)矩陣K應(yīng)該是半正定的（KN°）

這樣得到一個(gè)核函數(shù)的必要條件：

K是有效的核函數(shù)==>核函數(shù)矩陣K是對稱半正定的。

這個(gè)條件也是充分的，由Mercer定理來表達(dá)。

I----------------------------------------------------------------------------------

Mercer定理：

如果函數(shù)K是R=XR1sT工上的映射（也就是從兩個(gè)n維向量映射到實(shí)數(shù)域）。那么如

果K是一個(gè)有效核函數(shù)（也稱為Mercer核函數(shù)），那么當(dāng)且僅當(dāng)對于訓(xùn)練樣例

卜"…五（7},其相應(yīng)的核函數(shù)矩陣是對稱半正定的。

Mercer定理表明為了證明K是有效的核函數(shù)，那么不用去尋找。，而只需要在訓(xùn)練集

上求出各個(gè)向，然后判斷矩陣K是否是半正定（使用左上角主子式大于等于零等方法）即

可。

把一個(gè)本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就

像下圖這樣：

mar2in=2/

圓形和方形的點(diǎn)各有成千上萬個(gè)?，F(xiàn)在想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集

多了一篇文章，映射到高維空間以后（當(dāng)然，也使用了相同的核函數(shù)），也就多了一個(gè)樣本

點(diǎn)，但是這個(gè)樣本的位置是這樣的：

o

oo

□

o

就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使

得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點(diǎn)線性不可分）叫

做“近似線性可分''的問題。

但這種對噪聲的容錯(cuò)性是人的思維帶來的。由于原本的優(yōu)化問題的表達(dá)式中，確實(shí)要考

慮所有的樣本點(diǎn)，在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距

離，是非負(fù)的，像上面這種有噪聲的情況會使得整個(gè)問題無解。這種解法其實(shí)也叫做“硬間

隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值0

仿照人的思路，允許一些點(diǎn)到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各

點(diǎn)的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達(dá)形式的簡潔。

我們原先對樣本點(diǎn)的要求是：

yi[（wXi^b]>\是樣本數(shù)）

意思是說離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就給1這個(gè)

硬性的閾值加一個(gè)松弛變量，即允許

以0叫）+6]20=1,2,...,1）（1是樣本數(shù)）

因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這

種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著我們放棄了對這些點(diǎn)的精確分類，而

這對我們的分類器來說是種損失。但是放棄這些點(diǎn)也帶來了好處，那就是使分類面不必向這

些點(diǎn)的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。

顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。

回顧我們原始的硬間隔分類對應(yīng)的優(yōu)化問題：

min

subjectto其[（叫）+叫-]>。修12…J）Q是樣本數(shù)）

||w||2就是目標(biāo)函數(shù)（當(dāng)然系數(shù)可有可無），希望它越小越好，因而損失就必然是一個(gè)能

使之變大的量（能使它變小就不叫損失了，我們本來就希望目標(biāo)函數(shù)值越小越好）。那如何

/

來衡量損失，￡或

/=|

其中1都是樣本的數(shù)目。把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost,

也就是libSVM的諸多參數(shù)中的C）,原來的優(yōu)化問題就變成了下面這樣：

minA||w||24r￡<

sabjedto乂[（叫））句*1一?[=1>2?…J）（1是樣本數(shù)）（式1）

G。

一是并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對應(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)的松弛變量

的和一定時(shí)，定的C越大，對目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著不愿意放棄這些離群

點(diǎn)，最極端的情況是把C定為無限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成

無限大，問題變成無解，這就退化成了硬間隔問題。

四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問題在解的時(shí)候，C是一個(gè)必須事先指定的

值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如果不

夠好，換一個(gè)C的值，再解一次優(yōu)化問題，得到另一個(gè)分類器，再看看效果，如此就是一

個(gè)參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是

定值。

從大的方面說優(yōu)化問題解的過程，就是先試著確定一下W,也就是確定了前面圖中的三

條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直

線(你可以看到，分類的直線位置如果移動了，有些原來離群的點(diǎn)會變得不再離群，而有的

本來不離群的點(diǎn)會變成離群點(diǎn))，再把目標(biāo)函數(shù)的值算一算，如此往復(fù)(迭代)，直到最終找

到目標(biāo)函數(shù)最小時(shí)的W。

松弛變量也就是解決線性不可分問題的方法,核函數(shù)的引入也是為了解決線性不可分的

問題。其實(shí)兩者還有些不同。以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞郑?/p>

無論怎么找分類平面，總會有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果

仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)(就是達(dá)到了近似線性可分

的狀態(tài))，此時(shí)再用松弛變量處理那些少數(shù)“冥頑不化”的離群點(diǎn)，更加簡單有效。

對比復(fù)雜的推導(dǎo)過程，SVM的思想確實(shí)簡單。是在樣本中去找分隔線，為了評判哪條

分界線更好，引入了幾何間隔最大化的目標(biāo)。之后解決目標(biāo)函數(shù)的最優(yōu)化問題。在解決最優(yōu)

化的過程中，發(fā)現(xiàn)了w可以由特征向量內(nèi)積來表示，進(jìn)而發(fā)現(xiàn)了核函數(shù)，僅需要調(diào)整核函

數(shù)就可以將特征進(jìn)行低維到高維的變換，在低維上進(jìn)行計(jì)算，實(shí)質(zhì)結(jié)果表現(xiàn)在高維上。由于

并不是所有的樣本都可分，為了保證SVM的通用性，進(jìn)行了軟間隔的處理，導(dǎo)致的結(jié)果就

是將優(yōu)化問題變得更加復(fù)雜，然而驚奇的是松弛變量沒有出現(xiàn)在最后的目標(biāo)函數(shù)中。最后的

優(yōu)化求解問題，也被拉格朗日對偶和SMO算法化解，使SVM趨向于完美。

SVM有如下主要幾個(gè)特點(diǎn)：

(1)非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映

射；

(2)對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo)，最大化分類邊際的思想是SVM方法的核

心；

(3)支持向量是SVM的訓(xùn)練結(jié)果，在SVM分類決策中起決定作用的是支持向量。

(4)SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測度及大數(shù)

定律等，因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看，它避開了從歸納到演繹的傳統(tǒng)過程,實(shí)現(xiàn)了

高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”，大大簡化了通常的分類和回歸等問題。

(5)SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定，計(jì)算的復(fù)雜性取決于支持向量的數(shù)目，

而不是樣本空間的維數(shù)，這在某種意義上避免了“維數(shù)災(zāi)難”。

(6)少數(shù)支持向量決定了最終結(jié)果，這不但可以幫助我們抓住關(guān)鍵樣本、“剔除”大量冗余樣本,

而且注定了該方法不但算法簡單，而且具有較好的“魯棒”性。這種“魯棒”性主要體現(xiàn)在：

①增、刪非支持向量樣本對模型沒有影響；

②支持向量樣本集具有一定的魯棒性；

③有些成功的應(yīng)用中,SVM方法對核的選取不敏感

兩個(gè)不足：

(1)SVM算法對大規(guī)模訓(xùn)練樣本難以實(shí)施

由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計(jì)算(m為

樣本的個(gè)數(shù))，當(dāng)m數(shù)目很大時(shí)該矩陣的存儲和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間。

針對以上問題的主要改進(jìn)有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges

等的PCGC、張學(xué)工的CSVM以及OLMangasarian等的SOR算法

(2)用SVM解決多分類問題存在困難

經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中，一般要解決

多類的分類問題?？梢酝ㄟ^多個(gè)二類支持向量機(jī)的組合來解決。主要有一對多組合模式、一

對一組合模式和SVM決策樹；再就是通過構(gòu)造多個(gè)分類器的組合來解決。主要原理是克服

SVM固有的缺點(diǎn)，結(jié)合其他算法的優(yōu)勢，解決多類問題的分類精度。如：與粗集理論結(jié)合,

形成一種優(yōu)勢互補(bǔ)的多類問題的組合分類器。

2試驗(yàn)及分析

2.llibsvm自帶例子

1用heart_scale測試

?loadheart_scale.mat

model=svmtrain(heart_scale_1abe1,heart_scale_inst,'-c1-g0.07,);

[predict_label,accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model);

Accuracy=86.6667%(234/270)(classification)

?model=svmtrain(heart_scale_label,heart一seale_inst,'-c1000-g0.07')：

[predict_label,accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model);

Accuracy=100%(270/270)(classification)

調(diào)整c,分類準(zhǔn)確率會變化，但是，變?yōu)?00%,我認(rèn)為可能是測試數(shù)據(jù)和訓(xùn)練數(shù)據(jù)是

相同的數(shù)據(jù)集引起的。

2不同的參數(shù)t

I核函數(shù)類型：核函數(shù)設(shè)置類型(默認(rèn)2)

0-線性：u'v

1-多項(xiàng)式：(r*u'v+coefO)Adegree

2-RBF函數(shù)：exp(-r|u-v|A2)

3-sigmoid：tanh(r*u'v+coefO)

不同的核函數(shù)對分類準(zhǔn)確率的影響。

?loadheart_scale.mat

model=svmtrain(heart_scale_label,heart_scale_inst,'-c1-g0.07-tO');

[predict_label3accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model);

Accuracy=84.8148%(229/270)(classification)

?loadheart_scale.mat

model=svmtrain(heart_scale_label,heart_scale_inst,,-c1-g0.07-t1');

[predict_label,accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model):

Accuracy=85.5556%(231/270)(classification)

?model=svmtrain(heart_scale_label,heart_scale_inst,r-c1-g0.07-t2');

[predict_label,accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model);

Accuracy=86.6667%(234/270)(classification)

?model=svmtrain(heart_scale_label,heart_scale_inst,,-c1-g0.07-t3');

[predict_label3accuracy,dec_values]=svmpredict(heart_scale_label,heart_scale_inst,model);

Accuracy=85.1852%(230/270)(classification)

對于heart_scale不同的核函數(shù)對分類準(zhǔn)確率的影響不大,rbf核函數(shù)的性能最好。

3調(diào)整c和g以找到最優(yōu)的c和g使分類正確率最高

?bestcv=0;

forlog2c=-5:5,

forlog2g=-5:5,

cmd=U-v5-c7,num2str(2Alog2c),'-gnun2str(2*log2g)]：

cv=svmtrain(heart_scale_label,heart_scale_inst,cmd);

if(cv>=bestcv),

bestcv=cv;bestc=2*log2c;bestg=2*log2g;

end

end

end

fprintf(*%g%g%g(bestc=%g,g=%g,rate=%g)\n>,log2c,log2g,cv,bestc,bestg,bestcv);

cmd=-cnum2str(bestc),'-gnum2str(bestg)];

model=svmtrain(heart_scale_label,heart_scale_inst,cmd);

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=61.mix

CrossValidationAccuracy=63.7037X

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%：

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=65.9259%

CrossValidationAccuracy=56.2963%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=82.2222%

CrossValidationAccuracy=81.8519%

CrossValidationAccuracy=80.7407%

CrossValidationAccuracy=80%

CrossValidationAccuracy=79.6296%

CrossValidationAccuracy=75.1852%

CrossValidationAccuracy=63.3333%

CrossValidationAccuracy=57.037%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=83.3333%

CrossValidationAccuracy=82.2222%

CrossValidationAccuracy=79.6296%

CrossValidationAccuracy=77.7778%

CrossValidationAccuracy=76.6667%

CrossValidationAccuracy=75.1852%

CrossValidationAccuracy=67.037%

CrossValidationAccuracy=61.1111%

CrossValidationAccuracy=57.4074%

CrossValidationAccuracy=55.5556%

CrossValidationAccuracy=77.7778%

CrossValidationAccuracy=76.2963%

CrossValidationAccuracy=75.9259%

CrossValidationAccuracy=75.5556%

CrossValidationAccuracy=74.8148%

CrossValidationAccuracy=74.8148%

CrossValidationAccuracy=71.1111%

CrossValidationAccuracy=67.037%

CrossValidationAccuracy=61.1111%

CrossValidationAccuracy=57.4074%

CrossValidationAccuracy=55.5556%

5555.5556(bestc=l,g=0.03125,rate=83.3333)

調(diào)整c和g得到c=l和g=0.03125,分類正確率最高。

2.2wine數(shù)據(jù)集實(shí)驗(yàn)

I測試

?loadwine_SVM

?train_wine=[wine(1:30,:)：wine(60:95j:);wine(131:153,:)];

train_wine_labels=[wine_labels(1:30);wine_labels(60:95);wine_labels(131:153)]:

test_wine=[wine(31:59,:);wine(96:130,:);wine(154:178,:)];

test_wine_labels=[wine_labels(31:59);wine_labels(96:130);wine_labels(154:178)];

?model=svmtrain(train_wine_labels,train_wine,'-c2-g0.02-t2'):

[predict_label,accuracy]=svmpredict(test_wine_labels,test_wine,model);

Accuracy=49.4382%(44/89)(classification)

wine數(shù)據(jù)標(biāo)簽有三類，各選取一半作為測試集，一半為訓(xùn)練集。準(zhǔn)確率并不好。

2不同的參數(shù)t

t核函數(shù)類型：核函數(shù)設(shè)置類型（默認(rèn)2）

0-線性：u，v

1-多項(xiàng)式：(r*u'v+coefO)八degree

2-RBF函數(shù)：exp(-r|u-v|A2)

3-sigmoid：tanh(r*u'v+coefl))

不同的核函數(shù)對分類準(zhǔn)確率的影響。

?model=svmtrain(train_wine_labels,train_wine,'-c2-g0.02-tO');

[predict_label,accuracy]=svmpredict(test_wine_labels,test_vine,model)：

Accuracy=86.5169%(77/89)(classification)

?model=svmtrain(train_wine_labels,train_wine,'-c2-g0.02-t2');

[predict_label,accuracy]=svmpredict(test_wine_labels,test.wine,model);

Accuracy=86.5169%(77/89)(classification)

?model=svmtrain(train_wine_labels,train_wine,'-c2-g0.02-t1');

[predict_label,accuracy]=svmpredict(test_wine_labels,test—Wine,model);

Accuracy=74,1573%(66/89)(classification)

?model=svmtrain(train_wine_labels,train_wine,'-c2-g0.02-t3')：

[predict_label,accuracy]=svmpredict(test_wine_labels,test_wine,model);

Accuracy=71.9101%(64/89)(classification)

多項(xiàng)式和sigmoid函數(shù)的訓(xùn)練結(jié)果最差。

3調(diào)整c和g以找到最優(yōu)的c和g使分類正確率最高。

?bestcv=0;

forlog2c=-10:10,

forlog2g=-10:10j

cmd=f-v5-cnuni2str(2*log2c),'-gnum2str(2"log2g)];

cv=svmtrain(train_wine_labels,train.wine,cmd);

if(cv>=bestcv),

bestcv=cv;bestc=2*log2c;bestg=2*log2g;

end

end

end

yvuI、>上▲——、4WA、AAVyj-JAvaAAVAZV

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

CrossValidationAccuracy=40.4494%

(bestc=64,g=0.000976563,rate=94.382)

Accuracy=86.5169%(77/89)(classification)

調(diào)整c和g得到c=64和g=0.00097,分類正確率最高。

3圖形化

3結(jié)論及改進(jìn)

SVM有如下主要幾個(gè)特點(diǎn)：（1）非線性映射是SVM方法的理論基礎(chǔ),SVM用內(nèi)積核函

數(shù)代替向高維空間的非線性映射；（2）對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo)，最大化

分類間隔是SVM方法的核心；（3）支持向量是SVM的訓(xùn)練結(jié)果，在SVM分類決策中起決定

作用（4）SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的小樣本學(xué)習(xí)方法。它基本上不涉及概率測度及大數(shù)

定律等，因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看，它避開了從歸納到演繹的傳統(tǒng)過程,實(shí)現(xiàn)了

高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”,大大簡化了通常的分類和回歸等問題；（5）SVM

的最終決策函數(shù)只由少數(shù)的支持向量所確定，計(jì)算的復(fù)雜性取決于支持向量的數(shù)目，而不是樣

本空間的維數(shù)，這在某種意義上避免了“維數(shù)災(zāi)難”。（6）少數(shù)支持向量決定了最終結(jié)果，這不

但可以幫助我們抓住關(guān)鍵樣本、“剔除”大量冗余樣本，而且注定了該方法不但算法簡單，而且

具有較好的“魯棒”性。

SVM不足：（1）訓(xùn)練好SVM分類器后,得到的支持向量被用來構(gòu)成決策分類面。對于

大規(guī)模樣本集問題,SVM訓(xùn)練得到的支持向量數(shù)目很大，則進(jìn)行分類決策時(shí)的計(jì)算代價(jià)很大。

（2）用SVM解決多分類問題存在困難，經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，

要解決多類的分類問題?？梢酝ㄟ^多個(gè)二類支持向量機(jī)的組合來解決。

要針對不同的問題選擇不同的核函數(shù)。標(biāo)準(zhǔn)的SVM對噪聲是不具有魯棒性的,如何選

擇合適的目標(biāo)函數(shù)以實(shí)現(xiàn)魯棒性是至關(guān)重要的。要根據(jù)具體問題選擇合適的核函數(shù)及懲罰因

子，多次實(shí)驗(yàn)選擇最好的結(jié)果。一個(gè)好的分類器固然重要，但前期的數(shù)據(jù)預(yù)處理亦很重要。

當(dāng)數(shù)據(jù)預(yù)處理的好的話，特征提取的好的話，分類器的影響不會占很大比重。SVM算法參數(shù)選

擇可能是憑借經(jīng)驗(yàn)、實(shí)驗(yàn)對比、大范圍的搜尋或者利用軟件包提供的交互檢驗(yàn)功能進(jìn)行尋優(yōu)。

參考文獻(xiàn)

IChih-JenLinDepartmentofComputerScienceNationalTaiwanUniversityAPracticalGuideto

SupportVectorClassification

2Chih-ChungChangandChih-JenLinDepartmentofComputerScienceNationalTaiwan

University,Taipe