基于Python的支持向量機(jī)分類算法研究

1、摘 要在大數(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語言在語言簡潔，效率高等方面的優(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ù)集在Pytho

2、n上進(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í) Python SVM 最優(yōu)超平面 核函數(shù) AbstractIn the era of the prevalence of big data, machine learning is widely used in this discipline. And enumerate the advantages of using Python language for data processing, compare it with traditio

3、nal languages, and fully embody the advantages of Python language in terms of simple language and high efficiency. This is the main reason why this article chooses the Python language to implement the SVM algorithm.The main content of this paper expounds the basic connotation of Support Vector Machi

4、ne (SVM), and explains the basic principle of SVM concretely with graphic and mathematical methods. The classification of linearly separable data, linearly indivisible data, and data sets with outlier points in the SVM algorithm is specifically analyzed. The solution to the optimal hyperplane is ach

5、ieved through the dual problem solving method, kernel function, and SMO algorithm. And it has completed the promotion of the two-classification problem to the multi-label classification problem.Passing the end of the article, using the hand-written digital data set to train and test the SVM model in

6、 Python, to understand how the SVM algorithm solves practical problems. The specific performance of the SVM algorithm using Python language advantages, intuitive display of the experimental results.Keywords: machine learning, Python, SVM, optimal hyperplane, kernel function第一章 緒論1.1機(jī)器學(xué)習(xí)隨著互聯(lián)網(wǎng)計(jì)算機(jī)技術(shù)的普及

7、應(yīng)用與發(fā)展，隨處可見的數(shù)據(jù)信息數(shù)量日益龐大，數(shù)據(jù)與信息與人們的生活愈發(fā)的息息相關(guān)。數(shù)據(jù)量的不斷擴(kuò)大和信息獲取方式的不斷增多，帶來了信息處理日益困難的問題。伴隨著硬件性能的快速增長，人們寄希望于計(jì)算機(jī)可以幫助人類處理越來越龐大的數(shù)據(jù)。因此，機(jī)器學(xué)習(xí)在近年來得以迅速興起與發(fā)展。機(jī)器學(xué)習(xí)(Machine Learning, 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ù)。具體來說

8、，機(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è)簡潔的定義：對(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ù)

9、上，機(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ī)由Corinna Cortes和Vapnik等人于1995年提出，其創(chuàng)新的核技術(shù)使其不再局限于對(duì)線性數(shù)據(jù)的處理，在對(duì)于非線性數(shù)據(jù)的分類上也有了良好的表現(xiàn)，并已被廣泛應(yīng)用于文本識(shí)別、手寫字體識(shí)別、及時(shí)間序列預(yù)測(cè)等小型分類任務(wù)中。支持向量機(jī)(Support Vector Machines，SVM)這種機(jī)器學(xué)習(xí)方法是以統(tǒng)計(jì)學(xué)理論、VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理為基礎(chǔ)的。在解決特定問題，如小

10、樣本、非線性和高維模式問題時(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é)為一個(gè)受約束的二次型規(guī)劃(Quadratic Programming，QP)的求解問題 。(5)可以運(yùn)用牛頓法、內(nèi)點(diǎn)法等經(jīng)典優(yōu)化算法，方便快捷地求得最優(yōu)解。SVM作為一類二分類模型，可以處理以下三類數(shù)據(jù)：(1)線性可分

11、數(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.3 Python語言Python這門語言已經(jīng)產(chǎn)生并發(fā)展了30余年，是目前最受歡迎的程序設(shè)計(jì)語言，也是通用編程語言中最接近自然語言的。Python側(cè)

12、重于求解計(jì)算問題，其具有語法簡單，語言表達(dá)層次高等特點(diǎn)，這與計(jì)算機(jī)問題解決中的思維理念相吻合。Python語言將問題和問題的解決方案進(jì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í)，語言大大簡化，可以優(yōu)秀的支持中文；運(yùn)用變長

13、列表代替定長數(shù)組，可以將多種數(shù)據(jù)類型進(jìn)行兼容并可以靈活地表示集合長度。Python語言除了有基本語法，還是一個(gè)腳本語言，直接運(yùn)行源代碼便可以執(zhí)行，這可以讓程序運(yùn)行和源代碼相融合。這種模式的優(yōu)勢(shì)在于：(1)有利于源代碼維護(hù)。(2)可以跨操作系統(tǒng)操作。(3)可以實(shí)現(xiàn)代碼的交流與設(shè)計(jì)。Python具有簡潔的語言代碼，能支持兩種設(shè)計(jì)方法，即：面向過程與面向?qū)ο筮@兩種設(shè)計(jì)方法，且不需要通過函數(shù)封裝程序，因此代碼長度僅為C語言代碼長度的十分之一到五分之一。綜合以上所談，總結(jié)Python語言的優(yōu)點(diǎn)如下：(1)Python這種解釋語言可大大方便編程。解釋語言具有先天優(yōu)勢(shì)，即：不需要編譯時(shí)間，可以大大提高工作效

14、率。(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ù)分類這三類問題，并且通過使用具有編寫效率高、語言簡潔和可直接使用的第三方支持庫種類全面等特點(diǎn)的Python來實(shí)現(xiàn)SVM算法，快捷便利地實(shí)現(xiàn)數(shù)據(jù)樣本的分類

15、問題，展現(xiàn)了SVM與Python在機(jī)器學(xué)習(xí)方面的優(yōu)勢(shì)所在。1.4 論文主要研究內(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,xn,yn ，支持向量機(jī)的基本原理就是要在給定的樣本空間中找到一個(gè)超平面將不是同一類型類型的數(shù)據(jù)樣本分開。如圖2.1所示，在如下的二維平面中，將兩種不是同一類型的數(shù)據(jù)

16、分別用圖形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-1)式中，用W=(W1; W2;Wd)表示超平面的法向量，位移項(xiàng)則用常數(shù)b表示。由法向量W和位移項(xiàng)b確定的劃分超平面記為(W,b)。 圖2.2對(duì)于數(shù)據(jù)集里任意數(shù)據(jù)點(diǎn)，當(dāng)yi=1時(shí)，有WTxi+b>0,當(dāng)yi=-1時(shí)，有WTxi+b<0，即：WTxi+b1,yi=1WTxi+b1,yi=1 (2-2)當(dāng)式中等

17、號(hào)成立的時(shí)候，xi為距離超平面最近的樣本點(diǎn)，這些樣本點(diǎn)被稱為支持向量。2.2函數(shù)間隔與幾何間隔通過觀察WTxi+b的符號(hào)與yi的符號(hào)一致與否可判斷分類超平面是否選取正確，所以，可以用yi(WTxi+b)的正負(fù)性來判斷分類的正確性，由此，定義函數(shù)間隔(Functional margin)為：F=yWTx+b (2-3)據(jù)此，在超平面(W,b)中關(guān)于樣本集D中的所有樣本點(diǎn)xi,yi的最小函數(shù)間隔值便是超平面(W,b)對(duì)于樣本集D的函數(shù)間隔：F=minFi(i=1,n) (2-4)但是，當(dāng)W和b成比例改變時(shí)，函數(shù)間隔的值也會(huì)成比例變化，如W和b變化為3W和3b時(shí)，函數(shù)間隔的值也會(huì)變?yōu)樵档?倍，所以

18、如此定義的函數(shù)間隔是不完全正確的，還需要引入幾何間隔(Geometrical margin)這一定義。樣本集D中任一點(diǎn)xi到超平面(W,b)的距離，定義為幾何間隔。如圖2.3所示，在二維空間上有一點(diǎn)xi和超平面(W,b)（在此為直線），x0為xi在超平面上的垂直投影點(diǎn)，d為點(diǎn)xi到該超平面的距離，則有：xi=x0+dw|w| (2-5)圖2.3式(2-6)中的|W|為向量W的L2范數(shù)，即將向量W中的各元素求平方和后開根號(hào)所得的值。將點(diǎn)xi代入超平面方程式(2-1)，可得：WTx0=b (2-6)將式(2-6)兩邊同時(shí)乘上WT，又由WTW=|w|2及式(2-7)可推出：d=WTx+b|W| (2

19、-7)由于間隔一般為正值，因此將幾何距離與類別y的乘積定義為幾何間隔，即：G=F|W| (2-8)由式(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)超平面(Optimal Hyper Plane)，使得超平面的兩側(cè)的數(shù)據(jù)點(diǎn)與超平面的間隔，即圖2.5中的GAP的值盡可能大。 圖2.4 圖2.5 如圖2.5所示，最優(yōu)超平面用圖中的實(shí)線來表示，此條實(shí)線到位于其兩側(cè)的虛線的距離相等，此

20、距離等于幾何間隔，兩虛線之間的距離為幾何間隔的2倍。在超平面確定之后，再等比例地放大或縮小W和b，WTx+b的值也會(huì)隨之放大或縮小，所以函數(shù)間隔對(duì)于使間隔值最大化沒有意義。而幾何間隔為函數(shù)的間隔的|w|1，可以使得幾何間隔在放大或縮小W和b的時(shí)候保持不變，幾何間隔只因超平面的改變而改變。綜上所述，用于尋找最優(yōu)超平面的最大間隔指幾何間隔。為了方便公式的推導(dǎo)，令式(2-8)中的函數(shù)間隔F為1，可得：G=1|W| (2-9)目標(biāo)即為求在約束條件yiWTxi+b1(i=1,2,n)下，幾何間隔的最大值，即：max G=max1|W| (2-10)2.4用拉格朗日乘數(shù)法求最大值由上文可知，SVM的原目標(biāo)

21、函數(shù)為幾何間隔的兩倍，即：max 2G=max2|W| (2-11)為了求解方便，將目標(biāo)函數(shù)轉(zhuǎn)換為：min|W|22 (2-12)s.t. yiWTxi+b1(i=1,2,n) 圖2.6(2-13)現(xiàn)有的目標(biāo)函數(shù)式(2-12)為二次函數(shù)，約束條件為線性條件，該問題可以使用拉格朗日對(duì)偶性(Lagrange Duality)轉(zhuǎn)換為優(yōu)化對(duì)偶變量(Dual variable)的問題。在約束條件前乘以拉格朗日乘子，從而將目標(biāo)函數(shù)與約束條件融合為一個(gè)函數(shù)表達(dá)式：LW,b,=|W|22i=1niyiWTxi+b1令：W=maxi0LW,b, (2-14)當(dāng)約束條件不被滿足，即yiWTxi+b10時(shí)，顯然，W

22、=+；當(dāng)約束條件得到滿足時(shí)，即yiWTxi+b10時(shí)，W=|W|22，因此：W=W22，滿足約束條件+，不滿足約束條件 (2-15)由式(2-14)，目標(biāo)函數(shù)可轉(zhuǎn)換為：minW,bW=minW,bmaxi0LW,b,=p (2-16)其中，p*為問題的最優(yōu)解，為方便求解，根據(jù)對(duì)偶性，將式(2-15)轉(zhuǎn)換為：max i0min W,bLW,b,=d (2-17)其中，d*為新式的最優(yōu)值，且d*p*，當(dāng)滿足一定條件時(shí)等號(hào)成立，d*為p*的近似解。2.5對(duì)偶問題求解(1)假設(shè)為定值，求min W,bLW,b,。(2-18)首先對(duì)W、b，分別求偏導(dǎo)數(shù)，且令偏導(dǎo)數(shù)值為0：LW=0Lb=0W=i=1niy

23、ixii=1niyi=0(2-19)將式(2-18)的結(jié)果代入式(2-13)，得：LW,b,=12i,j=1nijyiyjxiTxji,j=1nijyiyjxiTxjbi=1niyi+i=1ni=i=1ni12i,j=1nijyiyjxiTxj推導(dǎo)過程如下：LW,b,=W22i=1niyiWTxi+b1=12WTWi=1niyiWTxi bi=1niyi+i=1ni=12WTi=1niyixii=1niyiWTxi bi=1niyi+i=1ni=12WTi=1niyixi bi=1niyi+i=1ni=12i=1niyixiTi=1niyixibi=1niyi+i=1ni=12i,j=1niy

24、ixiTjyjxjbi=1niyi+i=1ni=i=1ni12i,j=1nijyiyjxiTxj(2)根據(jù)(1)，變量W和b已被消去，只有未知，由式(2-19)，求min W,bLW,b,對(duì)的極大值：max i=1ni12i,j=1nijyiyjxiTxjs.t. i=1niyi=0i0 (2-20)(2-21)求得最優(yōu)解i，記作i*。根據(jù)KKT條件解得：W=i=1niyixib=yii=1niyixi,xj求得最優(yōu)超平面為：WTx+b=0 (2-22) 第三章 線性不可分3.1核函數(shù)在實(shí)際應(yīng)用的求解中，原始數(shù)據(jù)往往是線性不可分的。如圖3.1所示的二維空間內(nèi)，有若干紅球與籃球，顯然，無法找到一

25、個(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è)原始三維空

26、間經(jīng)映射將成為一個(gè)19維度空間。新空間的維數(shù)呈爆炸式增長，帶來了龐大而困難的計(jì)算量。并且，在無窮維的情況下，無法進(jìn)行計(jì)算。核函數(shù)的優(yōu)勢(shì)在于，由于在SVM的求解過程中只用到內(nèi)積計(jì)算，而核函數(shù)的值恰好等于其在高維空間內(nèi)的內(nèi)積值，因此可以大大簡化SVM的計(jì)算過程。此外，與傳統(tǒng)算法Logistic回歸算法、Decision Tree算法相比，利用核函數(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ù)Kx1,x2=(x1

27、·x2+c)d高斯核RBF函數(shù)Kx1,x2=exp(·|x1x2|2)Sigmoid核函數(shù)Kx1,x2=tanhx1·x2+c在選擇核函數(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偏向于粉色小球堆。黑

28、色虛線為根據(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更寬的紅色超平面。M圖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)用中，引入松弛變量(slack variable)i0，考慮outlier后的約束條件為：WTxi+b1i,yi=1WTxi+b1+i,yi=1 (3-1)式(3-1)

29、亦可表示為：yi(WTxi+b)1i (i=1,2,n) (3-2)由式(3-2)，顯然當(dāng)i取無限大值時(shí)，所有超平面都可以滿足條件，因此，在原目標(biāo)函數(shù)上添加一項(xiàng)，使i的和也取得最小值。隨之，SVM的目標(biāo)函數(shù)由式(2-13)轉(zhuǎn)化為式(3-3)：min|W|22+Ci=1ni,(i=1,2,n)s.t. yiWTxi+b1i,(i=1,2,n) (3-3)i0,(i=1,2,n)其中，C為權(quán)重值，用于在最大化GAP和最小化數(shù)據(jù)偏差之間平衡。(3-4)同樣，在約束條件前乘以拉格朗日乘子，從而將目標(biāo)函數(shù)與約束條件融合為一個(gè)函數(shù)表達(dá)式，構(gòu)造得到新的拉格朗日函數(shù)：LW,b,r=|W|22i=1niyiWT

30、xi+b1+ii=1nrii為求得最優(yōu)解，令L對(duì)W，b，i的偏導(dǎo)數(shù)都為0，即：LW=0Lb=0Li=0W=i=1niyixii=1niyi=0Ciri=0 (3-5) 將解代入式(3-4)得目標(biāo)函數(shù)：max i=1ni12i,j=1nijyiyjxi,xjs.t. i=1niyi=0 i=1,2,n 0iC (3-6)將式(3-6)與式(2-20)對(duì)比可知，含有outlier的分類問題中的i多了上限C的約束條件。而在核函數(shù)中也只需把xi,xj替換成Kxi,xj即可。綜上所述，可以解決線性可分、線性不可分和含有outlier點(diǎn)的三種SVM問題。3.3高斯核函數(shù)與松弛變量的綜合應(yīng)用綜合核函數(shù)與松弛

31、變量的使用，可以更好的解決分類問題。如圖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(

32、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)簽分類(multilabel classification）多標(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)行分類。另一種方法

33、是采用一對(duì)多(OAA)策略：訓(xùn)練針對(duì)類別i的二元分類器，將類別i訓(xùn)練樣本與其他樣本分離。在分類過程中，x被分為了多標(biāo)簽類。其中n為類別數(shù)。這種方法稱為二元相關(guān)方法，此方法是單標(biāo)簽一對(duì)多策略的擴(kuò)展。3.5 SMO求解對(duì)偶問題在第三章中得到了SVM的目標(biāo)函數(shù)式(3-6)，為了實(shí)求解結(jié)果同時(shí)適用于線性可分與線性不可分問題，首先將目標(biāo)函數(shù)式(3-6)中的xi,xj替換為核函數(shù)Kx1,x2并取負(fù)得到新的目標(biāo)函數(shù)：min ()=min 12i=1nj=1nijyiyjKxi,xji=1ni s.t. i=1niyi=0 ( i=1,2,n)0iC (3-7)該目標(biāo)函數(shù)需要求解向量的n個(gè)參數(shù)(1,2,3,n

34、),有多種算法可以求解該目標(biāo)函數(shù)，但序列最小優(yōu)化算法SMO將求解N個(gè)參數(shù)的二次規(guī)劃問題分解成了多個(gè)二次規(guī)劃問題分別求解，每次只求解兩個(gè)變量，同時(shí)將其他變量看作常量，不斷循環(huán)直到獲得最優(yōu)值。該方法雖然迭代次數(shù)較多，但每次迭代的計(jì)算量小，因此在求解效率和內(nèi)存需求上都有了顯著的進(jìn)步。假設(shè)已經(jīng)固定了n-2個(gè)參數(shù)(3,4,5,n)，求解1與2，則目標(biāo)函數(shù)轉(zhuǎn)換為：min 1,2=12K1112+12K2222+K12y1y212+y11v1+y22v2+M(3-8)(3-9)其中M為常量，Kij=Kxi,xj, vi=j=3njyjKxi,xj,i=1,2。為了求解該子問題，首先將目標(biāo)函數(shù)中的等式約束轉(zhuǎn)換

35、為：1y1+2y2=i=3niyi=則1=y1(2y2)，將其代入式(3-8)，對(duì)2求導(dǎo)并令其為0：(2)2=K11+K222K122K11y2+y1y21v1y2+v2y2=0 (3-10)可求解得到2，帶入式(3-9)得1，分別記作2new和1new。由于的值難以計(jì)算，對(duì)式(3-10)進(jìn)行變形，使得2new可以用更新前的2old表示。根據(jù)式(2-21)的超平面表達(dá)式可知，新的數(shù)據(jù)點(diǎn)的預(yù)測(cè)值為：fx=i=1niyiKxi,xj+b (3-11)則v1與v2的值為：v1=fx1b1y1K112y2K12v2=fx2b1y1K122y2K22 (3-12)將其帶入式（3-10），并令K11+K2

36、22K12=，預(yù)測(cè)值與真實(shí)值之差Ei=fxiyi，得：2new=2old+y2(E2E1) (3-13)由于此時(shí)獲得的2new在計(jì)算中未考慮約束條件，將2new記作2new,unclipped，而約束條件在二維平面中的表示為圖3.6，最優(yōu)解必須在圖中的線段上取得，因此L2newH，L與H的取值預(yù)決于y1與y2是否相等，具體取值為：L=max0,12H=minC,C+12,y1y2L=max0,1+2CH=minC,1+2,y1=y2 (3-14)經(jīng)過上述約束條件的修剪即可獲得最優(yōu)解2new：2new=H,2new,unclipped>H2new,unclipped,L2new,uncli

37、ppedHL,2new,unclipped<L (3-15)獲得2new后，根據(jù)2new與1new的關(guān)系可以求得1new的值：1new=1old+y1y2(2old2new)圖3-6而b的值首先需滿足如下條件：b=b1,0<1new<Cb2,0<2new<C(b1+b2)/2,其他 (3-16)更新格式為：b1new=boldE1y11new1oldKx1,x1y22new2oldKx1,x2(3-17)b2new=boldE2y11new1oldKx1,x2y22new2oldKx2,x2(3-18)當(dāng)1與2更新后，b和E的值也同時(shí)需要更新，當(dāng)所有都更新后，即可

38、獲得分類平面函數(shù)式(3-11)。以上所述為已選擇兩個(gè)乘子后，對(duì)兩乘子的求解過程。而乘子的選擇的步驟為：(1) 掃描所有乘子，將第一個(gè)不滿足KKT條件的乘子進(jìn)行更新。(2) 在所有滿足KKT條件的乘子中尋找滿足條件minEiEj乘子作為第二個(gè)乘子進(jìn)行更新。第四章 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ò)能力

39、。本章通過使用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”高度比寬度稍長的一個(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)簽