數(shù)據(jù)挖掘?qū)д?第5章-分類-5.5-SVM-2017

支持向量機(jī)支持向量機(jī)(SupportVectorMachines,SVM)源于Vapnik和Chervonenkis的統(tǒng)計(jì)學(xué)習(xí)理論的早期工作第一篇論文是Boser,Guyon和Vapnik[BGV92]的文章優(yōu)點(diǎn)對(duì)復(fù)雜的非線性邊界的建模能力與其它模型相比,它們不太容易過分?jǐn)M合支持向量機(jī)還提供了學(xué)習(xí)模型的緊湊表示廣泛的使用范圍SVM可以用來預(yù)測(cè)和分類它們已經(jīng)用在許多領(lǐng)域,包括手寫數(shù)字識(shí)別、對(duì)象識(shí)別、演說人識(shí)別,以及基準(zhǔn)時(shí)間序列預(yù)測(cè)檢驗(yàn)第一頁，共40頁。支持向量機(jī)兩個(gè)線性可分的類找到這樣一個(gè)超平面，使得所有的方塊位于這個(gè)超平面的一側(cè)，而所有的圓圈位于它的另一側(cè)可能存在無窮多個(gè)那樣的超平面第二頁，共40頁?！白畲筮吘墶痹恚杭醋非蠓诸惼鞯姆夯芰ψ畲蠡＜聪Ｍ业降臎Q策邊界，在滿足將兩類數(shù)據(jù)點(diǎn)正確的分開的前提下,對(duì)應(yīng)的分類器邊緣最大。這樣可以使得新的測(cè)試數(shù)據(jù)被錯(cuò)分的幾率盡可能小。

如下圖所示的情況(b)就比情況(a)與(c)的泛化能力強(qiáng),其原因在于其分界面與兩類樣本中的最近鄰的樣本的距離最大.(a)(b)(c)決策邊界的邊緣第三頁，共40頁。denotes+1denotes-1直觀而言，如何分類這些樣本？即給出一個(gè)決策超平面更多的例子：要考慮以下因素：◆經(jīng)驗(yàn)風(fēng)險(xiǎn)最小

(已知的樣本錯(cuò)分最少)◆泛化能力最大(可能出現(xiàn)的新樣本錯(cuò)分最少)決策邊界的邊緣第四頁，共40頁。denotes+1denotes-1更多的例子：決策邊界的邊緣第五頁，共40頁。denotes+1denotes-1更多的例子：決策邊界的邊緣第六頁，共40頁。denotes+1denotes-1更多的例子：決策邊界的邊緣第七頁，共40頁。denotes+1denotes-1所有的決策超平面都是可行的。但是應(yīng)該選擇哪一個(gè)為最優(yōu)決策超平面呢？更多的例子：決策邊界的邊緣第八頁，共40頁。ClassifierMargindenotes+1denotes-1Definethemarginofalinearclassifierasthewidththattheboundarycouldbeincreasedbybeforehittingadatapoint.更多的例子：決策邊界的邊緣第九頁，共40頁。MaximumMargindenotes+1denotes-1Themaximummarginlinearclassifieristhelinearclassifierwiththe,um,maximummargin.ThisisthesimplestkindofSVM(CalledanLSVM)LinearSVM更多的例子：決策邊界的邊緣第十頁，共40頁。denotes+1denotes-1Themaximummarginlinearclassifieristhelinearclassifierwiththemaximummargin.ThisisthesimplestkindofSVM(CalledanLSVM)SupportVectorsLinearSVM更多的例子：決策邊界的邊緣第十一頁，共40頁。SVM的決策邊界和邊緣一個(gè)線性分類器的決策邊界可以寫成如下形式：

wx+b=0其中，w和b是模型的參數(shù)第十二頁，共40頁。邊緣方塊的類標(biāo)號(hào)為+1，圓圈的類標(biāo)號(hào)為1z的類標(biāo)號(hào)y

調(diào)整決策邊界的參數(shù)w和b，兩個(gè)平行的超平面bi1和bi2可以表示如下bi1：wx+b=1bi2：wx+b=1可以證明,邊緣d第十三頁，共40頁。邊緣推導(dǎo)w的方向垂直于決策邊界如果xa和xb是任意兩個(gè)位于決策邊界上的點(diǎn)，則wxa+b=0,wxb+b=0于是w(xb

xa)=0.由于xb

xa是決策超平面中任意向量,于是w的方向必然垂直于決策邊界令x1是bi1上的數(shù)據(jù)點(diǎn)，x2是bi2上的數(shù)據(jù)點(diǎn).代入bi1和bi2相減得到w(x1

x2)=2由令u=w,v=x1

x2,得到||w||||x1

x2||cos(w,x1

x2)=2第十四頁，共40頁。邊緣推導(dǎo)(續(xù))||w||||x1

x2||cos(w,x1

x2)=2同時(shí)||x1

x2||cos(w,x1

x2)=d于是||w||d=2，即第十五頁，共40頁。SVMSVM的訓(xùn)練階段從訓(xùn)練數(shù)據(jù)中估計(jì)決策邊界的參數(shù)w和b

最大化邊緣d，并滿足wxi+b≥1如果yi

=1wxi+b≤1如果yi

=1

即yi(wxi+b)≥1

最大化d等價(jià)于最小化這是一個(gè)凸二次優(yōu)化問題，可以通過標(biāo)準(zhǔn)的拉格朗日乘子（Lagrangemultiplier）方法求解第十六頁，共40頁。SVM(續(xù))拉格朗日算子其中，參數(shù)i稱為拉格朗日乘子對(duì)Lp關(guān)于w和b求偏導(dǎo)，并令它們等于零因?yàn)槔窭嗜粘俗觟是未知的，因此仍然不能得到w和b的解(5-38)(5-39)(5-40)第十七頁，共40頁。SVM(續(xù))使用Karuch-Kuhn-Tucher（KKT）條件：i

≥0i

[yi(wxi+b)1]=0

（5.42）除非訓(xùn)練實(shí)例滿足方程yi(wxi

+b)=1,否則拉格朗日乘子i必須為零i

>0的訓(xùn)練實(shí)例位于超平面bi1或bi2上，稱為支持向量（5.39）和（5.40）代入到公式（5.38）中這是Lp的對(duì)偶問題(最大化問題).可以使用數(shù)值計(jì)算技術(shù),如二次規(guī)劃來求解(5-43)第十八頁，共40頁。SVM(續(xù))解出i后,用(5.39)求w,再用(5.42)求b決策邊界為z可以按以下的公式來分類如果f(z)=1，則檢驗(yàn)實(shí)例z被分為到正類，否則分到負(fù)類第十九頁，共40頁。對(duì)于許多實(shí)際問題,前面討論的最優(yōu)決策超平面的條件過于嚴(yán)格。

對(duì)存在數(shù)據(jù)污染、近似線性分類的情況,可能并不存在一個(gè)最優(yōu)的線性決策超平面

存在噪聲數(shù)據(jù)時(shí)，為保證所有訓(xùn)練數(shù)據(jù)的準(zhǔn)確分類，可能會(huì)導(dǎo)致過擬合不可分情況：軟邊緣(softmargin)SVM

第二十頁，共40頁。Class1Class2分類面不可分情況：軟邊緣(softmargin)SVM

第二十一頁，共40頁。Class1Class2分類面不可分情況：軟邊緣(softmargin)SVM

第二十二頁，共40頁。因此，需要允許有一定范圍內(nèi)的“錯(cuò)分”,又有較大分界區(qū)域的最優(yōu)分類面軟邊緣（softmargin）

SVM通過引入松弛變量、懲罰因子，在一定程度上允許錯(cuò)誤分類樣本，以增大間隔距離。在分類準(zhǔn)確性與泛化能力上尋求一個(gè)平衡點(diǎn)不可分情況：軟邊緣(softmargin)SVM

引入松馳變量i其中C和k是用戶指定的參數(shù)，對(duì)誤分訓(xùn)練實(shí)例加罰取k=1，

C根據(jù)模型在確認(rèn)集上的性能選擇第二十三頁，共40頁。拉格朗日算子其中，前面兩項(xiàng)是需要最小化的目標(biāo)函數(shù)，第三項(xiàng)表示與松弛變量相關(guān)的不等式約束，而最后一項(xiàng)是要求i的值非負(fù)的結(jié)果KKT條件i

≥0,i

≥0,i

≥0i

{yi(wxi+b)1+i}=0ii=0不可分情況：軟邊緣(softmargin)SVM

其中，C為懲罰因子，C越大,表示分類越嚴(yán)格,允許錯(cuò)分的樣本受到的限制越大,錯(cuò)分的樣本數(shù)少,越容易產(chǎn)生過擬合。第二十四頁，共40頁。虛線與實(shí)線為C=1和104所解得的決策超平面不可分情況：軟邊緣(softmargin)SVM

第二十五頁，共40頁。軟邊緣(softmargin)SVM的基本工作原理：對(duì)存在數(shù)據(jù)污染、近似線性分類的情況,可能并不存在一個(gè)最優(yōu)的線性決策超平面；當(dāng)存在噪聲數(shù)據(jù)時(shí)，為保證所有訓(xùn)練數(shù)據(jù)的準(zhǔn)確分類，可能會(huì)導(dǎo)致過擬合。因此，需要允許有一定程度“錯(cuò)分”,又有較大分界區(qū)域的最優(yōu)決策超平面，即軟間隔支持向量機(jī)。軟間隔支持向量機(jī)通過引入松弛變量、懲罰因子，在一定程度上允許錯(cuò)誤分類樣本，以增大間隔距離。在分類準(zhǔn)確性與泛化能力上尋求一個(gè)平衡點(diǎn)。不可分情況：軟邊緣(softmargin)SVM

第二十六頁，共40頁。非線性SVM使用非線性變換例:第二十七頁，共40頁。樣本非線性可分，將其映射到高維空間，可使樣本線性可分非線性SVM：從低維空間到高維空間的映射第二十八頁，共40頁。樣本非線性可分，將其映射到高維空間，可使樣本線性可分Φ:x

→

φ(x)非線性SVM：從低維空間到高維空間的映射因此對(duì)非線性問題,可以把樣本x映射到某個(gè)高維特征空間H,并在H中使用線性分類器.第二十九頁，共40頁。非線性SVM非線性SVM的優(yōu)化問題約束條件:yi(w(xi)+b)≥1,i=1,2,...,N

對(duì)偶拉格朗日問題參數(shù)w和b

第三十頁，共40頁。非線性支持向量機(jī)的基本工作原理對(duì)非線性可分的問題，可以利用核變換，把原樣本映射到某個(gè)高維特征空間，使得原本在低維特征空間中非線性可分的樣本，在新的高維特征空間中變得線性可分，并使用線性支持向量機(jī)進(jìn)行分類。非線性SVM第三十一頁，共40頁。核技術(shù)Mercer定理:

核函數(shù)K可以表示為K(u,v)=(u)(v),當(dāng)且僅當(dāng)對(duì)于任意滿足g(x)2dx為有限值的函數(shù)g(x)，則K(x,y)g(x)g(y)dxdy≥0滿足定理5.1的核函數(shù)稱為正定（positivedefinite）核函數(shù)常用核函數(shù)第三十二頁，共40頁。SVM的特點(diǎn)SVM學(xué)習(xí)問題可以表示為凸優(yōu)化問題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值SVM通過最大化決策邊界的邊緣來控制模型的能力需要提供其他參數(shù)，如使用的核函數(shù)類型、為了引入松弛變量所需的代價(jià)函數(shù)C等分類屬性處理每個(gè)分類屬性值引入一個(gè)啞變量,轉(zhuǎn)化為二元變量例如，如果婚姻狀況有3個(gè)值{單身，已婚，離異}，可以對(duì)每一個(gè)屬性值引入一個(gè)二元變量可以推廣到多類問題第三十三頁，共40頁。多類問題SVM是對(duì)二類問題設(shè)計(jì)的還有一些方法也是針對(duì)二類問題的如何處理多類問題?訓(xùn)練令Y={y1,y2,...,yK}是類標(biāo)號(hào)的集合1-r方法:分解成K個(gè)二類問題每一個(gè)類yiY創(chuàng)建一個(gè)二類問題,其中所有屬于yi的樣本都被看作正類,而其他樣本作為負(fù)類1-1方法:構(gòu)建K(K

1)/2個(gè)二類分類器每一個(gè)分類器用來區(qū)分一對(duì)類(yi,yj)為類(yi,yj)構(gòu)建二類分類器時(shí),不屬于yi或yj的樣本被忽略掉第三十四頁，共40頁。常用的SVM程序LIBSVM：

.tw/~cjlin/mySVMMYSVM/SVM-Light……第三十五頁，共40頁。matlab的SVM函數(shù)使用1、數(shù)據(jù)預(yù)處理2、數(shù)據(jù)載入、歸一化3、訓(xùn)練SVM分類器（svmtrain）4、分類可選的步驟：交叉檢驗(yàn)，選擇最優(yōu)的核函數(shù)和參數(shù)第三十六頁，共40頁。svmtrain和svmclassify函數(shù)Svmtrain：Trainsupportvectormachineclassifier（訓(xùn)練SVM分類器）語法及調(diào)用參數(shù)：SVMStruct=svmtrain(Training,Group)SVMStruct=svmtrain(...,'Kernel_Function',Kernel_FunctionValue,...)SVMStruct=svmtrain(...,'RBF_Sigma',RBFSigmaValue,...)SVMStruct=svmtrain(...,'Polyorder',PolyorderValue,...)SVMStruct=svmtrain(...,'Mlp_Params',Mlp_ParamsValue,...)SVMStruct=svmtrain(...,'Method',MethodValue,...)SVMStruct=svmtrain(...,'QuadProg_Opts',QuadProg_OptsValue,...)SVMStruct=svmtrain(...,'SMO_Opts',SMO_OptsValue,...)SVMStruct=svmtrain(...,'BoxConstraint',BoxConstraintValue,...)SVMStruct=svmtrain(...,'Autoscale',AutoscaleValue,...)SVMStruct=svmtrain(...,'Showplot',ShowplotValue,...)第三十七頁，共40頁。svmtrain和svmclassify函數(shù)核函數(shù)的選擇：Kernel_FunctionValue Stringorfunctionhandlespecifyingthekernelfunctionthatmapsthetrainingdataintokernelspace.Choicesare:linear—Default.Linearkernelordotproduct.quadratic—Quadratickernel.rbf—GaussianRadialBasisFunctionkernelwithadefaultscalingfactor,sigma,of1.polynomial—Polynomialkernelwithadefaultorderof3.mlp—MultilayerPerceptronkernelwithdefaultscaleandbiasparametersof[1,-1].@functionname—Handletoakernelfunctionspecifiedusing@andthefunctionname.Forexample,@kfun,orananonymousfunction.第三十八頁，共40頁。Example:loadfisheririsdata=[meas(:,1),meas(:,2)];%ExtracttheSetosaclassgroups=ismember(species,'setosa');ind