機器學習簡明教程-基于Python語言實現(xiàn) 課件 第7章支持向量機

支持向量機《機器學習簡明教程》高延增侯躍恩羅志堅機械工業(yè)出版社07本章目標?理解線性可分、間隔最大化的概念?理解對偶問題?掌握線性支持向量機?了解非線性支持向量機支持向量機（SupportVectorMachine,SVM）是一種非常優(yōu)雅的算法，具有完善的數(shù)學理論支撐，早在1963年就由Vapnik提出了，直到20世紀末才被廣泛使用。在深度學習算法流行之前，SVM一直是傳統(tǒng)機器學習算法的典型代表，在模式識別、回歸、分類等領(lǐng)域得到廣泛應用，一度被業(yè)界稱為最成功的機器學習算法。SVM是一種有監(jiān)督的二分類模型，目前在小樣本、非線性、高維場景下依然表現(xiàn)亮眼，并且該算法數(shù)學理論完備，是數(shù)據(jù)挖掘從業(yè)者必須掌握的算法之一。SVM的核心思想是在對樣本空間分類的時候使用間隔最大化的分類器，而最讓人稱奇的問題解決思路是將低維度上線性不可分的樣本擴展到多維空間中，然后就可以在多維空間中構(gòu)建一個線性分類器將這些樣本分開，同時使用核技巧降低這一過程的計算復雜度。SVM實現(xiàn)樣本分類過程中涉及到線性可分、間隔最大化、核技巧等知識，本章將分別介紹。目錄/Contents7.17.2SVM相關(guān)概念線性SVM7.3非線性SVM7.4軟間隔7.5應用案例7.1SVM的相關(guān)概念

7.1SVM的相關(guān)概念——線性可分

若找不到這樣的超平面，數(shù)據(jù)集就是線性不可分的線性可分線性不可分7.1SVM的相關(guān)概念——間隔最大化點到面的距離

7.1SVM的相關(guān)概念——間隔最大化

但僅滿足上式的參數(shù)構(gòu)成的分隔超平面魯棒性較弱，我們希望能找到類似下圖中兩條虛線中間的實線作為分隔線，這樣的分割線具有較好的魯棒性。上面的公式變成：支持向量（SupportVector）就是左圖落在虛線上的正負實例點。而正負支持向量與分隔平面的距離之和被稱為間隔，如公式

（7.7）7.1SVM的相關(guān)概念——間隔最大化上頁圖中，改變ω,b的值即改變分隔平面的法向量和相對坐標原點的平移量，會使得間隔的大小也發(fā)生變化，我們希望能找到可以使間隔取得最大值的ω確定的那個分隔平面。間隔的最大值，被稱為最大間隔，正因如此SVM又常被稱為大間隔分類器（largemarginclassifier）。對應的兩條包含支持向量的兩條虛線被稱為間隔邊界，由上頁圖可知分隔超平面、分割邊界由支持向量決定。

（7.9）

目錄/Contents7.17.2SVM相關(guān)概念線性SVM7.3非線性SVM7.4軟間隔7.5應用案例7.2線性SVM式（7.9）的解ω*,b*確定一個樣本集的分隔超平面

（7.10）式（7.9）是一個凸二次規(guī)劃問題，可以用拉格朗日乘子法得到其對偶問題，通過求解對偶問題得到原始問題的最優(yōu)解。引進拉格朗日乘子后會使對偶問題相對原始問題更容易求解，而且可以推廣到非線性分類問題。7.2線性SVM——對偶問題

（7.11）定義廣義拉格朗日函數(shù)為：

（7.12）7.2線性SVM——對偶問題

7.2線性SVM——學習算法

（7.19）

7.2線性SVM——學習算法利用對偶性轉(zhuǎn)換，得到對偶問題（7.20）（7.20）

（7.21）（7.22）可得式（7.23）、（7.24）。

（7.23）（7.24）7.2線性SVM——學習算法

（7.25）（7.26）由此得到式（7.9）的對偶問題

若對偶問題（7.26）的解恰好對應（7.9）的解，需滿足KKT條件，此處的KKT條件是（7.27）7.2線性SVM——學習算法

（7.28）

（7.29）

（7.30）7.2線性SVM——學習算法

（7.31）

（7.32）至此，就完成了線性支持向量機的求解，由支持向量得到了一個線性分類器（7.33）

目錄/Contents7.17.2SVM相關(guān)概念線性SVM7.3非線性SVM7.4軟間隔7.5應用案例7.3非線性SVM——核心思想對于線性不可分集合，SVM算法將它們從原始空間映射到更高維度的空間中，使得它們在高維的空間中變成線性可分的

（7.34）（7.35）

7.3非線性SVM——核心思想對偶問題也由（7.26）轉(zhuǎn)變?yōu)槭剑?.36）（7.36）

如果有辦法在原始特征空間計算映射后的高維空間的內(nèi)積，就可以直接在原始特征空間上構(gòu)建一個分類器了，這種直接在原始空間上計算內(nèi)積的方法稱為核函數(shù)方法。7.3非線性SVM——核心思想

（7.37）7.3非線性SVM——核函數(shù)的應用

（7.38）對于一個新的樣本，式（7.38）給出了高維空間上的線性分類器的計算方法,但是有了核函數(shù)，我們不需要計算內(nèi)積，使用式（7.39）進行分類，這樣就避免了高維空間中計算量大增的“維數(shù)災難”問題。（7.39）

7.3非線性SVM——核函數(shù)的應用例7.3.1：假設二維空間上的向量x到三維空間上的映射如式（7.40），求這個映射的核函數(shù)。（7.40）（7.41）（7.42）已知映射公式（7.40）假設二維空間上的兩個向量x,y，映射到三維空間后的向量內(nèi)積如式（7.41）。而在映射之前的二維空間中，向量x,y的內(nèi)積如式（7.42）

7.3非線性SVM——核函數(shù)的應用（7.43）若將例7.3.1中的映射變得更復雜一點，將二維空間的向量映射到四維空間中，如式（7.43）。你會發(fā)現(xiàn)映射（7.43）與（7.40）具有相同的核函數(shù)。顯然，核函數(shù)的計算復雜度要比在映射后的高維空間中直接計算向量內(nèi)積的復雜度更低。

從式（7.36）、（7.39）知，高維空間中對偶問題求解、最后分隔超平面的解析式都只需要計算映射后的向量內(nèi)積，不需要知道映射的具體形式。我們直接在原始空間中找到一些函數(shù)，判斷這些函數(shù)是否可以作為有效的核函數(shù)，然后將核函數(shù)直接代入（7.36）、（7.39）就可以得到高維的線性分隔超平面，這樣就節(jié)省了高維映射、高維空間向量內(nèi)積運算等操作，降低了復雜度。Mercer定理給出了一個判斷某個函數(shù)是否可以作為核函數(shù)的方法。7.3非線性SVM——核函數(shù)的應用

（7.44）定理第一句是說核函數(shù)是原始空間上兩個向量到一個實數(shù)的映射，后半句中訓練樣例的核函數(shù)矩陣如式Mercer定理說明任何一個使矩陣（7.44）為半正定矩陣的函數(shù)k?,?都可以使一個有效的核函數(shù)，而每個有效的核函數(shù)又可以隱式地定義了一個特征空間，這個特征空間被稱為再生核希爾伯特空間（ReproducingKernelHilbertSpaces,RKHS）。

7.3非線性SVM——核函數(shù)的應用

有了核函數(shù)就可以隱式的生成一個高維空間，但是樣本集在這個隱式的高維空間中是否具有一個良好的線性分隔超平面呢？這就要看核函數(shù)的選擇了，所以現(xiàn)在原始空間上線性不可分樣本集的分類問題就變成了尋找合適的核函數(shù)問題了。7.3非線性SVM——常用核函數(shù)核函數(shù)的選取直接關(guān)系到對樣本集的分類效果，因此通常需要根據(jù)應用場景選擇合適的核函數(shù)。具體的應用場景中，有專用核函數(shù)和通用核函數(shù)兩類，專用核函數(shù)需要根據(jù)具體應用場景去構(gòu)造，而常見的通用核函數(shù)包括：線性核、多項式核、高斯核、拉普拉斯核、Sigmoid核。線性核函數(shù)如式（7.46）,

線性核主要用于線性可分的場景，原始空間和映射空間的維度并沒有發(fā)生變化。線性核的優(yōu)點是參數(shù)少、速度快，缺點是不能解決線性不可分的樣本集分類問題。（7.46）多項式核函數(shù)如式（7.47），式中γ=1,n=1時就變成了線性核。通過升維使原本線性不可分的樣本集變得線性可分。（7.47）7.3非線性SVM——常用核函數(shù)高斯核函數(shù)如式（7.48），式中σ為高斯核的帶寬。高斯核函數(shù)是一種局部性強的核函數(shù)，其可以將一個樣本映射到一個更高維的空間內(nèi)，該核函數(shù)是應用最廣的一個，無論大樣本還是小樣本都有比較好的性能，相對于多項式核函數(shù)參數(shù)要少，在不確定合適的核函數(shù)的場景下可以優(yōu)先嘗試高斯核函數(shù)的分類效果。Sigmoid核函數(shù)如式（7.49），式中tanh?為雙曲正切函數(shù)。Sigmoid函數(shù)經(jīng)常用在神經(jīng)網(wǎng)絡的映射中。

（7.48）（7.49）

7.3非線性SVM——學習算法有了核函數(shù)后，就是對公式（7.37）的求解，求解方法與線性SVM類似，假設最優(yōu)解為α*,b*，則對應的非線性SVM如式（7.50）。（7.50）

（7.51）與線性SVM的算法相比，非線性SVM的學習算法步驟多了選取適當核函數(shù)的工作，其算法步驟包括：（1）選擇適當?shù)暮撕瘮?shù)；（2）求解對偶問題α*；（3）求解偏移量b*；（4）構(gòu)造分類決策函數(shù)（7.50）。步驟一：選擇核函數(shù)。具體哪種核函數(shù)更適合，要看待分類的訓練集。如果訓練集的特征數(shù)量多，樣本數(shù)量不太多可以考慮使用線性核；如果特征數(shù)量少、樣本數(shù)量比較多的時候考慮使用高斯核。在不確定哪種核函數(shù)更合適的時候，可以采用交叉驗證的方式比較各種不同核函數(shù)的分類效果，然后選擇一個最優(yōu)的。步驟二：求解最優(yōu)化問題。選定了核函數(shù)后，就是解對偶問題（7.37），與線性SVM求解類似也可以使用SMO算法求解。步驟三：計算偏移量。選擇α*的正分量αi*計算b*，如式（7.52）。

步驟四：構(gòu)造非線性SVM的決策函數(shù)（7.50）。7.3非線性SVM——學習算法（7.52）目錄/Contents7.17.2SVM相關(guān)概念線性SVM7.3非線性SVM7.4軟間隔7.5應用案例7.4軟間隔——定義前面SVM求解的假設是樣本集都是嚴格可分的，原始空間上線性可分或映射空間上線性可分。但是，現(xiàn)實應用中由于噪聲點一類的影響導致訓練集可能并不是完美可分的，而且嚴格完美的分隔超平面很有可能是過擬合的結(jié)果。為了解決這些問題，在SVM算法的間隔最大化時使用軟間隔對公式（7.9）進行優(yōu)化。為使SVM更具通用性、防止過擬合，引入軟間隔如下圖，軟間隔允許某些樣本不滿足約束條件，即軟間隔支持向量并不一定是離分隔超平面最近的點。這樣就可以過濾掉在分隔超平面附近由于噪聲而被錯誤歸類的點。7.4軟間隔——定義

（7.54）

（7.55）

7.4軟間隔——采用軟間隔的SVM與硬間隔線性SVM算法類似，采用軟間隔的SVM求解也經(jīng)過拉格朗日函數(shù)構(gòu)建、對偶問題、問題求解、利用求解得到的分隔超平面構(gòu)建分類模型四個步驟。式（7.55）引入拉格朗日乘子，得到拉格朗日函數(shù)如式（7.56）。（7.56）式（7.56）中，αi,γi為拉格朗日乘子。與7.2.2的方法類似，Lω,b,α,ε,μ分別對ω,b,ε求偏導,令其為0，得：（7.57）（7.58）（7.59）7.4軟間隔——采用軟間隔的SVM

（7.60）由于采用的是軟間隔，相對應的KKT條件也變?yōu)椋?.61）7.4軟間隔——采用軟間隔的SVM

（7.62）（7.63）

目錄/Contents7.17.2SVM相關(guān)概念線性SVM7.3非線性SVM7.4軟間隔7.5應用案例7.5應用案例使用SVM算法制作一個鳶尾花的分類器。尾花，它是一種較常見的單子葉百合目花卉。早在上世紀30年代，就有科學家采集了鳶尾花的萼長、萼寬、瓣長、瓣寬與具體種類之間的對應數(shù)據(jù)作為線性分類器的驗證集。鳶尾花數(shù)據(jù)集非常經(jīng)典，是各種機器學習算法常用的驗證數(shù)據(jù)源。Sklearn包的數(shù)據(jù)集中就包含了鳶尾花數(shù)據(jù)，可以通過load_iris來加載。數(shù)據(jù)集包含三種鳶尾花（setosa,versicolor,virginica）合計150條記錄，每個種類50條記錄。每條記錄都包含了花的萼長、萼寬、瓣長、瓣寬（單位：cm），以及對應的鳶尾花種類。7.5應用案例使用SVM算法制作一個鳶尾花的分類器。

以萼長（sepallength）和萼寬（sepalwidth）為橫、縱坐標，然后根據(jù)鳶尾花類別不同使用不同大小和顏色的點繪制成散點圖如右圖以花萼尺寸構(gòu)建二維平面上鳶尾花不是線性可分的。7.5應用案例構(gòu)建并求解SVM分類器，python的sklearn包提供了很好的SVM分類器實現(xiàn)，使用時只需通過設置合適的接口參數(shù)即可得到適用于所處理數(shù)據(jù)的SVM分類器。Sklearn.svm.SVC使用時常被調(diào)整參數(shù)包括：核函數(shù)（kernel）、正則化參數(shù)（C）、多項式核函數(shù)的次數(shù)（degree，poly核時有效）、核系數(shù)（gamma，rbf,poly,sigmoid核有效）、核函數(shù)中的常數(shù)項（coef0，poly,sigmoid核有效）等。核函數(shù)的選取對分類效果影響較大，可選的包括線性核（linear）、多項式核（poly）、徑向基函數(shù)核（rbf）、S