支持向量機(jī)原理

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第3章 支持向量機(jī)基礎(chǔ)By Dean 支持向量機(jī)（Support Vector Machies）是由Vapnik等人于1995年提出來(lái)的。之后隨著統(tǒng)計(jì)理論的發(fā)展，支持向量機(jī)也逐漸受到了各領(lǐng)域研究者的關(guān)注，在很短的時(shí)間就得到很廣泛的應(yīng)用。支持向量機(jī)是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的，利用有限的樣本所提供的信息對(duì)模型的復(fù)雜性和學(xué)習(xí)能力兩者進(jìn)行了尋求最佳的折衷，以獲得最好的泛化能力。SVM的基本思想是把訓(xùn)練數(shù)據(jù)非線性的映射到一個(gè)更高維的特征空間（Hilbert空間）中，在這個(gè)高維的特征空間中尋找到一個(gè)超平面使得正例和反例兩者間的隔離邊緣被最大化。S

2、VM的出現(xiàn)有效的解決了傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)結(jié)果選擇問(wèn)題、局部極小值、過(guò)擬合等問(wèn)題。并且在小樣本、非線性、數(shù)據(jù)高維等機(jī)器學(xué)習(xí)問(wèn)題中表現(xiàn)出很多令人注目的性質(zhì)，被廣泛地應(yīng)用在模式識(shí)別，數(shù)據(jù)挖掘等領(lǐng)域(張學(xué)工 2000；崔偉東2001)。支持向量機(jī)可以用于分類和回歸問(wèn)題，本章著重介紹分類相關(guān)的知識(shí)。3.1 SVM的基本思想3.1.1最優(yōu)分類面SVM是由線性可分情況的最優(yōu)分類面發(fā)展而來(lái)的，用于兩類問(wèn)題的分類。下面用一個(gè)二維兩類問(wèn)題來(lái)說(shuō)明SVM基本思想(白鵬 等，2008)。圖3.1 最優(yōu)超平面示意圖C1和C2代表兩類數(shù)據(jù)樣本，各樣本在二維中顯示如圖3.1， 圖中的直線P0,P1就是分類函數(shù)。如果一個(gè)線性函數(shù)就

3、完全可以把兩類所有樣本分開，那么就稱這些數(shù)據(jù)是線性可分的；否則稱非線性可分。假設(shè)兩類線性可分的訓(xùn)練數(shù)據(jù)樣本x1,y1,x2,y2,xN,yN, xiRd(d代表樣本xi的長(zhǎng)度), yi+1,-1, i=1,2,N. 其線性判別函數(shù)的一般表達(dá)式是fx=w*x+b, 該函數(shù)對(duì)應(yīng)的分類面方程是：w*x+b=0 (3-1)線性判別函數(shù)的值一般是連續(xù)的實(shí)數(shù)，而分類問(wèn)題需要輸出的是離散值。例如利用數(shù)值-1表示類別C1，而用數(shù)值+1表示類別C2.所有的樣本都只能用數(shù)值-1和+1表示。這時(shí)我們可以通過(guò)設(shè)置一個(gè)閥值，通過(guò)判斷判別函數(shù)的值是大于或者小于這個(gè)閥值來(lái)判斷屬于某一類。若我們?nèi)∵@個(gè)閥值為0，即當(dāng)f(x)0

4、時(shí)，判別樣本為類別C1(即-1)；當(dāng)f(x)0時(shí)，判別樣本為類別C2(即+1).現(xiàn)在將判別函數(shù)進(jìn)行歸一化，使兩類所有樣本都滿足f(x)1，這時(shí)離分類面近的樣本都有f(x)=1。若要對(duì)所有樣本正確分類需滿足，yiw*x+b-10, i=1,N (3-2)這時(shí)分類間隔為2w. 尋求最優(yōu)的分類面即使得分類間隔最大化。可以發(fā)現(xiàn)間隔最大等價(jià)于12w2最小。因此最優(yōu)化分類面問(wèn)題可以表示成如下的約束優(yōu)化問(wèn)題，如下：Min w=12w2 (3-3)約束條件為：yiw*x+b-10, i=1,N (3-4)定義如下Lagrange函數(shù):Lw,b,=12w2-i=1Niyiw*xi+b-1 (3-5)式中，i0為

5、Lagrange乘子。為了求得函數(shù)式(3-5)的最小值，我們對(duì)w,b,分別求導(dǎo)有：Lw=0 w=i=1Niyixi Lb=0 i=1Niyi=0 L=0 iyiw*xi+b-1=0 (3-6)由式(3-6)和(3-2)可將上述的最優(yōu)化分類面的求解問(wèn)題轉(zhuǎn)化為一個(gè)凸二次規(guī)劃尋優(yōu)的對(duì)偶問(wèn)題，如下：Max i=1Ni-12i=1Nj=1Nijyiyj(xi,xj) (3-7)約束條件為：i0i=1Niyi=0 (3-8)這個(gè)二次函數(shù)尋優(yōu)的問(wèn)題存在唯一解，若i*為最優(yōu)解，則：w*=i=1Ni*yixi (3-9)其中i*不為0對(duì)應(yīng)的即為支持向量(Support Vector). 并且最優(yōu)分類面的權(quán)系數(shù)向

6、量是支持向量的線性組合。分類閥值b*可由(3-6)式求得，b*=-12w*, xr+xs (3-10)式中xr,xs分別是兩類中任意支持向量，r,s>0,yr=-1,ys=1.由于除了支持向量外，非支持向量所對(duì)應(yīng)的i=0,所以最優(yōu)分類面函數(shù)可簡(jiǎn)寫為：fx=sgnsvi*yixi,x+b* (3-11)此時(shí)SVM最一般的表達(dá)式已經(jīng)被求得。3.1.2廣義的最優(yōu)分類面但當(dāng)有少數(shù)樣本使得原來(lái)線性可分的問(wèn)題變成不可分問(wèn)題，從而影響了分類器的性能。有時(shí)這少數(shù)的樣本也是噪聲，或是奇異值點(diǎn)，是我們?cè)谌斯?duì)數(shù)據(jù)分類錯(cuò)分的，為了忽略這些點(diǎn)對(duì)分類器的影響，和在經(jīng)驗(yàn)風(fēng)險(xiǎn)和泛化性能之間求得平衡，松弛因子被引入。它

7、容許錯(cuò)分樣本的存在，這時(shí)分類面滿足：yiw*x+b1-i, i=1,N (3-12)當(dāng)0i1時(shí)，樣本xi可以正確分類；當(dāng)i1時(shí)，樣本xi會(huì)被錯(cuò)分。由于松弛因子的引入，式（3-3）的目標(biāo)函數(shù)被改寫為:w,=12w2+Ci=1Ni (3-13)式中C是懲罰因子(一個(gè)正常數(shù)). 此時(shí)，式目標(biāo)函數(shù)凸二次規(guī)劃尋優(yōu)的對(duì)偶問(wèn)題約束條件(3-8)可被變換為如為： 0iCi=1Niyi=0 (3-14)3.2核函數(shù)3.2.1核函數(shù)變換基本思想對(duì)于非線性分類問(wèn)題，在原始空間中最優(yōu)化分類面也許不能得到令人滿意的分類結(jié)果。針對(duì)這種情況，一個(gè)解決的思想是把原始空間中的非線性樣本數(shù)據(jù)投影到某個(gè)更高維的空間中，在高維的空間

8、中尋找一個(gè)最優(yōu)超平面能線性地將樣本數(shù)據(jù)分開，但是這種變化可能非常復(fù)雜。支持向量機(jī)利用核函數(shù)巧妙地解決了這個(gè)問(wèn)題。核函數(shù)變換的基本思想是將一個(gè)n維空間中矢量x映射到更高維的特征空間中去，然后在高維空間中進(jìn)行線性地分類。核函數(shù)變換的基本原理示意圖如圖3.2所示。由（3-7）、（3-11）可看出，都只涉及訓(xùn)練樣本之間的點(diǎn)積運(yùn)算xi,xj。假設(shè)存在一個(gè)非線性映射將Rn空間的樣本映射到更高維的H空間中，即：RnH在特征空間H中構(gòu)造最優(yōu)分類面時(shí)，計(jì)算的過(guò)程中僅使用了空間中的點(diǎn)積xi,xj，而沒(méi)有用到單獨(dú)的xi。如果存在一個(gè)“核函數(shù)”K，且Kxi,xj=xi,xj，那么在訓(xùn)練算法是，我們將僅僅需要使用核函數(shù)

9、K，且不需要知道具體的是什么。這樣在高維空間中只需要進(jìn)行點(diǎn)積運(yùn)算，且這種運(yùn)算是用原來(lái)空間中的函數(shù)實(shí)現(xiàn)的。根據(jù)泛函的相關(guān)理論，只要核函數(shù)Kxi,xj滿足Mercer條件，它就可以對(duì)應(yīng)某一變換空間的點(diǎn)積，這樣就能德奧原輸入空間中對(duì)應(yīng)的非線性算法。圖3.2 核函數(shù)變換示意圖3.2常見核函數(shù)核函數(shù)作為支持向量機(jī)理論的重要的組成部分引起了很多研究者的興趣。常用的滿足Mercer條件的核函數(shù)有線性函數(shù)，多項(xiàng)式函數(shù)，徑向基函數(shù)，Sigmoid函數(shù)等，選擇不同的核函數(shù)可以構(gòu)造不同的支持向量機(jī)(張浩然 2002)。下面對(duì)這四種常見的核函數(shù)進(jìn)行簡(jiǎn)單地介紹.（1） 線性函數(shù)Kx,xi=x,xi（2） 多項(xiàng)式函數(shù)Kx

10、,xi=x,xi+1d（3） 徑向基函數(shù)Kx,xi=exp-x-xi22（4） Sigmoid函數(shù)Kx,xi=tanhvx,xi+a由這四種核函數(shù)可以構(gòu)造出線性SVM、多項(xiàng)式SVM、RBF SVM和感知SVM。滿足Mercer條件核函數(shù)很多，這樣又帶來(lái)另外一個(gè)問(wèn)題，即SVM的核函數(shù)如何選擇。目前沒(méi)有明確的標(biāo)準(zhǔn)來(lái)指導(dǎo)核函數(shù)的選擇。在模型不確定的情況下，RBF核函數(shù)是一個(gè)不錯(cuò)的選擇。3.3 SVM參數(shù)優(yōu)化問(wèn)題在實(shí)際應(yīng)用的過(guò)程中，選擇合適的支持向量機(jī)的參數(shù)是一項(xiàng)艱巨而又重要的一步，它會(huì)影響分類器的泛化能力和分類性能。參數(shù)選擇實(shí)際上是一個(gè)優(yōu)化搜索的過(guò)程，搜索空間中的每一個(gè)點(diǎn)都有可能是最佳模型的潛在解，

11、并可由推廣能力估計(jì)值做出相應(yīng)的評(píng)估。所以，參數(shù)優(yōu)化求解的過(guò)程在本質(zhì)上是泛化誤差最小化的求解問(wèn)題。3.3.1常見SVM的尋優(yōu)方法一般情況下，人們會(huì)使用簡(jiǎn)單并且直觀的方法（如網(wǎng)格劃分），通過(guò)大量的實(shí)驗(yàn)比較獲得較優(yōu)的參數(shù)。這種方法可以找到在交叉驗(yàn)證意義下的最高的分類準(zhǔn)確率，但是當(dāng)想在更大的范圍內(nèi)尋找最佳的參數(shù)和時(shí)，這會(huì)有很大的計(jì)算量。Chapelle 等人采用了一種梯度下降(gradient descend, GD)的方法（Chapelle 2002）來(lái)對(duì)參數(shù)進(jìn)行選擇，這種方法雖然在計(jì)算時(shí)間上獲得有效改善。但是梯度下降方法是一種線性的搜索方法，并且對(duì)初始點(diǎn)要求比較高，所有在尋優(yōu)的過(guò)程中容易陷入局部最

12、優(yōu)。遺傳算法(GA, Genetic Algorithm)是Michigan大學(xué)的Holland教授及其學(xué)生受生物模擬技術(shù)啟發(fā)，提出的一種基于生物遺傳和進(jìn)化機(jī)制的自適應(yīng)概率優(yōu)化的技術(shù)。作為一種實(shí)用、高效、魯棒性強(qiáng)的優(yōu)化方法，遺傳算法很快收到國(guó)內(nèi)外學(xué)者的高度重視并迅速發(fā)展。Chen (2004)和Zheng (2004)用不同的推廣能力估計(jì)作為遺傳算法的適應(yīng)度函數(shù)對(duì)SVM的參數(shù)進(jìn)行優(yōu)化。結(jié)果表明：基于GA對(duì)SVM參數(shù)進(jìn)行優(yōu)化的方法大大的縮小了計(jì)算的時(shí)間，并且減小了對(duì)初始值的依賴度。但是遺傳算法的操作往往比較復(fù)雜，對(duì)不同的優(yōu)化問(wèn)題需要設(shè)計(jì)不同的交叉或變異方式。粒子群算法(particle swar

13、m optimization,PSO)是計(jì)算智能領(lǐng)域的一種群體智能優(yōu)化算法，該算法最早是由Kenedy和Eberhat在對(duì)鳥類捕食行為研究時(shí)所提出的。PSO算法是從這種生物種群行為特征中得到啟發(fā)，并應(yīng)用于優(yōu)化問(wèn)題的求解。與遺傳算法不同，PSO是通過(guò)個(gè)體間的協(xié)作來(lái)尋找最優(yōu)解, 這使得粒子群算法更加簡(jiǎn)單, 效率更高, 更容易實(shí)現(xiàn), 因?yàn)樗娘@著的優(yōu)點(diǎn)已被廣泛應(yīng)用于函數(shù)優(yōu)化、模式分類等領(lǐng)域。楊慧中等人(2006)將粒子群算法應(yīng)用于對(duì)SVM參數(shù)的優(yōu)化，仿真結(jié)果表明PSO算法強(qiáng)勁的全局搜索能力大大提高了模型的準(zhǔn)確率。3.3.2 PSO尋優(yōu)算法PSO算法首先在搜索空間中初始化一群粒子，每一個(gè)粒子都有可能是

14、極值優(yōu)化問(wèn)題的潛在最優(yōu)解。我們可以用位置，速度和適應(yīng)度值來(lái)三項(xiàng)指標(biāo)來(lái)表示粒子的特征，并通過(guò)適應(yīng)度值可以用來(lái)衡量粒子的好壞。其中，適應(yīng)度值是通過(guò)適應(yīng)度函數(shù)來(lái)計(jì)算得到的。假設(shè)在d維的搜索空間中，由n個(gè)粒子組成的種群X=X1,X2,Xn,其中第i個(gè)粒子表示一個(gè)d維向量Xi=xi1,xi2,xid。根據(jù)目標(biāo)函數(shù)可以計(jì)算出每個(gè)粒子位置所對(duì)應(yīng)的適應(yīng)度值。設(shè)第i個(gè)粒子的速度為Vi=Vi1,Vi2,VidT,其個(gè)體極值為Pi=Pi1,Pi2,PidT，種群的群體極值為Pg=Pg1,Pg2,PgdT。在每次迭代中，粒子的速度和位置的更新公式可以表示為：Vijk+1=wVijk+c1r1Pijk-Xijk+c2r

15、2(Pgjk-Xijk) (3-15)Xijk+1=Xijk+Vijk+1 (3-16)這里w為慣性權(quán)重,j=1,2,d,i=1,2,n;k是當(dāng)前迭代的次數(shù)。Vij是粒子速度，加速度因子c1,c20；隨機(jī)數(shù)r1,r20,1.為了防止粒子盲目搜索，一般將其位置和速度限制在一定的范圍-Xmax,Xmax,-Vmax,Vmax。3.3.2 基于PSO算法的SVM參數(shù)優(yōu)化推廣能力估計(jì)是參數(shù)選擇的基礎(chǔ)，通常的方法包括：留一法(leave-one-out), k-fold交叉驗(yàn)證法，支持向量率法等。由于k-fold交叉驗(yàn)證法的估計(jì)是無(wú)偏的，通常選用k-fold交叉驗(yàn)證支持向量機(jī)參數(shù)選擇的目標(biāo)值。由于本文中

16、選擇徑向基核函數(shù)，所以PSO需優(yōu)化的參數(shù)有懲罰系數(shù)C和核參數(shù)，具體的步驟如下(邵信光 等,2006)：1) 讀取訓(xùn)練樣本，然后隨機(jī)產(chǎn)生一組C,作為粒子的初始位置;2) 把所以訓(xùn)練樣本均勻地分割成k個(gè)互不包含的子集S1,S2,Sk;3) 根據(jù)當(dāng)前C,訓(xùn)練SVM，并計(jì)算出k次識(shí)別率的平均值得到k-fold交叉驗(yàn)證識(shí)別率；4) 將k-fold交叉驗(yàn)證識(shí)別率作為適應(yīng)度，并記憶個(gè)體與群體所對(duì)應(yīng)的最佳適應(yīng)度位置，然后更新位置和速度搜索更好的C,；5) 重復(fù)步驟2)直到滿足最大迭代次數(shù)；6) 優(yōu)化結(jié)束，輸出結(jié)果。3.4 SVM多類分類問(wèn)題 支持向量機(jī)是一種二類問(wèn)題分類器，它只能回答屬于正類還是負(fù)類的問(wèn)題，但

17、在實(shí)際的應(yīng)用過(guò)程還會(huì)遇到多類問(wèn)題。下面我們介紹詳細(xì)介紹下多類分類問(wèn)題的基本原理。由SVM推到多類SVM目前主要有兩種方法：(1)在一個(gè)優(yōu)化公式中對(duì)所有的數(shù)據(jù)同時(shí)進(jìn)行全局優(yōu)化 (2) 將多類問(wèn)題分解成多個(gè)二值分類問(wèn)題。在數(shù)據(jù)相同的情況下，前者的計(jì)算比后者復(fù)雜的多。所以在實(shí)際使用過(guò)程中，多類SVM問(wèn)題被分解成多了二值分類問(wèn)題(Rocha and Goldenstein 2009)。多類分類器常用的二值分類器組合有一對(duì)多(one against all), 一對(duì)一(one against one),DAGSSVM(Directed Acyclic Graph SVM)三種。在文獻(xiàn)（Hsu and L

18、in 2002）中，作者通過(guò)實(shí)驗(yàn)證明了在實(shí)際的應(yīng)用的過(guò)程中，“一對(duì)一”和DAG方法更適合被應(yīng)用于復(fù)雜問(wèn)題的識(shí)別分類。本文中采用的是“一對(duì)一”結(jié)構(gòu)。3.4.1 基于二值分類的SVM多類分類原理已知n類數(shù)據(jù)樣本訓(xùn)練集：x11,xt11,x1n,xtnn上標(biāo)代表類別數(shù)， ti代表第i類訓(xùn)練樣本數(shù), 訓(xùn)練集樣本總數(shù)為 t1+t2+.+tn，其中xiRd, yi1,2,3,M, M 代表類別數(shù)。Rd上的一個(gè)判別函數(shù)fx, 對(duì)于任一個(gè)輸入x都有對(duì)應(yīng)的y輸出值。利用二值分類方法構(gòu)造n類分類器的方法步驟：1) 首先構(gòu)造n個(gè)二值分類器，fkx, k=1,n將第k類的訓(xùn)練樣本和其他訓(xùn)練樣本集分開。如果樣本xi屬于

19、第k類，則有sgnfkxi=1；否則sgnfkxi=-1。2) 然后，尋找函數(shù)fkxi，k=1,n中最大值所對(duì)應(yīng)的類別即為xi的類別:yi=argmaxf1xi,f2xi,fnxi, (3-17)3.4.2 多類二值分類器組合1) 一對(duì)多組合(one-against-rest)這種方法由n個(gè)SVM分類器組成，第i層SVM的訓(xùn)練樣本是由正樣本(第i類的數(shù)據(jù)樣本)和負(fù)樣本(其余所有類樣本)組成。以4類樣本為例，首先把樣本類1作為正樣本，把類2、3、4作為負(fù)樣本，訓(xùn)練得到SVM1；再將樣本類2作為正樣本，把類1、3、4作為負(fù)樣本，訓(xùn)練得到SVM2；按照這個(gè)方法訓(xùn)練得到4個(gè)二類分類器SVM。所得到SV

20、M數(shù)目和樣本的類別數(shù)一致。這種方法的有點(diǎn)是每個(gè)優(yōu)化問(wèn)題的規(guī)模比較小，分類速度比較快。但是有時(shí)會(huì)出現(xiàn)這種尷尬的問(wèn)題，對(duì)于一個(gè)待分類的樣本，所有的類別都說(shuō)不是自己的，或者所有的類別都說(shuō)是自己的，這就會(huì)出現(xiàn)不可分類現(xiàn)象和重疊分類現(xiàn)象。其分類原理結(jié)構(gòu)圖可表示如下圖3.3。圖3.3 一對(duì)多組合2) 一對(duì)一組合(one-against-one)“一對(duì)一”方法的分類思想是每次從樣本數(shù)據(jù)的n類別中挑出兩個(gè)不同類別，對(duì)這兩類用二值分類器SVM分類，這樣可以構(gòu)建出nn-12個(gè)分類器。第一個(gè)SVM分類器只告訴你別類是“1或是2”，第二個(gè)SVM只告訴你別類是“1或者3”，最后一個(gè)待識(shí)別的別類由這nn-12個(gè)SVM共同投票決定。結(jié)果待識(shí)別的類即為得票數(shù)最多的類別。顯然，“一對(duì)一”的方法可能會(huì)出現(xiàn)分類重疊，但由于不能所有的別類的票數(shù)都是0的情況，所以不會(huì)有不可分的現(xiàn)象。其分類原理結(jié)構(gòu)圖可表示如下圖。圖3.4 一對(duì)一組合3） DAG DAG多類結(jié)構(gòu)實(shí)際上就是將支持向量機(jī)將決策樹相結(jié)合而形成的。這種方法的訓(xùn)練的過(guò)程和“一對(duì)一”方法也是通過(guò)構(gòu)造 nn-12個(gè)SVM分類器（王建芬 2001）。對(duì)n類樣本分類問(wèn)題構(gòu)造DAG(二叉決策樹)結(jié)構(gòu)的多類分類結(jié)構(gòu)，樹的每一個(gè)葉節(jié)點(diǎn)代表一類，度為2的非葉節(jié)點(diǎn)即為一個(gè)子SVM分類器。因此，對(duì)于有2