基于Python的支持向量機(jī)分類算法研究分析 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)

摘要在大數(shù)據(jù)盛行的時(shí)代背景下，機(jī)器學(xué)習(xí)這門學(xué)科的廣泛應(yīng)用。并且列舉運(yùn)用Python語言進(jìn)行數(shù)據(jù)處理的優(yōu)勢(shì)，將其與傳統(tǒng)語言進(jìn)行對(duì)比，充分體現(xiàn)了Python語言在語言簡(jiǎn)潔，效率高等方面的優(yōu)勢(shì)。這也是本文最后選擇Python語言實(shí)現(xiàn)SVM算法的主要原因。本文主體內(nèi)容闡述了支持向量機(jī)算法(SVM)的基本內(nèi)涵，并且用圖示和數(shù)學(xué)方法形象具體講解了SVM的基本原理。具體分析了SVM算法中線性可分?jǐn)?shù)據(jù)、線性不可分?jǐn)?shù)據(jù)和含有outlier點(diǎn)的數(shù)據(jù)集的分類方式。通過對(duì)偶問題求解法、核函數(shù)、及SMO算法等實(shí)現(xiàn)了對(duì)最優(yōu)超平面的求解。并且完成了二分類問題向多標(biāo)簽分類問題的推廣。文章通過，使用手寫數(shù)字?jǐn)?shù)據(jù)集在Python上進(jìn)行SVM模型的訓(xùn)練與測(cè)試，體會(huì)SVM算法如何解決實(shí)際問題。具體的表現(xiàn)了用Python語言實(shí)現(xiàn)SVM算法的優(yōu)勢(shì)，直觀的展現(xiàn)了實(shí)驗(yàn)成果。關(guān)鍵字：機(jī)器學(xué)習(xí)PythonSVM最優(yōu)超平面核函數(shù)AbstractIntheeraoftheprevalenceofbigdata,machinelearningiswidelyusedinthisdiscipline.AndenumeratetheadvantagesofusingPythonlanguagefordataprocessing,compareitwithtraditionallanguages,andfullyembodytheadvantagesofPythonlanguageintermsofsimplelanguageandhighefficiency.ThisisthemainreasonwhythisarticlechoosesthePythonlanguagetoimplementtheSVMalgorithm.ThemaincontentofthispaperexpoundsthebasicconnotationofSupportVectorMachine(SVM),andexplainsthebasicprincipleofSVMconcretelywithgraphicandmathematicalmethods.Theclassificationoflinearlyseparabledata,linearlyindivisibledata,anddatasetswithoutlierpointsintheSVMalgorithmisspecificallyanalyzed.Thesolutiontotheoptimalhyperplaneisachievedthroughthedualproblemsolvingmethod,kernelfunction,andSMOalgorithm.Andithascompletedthepromotionofthetwo-classificationproblemtothemulti-labelclassificationproblem.Passingtheendofthearticle,usingthehand-writtendigitaldatasettotrainandtesttheSVMmodelinPython,tounderstandhowtheSVMalgorithmsolvespracticalproblems.ThespecificperformanceoftheSVMalgorithmusingPythonlanguageadvantages,intuitivedisplayoftheexperimentalresults.Keywords:machinelearning,Python,SVM,optimalhyperplane,kernelfunction第一章緒論1.1機(jī)器學(xué)習(xí)隨著互聯(lián)網(wǎng)計(jì)算機(jī)技術(shù)的普及應(yīng)用與發(fā)展，隨處可見的數(shù)據(jù)信息數(shù)量日益龐大，數(shù)據(jù)與信息與人們的生活愈發(fā)的息息相關(guān)。數(shù)據(jù)量的不斷擴(kuò)大和信息獲取方式的不斷增多，帶來了信息處理日益困難的問題。伴隨著硬件性能的快速增長(zhǎng)，人們寄希望于計(jì)算機(jī)可以幫助人類處理越來越龐大的數(shù)據(jù)。因此，機(jī)器學(xué)習(xí)在近年來得以迅速興起與發(fā)展。機(jī)器學(xué)習(xí)(MachineLearning,ML)是集合了多種領(lǐng)域知識(shí)的一門學(xué)科，涵蓋統(tǒng)計(jì)學(xué)、概率論、算法復(fù)雜度理論等多個(gè)領(lǐng)域。用于研究計(jì)算機(jī)通過模擬人類的學(xué)習(xí)行為，并且由此去的新知識(shí)和技能的能力。機(jī)器學(xué)習(xí)是計(jì)算機(jī)人工智能的核心，被應(yīng)用于人工智能的多個(gè)領(lǐng)域。顧名思義，機(jī)器學(xué)習(xí)是使用機(jī)器來模擬人類學(xué)習(xí)行為的一項(xiàng)技術(shù)。具體來說，機(jī)器學(xué)習(xí)是一門訓(xùn)練機(jī)器獲取新知識(shí)或新技能，包括獲取現(xiàn)有知識(shí)的學(xué)科。這里所說的“機(jī)器”，指的就是計(jì)算機(jī)、電子計(jì)算機(jī)、中子計(jì)算機(jī)、光子計(jì)算機(jī)或神經(jīng)計(jì)算機(jī)等等。機(jī)器學(xué)習(xí)已經(jīng)在很多領(lǐng)域進(jìn)行了廣泛應(yīng)用，例如：計(jì)算機(jī)視覺、DNA序列測(cè)序、語音識(shí)別、手寫識(shí)別、醫(yī)學(xué)診斷。機(jī)器學(xué)習(xí)算法是一種能夠從數(shù)據(jù)中進(jìn)行持續(xù)學(xué)習(xí)的算法。Mitchell(1997)為其提供了一個(gè)簡(jiǎn)潔的定義：對(duì)于某類任務(wù)T和性能度量P，一個(gè)計(jì)算機(jī)程序被認(rèn)為可以從經(jīng)驗(yàn)E中學(xué)習(xí)是指，通過經(jīng)驗(yàn)E改進(jìn)后，它在任務(wù)T上由性能度量P衡量的性能有所提升。其中任務(wù)T指的是人們希望機(jī)器可以實(shí)現(xiàn)的功能。在分類、回歸、異常檢測(cè)、轉(zhuǎn)錄、機(jī)器翻譯等任務(wù)上，機(jī)器學(xué)習(xí)已經(jīng)有了廣泛的應(yīng)用。而獲取經(jīng)驗(yàn)E的過程可以分為無監(jiān)督算法和有監(jiān)督算法。兩者的區(qū)別在于是否對(duì)數(shù)據(jù)集中的數(shù)據(jù)樣本給予標(biāo)簽。1.2支持向量機(jī)在監(jiān)督學(xué)習(xí)中，支持向量機(jī)是影響力最大的機(jī)器學(xué)習(xí)方法之一。支持向量機(jī)由CorinnaCortes和Vapnik等人于1995年提出，其創(chuàng)新的核技術(shù)使其不再局限于對(duì)線性數(shù)據(jù)的處理，在對(duì)于非線性數(shù)據(jù)的分類上也有了良好的表現(xiàn)，并已被廣泛應(yīng)用于文本識(shí)別、手寫字體識(shí)別、及時(shí)間序列預(yù)測(cè)等小型分類任務(wù)中。支持向量機(jī)(SupportVectorMachines，SVM)這種機(jī)器學(xué)習(xí)方法是以統(tǒng)計(jì)學(xué)理論、VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理為基礎(chǔ)的。在解決特定問題，如小樣本、非線性和高維模式問題時(shí)表現(xiàn)優(yōu)異，并且大大優(yōu)化克服了機(jī)器學(xué)習(xí)中會(huì)遇到的“維數(shù)災(zāi)難”問題與“過學(xué)習(xí)”問題。SVM具有如下特點(diǎn)：(1)以非線性映射為理論基礎(chǔ)，利用內(nèi)積核函數(shù)實(shí)現(xiàn)由低維空間到高維空間的非線性映射。(2)以尋找最優(yōu)超平面為目標(biāo)，核心思想為最大化分類間隔。(3)以少數(shù)支持向量為訓(xùn)練結(jié)果，去除了大量冗余樣本，具有良好的魯棒性。(4)理論基礎(chǔ)堅(jiān)實(shí)、數(shù)學(xué)模型簡(jiǎn)單明了，可以歸結(jié)為一個(gè)受約束的二次型規(guī)劃(QuadraticProgramming，QP)的求解問題。(5)可以運(yùn)用牛頓法、內(nèi)點(diǎn)法等經(jīng)典優(yōu)化算法，方便快捷地求得最優(yōu)解。SVM作為一類二分類模型，可以處理以下三類數(shù)據(jù)：(1)線性可分?jǐn)?shù)據(jù)。使硬間隔最大化，進(jìn)行線性分類器學(xué)習(xí)(2)近似線性可分?jǐn)?shù)據(jù)。使軟間隔最大化，進(jìn)行線性分類器學(xué)習(xí)(3)線性可分?jǐn)?shù)據(jù)。使核函數(shù)與軟間隔最大化，進(jìn)行非線性分類器學(xué)習(xí)。平面內(nèi)的直線，對(duì)應(yīng)線性分類器；平面上的曲線，對(duì)應(yīng)非線性分類器。硬間隔雖然可以將線性可分?jǐn)?shù)據(jù)集中的樣本正確分類，但是受到outlier樣本的很大影響，不推薦使用。軟間隔可以對(duì)近似線性可分?jǐn)?shù)據(jù)和非線性可分?jǐn)?shù)據(jù)進(jìn)行分類，離超平面很近的outlier點(diǎn)可以允許被錯(cuò)誤分類，從而可以更廣泛的應(yīng)用。1.3Python語言Python這門語言已經(jīng)產(chǎn)生并發(fā)展了30余年，是目前最受歡迎的程序設(shè)計(jì)語言，也是通用編程語言中最接近自然語言的。Python側(cè)重于求解計(jì)算問題，其具有語法簡(jiǎn)單，語言表達(dá)層次高等特點(diǎn)，這與計(jì)算機(jī)問題解決中的思維理念相吻合。Python語言將問題和問題的解決方案進(jìn)行簡(jiǎn)化，從而達(dá)到問題的自動(dòng)化求解，是當(dāng)下最直觀的利用計(jì)算機(jī)解決復(fù)雜信息系統(tǒng)的工具。Python語言的適用群體廣泛，任何需要使用計(jì)算機(jī)來解決計(jì)算問題的人群都可以使用，即使是非計(jì)算機(jī)專業(yè)從業(yè)人員。Python語言是一種輕化語法，弱化類型的計(jì)算機(jī)語言，同C語言等相比較，不需要指針和地址等計(jì)算機(jī)系統(tǒng)內(nèi)必須的結(jié)構(gòu)元素；可以不定義變量就直接使用（解釋器會(huì)自動(dòng)匹配）；語言內(nèi)部通過UTF-8編碼來實(shí)現(xiàn)，字符串類型獨(dú)立，操作多語言文本時(shí)，語言大大簡(jiǎn)化，可以優(yōu)秀的支持中文；運(yùn)用變長(zhǎng)列表代替定長(zhǎng)數(shù)組，可以將多種數(shù)據(jù)類型進(jìn)行兼容并可以靈活地表示集合長(zhǎng)度。Python語言除了有基本語法，還是一個(gè)腳本語言，直接運(yùn)行源代碼便可以執(zhí)行，這可以讓程序運(yùn)行和源代碼相融合。這種模式的優(yōu)勢(shì)在于：(1)有利于源代碼維護(hù)。(2)可以跨操作系統(tǒng)操作。(3)可以實(shí)現(xiàn)代碼的交流與設(shè)計(jì)。Python具有簡(jiǎn)潔的語言代碼，能支持兩種設(shè)計(jì)方法，即：面向過程與面向?qū)ο筮@兩種設(shè)計(jì)方法，且不需要通過函數(shù)封裝程序，因此代碼長(zhǎng)度僅為C語言代碼長(zhǎng)度的十分之一到五分之一。綜合以上所談，總結(jié)Python語言的優(yōu)點(diǎn)如下：(1)Python這種解釋語言可大大方便編程。解釋語言具有先天優(yōu)勢(shì)，即：不需要編譯時(shí)間，可以大大提高工作效率。(2)Python有很多非常成熟的庫可以利用，開發(fā)生態(tài)優(yōu)秀。如：NumPy（存儲(chǔ)和處理大型矩陣）、SciPy（高效的數(shù)學(xué)運(yùn)算）、pandas（處理數(shù)據(jù)的函數(shù)和方法）、matplotlib（數(shù)據(jù)操作、聚合和可視化）等。(3)Python的運(yùn)行效率不低。與Python友好的庫可以提高程序運(yùn)行的速度，在團(tuán)隊(duì)的有力支撐下，庫的效率可比程序員用C語言調(diào)試優(yōu)化一個(gè)月的效率還高。在本文中，介紹了支持向量機(jī)可解決的線性數(shù)據(jù)分類、近似線性數(shù)據(jù)分類和非線性數(shù)據(jù)分類這三類問題，并且通過使用具有編寫效率高、語言簡(jiǎn)潔和可直接使用的第三方支持庫種類全面等特點(diǎn)的Python來實(shí)現(xiàn)SVM算法，快捷便利地實(shí)現(xiàn)數(shù)據(jù)樣本的分類問題，展現(xiàn)了SVM與Python在機(jī)器學(xué)習(xí)方面的優(yōu)勢(shì)所在。1.4論文主要研究?jī)?nèi)容本文分析了在信息化飛速發(fā)展的大數(shù)據(jù)背景下，運(yùn)用Python語言處理數(shù)據(jù)的優(yōu)勢(shì)與可行性，重點(diǎn)講解了SVM算法的基本原理，和在面臨不同數(shù)據(jù)集的分類問題時(shí)所用的具體方法，對(duì)此進(jìn)行了詳盡的數(shù)學(xué)分析和原理闡述。并最終用Python語言實(shí)現(xiàn)了多標(biāo)簽的SVM分類訓(xùn)練。第二章支持向量機(jī)的原理2.1線性可分問題對(duì)于一個(gè)給定的數(shù)據(jù)樣本集D={x1,y1,x2,y2,…,x如圖2.1所示，在如下的二維平面中，將兩種不是同一類型的數(shù)據(jù)分別用圖形O和X進(jìn)行表示，對(duì)于線性可分的兩類數(shù)據(jù)，可以用一條直線將兩類數(shù)據(jù)分開。這樣的直線就是一個(gè)超平面。將這條直線一側(cè)的數(shù)據(jù)點(diǎn)標(biāo)記為y=-1

，另一側(cè)的數(shù)據(jù)點(diǎn)標(biāo)記為y=1。圖2.1如圖2.2所示，在一個(gè)給定樣本空間中，超平面可由式(2-1)表示：WTx+b=0(2式中，用W=(W1;W2;…;Wd)表示超平面的法向量，位移項(xiàng)則用常數(shù)b表示。由法向量W圖2.2對(duì)于數(shù)據(jù)集里任意數(shù)據(jù)點(diǎn)，當(dāng)yi=1時(shí)，有WTxi+b>0,當(dāng)yWTxi+b≥1,當(dāng)式中等號(hào)成立的時(shí)候，xi2.2函數(shù)間隔與幾何間隔通過觀察WTxi+b的符號(hào)與yi的符號(hào)一致與否可判斷分類超平面是否選取正確，所以，可以用yi(WγF=yWTx+b據(jù)此，在超平面(W,b)中關(guān)于樣本集D中的所有樣本點(diǎn)xi,yiγF=minγFi(i=1,…,n)但是，當(dāng)W和b成比例改變時(shí)，函數(shù)間隔的值也會(huì)成比例變化，如W和b變化為3W和3b時(shí)，函數(shù)間隔的值也會(huì)變?yōu)樵档?倍，所以如此定義的函數(shù)間隔是不完全正確的，還需要引入幾何間隔(Geometricalmargin)這一定義。樣本集D中任一點(diǎn)xi到超平面(W,b)的距離，定義為幾何間隔。如圖2.3所示，在二維空間上有一點(diǎn)xi和超平面(W,b)（在此為直線），xxi=x0+dw圖2.3式(2-6)中的||W||為向量W的L2范數(shù)，即將向量W中的各元素求平方和后開根號(hào)所得的值。將點(diǎn)xi代入超平面方程式(2-1)WTx0將式(2-6)兩邊同時(shí)乘上WT，又由WTW=||w||2d=WTx由于間隔一般為正值，因此將幾何距離與類別y的乘積定義為幾何間隔，即：γG=γF|W由式(2-8)可看出，函數(shù)間隔乘向量W的L2范數(shù)就可以得到幾何間隔。2.3最大間隔分類器如圖2.4所示，對(duì)于一個(gè)樣本集D，存在多個(gè)滿足分類條件的超平面，這些超平面與數(shù)據(jù)點(diǎn)之間的間隔不一，甚至部分幾乎緊貼數(shù)據(jù)點(diǎn)。對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類的時(shí)候，為了提高分類的可靠性，需要尋找最優(yōu)超平面(OptimalHyperPlane)，使得超平面的兩側(cè)的數(shù)據(jù)點(diǎn)與超平面的間隔，即圖2.5中的GAP的值盡可能大。圖2.4圖2.5如圖2.5所示，最優(yōu)超平面用圖中的實(shí)線來表示，此條實(shí)線到位于其兩側(cè)的虛線的距離相等，此距離等于幾何間隔，兩虛線之間的距離為幾何間隔的2倍。在超平面確定之后，再等比例地放大或縮小W和b，WTx+b的值也會(huì)隨之放大或縮小，所以函數(shù)間隔對(duì)于使間隔值最大化沒有意義。而幾何間隔為函數(shù)的間隔的||w||-1，可以使得幾何間隔在放大或縮小為了方便公式的推導(dǎo)，令式(2-8)中的函數(shù)間隔γF為1γG=1|W|目標(biāo)即為求在約束條件yiWmaxγG=max2.4用拉格朗日乘數(shù)法求最大值由上文可知，SVM的原目標(biāo)函數(shù)為幾何間隔的兩倍，即：max2γG=max2|W|為了求解方便，將目標(biāo)函數(shù)轉(zhuǎn)換為：min|W|22s.t.yiWT圖2.6(2-13)現(xiàn)有的目標(biāo)函數(shù)式(2-12)為二次函數(shù)，約束條件為線性條件，該問題可以使用拉格朗日對(duì)偶性(LagrangeDuality)轉(zhuǎn)換為優(yōu)化對(duì)偶變量(Dualvariable)(2-13)L令：θW=maxα當(dāng)約束條件不被滿足，即yiWTxi+b-1＜θW=W22，滿足約束條件+∞，不滿足約束條件由式(2-14)，目標(biāo)函數(shù)可轉(zhuǎn)換為：minW,bθW=minW,b其中，p*為問題的最優(yōu)解，為方便求解，根據(jù)對(duì)偶性，將式(2-15)轉(zhuǎn)換為：maxαi≥0min其中，d*為新式的最優(yōu)值，且d*≤p*，當(dāng)滿足一定條件時(shí)等號(hào)成立，d*為p*的近似解。2.5對(duì)偶問題求解(1)假設(shè)α為定值，求min(2-18)首先對(duì)W、b，分別求偏導(dǎo)數(shù)，且令偏導(dǎo)數(shù)值為0(2-18)?(2-19)將式(2-18)的結(jié)果代入式(2-13)(2-19)L=推導(dǎo)過程如下：L===-=-==(2)根據(jù)(1)，變量W和b已被消去，只有α未知，由式(2-19)，求minW,bLmaxs.t.αi≥0(2-(2-21)求得最優(yōu)解αi，記作αi*。根據(jù)KKT(2-21)W求得最優(yōu)超平面為：WTx+b*=0第三章線性不可分3.1核函數(shù)在實(shí)際應(yīng)用的求解中，原始數(shù)據(jù)往往是線性不可分的。如圖3.1所示的二維空間內(nèi)，有若干紅球與籃球，顯然，無法找到一個(gè)超平面（直線）將這兩類小球進(jìn)行分類。對(duì)于這種線性不可分的情況，在SVM中，可以使用核函數(shù)和松弛變量來求解這類問題。圖3.1數(shù)據(jù)在原始空間內(nèi)不線性可分的問題，可以通過將其投射到高維空間這一辦法來解決。其原理是當(dāng)數(shù)據(jù)線性不可分時(shí)，SVM會(huì)優(yōu)先在低維空間中進(jìn)行計(jì)算，然后使用核函數(shù)將原始空間映射到高維空間，達(dá)到在高維空間中找到最優(yōu)超平面的效果，成功地實(shí)現(xiàn)在低維空間本身將不能分類的非線性數(shù)據(jù)分類。如圖3.2所示，這些數(shù)據(jù)在二維空間中無法進(jìn)行線性分類，因此將原始數(shù)據(jù)投射到三維空間中進(jìn)行分類。圖3.2然而，若一遇到非線性數(shù)據(jù)就將其投射到高維空間，那么一個(gè)原始二維空間經(jīng)映射將成為一個(gè)五維空間；一個(gè)原始三維空間經(jīng)映射將成為一個(gè)19維度空間。新空間的維數(shù)呈爆炸式增長(zhǎng)，帶來了龐大而困難的計(jì)算量。并且，在無窮維的情況下，無法進(jìn)行計(jì)算。核函數(shù)的優(yōu)勢(shì)在于，由于在SVM的求解過程中只用到內(nèi)積計(jì)算，而核函數(shù)的值恰好等于其在高維空間內(nèi)的內(nèi)積值，因此可以大大簡(jiǎn)化SVM的計(jì)算過程。此外，與傳統(tǒng)算法Logistic回歸算法、DecisionTree算法相比，利用核函數(shù)進(jìn)行數(shù)據(jù)分類時(shí)，效果更加完美。在圖3.3中的三種分類方式效果對(duì)比圖可以很直觀的體現(xiàn)這一優(yōu)勢(shì)。圖3.3如表3.1所示，常用的核函數(shù)有多項(xiàng)式核函數(shù)、高斯核RBF函數(shù)、Sigmoid核函數(shù)。表3.1常用核函數(shù)核函數(shù)名稱核函數(shù)式多項(xiàng)式核函數(shù)K高斯核RBF函數(shù)KSigmoid核函數(shù)K在選擇核函數(shù)時(shí)，需要依靠先驗(yàn)領(lǐng)域知識(shí)或交叉驗(yàn)證等方法，若沒有更多信息，普遍選用高斯核函數(shù)。3.2松弛變量在前文中，已經(jīng)討論了線性可分?jǐn)?shù)據(jù)和非線性可分?jǐn)?shù)據(jù)的處理方式，即當(dāng)數(shù)據(jù)為線性可分時(shí)，可找到一個(gè)超平面將數(shù)據(jù)直接進(jìn)行分類；當(dāng)處理非線性數(shù)據(jù)時(shí)，可以使用核函數(shù)將原始數(shù)據(jù)投射到更高維空間后進(jìn)行分類。然而，還是存在一些特殊情況對(duì)于以上兩種方法都不適用。如圖3.4所示有若干藍(lán)色小球與粉色小球，其中有一個(gè)藍(lán)色小球(outlier)M偏向于粉色小球堆。黑色虛線為根據(jù)數(shù)據(jù)計(jì)算得到的超平面，此時(shí)該超平面嚴(yán)格地將紅色小球與藍(lán)色小球進(jìn)行了分類，然而GAP的值卻變得很小。甚至在某些情況下，當(dāng)藍(lán)色小球M混入粉色小球堆中，SVM無法找到一個(gè)合適的超平面將兩類小球進(jìn)行分離。如果將偏離的藍(lán)色小球忽略后進(jìn)行分類，可以獲得圖中的GAP更寬的紅色超平面。MM圖3.4為了應(yīng)對(duì)這樣的由于個(gè)別數(shù)據(jù)點(diǎn)嚴(yán)重偏離大多數(shù)數(shù)據(jù)點(diǎn)所在區(qū)域的情況，SVM允許有個(gè)別數(shù)據(jù)點(diǎn)偏離超平面，即某些數(shù)據(jù)點(diǎn)的函數(shù)間隔小于1。在實(shí)際應(yīng)用中，引入松弛變量(slackvariable)ξi≥0，考慮outlier后的WTxi+b式(3-1)亦可表示為：yi(WTxi+b)由式(3-2)，顯然當(dāng)ξi取無限大值時(shí)，所有超平面都可以滿足條件，因此，在原目標(biāo)函數(shù)上添加一項(xiàng)，使ξi的和也取得最小值。隨之，SVM的目標(biāo)函數(shù)由式(2-13)轉(zhuǎn)化為式(3-3ms.t.yiWTxiξi其中，C為權(quán)重值，用于在最大化GAP和最小化數(shù)據(jù)偏差之間平衡。(3-4)同樣，在約束條件前乘以拉格朗日乘子α，從而將目標(biāo)函數(shù)與約束條件融合為一個(gè)函數(shù)表達(dá)式，構(gòu)造得到新的拉格朗日函數(shù)：(3-4)L為求得最優(yōu)解，令L對(duì)W，b，ξi的偏導(dǎo)數(shù)都為0?L?W=0將解代入式(3-4)得目標(biāo)函數(shù)：maxs.t.0≤α將式(3-6)與式(2-20)對(duì)比可知，含有outlier的分類問題中的αi多了上限C的約束條件。而在核函數(shù)中也只需把xi,xj替換成Kx3.3高斯核函數(shù)與松弛變量的綜合應(yīng)用綜合核函數(shù)與松弛變量的使用，可以更好的解決分類問題。如圖3-5所示有若干紅球與綠球，且個(gè)別紅色小球混入了綠色小球堆中，而個(gè)別綠色小球混入了紅色小球中。通過使用高斯核，獲得超平面后映射回原空間中，得到曲線將兩類小球分離，而通過引入松弛變量，允許有個(gè)別小球偏離超平面。在已經(jīng)使用高斯核的基礎(chǔ)上，選擇不同的C和ξ可以獲得不同的分類效果，觀察圖3.5(a)和圖3.5(e)、圖3.5(b)和圖3.5(f)、圖3.5(c)和圖3.5(g)、圖3.5(d)和圖3.5(h)四組圖片可知，懲罰因子C越大，意味著對(duì)outlier點(diǎn)約重視，越不愿意放棄outlier點(diǎn)；而觀察圖3.5(a)、圖3.5(d)和圖3.5(e)、圖3.5(h)兩組圖片可知，ξ值越大，意味著outlier點(diǎn)的數(shù)量和GAP值越小。在實(shí)際應(yīng)用中，需要選擇合適的核函數(shù)、懲罰因子C與松弛變量ξ的值以獲得合適的超平面。圖3.5(a)圖3.5(b)圖3.5(c)圖3.5(d)圖3.5(e)圖3.5(f)圖3.5(g)圖3.5(h)相關(guān)代碼如下所示。3.4多標(biāo)簽分類(multilabelclassification）多標(biāo)簽分類可以轉(zhuǎn)換為單標(biāo)簽分類。其中一種方法是將每個(gè)多標(biāo)記實(shí)例的所屬標(biāo)記聯(lián)合起來創(chuàng)建為一個(gè)新的標(biāo)記。這種方法被稱Label-Powerset。由此，多標(biāo)簽分類問題轉(zhuǎn)換為了單標(biāo)簽分類問題。轉(zhuǎn)換后的分類問題可以使用任何分類器進(jìn)行分類。另一種方法是采用一對(duì)多(OAA)策略：訓(xùn)練針對(duì)類別i的二元分類器，將類別i訓(xùn)練樣本與其他樣本分離。在分類過程中，x被分為了多標(biāo)簽類。其中n為類別數(shù)。這種方法稱為二元相關(guān)方法，此方法是單標(biāo)簽一對(duì)多策略的擴(kuò)展。

3.5SMO求解對(duì)偶問題在第三章中得到了SVM的目標(biāo)函數(shù)式(3-6)，為了實(shí)求解結(jié)果同時(shí)適用于線性可分與線性不可分問題，首先將目標(biāo)函數(shù)式(3-6)中的xi,xj替換為核函數(shù)Kmins.t.0≤αi≤C該目標(biāo)函數(shù)需要求解向量α的n個(gè)參數(shù)(α1,α2,α3,…,αn),有多種算法可以求解該目標(biāo)函數(shù)，但序列最小優(yōu)化算法SMO假設(shè)已經(jīng)固定了n-2個(gè)參數(shù)(α3,α4,αmin(3-8)(3-9)其中M為常量，Ki(3-9)為了求解該子問題，首先將目標(biāo)函數(shù)中的等式約束轉(zhuǎn)換為：α則α1=y1(ζ-α2y2?ψ(α2)可求解得到α2，帶入式(3-9)得α1，分別記作α2new和α1new。由于ζ的值難以計(jì)算，對(duì)式(3-根據(jù)式(2-21)的超平面表達(dá)式可知，新的數(shù)據(jù)點(diǎn)的預(yù)測(cè)值為：fx=i=1nαi則v1與vv1=f將其帶入式（3-10），并令K11+Kα2new=α2old由于此時(shí)獲得的α2new在計(jì)算中未考慮約束條件，將α2new記作α2new,unclipped，而約束條件在二維平面中的表示為圖3.6，最優(yōu)解必須在圖中的線段上取得，因此L≤α2LL=max0,α1經(jīng)過上述約束條件的修剪即可獲得最優(yōu)解α2α2new=H,α2獲得α2new后，根據(jù)α2new與α圖3-6而b的值首先需滿足如下條件：b=b1,0<α更新格式為：b1new=b2new=當(dāng)α1與α2更新后，b和E的值也同時(shí)需要更新，當(dāng)所有α都更新后，即可獲得分類平面函數(shù)式(3-以上所述為已選擇兩個(gè)乘子后，對(duì)兩乘子的求解過程。而乘子的選擇的步驟為：掃描所有乘子，將第一個(gè)不滿足KKT條件的乘子進(jìn)行更新。在所有滿足KKT條件的乘子中尋找滿足條件minE

第四章SVM分類實(shí)例4.1使用Python運(yùn)行SVM分類實(shí)例在前文中介紹了SVM分類算法的基本理論。SVM的基本思想為尋找樣本空間的超平面并在最大化數(shù)據(jù)間隔的基礎(chǔ)上進(jìn)行分類。當(dāng)處理非線性問題時(shí)，SVM引入了核函數(shù)，將低維數(shù)據(jù)映射至高維數(shù)據(jù)后使其變?yōu)榫€性可分后進(jìn)行分類?？紤]到數(shù)據(jù)樣本中可能存在“噪聲”，引入了松弛變量，使分類器有一定的容錯(cuò)能力。本章通過使用mnist手寫數(shù)字?jǐn)?shù)據(jù)集在Python上進(jìn)行SVM模型的訓(xùn)練與測(cè)試，體會(huì)SVM算法如何解決實(shí)際問題。Mnist手寫數(shù)字?jǐn)?shù)據(jù)集是機(jī)器學(xué)習(xí)的一個(gè)典型數(shù)據(jù)集，其數(shù)據(jù)來源于250個(gè)不同的人的手寫數(shù)字，共包含70000張28*28像素的圖片。如圖4-1所示為一個(gè)典型的手寫數(shù)字，對(duì)于人眼而言可以輕易地識(shí)別出該數(shù)字為“0”——高度比寬度稍長(zhǎng)的一個(gè)橢圓。然而對(duì)于計(jì)算機(jī)而言很難將人類的這種直觀感受用算法表達(dá)出來。圖4.1手寫數(shù)字圖表4.1分類器結(jié)果預(yù)測(cè)值實(shí)際值PositiveNegative正TPFN負(fù)FPTN機(jī)器學(xué)習(xí)通過大量樣本學(xué)習(xí)認(rèn)知規(guī)律這一方法與人類類似，但其具體地學(xué)習(xí)認(rèn)知規(guī)律的過程與人類有所不同。對(duì)于SVM，解決本問題的思路是首先讀取大量帶有標(biāo)簽的手寫數(shù)字，之后尋找出可將不同標(biāo)簽數(shù)據(jù)進(jìn)行分類的超平面，即獲得了預(yù)測(cè)函數(shù)——可以識(shí)別出新的手寫數(shù)字的規(guī)則。此外，隨著樣本數(shù)量的增加，SVM可以學(xué)習(xí)到更準(zhǔn)確地認(rèn)知規(guī)律。然而，當(dāng)樣本數(shù)過多時(shí)，也可能出現(xiàn)過擬合的情況，即模型過度地?cái)M合了訓(xùn)練數(shù)據(jù)，而對(duì)于測(cè)試數(shù)據(jù)而言，其分類效果卻較差。圖4.2為樣本集中的部分圖像，由于mnist手寫數(shù)字?jǐn)?shù)據(jù)集原始數(shù)據(jù)為圖像，而SVM