支持向量機(jī)實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)人工智能課程項(xiàng)目報(bào)告姓名： * 班級(jí)：* 目錄TOC o 1-3 h u 一、實(shí)驗(yàn)背景本學(xué)期學(xué)習(xí)了高級(jí)人工智能課程，對(duì)人工智能的各方面知識(shí)有了新的認(rèn)識(shí)和了解。為了更好的深入學(xué)習(xí)人工智能的相關(guān)知識(shí)，決定以數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)的基礎(chǔ)算法為研究對(duì)象，進(jìn)行算法的研究與實(shí)現(xiàn)。在數(shù)據(jù)挖掘的各種算法中，有一種分類算法的分類效果，在大多數(shù)情況下都非常的好，它就是支持向量機(jī)（SVM）算法。這種算法的理論基礎(chǔ)強(qiáng)，有著嚴(yán)格的推導(dǎo)論證，是研究和學(xué)習(xí)數(shù)據(jù)挖掘算法的很好的切入點(diǎn)。二、實(shí)驗(yàn)?zāi)康膶?duì)SVM

2、算法進(jìn)行研究與實(shí)現(xiàn)，掌握理論推導(dǎo)過程，培養(yǎng)嚴(yán)謹(jǐn)治學(xué)的科研態(tài)度。三、實(shí)驗(yàn)原理支持向量機(jī)基本上是最好的有監(jiān)督學(xué)習(xí)算法。SVM由Vapnik首先提出(Boser,Guyon and Vapnik,1992;Cortes and Vapnik,1995;Vapnik, 1995,1998)。它的主要思想是建立一個(gè)超平面作為決策曲面,使得正例和反例之間的隔離邊緣被最大化。SVM的優(yōu)點(diǎn):1.通用性(能夠在各種函數(shù)集中構(gòu)造函數(shù))2.魯棒性(不需要微調(diào))3.有效性(在解決實(shí)際問題中屬于最好的方法之一)4.計(jì)算簡(jiǎn)單(方法的實(shí)現(xiàn)只需要利用簡(jiǎn)單的優(yōu)化技術(shù))5.理論上完善(基于VC推廣理論的框架)3.1線性可分：首先

3、討論線性可分的情況，線性不可分可以通過數(shù)學(xué)的手段變成近似線性可分?；灸Ｐ停哼@里的裕量是幾何間隔。我們的目標(biāo)是最大化幾何間隔，但是看過一些關(guān)于SVM的論文的人一定記得什么優(yōu)化的目標(biāo)是要最小化|w|這樣的說法，這是怎么回事呢？原因來自于對(duì)間隔和幾何間隔的定義（數(shù)學(xué)基礎(chǔ)）：間隔：=y(wx+b)=|g(x)|幾何間隔：|w|叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。我們常說的向量長(zhǎng)度其實(shí)指的是它的2-范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達(dá)式：另外，注意我們的目標(biāo)：最大化幾何間隔，而不是求出這個(gè)間隔。即，在什么情況下間隔最大，我們要得到的是這個(gè)“情況”（w和b取什么值，因?yàn)樗衳

4、和y是已知的）所以，我們可以把目標(biāo)轉(zhuǎn)換：=在這個(gè)問題中，自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（不要把xi當(dāng)成變量，它代表樣本，是已知的）這種規(guī)劃問題有個(gè)很有名氣的稱呼二次規(guī)劃（Quadratic Programming，QP），而且可以更進(jìn)一步的說，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。拉格朗日乘子法可以求解這個(gè)問題。問題1：實(shí)際上就是目標(biāo)函數(shù)減去，ai乘上約束條件的累加和。將問題轉(zhuǎn)化為拉格朗日乘子待定問題。經(jīng)過數(shù)學(xué)計(jì)算（求導(dǎo)），可以發(fā)現(xiàn)：樣本確定了w，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合：w=1y1x1+2y2x2+nynxn式子中的

5、i是一個(gè)一個(gè)的數(shù)，而xi是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。w的表達(dá)式可以簡(jiǎn)寫如下：另外可以得到約束條件：把問題1寫成其對(duì)偶形式，可轉(zhuǎn)化成問題2：這樣就可以解了，而且方法很多，如SMO。解出來得到的是a，然后可以得到w和b，進(jìn)而得到分類超平面。(事實(shí)上，不需要求出w，非線性下求出w也無意義)3.2線性不可分：在線性不可分的情況下，支持向量機(jī)首先在低維空間中完成計(jì)算，然后通過核函數(shù)將輸入空間映射到高維特征空間，最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面，從而把平面上本身不好分的非線性數(shù)據(jù)分開。那是否意味著，每當(dāng)我們解決一個(gè)問題，都需要找一個(gè)函數(shù)，從低維映射到高維？這個(gè)函數(shù)是什么樣子的呢？首

6、先觀察一下線性下的目標(biāo)函數(shù)（轉(zhuǎn)化后的）。（注：之所以觀察這個(gè)公式，是因?yàn)檗D(zhuǎn)化到高維后，就線性可分了，最后推導(dǎo)得到的還是這個(gè)式子）我們發(fā)現(xiàn)它關(guān)注的不是函數(shù)本身，而是函數(shù)結(jié)果的內(nèi)積。即，我不在乎你把x(二維)，轉(zhuǎn)化為了x幾維，也不在乎轉(zhuǎn)化后的值是多少，我在乎的是轉(zhuǎn)化之后，兩個(gè)x再求內(nèi)積（一個(gè)數(shù)）是多少。幸運(yùn)的是，數(shù)學(xué)中有這樣一些函數(shù)，他們叫核函數(shù)，計(jì)算效果相當(dāng)于轉(zhuǎn)化到高維后的內(nèi)積。百度百科的解釋：核函數(shù)將m維高維空間的內(nèi)積運(yùn)算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計(jì)算，從而巧妙地解決了在高維特征空間中計(jì)算的“維數(shù)災(zāi)難”等問題，從而為在高維特征空間解決復(fù)雜的分類或回歸問題奠定了理論基礎(chǔ)。幾個(gè)核函數(shù)：多項(xiàng)式核

7、：高斯核：它能將原始空間映射為無窮維空間。不過，如果sita選得很大的話,就相當(dāng)于一個(gè)低維的子空間；反過來，如果選得很小，則可以將任意的數(shù)據(jù)映射為線性可分當(dāng)然，這并不一定是好事，因?yàn)殡S之而來的可能是非常嚴(yán)重的過擬合問題。不過，總的來說，通過調(diào)控參數(shù)，高斯核實(shí)際上具有相當(dāng)高的靈活性，也是使用最廣泛的核函數(shù)之一。同樣，經(jīng)過數(shù)學(xué)推導(dǎo)，非線性SVM的目標(biāo)函數(shù)為：同樣，可以用SMO求解。如上圖：如果轉(zhuǎn)化到高維還是不可分呢？或者轉(zhuǎn)的維數(shù)不夠，或者存在噪聲點(diǎn)？這個(gè)時(shí)候怎么辦？引入松弛變量：其中稱為松弛變量，C是一個(gè)參數(shù)。同樣，經(jīng)過轉(zhuǎn)化：此時(shí)，我們發(fā)現(xiàn)沒有了參數(shù)，與之前模型唯一不同在于C的限制條件。為了不失一

8、般性，我們使用引入松弛變量的模型。也就是需要求解的目標(biāo)問題。根據(jù)KKT條件可以得出目標(biāo)函數(shù)中取值的意義：這里的還是拉格朗日乘子：對(duì)第1種情況，表明是正常分類，在邊界內(nèi)部（我們知道正確分類的點(diǎn)）；對(duì)第2種情況，表明了是支持向量，在邊界上；對(duì)第3種情況，表明了是在兩條邊界之間；3.3坐標(biāo)上升法：在最后討論W()的求解之前，我們先看看坐標(biāo)上升法的基本原理。假設(shè)要求解下面的優(yōu)化問題：這里 W 是向量的函數(shù)（也就是前面轉(zhuǎn)化后的目標(biāo)函數(shù)）。求最優(yōu)解的方法有多種：一種是梯度下降法，一種是牛頓法，還有一種是坐標(biāo)上升法。方法過程：坐標(biāo)上升法可以用一張圖來表示：3.4 SMO算法：SMO 算法由 Microsof

9、t Research 的 John C. Platt 在 1998 年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對(duì)線性 SVM 和數(shù)據(jù)稀疏時(shí)性能更優(yōu)。關(guān)于 SMO 最好的資料就是他本人寫的論文 Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines。算法框架：for i=1:itera. 根據(jù)預(yù)先設(shè)定的規(guī)則， 從所有樣本中選出兩個(gè)b. 保持其他拉格朗日乘子不變，更新所選樣本對(duì)應(yīng)的拉格朗日乘子end樣本選取規(guī)則：第一個(gè)參數(shù)是違反kkt條件的。第二個(gè)參數(shù)：選擇使得 （實(shí)際輸出和期望輸

10、出的誤差）最大的參數(shù)。情況比較復(fù)雜，原算法分了很多情況。當(dāng)所有變量都滿足kkt條件時(shí)，算法結(jié)束，求得a。選出了參數(shù)就要進(jìn)行計(jì)算。其中一個(gè)參數(shù)是可以求導(dǎo)等于0然后解出來（不失一般性，記為a2）。另一個(gè)參數(shù)隨之發(fā)生變化（記為a1）。解之前要先確定取值范圍：根據(jù)y1和y2異號(hào)或同號(hào)，可得出a2的上下界分別為：如果是極值點(diǎn)，二階導(dǎo)應(yīng)該大于0，關(guān)于a2的二階導(dǎo)為：經(jīng)過數(shù)學(xué)計(jì)算，在二階導(dǎo)大于0的情況下，結(jié)合取值范圍：然后得到a1:在一些情況下，二階導(dǎo)不是正數(shù)，這時(shí)候需要用到目標(biāo)函數(shù)在取最小值和最大值時(shí)候的值：計(jì)算出a1和a2后，相應(yīng)的更新b。更新完a和b，一個(gè)周期結(jié)束，進(jìn)入下一次循環(huán)。當(dāng)所有的參數(shù)符合kk

11、t條件，循環(huán)結(jié)束。四、實(shí)驗(yàn)內(nèi)容SVM算法步驟：1，讀入訓(xùn)練數(shù)據(jù)。2，用SMO算法求解，得到分類預(yù)測(cè)模型。3，根據(jù)預(yù)測(cè)模型進(jìn)行預(yù)測(cè)。我們發(fā)現(xiàn)SVM算法的難點(diǎn)和重點(diǎn)是SMO算法。算法流程圖：SMO主循環(huán)部分：參數(shù)選擇：參數(shù)更新：五、實(shí)驗(yàn)結(jié)果與分析5.1 實(shí)驗(yàn)環(huán)境與工具Windows 7 旗艦版（Service Pack 1）MyEclipse2014。5.2 實(shí)驗(yàn)數(shù)據(jù)集與參數(shù)設(shè)置bigdata.txt =線性可分 （y=x程序產(chǎn)生）cycle.txt=線性不可分 （x2+y2=1,程序生成）cycle2.txt=線性不可分 （x2+y2=02.5）heart_scale =線性不可分 實(shí)際數(shù)據(jù)te

12、stSet.txt=線性可分不規(guī)則圖形.txt =線性不可分 （圖像數(shù)據(jù)）人臉.txt=線性不可分 （圖像數(shù)據(jù)）5.3 評(píng)估標(biāo)準(zhǔn)算法經(jīng)過訓(xùn)練集的訓(xùn)練之后，在測(cè)試集上的分類準(zhǔn)確率。通過實(shí)際圖像也可以看到分類效果。5.4 實(shí)驗(yàn)結(jié)果與分析testSet.txt實(shí)驗(yàn)結(jié)果：Cycle.txt：Cycle2.txt：支持向量是少數(shù)，分類超平面在中間。不規(guī)則圖形.txt：分類超平面是比較優(yōu)秀的，并不是在圖像的點(diǎn)上，而是大約在中間。存在容錯(cuò)點(diǎn)：人臉.txt：同樣的處理。人臉圖像更復(fù)雜一些，同一類是不連在一起的。能正確分類同樣存在容錯(cuò)點(diǎn)。heart_scale：核函數(shù)為線性的時(shí)候：非線性（高斯核，sita=1）：非線性（高斯核，sita=0.5）：(過小存在過度擬合的情況)Bigdata.txt：總共10000條，主要用來測(cè)試運(yùn)行時(shí)間。發(fā)現(xiàn)數(shù)據(jù)量大就很難進(jìn)行訓(xùn)練。訓(xùn)練數(shù)據(jù)運(yùn)行時(shí)間500