支持向量機(jī)課件

支持向量機(jī)，一種線性和非線性數(shù)據(jù)有前途的新劃分類方法。巧妙利用向量內(nèi)積的回旋，通過將非線性核函數(shù)將問題變?yōu)楦呔S特征空間與低維輸入空間的相互轉(zhuǎn)換，解決了數(shù)據(jù)挖掘中的維數(shù)災(zāi)難。由于計(jì)算問題最終轉(zhuǎn)化為凸二次規(guī)劃問題，因此挖掘算法是無解或有全局最優(yōu)解。第一頁第二頁，共30頁。支持向量機(jī)定義所謂支持向量機(jī)，顧名思義，分為兩個(gè)部分了解：一，什么是支持向量（簡單來說，就是支持或支撐平面上把兩類類別劃分開來的超平面的向量點(diǎn)）二，這里的“機(jī)（machine，機(jī)器）”便是一個(gè)算法。在機(jī)器學(xué)習(xí)領(lǐng)域，常把一些算法看做是一個(gè)機(jī)器，如分類機(jī)（當(dāng)然，也叫做分類器），而支持向量機(jī)本身便是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。第二頁第三頁，共30頁。SVM的描述目標(biāo)：找到一個(gè)超平面，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。解決方法：構(gòu)造一個(gè)在約束條件下的優(yōu)化問題，具體的說是一個(gè)約束二次規(guī)劃問題(constrainedquadraticprograming),求解該問題，得到分類器。第三頁第四頁，共30頁。概述第四頁第五頁，共30頁。1.線性可分情形第五頁第六頁，共30頁。線性可分情形最大邊緣超平面(MMH)邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到其邊緣的另一個(gè)側(cè)面的最短距離，邊緣側(cè)面平行于超平面第六頁第七頁，共30頁。分類面與邊界距離(margin)的數(shù)學(xué)表示:分類超平面表示為：Class1Class2m數(shù)學(xué)語言描述第七頁第八頁，共30頁。一、線性可分的支持向量(分類)機(jī)首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集：

線性可分情況意味著存在超平面使訓(xùn)練點(diǎn)中的正類和負(fù)類樣本分別位于該超平面的兩側(cè)。如果能確定這樣的參數(shù)對(duì)（w,b）的話,就可以構(gòu)造決策函數(shù)來進(jìn)行識(shí)別新樣本。第八頁第九頁，共30頁。線性可分的支持向量(分類)機(jī)問題是：這樣的參數(shù)對(duì)（w,b）有許多。解決的方法是采用最大間隔原則。最大間隔原則：選擇使得訓(xùn)練集D對(duì)于線性函數(shù)(w·x)+b的幾何間隔取最大值的參數(shù)對(duì)(w,b)，并由此構(gòu)造決策函數(shù)。在規(guī)范化下，超平面的幾何間隔為于是，找最大幾何間隔的超平面表述成如下的最優(yōu)化問題：(1)第九頁第十頁，共30頁。線性可分的支持向量(分類)機(jī)

為求解問題(1),使用Lagrange乘子法將其轉(zhuǎn)化為對(duì)偶問題。于是引入Lagrange函數(shù)：其中，稱為Lagrange乘子。首先求Lagrange函數(shù)關(guān)于w,b的極小值。由極值條件有：得到：(2)(3)(4)第十頁第十一頁，共30頁。線性可分的支持向量(分類)機(jī)將(3)式代入Lagrange函數(shù)，并利用(4)式，則原始的優(yōu)化問題轉(zhuǎn)化為如下的對(duì)偶問題(使用極小形式)：這是一個(gè)凸二次規(guī)劃問題有唯一的最優(yōu)解(5)求解問題(5)，得

。則參數(shù)對(duì)(w,b)可由下式計(jì)算：第十一頁第十二頁，共30頁。線性可分的支持向量(分類)機(jī)

支持向量：稱訓(xùn)練集D中的樣本xi為支持向量，如果它對(duì)應(yīng)的

i*>0。

根據(jù)原始最優(yōu)化問題的KKT條件，有

于是，支持向量正好在間隔邊界上

于是，得到如下的決策函數(shù)：第十二頁第十三頁，共30頁。幾何意義：超平面法向量是支持向量的線性組合。幾何意義a6=1.4Class1Class2a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0第十三頁第十四頁，共30頁。對(duì)于線性不可分的樣本怎么辦？非線性可分情形如何找到正確的分類曲線和正確的超平面對(duì)此類情況分類?第十四頁第十五頁，共30頁。非線性可分情形關(guān)鍵點(diǎn):把xi

變換到高維的特征空間為什么要變換？通過加入一個(gè)新的特征xi，使得樣本變成線性可分的，此時(shí)特征空間維數(shù)變高Transformx

(x)第十五頁第十六頁，共30頁。例子ax12+bx22=1[w]1z1+[w]2z2

+[w]3z3+b=0第十六頁第十七頁，共30頁。設(shè)訓(xùn)練集，其中假定可以用平面上的二次曲線來劃分：現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個(gè)超平面：非線性分類第十七頁第十八頁，共30頁?？梢姡灰米儞Q，把x

所在的2維空間的兩類輸入點(diǎn)映射x所在的6維空間，然后在這個(gè)6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線：非線性分類第十八頁第十九頁，共30頁。如何選擇到較高維空間的非線性映射？給定的檢驗(yàn)元組，必須計(jì)算與每個(gè)支持向量的點(diǎn)積，出現(xiàn)形如可以引入核函數(shù)（內(nèi)積的回旋）來替代第十九頁第二十頁，共30頁。需要求解的最優(yōu)化問題非線性分類最后得到?jīng)Q策函數(shù)或?yàn)榇?，引進(jìn)函數(shù)第二十頁第二十一頁，共30頁。實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問題第二十一頁第二十二頁，共30頁。實(shí)現(xiàn)非線性分類的思想其中解得，而決策函數(shù)第二十二頁第二十三頁，共30頁。目前研究最多的核函數(shù)主要有三類：核函數(shù)的選擇多項(xiàng)式內(nèi)核得到q階多項(xiàng)式分類器包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定Sigmoid內(nèi)核每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定高斯徑向基函數(shù)內(nèi)核RBF第二十三頁第二十四頁，共30頁。幾個(gè)典型的核函數(shù)第二十四頁第二十五頁，共30頁。核的比較第二十五頁第二十六頁，共30頁?，F(xiàn)有5個(gè)一維數(shù)據(jù)x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6為class1，4,5為class2

y1=1,y2=1,y3=-1,y4=-1,y5=1選擇polynomialkernelofdegree2K(x,y)=(xy+1)2C=100求解ai(i=1,…,5)12456例子第二十六頁第二十七頁，共30頁。例子通過二次規(guī)劃求解，得到支持向量為{x2=2,x4=5,x5=