1、人工智能課程項目報告姓名：moiuiuimc班級：4亠4亠4亠4亠4亠4亠4亠4亠亠4亠4亠4亠4亠丄亠目錄TOC o 1-5 h z一、實驗背景1二、實驗?zāi)康?三、實驗原理1線性可分：1線性不可分：4坐標上升法：7SMO算法：8四、實驗內(nèi)容10五、實驗結(jié)果與分析125.1實驗環(huán)境與工具125.2實驗數(shù)據(jù)集與參數(shù)設(shè)置125.3評估標準13實驗結(jié)果與分析13 一、實驗背景本學期學習了高級人工智能課程，對人工智能的各方面知識有了新的認識和了解。為了更好的深入學習人工智能的相關(guān)知識，決定以數(shù)據(jù)挖掘與機器學習的基礎(chǔ)算法為研究對象，進行算法的研究與實現(xiàn)。在數(shù)據(jù)挖掘的各種算法中，有一種分類算法的分類效果，

2、在大多數(shù)情況下都非常的好，它就是支持向量機（SVM）算法。這種算法的理論基礎(chǔ)強，有著嚴格的推導論證，是研究和學習數(shù)據(jù)挖掘算法的很好的切入點。二、實驗?zāi)康膶VM算法進行研究與實現(xiàn)，掌握理論推導過程，培養(yǎng)嚴謹治學的科研態(tài)度。三、實驗原理支持向量機基本上是最好的有監(jiān)督學習算法。SVM由Vapnik首先提出（Boser,GuyonandVapnik,1992;CortesandVapnik,1995;Vapnik,1995,1998）。它的主要思想是建立一個超平面作為決策曲面,使得正例和反例之間的隔離邊緣被最大化。SVM的優(yōu)點:通用性（能夠在各種函數(shù)集中構(gòu)造函數(shù)）魯棒性（不需要微調(diào)）有效性（在解決實

3、際問題中屬于最好的方法之一）計算簡單（方法的實現(xiàn)只需要利用簡單的優(yōu)化技術(shù)）理論上完善（基于VC推廣理論的框架）3.1線性可分：首先討論線性可分的情況，線性不可分可以通過數(shù)學的手段變成近似線性可分?；灸Ｐ停阂慌卸ê瘮?shù)形式；9(兀)=wlx4-b因此，yi(wXf+b)mvt-裕量(margin):誅一令m二1這里的裕量是幾何間隔。我們的目標是最大化幾何間隔，但是看過一些關(guān)于SVM的論文的人一定記得什么優(yōu)化的目標是要最小化llwlI這樣的說法，這是怎么回事呢?原因來自于對間隔和幾何間隔的定義(數(shù)學基礎(chǔ))：間隔：6=y(wx+b)=Ig(x)l%百3幾何間隔：llwll叫做向量w的范數(shù)，范數(shù)是對向

4、量長度的一種度量。我們常說的向量長度其實指的是它的2-范數(shù)，范數(shù)最一般的表示形式為P-范數(shù)，可以寫成如下表達式：II叫斫尹二7另外，注意我們的目標：最大化幾何間隔，而不是求出這個間隔。即在什么情況下間隔最大，我們要得到的是這個“情況”（W和b取什么值,因為所有x和y是已知的）所以，我們可以把目標轉(zhuǎn)換：“13=在這個問題中，自變量就是W,而目標函數(shù)是W的二次函數(shù)，所有的約束條件都是W的線性函數(shù)（不要把xi當成變量，它代表樣本，是已知的）這種規(guī)劃問題有個很有名氣的稱呼二次規(guī)劃（QuadraticProgramming，QP），而且可以更進一步的說，由于它的可行域是一個凸集,因此它是一個凸二次規(guī)劃。

5、拉格朗日乘子法可以求解這個問題。（叫肌a）二+|w|a-仏仙7也+可問題1：亠-實際上就是目標函數(shù)減去，ai乘上約束條件的累加和。將問題轉(zhuǎn)化為拉格朗日乘子待定問題。經(jīng)過數(shù)學計算（求導），可以發(fā)現(xiàn)：樣本確定了w,用數(shù)學的語言描述,就是w可以表示為樣本的某種組合：w=alylxl+a2y2x2+anynxn式子中的ai是一個一個的數(shù)，而xi是樣本點，因而是向量，n就是總樣本點的個數(shù)。w的表達式可以簡寫如下：L1max2ttj-在Zii=i2subjecttoayi=0;0Vii=l這樣就可以解了，而且方法很多，如SMO。解出來得到的是a,然后可以得到w和b，進而得到分類超平面。（事實上，不需要求出

6、w,非線性下求出w也無意義）3.2線性不可分：在線性不可分的情況下，支持向量機首先在低維空間中完成計算，然后通過核函數(shù)將輸入空間映射到高維特征空間，最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面，從而把平面上本身不好分的非線性數(shù)據(jù)分開。射到高維？這個函數(shù)是什么樣子的呢？首先觀察一下線性下的目標函數(shù)（轉(zhuǎn)化后的）。（注：之所以觀察這個公式，是因為轉(zhuǎn)化到高維后，就線性可分了，最后推導得到的還是這個式子）nwx_伉叩卩護j我們發(fā)現(xiàn)它關(guān)注的不是函數(shù)本身，而是函數(shù)結(jié)果的內(nèi)積。即，我不在乎你把x（二維），轉(zhuǎn)化為了x幾維，也不在乎轉(zhuǎn)化后的值是多少，我在乎的是轉(zhuǎn)化之后，兩個x再求內(nèi)積（一個數(shù)）是多少。幸運的是，數(shù)學中

7、有這樣一些函數(shù)，他們叫核函數(shù)，計算效果相當于轉(zhuǎn)化到高維后的內(nèi)積。百度百科的解釋：核函數(shù)將m維高維空間的內(nèi)積運算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計算，從而巧妙地解決了在高維特征空間中計算的“維數(shù)災(zāi)難”等問題，從而為在高維特征空間解決復雜的分類或回歸問題奠定了理論基礎(chǔ)。幾個核函數(shù)：多項式核：Jin它能將原始空間映射為無窮維空間。不過，如果sita選得很大的話,就相當于一個低維的子空間；反過來，如果選得很小，則可以將任意的數(shù)據(jù)映射為線性可分當然，這并不一定是好事，因為隨之而來的可能是非常嚴重的過擬合問題。不過，總的來說，通過調(diào)控參數(shù)，高斯核實際上具有相當高的靈活性，也是使用最廣泛的核函數(shù)之一。經(jīng)過數(shù)學

8、推導，非線性SVM的目標函數(shù)為：同樣，同樣，可以用SMO求解。如上圖：如果轉(zhuǎn)化到高維還是不可分呢？或者轉(zhuǎn)的維數(shù)不夠，或者存在噪聲點？這個時候怎么辦？引入松弛變量:min*|2f-i其中稱為松弛變量，c是一個參數(shù)。同樣，經(jīng)過轉(zhuǎn)化:您幻力刃0（芯）鈾（可）（iijs.t.aiyt=OrQatCyi此時，我們發(fā)現(xiàn)沒有了參數(shù)，與之前模型唯一不同在于c的限制條件。為了不失一般性，我們使用引入松弛變量的模型。也就是需要求解的目max.a如勾旳丹0（御）環(huán)（巧）a-IIJs.t.工aiyt=OrOatL0aJCy“=lta=Coy-u.1.這里的還是拉格朗日乘子：對第1種情況，表明是正常分類，在邊界內(nèi)部(我

9、們知道正確分類的點)；對第2種情況，表明了是支持向量，在邊界上；對第3種情況，表明了是在兩條邊界之間；3.3坐標上升法：在最后討論W(a)的求解之前，我們先看看坐標上升法的基本原理。假max,幗)設(shè)要求解下面的優(yōu)化問題：這里W是a向量的函數(shù)(也就是前面轉(zhuǎn)化后的目標函數(shù))。求最優(yōu)解的方法有多種：一種是梯度下降法，一種是牛頓法，還有一種是坐標上升法。Loopuntilconvergence:ForiL.,.%:-=tagIILv(1ffL(ij,Ufj+|,rn)*方法過程：坐標上升法可以用一張圖來表示：34SMO算法:SMO算法由MicrosoftResearch的JohnC.Platt在199

10、8年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對線性SVM和數(shù)據(jù)稀疏時性能更優(yōu)。關(guān)于SMO最好的資料就是他本人寫的論文SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachines。算法框架：fori=1:itera.根據(jù)預(yù)先設(shè)定的規(guī)則，從所有樣本中選出兩個b.保持其他拉格朗日乘子不變，更新所選樣本對應(yīng)的拉格朗日乘子end樣本選取規(guī)則：第一個參數(shù)是違反kkt條件的。第二個參數(shù)：選擇使得-（實際輸出和期望輸出的誤差）最大的參數(shù)。情況比較復雜，原算法分了很多情況。當所有變量都滿足kkt條件時，算法結(jié)束，求得a。

11、選出了參數(shù)就要進行計算。其中一個參數(shù)是可以求導等于0然后解出來（不失一般性，記為a2）。另一個參數(shù)隨之發(fā)生變化（記為al）。解之前要先確定取值范圍：CaC0Ca300aaiTj=0旳二旳=碼+弼=氐根據(jù)yl和y2異號或同號，可得出a2的上下界分別為:L=nwx（g翼-ad）tH=ininfCC+毎-屮）if加/也L+V嚴C）,li-min（G+嘗）ifyi=蟲如果是極值點，二階導應(yīng)該大于0關(guān)于a2的二階導為:7；=K（元|,元J+K（召，元J2K（耳,爲）.經(jīng)過數(shù)學計算，在二階導大于0的情況下，訐ifLr/;if疣尹0|$xamin$Al1)numCh日ngEd=0;if(examineA_l

12、)loopIoveralltrailingexamplesnumChanged+=ezaTnineExample(I)環(huán)丄weloopIoverexampleswherealphaisnot0瓦notCnumChanged+=examineExample(I)if(examineAl1=1)examineAl_Lelseiz|(numChanged=0)examineA=1參數(shù)選擇：procedureexamineExample(12)y2=targe-12alph2-Lagrangemultipiierfor丄2E2=SVMoutputonpoint12-y2checkinerrorcach

13、e)r2=E2*y2if(r2t:口丄&alph2tol&短alph20)Lf(nunibexofnon-ze丄o&non-Calpha1)i1=res口丄t.qfsecondchoiceheuristic(sect：on2*2)iftakeStep(ilfi2)return1loopovrallnoinzero蘋ndnon-CcLlphafstartingatarandompoint11=identityofcurrentalphaiftakeStep(ilfi2return1loopoverallpossibleilfstartingatarandonipoint.11=loopvaria

14、bleif(takeStep(ilf12)return1return0endprocedure參數(shù)更新：proceduretakeStep(i1,i2)if(il=i2)return0alphl=Lagrangemu1t.iplierfori1yl=targetn1El=SVMoutputonpointi11-ylcheckinerrorcache)s=yl*y2ComputeLfHviaequations(13)and(14)if(L=H)return0kl1=kernel(pointil,il)kl2=kernel(pointillfpointi2)k22=kernel(poi

15、nti2fpointi2)eta=kll+k22-2+kl2if(eta0a2=alph2+y2*(E1-E2/etaifU2H)己2=HelseLobj=objectivefunctionata2=LHobjobjactivefunctionata2=Hif(LobjHotij+ep$)a2=Helsea2=alph2if(|a2-aiph2|J-lKJIIU.th-r,T入8_1IIu幵姑訓釦1856300.126801387916420324.6581913.5073960.24024386748112373*457096-0,0822160.36704525539754386*0805

16、739.4188860.8106342724751081-0.271240G721112174-3.8247408239349932訓練結(jié)束幵紿預(yù)測預(yù)測正確率為：1.032ms200-200246呂10來Cycle.txt：Cycle2.txt：支持向量是少數(shù)，分類超平面在中間0-心超片面映射.到2維:&量h-:向，-持亠支5101520253035402.521.50.54）方-1.5-2.5-2.5-2-1.5-1-0.50O.&11.522.5不規(guī)則圖形.txt：40-35-30-25-20-15-10-分類超平面是比較優(yōu)秀的，并不是在圖像的點上，而是大約在中間。存在容錯點：人臉.txt：同樣的處理。人臉圖像更復雜一些，同一類是不連在一起的。能正確分類同樣存在容錯點。0國眇一zz-適固託丄0一口0一Ql7heart_scale：核函數(shù)為線性的時候非線性（高斯核，sita=l）：非線性（高斯核，sita=0.5）：（過小存在過度擬合的情況）Bigdata.txt：總共10000條，主要用來測試運行