支持向量機原理

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

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

3、表兩類數(shù)據(jù)樣本，各樣本在二維中顯示如圖3.1， 圖中的直線P0,P1就是分類函數(shù)。如果一個線性函數(shù)就完全可以把兩類所有樣本分開，那么就稱這些數(shù)據(jù)是線性可分的；否則稱非線性可分。假設(shè)兩類線性可分的訓(xùn)練數(shù)據(jù)樣本x1,y1,x2,y2,xN,yw*線性判別函數(shù)的值一般是連續(xù)的實數(shù)，而分類問題需要輸出的是離散值。例如利用數(shù)值-1表示類別C1，而用數(shù)值+1表示類別C2.所有的樣本都只能用數(shù)值-1和+1表示。這時我們可以通過設(shè)置一個閥值，通過判斷判別函數(shù)的值是大于或者小于這個閥值來判斷屬于某一類。若我們?nèi)∵@個閥值為0，即當(dāng)f(x)0時，判別樣本為類別C1(即-1)；當(dāng)f(x)0時，判別樣本為類別C2(即+

4、1).現(xiàn)在將判別函數(shù)進行歸一化，使兩類所有樣本都滿足f(x)1，這時離分類面近的樣本都有f(x)=1yiw*x+b-10, i=1,這時分類間隔為2w. 尋求最優(yōu)的分類面即使得分類間隔最大化。可以發(fā)現(xiàn)間隔最大等價于1因此最優(yōu)化分類面問題可以表示成如下的約束優(yōu)化問題，如下：Min w約束條件為：yiw*x+b-10, i=1,定義如下Lagrange函數(shù):Lw,b,式中，i0為Lagrange乘子。為了求得函數(shù)式(3-5)的最小值，我們對Lw由式(3-6)和(3-2)可將上述的最優(yōu)化分類面的求解問題轉(zhuǎn)化為一個凸二次規(guī)劃尋優(yōu)的對偶問題，如下：Max i=1N約束條件為：i這個二次函數(shù)尋優(yōu)的問題存在

5、唯一解，若iw*其中i*不為0對應(yīng)的即為支持向量(Support Vector). 并且最優(yōu)分類面的權(quán)系數(shù)向量是支持向量的線性組合。分類閥值b*式中xr,xs分別是兩類中任意支持向量，fx此時SVM最一般的表達式已經(jīng)被求得。3.1.2廣義的最優(yōu)分類面但當(dāng)有少數(shù)樣本使得原來線性可分的問題變成不可分問題，從而影響了分類器的性能。有時這少數(shù)的樣本也是噪聲，或是奇異值點，是我們在人工對數(shù)據(jù)分類錯分的，為了忽略這些點對分類器的影響，和在經(jīng)驗風(fēng)險和泛化性能之間求得平衡，松弛因子被引入。它容許錯分樣本的存在，這時分類面滿足：yi當(dāng)0i1時，樣本xi可以正確分類；當(dāng)w,式中C是懲罰因子(一個正常數(shù)). 此時，

6、式目標(biāo)函數(shù)凸二次規(guī)劃尋優(yōu)的對偶問題約束條件(3-8)可被變換為如為： 0i3.2核函數(shù)3.2.1核函數(shù)變換基本思想對于非線性分類問題，在原始空間中最優(yōu)化分類面也許不能得到令人滿意的分類結(jié)果。針對這種情況，一個解決的思想是把原始空間中的非線性樣本數(shù)據(jù)投影到某個更高維的空間中，在高維的空間中尋找一個最優(yōu)超平面能線性地將樣本數(shù)據(jù)分開，但是這種變化可能非常復(fù)雜。支持向量機利用核函數(shù)巧妙地解決了這個問題。核函數(shù)變換的基本思想是將一個n維空間中矢量x映射到更高維的特征空間中去，然后在高維空間中進行線性地分類。核函數(shù)變換的基本原理示意圖如圖3.2所示。由（3-7）、（3-11）可看出，都只涉及訓(xùn)練樣本之間的

7、點積運算xi,xj。假設(shè)存在一個非線性映射將在特征空間H中構(gòu)造最優(yōu)分類面時，計算的過程中僅使用了空間中的點積xi,xj，而沒有用到單獨的xi。如果存在一個“核函數(shù)”K，且Kxi,圖3.2 核函數(shù)變換示意圖3.2常見核函數(shù)核函數(shù)作為支持向量機理論的重要的組成部分引起了很多研究者的興趣。常用的滿足Mercer條件的核函數(shù)有線性函數(shù)，多項式函數(shù)，徑向基函數(shù)，Sigmoid函數(shù)等，選擇不同的核函數(shù)可以構(gòu)造不同的支持向量機(張浩然 2002)。下面對這四種常見的核函數(shù)進行簡單地介紹.線性函數(shù)K多項式函數(shù)K徑向基函數(shù)KSigmoid函數(shù)K由這四種核函數(shù)可以構(gòu)造出線性SVM、多項式SVM、RBF SVM和感

8、知SVM。滿足Mercer條件核函數(shù)很多，這樣又帶來另外一個問題，即SVM的核函數(shù)如何選擇。目前沒有明確的標(biāo)準(zhǔn)來指導(dǎo)核函數(shù)的選擇。在模型不確定的情況下，RBF核函數(shù)是一個不錯的選擇。3.3 SVM參數(shù)優(yōu)化問題在實際應(yīng)用的過程中，選擇合適的支持向量機的參數(shù)是一項艱巨而又重要的一步，它會影響分類器的泛化能力和分類性能。參數(shù)選擇實際上是一個優(yōu)化搜索的過程，搜索空間中的每一個點都有可能是最佳模型的潛在解，并可由推廣能力估計值做出相應(yīng)的評估。所以，參數(shù)優(yōu)化求解的過程在本質(zhì)上是泛化誤差最小化的求解問題。3.3.1常見SVM的尋優(yōu)方法一般情況下，人們會使用簡單并且直觀的方法（如網(wǎng)格劃分），通過大量的實驗比較

9、獲得較優(yōu)的參數(shù)。這種方法可以找到在交叉驗證意義下的最高的分類準(zhǔn)確率，但是當(dāng)想在更大的范圍內(nèi)尋找最佳的參數(shù)和時，這會有很大的計算量。Chapelle 等人采用了一種梯度下降(gradient descend, GD)的方法（Chapelle 2002）來對參數(shù)進行選擇，這種方法雖然在計算時間上獲得有效改善。但是梯度下降方法是一種線性的搜索方法，并且對初始點要求比較高，所有在尋優(yōu)的過程中容易陷入局部最優(yōu)。遺傳算法(GA, Genetic Algorithm)是Michigan大學(xué)的Holland教授及其學(xué)生受生物模擬技術(shù)啟發(fā)，提出的一種基于生物遺傳和進化機制的自適應(yīng)概率優(yōu)化的技術(shù)。作為一種實用、高

10、效、魯棒性強的優(yōu)化方法，遺傳算法很快收到國內(nèi)外學(xué)者的高度重視并迅速發(fā)展。Chen (2004)和Zheng (2004)用不同的推廣能力估計作為遺傳算法的適應(yīng)度函數(shù)對SVM的參數(shù)進行優(yōu)化。結(jié)果表明：基于GA對SVM參數(shù)進行優(yōu)化的方法大大的縮小了計算的時間，并且減小了對初始值的依賴度。但是遺傳算法的操作往往比較復(fù)雜，對不同的優(yōu)化問題需要設(shè)計不同的交叉或變異方式。粒子群算法(particle swarm optimization,PSO)是計算智能領(lǐng)域的一種群體智能優(yōu)化算法，該算法最早是由Kenedy和Eberhat在對鳥類捕食行為研究時所提出的。PSO算法是從這種生物種群行為特征中得到啟發(fā)，并應(yīng)

11、用于優(yōu)化問題的求解。與遺傳算法不同，PSO是通過個體間的協(xié)作來尋找最優(yōu)解, 這使得粒子群算法更加簡單, 效率更高, 更容易實現(xiàn), 因為它的顯著的優(yōu)點已被廣泛應(yīng)用于函數(shù)優(yōu)化、模式分類等領(lǐng)域。楊慧中等人(2006)將粒子群算法應(yīng)用于對SVM參數(shù)的優(yōu)化，仿真結(jié)果表明PSO算法強勁的全局搜索能力大大提高了模型的準(zhǔn)確率。3.3.2 PSO尋優(yōu)算法PSO算法首先在搜索空間中初始化一群粒子，每一個粒子都有可能是極值優(yōu)化問題的潛在最優(yōu)解。我們可以用位置，速度和適應(yīng)度值來三項指標(biāo)來表示粒子的特征，并通過適應(yīng)度值可以用來衡量粒子的好壞。其中，適應(yīng)度值是通過適應(yīng)度函數(shù)來計算得到的。假設(shè)在d維的搜索空間中，由n個粒子

12、組成的種群X=X1,X2,Xn,其中第i個粒子表示一個d維向量XiVijXij這里w為慣性權(quán)重,j=1,2,d,i=1,2,n;k是當(dāng)前迭代的次數(shù)。Vij是粒子速度，加速度因子c3.3.2 基于PSO算法的SVM參數(shù)優(yōu)化推廣能力估計是參數(shù)選擇的基礎(chǔ)，通常的方法包括：留一法(leave-one-out), k-fold交叉驗證法，支持向量率法等。由于k-fold交叉驗證法的估計是無偏的，通常選用k-fold交叉驗證支持向量機參數(shù)選擇的目標(biāo)值。由于本文中選擇徑向基核函數(shù)，所以PSO需優(yōu)化的參數(shù)有懲罰系數(shù)C和核參數(shù)，具體的步驟如下(邵信光 等,2006)：讀取訓(xùn)練樣本，然后隨機產(chǎn)生一組C,作為粒子的

13、初始位置;把所以訓(xùn)練樣本均勻地分割成k個互不包含的子集S1根據(jù)當(dāng)前C,訓(xùn)練SVM，并計算出k次識別率的平均值得到k-fold交叉驗證識別率；將k-fold交叉驗證識別率作為適應(yīng)度，并記憶個體與群體所對應(yīng)的最佳適應(yīng)度位置，然后更新位置和速度搜索更好的C,；重復(fù)步驟2)直到滿足最大迭代次數(shù)；優(yōu)化結(jié)束，輸出結(jié)果。3.4 SVM多類分類問題 支持向量機是一種二類問題分類器，它只能回答屬于正類還是負(fù)類的問題，但在實際的應(yīng)用過程還會遇到多類問題。下面我們介紹詳細(xì)介紹下多類分類問題的基本原理。由SVM推到多類SVM目前主要有兩種方法：(1)在一個優(yōu)化公式中對所有的數(shù)據(jù)同時進行全局優(yōu)化 (2) 將多類問題分解

14、成多個二值分類問題。在數(shù)據(jù)相同的情況下，前者的計算比后者復(fù)雜的多。所以在實際使用過程中，多類SVM問題被分解成多了二值分類問題(Rocha and Goldenstein 2009)。多類分類器常用的二值分類器組合有一對多(one against all), 一對一(one against one),DAGSSVM(Directed Acyclic Graph SVM)三種。在文獻（Hsu and Lin 2002）中，作者通過實驗證明了在實際的應(yīng)用的過程中，“一對一”和DAG方法更適合被應(yīng)用于復(fù)雜問題的識別分類。本文中采用的是“一對一”結(jié)構(gòu)。3.4.1 基于二值分類的SVM多類分類原理已知n

15、類數(shù)據(jù)樣本訓(xùn)練集：x上標(biāo)代表類別數(shù)， ti代表第i類訓(xùn)練樣本數(shù), 訓(xùn)練集樣本總數(shù)為 t1+t2+.+tn，其中xiRd, 首先構(gòu)造n個二值分類器，fkx, k=1,n將第k類的訓(xùn)練樣本和其他訓(xùn)練樣本集分開。如果樣本xi屬于第k類，則有然后，尋找函數(shù)fkxi，k=1,nyi3.4.2 多類二值分類器組合一對多組合(one-against-rest)這種方法由n個SVM分類器組成，第i層SVM的訓(xùn)練樣本是由正樣本(第i類的數(shù)據(jù)樣本)和負(fù)樣本(其余所有類樣本)組成。以4類樣本為例，首先把樣本類1作為正樣本，把類2、3、4作為負(fù)樣本，訓(xùn)練得到SVM1；再將樣本類2作為正樣本，把類1、3、4作為負(fù)樣本，

16、訓(xùn)練得到SVM2；按照這個方法訓(xùn)練得到4個二類分類器SVM。所得到SVM數(shù)目和樣本的類別數(shù)一致。這種方法的有點是每個優(yōu)化問題的規(guī)模比較小，分類速度比較快。但是有時會出現(xiàn)這種尷尬的問題，對于一個待分類的樣本，所有的類別都說不是自己的，或者所有的類別都說是自己的，這就會出現(xiàn)不可分類現(xiàn)象和重疊分類現(xiàn)象。其分類原理結(jié)構(gòu)圖可表示如下圖3.3。圖3.3 一對多組合一對一組合(one-against-one)“一對一”方法的分類思想是每次從樣本數(shù)據(jù)的n類別中挑出兩個不同類別，對這兩類用二值分類器SVM分類，這樣可以構(gòu)建出nn-12個分類器。第一個SVM分類器只告訴你別類是“1或是2”，第二個SVM只告訴你別

17、類是“1或者3”，最后一個待識別的別類由這nn-12個圖3.4 一對一組合 DAG DAG多類結(jié)構(gòu)實際上就是將支持向量機將決策樹相結(jié)合而形成的。這種方法的訓(xùn)練的過程和“一對一”方法也是通過構(gòu)造 nn-12個SVM分類器（王建芬 2001）。對n類樣本分類問題構(gòu)造DAG(二叉決策樹)結(jié)構(gòu)的多類分類結(jié)構(gòu)，樹的每一個葉節(jié)點代表一類，度為2的非葉節(jié)點即為一個子SVM分類器。因此，對于有2n-1結(jié)點的決策樹，則有葉節(jié)點個數(shù)為n(即為n類),子SVM分類器個數(shù)為n-1。DAG的特點是具有層次結(jié)構(gòu)，測試速度快，沒有理論指導(dǎo)，需要一定的先驗知識。 對于一個有k個葉節(jié)點的圖3.5 多類分類問題的二叉決策樹結(jié)構(gòu)3.5 本章小結(jié)支持向量機是一種基于結(jié)構(gòu)風(fēng)險最小化原則提出的二值分類器方法，其作為統(tǒng)計學(xué)習(xí)理論的實踐方法受到了廣大研究者的興趣。本章節(jié)主要介紹了支持向量機的基本思想、核函數(shù)、參數(shù)的選擇和多類分類問題。SVM的基本思想是構(gòu)造一個超平面作為分類判別平面，使得兩類樣本之間的間隔最大。對于比較復(fù)雜的非線性問題，如果在原始空間中不能夠?qū)ふ业搅钊藵M意的分類效果的最優(yōu)超平面，則通過非線性變換轉(zhuǎn)化為某個更高維空間中的線性問題。這里引入核函數(shù)的概念，使得實現(xiàn)某一個非線性變換后的線性分類而沒有增加計算的復(fù)雜度。SVM是針對二類問題設(shè)計的分類器，當(dāng)用其來解決多類問題時，我