機(jī)器學(xué)習(xí)簡(jiǎn)明教程-基于Python語(yǔ)言實(shí)現(xiàn) 課件 第7章支持向量機(jī)

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

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

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

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

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

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

（7.9）

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

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

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

（7.12）7.2線性SVM——對(duì)偶問(wèn)題

7.2線性SVM——學(xué)習(xí)算法

（7.19）

7.2線性SVM——學(xué)習(xí)算法利用對(duì)偶性轉(zhuǎn)換，得到對(duì)偶問(wèn)題（7.20）（7.20）

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

（7.23）（7.24）7.2線性SVM——學(xué)習(xí)算法

（7.25）（7.26）由此得到式（7.9）的對(duì)偶問(wèn)題

若對(duì)偶問(wèn)題（7.26）的解恰好對(duì)應(yīng)（7.9）的解，需滿足KKT條件，此處的KKT條件是（7.27）7.2線性SVM——學(xué)習(xí)算法

（7.28）

（7.29）

（7.30）7.2線性SVM——學(xué)習(xí)算法

（7.31）

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

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

（7.34）（7.35）

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

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

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

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

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

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

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

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

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

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

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

（7.48）（7.49）

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

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

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

（7.54）

（7.55）

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

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

（7.62）（7.63）

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

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