• • 第六章 支持向量機(jī)
    • 6.1 什么是支持向量機(jī)
      • 6.1.1 線性SVM
      • 6.1.2 函數(shù)間隔和幾何間隔
      • 6.1.3 最大間隔分離超平面
      • 6.1.4 支持向量和間隔邊界
      • 6.1.4 學(xué)習(xí)的對(duì)偶算法
    • 6.2 線性支持向量機(jī)與軟間隔最大化
      • 6.2.1 線性支持向量機(jī)
      • 6.2.2 學(xué)習(xí)的對(duì)偶算法
      • 6.2.3 支持向量
      • 6.2.4 合頁(yè)損失函數(shù)
      • 6.2.5 編程求解線性SVM
      • 6.2.6 簡(jiǎn)化版SMO算法
    • 6.3 非線性支持向量機(jī)與核函數(shù)
      • 6.3.1 核技巧
      • 6.3.2 正定核
      • 6.3.3 常用核函數(shù)
      • 6.3.4 非線性支持向量分類機(jī)
      • 6.3.5 編程實(shí)現(xiàn)非線性SVM
    • 6.4 序列最小最優(yōu)化算法（SMO算法）
      • 6.4.1 兩個(gè)變量二次規(guī)劃的求解方法
      • 6.4.2 變量的選擇方法
      • 6.4.3 SMO算法步驟
      • 6.4.4 SMO算法優(yōu)化
      • 6.4.5 完整版SMO算法
    • 6.5 使用sklearn構(gòu)建SVM分類器
      • 6.5.1 Sklearn.svm.SVC
      • 6.5.2 編寫代碼
    • 6.6 SVM的優(yōu)缺點(diǎn)

第六章 支持向量機(jī)

6.1 什么是支持向量機(jī)

支持向量機(jī)(Support Vector Machines)是目前被認(rèn)為最好的現(xiàn)成的算法之一

在很久以前的情人節(jié)，大俠要去救他的愛人，但魔鬼和他玩了一個(gè)游戲。

魔鬼在桌子上似乎有規(guī)律放了兩種顏色的球，說(shuō)：“你用一根棍分開它們？要求：盡量在放更多球之后，仍然適用。”

于是大俠這樣放，干的不錯(cuò)？

然后魔鬼，又在桌上放了更多的球，似乎有一個(gè)球站錯(cuò)了陣營(yíng)。

SVM就是試圖把棍放在最佳位置，好讓在棍的兩邊有盡可能大的間隙。

現(xiàn)在即使魔鬼放了更多的球，棍仍然是一個(gè)好的分界線。

然后，在SVM 工具箱中有另一個(gè)更加重要的 trick。 魔鬼看到大俠已經(jīng)學(xué)會(huì)了一個(gè)trick，于是魔鬼給了大俠一個(gè)新的挑戰(zhàn)。

現(xiàn)在，大俠沒有棍可以很好幫他分開兩種球了，現(xiàn)在怎么辦呢？當(dāng)然像所有武俠片中一樣大俠桌子一拍，球飛到空中。然后，憑借大俠的輕功，大俠抓起一張紙，插到了兩種球的中間。

現(xiàn)在，從魔鬼的角度看這些球，這些球看起來(lái)像是被一條曲線分開了。

再之后，無(wú)聊的大人們，把這些球叫做 「data」，把棍子 叫做 「classifier」, 最大間隙trick 叫做「optimization」， 拍桌子叫做「kernelling」, 那張紙叫做「hyperplane」。

圖片來(lái)源：Support Vector Machines explained well

當(dāng)數(shù)據(jù)為線性可分的時(shí)候，也就是可以用一根棍子將兩種小球分開的時(shí)候，只要將棍子放在讓小球距離棍子的距離最大化的位置即可，尋找該最大間隔的過(guò)程就叫做最優(yōu)化。

但是一般的數(shù)據(jù)是線性不可分的，所以要將其轉(zhuǎn)化到高維空間去，用一張紙將其進(jìn)行分類，空間轉(zhuǎn)化就是需要核函數(shù)，用于切分小球的紙就是超平面。

什么是SVM：

分類作為數(shù)據(jù)挖掘領(lǐng)域中一項(xiàng)非常重要的任務(wù)，它的目的是學(xué)會(huì)一個(gè)分類函數(shù)或分類模型(或者叫做分類器)，而支持向量機(jī)本身便是一種監(jiān)督式學(xué)習(xí)的方法(至于具體什么是監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)，請(qǐng)參見此系列Machine L&Data Mining第一篇)，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。

支持向量機(jī)（SVM）是90年代中期發(fā)展起來(lái)的基于統(tǒng)計(jì)學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法，通過(guò)尋求結(jié)構(gòu)化風(fēng)險(xiǎn)最小來(lái)提高學(xué)習(xí)機(jī)泛化能力，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化，從而達(dá)到在統(tǒng)計(jì)樣本量較少的情況下，亦能獲得良好統(tǒng)計(jì)規(guī)律的目的。

通俗來(lái)講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機(jī)的學(xué)習(xí)策略便是間隔最大化，最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解。

6.1.1 線性SVM

線性可分的二分類問(wèn)題：

上圖中紅色和藍(lán)色分別表示不同的兩個(gè)類別，數(shù)據(jù)為線性可分，但是將其分開的直線不止一條，(b)(c)分別給出了不同的方法。黑色的實(shí)現(xiàn)為“決策面”，每個(gè)決策面對(duì)應(yīng)一個(gè)線性分類器，兩者的性能是有差距的。

決策面不同的情況下，添加一個(gè)紅色的點(diǎn)，顯然(b)仍然能夠很好的分類，但是(c)已經(jīng)分類錯(cuò)誤了，所以決策面(b)優(yōu)于(c)。

如何選擇較好的決策面：

在保證決策面方向不變且不會(huì)出現(xiàn)錯(cuò)分樣本的情況下移動(dòng)決策面，會(huì)在原來(lái)的決策面兩側(cè)找到兩個(gè)極限位置（越過(guò)該位置就會(huì)產(chǎn)生錯(cuò)分現(xiàn)象），如虛線所示。

虛線的位置由決策面的方向和距離原決策面最近的幾個(gè)樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當(dāng)前決策面方向不變的前提下的最優(yōu)決策面。

兩條虛線之間的垂直距離就是這個(gè)最優(yōu)決策面對(duì)應(yīng)的分類間隔。顯然每一個(gè)可能把數(shù)據(jù)集正確分開的方向都有一個(gè)最優(yōu)決策面（有些方向無(wú)論如何移動(dòng)決策面的位置也不可能將兩類樣本完全分開），而不同方向的最優(yōu)決策面的分類間隔通常是不同的，那個(gè)具有“最大間隔”的決策面就是SVM要尋找的最優(yōu)解。

而這個(gè)真正的最優(yōu)解對(duì)應(yīng)的兩側(cè)虛線所穿過(guò)的樣本點(diǎn)，就是SVM中的支持樣本點(diǎn)，稱為”支持向量”。

學(xué)習(xí)的目標(biāo)是在特征空間中找到一個(gè)分離超平面，能將實(shí)例分到不同的類中。

分離超平面的方程：w?x+b=0?w?x+b=0

方程由法向量w?w和截距b b決定，可以用(w,b)?(w,b)來(lái)表示。

分離超平面將特征空間劃分為兩部分，一部分為正類，一部分為負(fù)類，法向量指向的一側(cè)為正類，另一側(cè)為負(fù)類。

6.1.2 函數(shù)間隔和幾何間隔

備注：

上圖7.1中有A,B,C三個(gè)點(diǎn)，表示3個(gè)實(shí)例，均在分離超平面的正類一側(cè)，預(yù)測(cè)他們的類，點(diǎn)A距離超平面較遠(yuǎn)，若預(yù)測(cè)該類為正類，就比較確信為正確的，點(diǎn)C距離分離超平面較近，不是很確信。

函數(shù)間隔（function margin）：

一般來(lái)說(shuō)，一個(gè)點(diǎn)距離分離超平面的遠(yuǎn)近可以表示分類預(yù)測(cè)的確信程度，在超平面w?x+b=0?w?x+b=0確定的情況下，|w?x+b|?|w?x+b|能夠相對(duì)的表示點(diǎn)x距離超平面的遠(yuǎn)近，而w?x+b?w?x+b的符號(hào)與類標(biāo)記y的符號(hào)是否一致能夠表示分類是否正確，所以可以量y(w?x+b)?y(w?x+b)來(lái)表示分離的正確性和確信度。

從函數(shù)間隔變?yōu)閹缀伍g隔：

雖然函數(shù)間隔可以表示分類預(yù)測(cè)的正確性即確信度，但是選擇分離超平面時(shí)，只有函數(shù)間隔遠(yuǎn)遠(yuǎn)不夠，因?yàn)橹灰杀壤母淖?span id="ze8trgl8bvbq" class="MathJax_Preview" style="color: inherit; display: none;">w?w和b b，例如將它們改變?yōu)?span id="ze8trgl8bvbq" class="MathJax_Preview" style="color: inherit; display: none;">2w?2w和2b?2b，超平面并沒有改變（w?x+b=0?w?x+b=0，右邊為0，不會(huì)因?yàn)橄禂?shù)而改變），但是函數(shù)間隔（y(w?x+b)?y(w?x+b)）卻變?yōu)樵瓉?lái)的2倍。

對(duì)分離超平面的法向量w?w加某些約束，如規(guī)范化，||w||=1 ||w||=1，使得間隔是確定的，此時(shí)函數(shù)間隔變?yōu)閹缀伍g隔。

上圖給出了超平面(w,b)?(w,b)和其法向量w?w，點(diǎn)A A表示某一實(shí)例x?i??xi，其類標(biāo)記為y?i?=+1?yi=+1，點(diǎn)A?A與超平面的距離由線段AB AB給出，記作y?i??yi：

y?i?=w||w||??x?i?+b||w||??yi=w||w||?xi+b||w||

其中，||w||?||w||為w?w的L 2  L2范數(shù)，如果點(diǎn)A?A在超平面的負(fù)一側(cè)，即y i =?1 yi=?1，則：

y?i?=?(w||w||??b||w||?)?yi=?(w||w||?b||w||)

一般情況，當(dāng)樣本點(diǎn)(x?i?,y?i?)?(xi,yi)被超平面(w,b)?(w,b)正確分類時(shí)，點(diǎn)x?i??xi與超平面(w,b)?(w,b)的距離是：

γ?i?=y?i?(w||w||??x?i?+b||w||?)?γi=yi(w||w||?xi+b||w||)

幾何間隔的概念：

6.1.3 最大間隔分離超平面

最大間隔分離超平面，即為下面的約束最優(yōu)化問(wèn)題：

取γ=1?γ=1，最大化1||w||??1||w||，和最小化12?||w||?2??12||w||2是等價(jià)的，所以變?yōu)?#xff1a;

這就變?yōu)橐粋€(gè)凸二次規(guī)劃問(wèn)題，求出上式的解w????w?和b????b?，就可以得到最大間隔分離超平面w????x+b????w??x+b?及分類決策函數(shù)f(x)=sign(w????x+b???)?f(x)=sign(w??x+b?)，即線性可分支持向量機(jī)模型。

總結(jié)：

線性可分訓(xùn)練數(shù)據(jù)集的最大間隔分離超平面是存在且唯一的

6.1.4 支持向量和間隔邊界

支持向量：

在線性可分情況下，訓(xùn)練數(shù)據(jù)集的樣本點(diǎn)中與分離超平面距離最近的樣本點(diǎn)的實(shí)例稱為支持向量，支持向量是使約束條件等號(hào)成立的點(diǎn)，即：

y?i?(w×x?i?+b)?1=0?yi(w×xi+b)?1=0

對(duì)y?i?=+1?yi=+1的正例點(diǎn)，支持向量在超平面：

H?1?:w×x?i?+b=1?H1:w×xi+b=1

對(duì)y?i?=+1?yi=+1的正例點(diǎn)，支持向量在超平面：

H?2?:w×x?i?+b=1?H2:w×xi+b=1

如下圖所示，在H?1??H1和H?2??H2上的點(diǎn)就是支持向量。

間隔邊界：

H?1??H1和H?2??H2平行，且沒有實(shí)例點(diǎn)落在它們中間，分離超平面與它們平行且位于中央，間隔即為H?1??H1和H?2??H2直接的距離，依賴于分離超平面的法向量w?w，等于2||w||  2||w||，H?1??H1和H?2??H2稱為間隔邊界。

分離超平面是由支持向量決定的，其他實(shí)例點(diǎn)并不起作用，移動(dòng)支持向量將會(huì)改變所求平面，移動(dòng)其他實(shí)例點(diǎn)所求平面不會(huì)改變。

由于支持向量在確定分離超平面中起著決定性作用，所以將這種分離模型稱為支持向量機(jī)。

支持向量的個(gè)數(shù)一般很少，所以支持向量機(jī)由很少的“重要的”訓(xùn)練樣本確定。

6.1.4 學(xué)習(xí)的對(duì)偶算法

為了求解線性可分支持向量機(jī)的最優(yōu)化問(wèn)題，將它作為原始最優(yōu)化問(wèn)題，應(yīng)用拉格朗日對(duì)偶性，通過(guò)求解對(duì)偶問(wèn)題得到原始問(wèn)題的最優(yōu)解，這就是線性可分支持向量機(jī)的對(duì)偶算法。

對(duì)偶算法的優(yōu)點(diǎn)：

1）對(duì)偶問(wèn)題往往更容易求解
2）自然引入核函數(shù)，進(jìn)而推廣到非線性分類問(wèn)題

首先，我們先要從宏觀的視野上了解一下拉格朗日對(duì)偶問(wèn)題出現(xiàn)的原因和背景。

我們知道我們要求解的是最小化問(wèn)題，所以一個(gè)直觀的想法是如果我能夠構(gòu)造一個(gè)函數(shù)，使得該函數(shù)在可行解區(qū)域內(nèi)與原目標(biāo)函數(shù)完全一致，而在可行解區(qū)域外的數(shù)值非常大，甚至是無(wú)窮大，那么這個(gè)沒有約束條件的新目標(biāo)函數(shù)的優(yōu)化問(wèn)題就與原來(lái)有約束條件的原始目標(biāo)函數(shù)的優(yōu)化問(wèn)題是等價(jià)的問(wèn)題。這就是使用拉格朗日方程的目的，它將約束條件放到目標(biāo)函數(shù)中，從而將有約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題。

隨后，人們又發(fā)現(xiàn)，使用拉格朗日獲得的函數(shù)，使用求導(dǎo)的方法求解依然困難。進(jìn)而，需要對(duì)問(wèn)題再進(jìn)行一次轉(zhuǎn)換，即使用一個(gè)數(shù)學(xué)技巧：拉格朗日對(duì)偶。

所以，顯而易見的是，我們?cè)诶窭嗜諆?yōu)化我們的問(wèn)題這個(gè)道路上，需要進(jìn)行下面二個(gè)步驟：

• 將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無(wú)約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)
• 使用拉格朗日對(duì)偶性，將不易求解的優(yōu)化問(wèn)題轉(zhuǎn)化為易求解的優(yōu)化

而求解這個(gè)對(duì)偶學(xué)習(xí)問(wèn)題，可以分為三個(gè)步驟：首先要讓L(w,b,α)?L(w,b,α)關(guān)于w?w和b b最小化，然后求對(duì)α的極大，最后利用SMO算法求解對(duì)偶問(wèn)題中的拉格朗日乘子。

• KKT條件

假設(shè)一個(gè)最優(yōu)化模型能夠表示成下列標(biāo)準(zhǔn)形式：

KKT條件的全稱是Karush-Kuhn-Tucker條件，KKT條件是說(shuō)最優(yōu)值條件必須滿足以下條件：
1）條件一：經(jīng)過(guò)拉格朗日函數(shù)處理之后的新目標(biāo)函數(shù)L(w,b,α)對(duì)α求導(dǎo)為零：
2）條件二：h(x)=0?h(x)=0；
3）條件三：α?g(x)=0?α?g(x)=0；

對(duì)于我們的優(yōu)化問(wèn)題：

上述優(yōu)化問(wèn)題滿足三個(gè)條件，故滿足了凸優(yōu)化問(wèn)題和KKT條件。

示例：

6.2 線性支持向量機(jī)與軟間隔最大化

6.2.1 線性支持向量機(jī)

線性可分問(wèn)題的支持向量機(jī)學(xué)習(xí)方法對(duì)線性不可分訓(xùn)練數(shù)據(jù)是不適用的，因?yàn)樯鲜龇椒ㄔ谀莻€(gè)的不等式約束并不成立。

如何將其擴(kuò)展到線性不可分問(wèn)題：

修改硬間隔最大化，使其成為軟間隔最大化。

假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集：

T={(X?1?,Y?1?),(X?2?,Y?2?),...,(x?N?,y?N?)}?T={(X1,Y1),(X2,Y2),...,(xN,yN)}
其中，x?i∈χ=R?n?,y?i?∈Y={+1,?1},i=1,2,...,N?x?i∈χ=Rn,yi∈Y={+1,?1},i=1,2,...,N，x?i??xi為第i個(gè)特征向量，y?i??yi為x?i??xi的類標(biāo)記，假設(shè)訓(xùn)練數(shù)據(jù)集是線性不可分的，通常情況是，訓(xùn)練數(shù)據(jù)中有一些特異點(diǎn)（outlier），將這些特異點(diǎn)去除后，剩下的大部分樣本點(diǎn)組成的幾何是線性可分的。

線性支持向量機(jī)定義：

給定的線性不可分的訓(xùn)練數(shù)據(jù)集，通過(guò)求解凸二次規(guī)劃問(wèn)題，即軟間隔最大化問(wèn)題(7.32)~(7.34)，得到的分離超平面為：

w????x+b???=0?w??x+b?=0

以及相應(yīng)的分類決策函數(shù)：

f(x)=sign(w????x+b???)?f(x)=sign(w??x+b?)

稱為線性支持向量機(jī)

6.2.2 學(xué)習(xí)的對(duì)偶算法

步驟（2）中，對(duì)任一適合條件0<α???j?<C?0<αj?<C的α???j??αj?都可以求出b????b?，但是由于問(wèn)題(7.32)~(7.34)對(duì)b?b的解不唯一，所以實(shí)際計(jì)算時(shí)可以取在所有符合條件的樣本點(diǎn)上的平均值。

6.2.3 支持向量

6.2.4 合頁(yè)損失函數(shù)

6.2.5 編程求解線性SVM

可視化數(shù)據(jù)集

import matplotlib.pylab as plt import numpy as np""" 函數(shù)說(shuō)明：讀取數(shù)據(jù) """# readlines() 自動(dòng)將文件內(nèi)容分析成一個(gè)行的列表，該列表可以由 Python 的 for... in...結(jié)構(gòu)進(jìn)行處理 # readlines()一次讀取整個(gè)文件，readline() 每次只讀取一行，通常比 .readlines() 慢得多def loadDataSet(fileName):dataMat = []; labelMat = []fr = open(fileName)for line in fr.readlines(): #逐行讀取，濾除空格等lineArr = line.strip().split('\t')dataMat.append([float(lineArr[0]), float(lineArr[1])]) #添加數(shù)據(jù)labelMat.append(float(lineArr[2])) #添加標(biāo)簽return dataMat,labelMat""" 函數(shù)說(shuō)明：數(shù)據(jù)可視化"""def showDataSet(dataMat, labelMat):data_plus = [] # 正樣本data_minus = [] # 負(fù)樣本for i in range(len(dataMat)):if labelMat[i] > 0:data_plus.append(dataMat[i])else:data_minus.append(dataMat[i])data_plus_np = np.array(data_plus) # 轉(zhuǎn)換為numpy矩陣data_minus_np = np.array(data_minus) # 轉(zhuǎn)換為numpy矩陣plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1]) # 正樣本散點(diǎn)圖plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1]) # 負(fù)樣本散點(diǎn)圖plt.show()if __name__ == '__main__':dataMat, labelMat = loadDataSet('testSet.txt')showDataSet(dataMat, labelMat)

結(jié)果：

6.2.6 簡(jiǎn)化版SMO算法

from time import sleep import matplotlib.pylab as plt import numpy as np import random import types""" 函數(shù)說(shuō)明：讀取數(shù)據(jù)"""def loadDataSet(fileName):dataMat = []labelMat = []fr = open(fileName)for line in fr.readlines(): # 逐行讀取，濾除空格等lineArr = line.strip().split('\t')dataMat.append([float(lineArr[0]), float(lineArr[1])]) # 添加數(shù)據(jù)labelMat.append(float(lineArr[2])) # 添加標(biāo)簽return dataMat, labelMat""" 函數(shù)說(shuō)明：隨機(jī)選擇alphaParameters:i：alpham：alpha參數(shù)個(gè)數(shù) """def selectJrand(i, m):j = i# 選擇一個(gè)不等于i的jwhile (j == i):j = int(random.uniform(0, m))return j""" 函數(shù)說(shuō)明：修剪alpha Parameters：aj:alpha的值H：alpha上限L：alpha下限Returns：aj：alpha的值 """def clipAlpha(aj, H, L):if aj > H:aj = Hif L > aj:aj = Lreturn aj""" 函數(shù)說(shuō)明：簡(jiǎn)化版SMO算法Parameters：dataMatIn：數(shù)據(jù)矩陣classLabels：數(shù)據(jù)標(biāo)簽C：松弛變量toler：容錯(cuò)率maxIter：最大迭代次數(shù) """def smoSimple(dataMatIn, classLabels, C, toler, maxIter):# 轉(zhuǎn)換為numpy的mat存儲(chǔ)dataMatrix = np.mat(dataMatIn)labelMat = np.mat(classLabels).transpose()# 初始化b參數(shù)，統(tǒng)計(jì)dataMatrix的維度b = 0;m, n = np.shape(dataMatrix)# 初始化alpha參數(shù)，設(shè)為0alphas = np.mat(np.zeros((m, 1)))# 初始化迭代次數(shù)iter_num = 0# 最多迭代matIter次while (iter_num < maxIter):alphaPairsChanged = 0for i in range(m):# 步驟1：計(jì)算誤差EifXi = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + bEi = fXi - float(labelMat[i])# 優(yōu)化alpha，設(shè)定一定的容錯(cuò)率。if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):# 隨機(jī)選擇另一個(gè)與alpha_i成對(duì)優(yōu)化的alpha_jj = selectJrand(i, m)# 步驟1：計(jì)算誤差EjfXj = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j, :].T)) + bEj = fXj - float(labelMat[j])# 保存更新前的aplpha值，使用深拷貝alphaIold = alphas[i].copy()alphaJold = alphas[j].copy()# 步驟2：計(jì)算上下界L和Hif (labelMat[i] != labelMat[j]):L = max(0, alphas[j] - alphas[i])H = min(C, C + alphas[j] - alphas[i])else:L = max(0, alphas[j] + alphas[i] - C)H = min(C, alphas[j] + alphas[i])if L == H: print("L==H"); continue# 步驟3：計(jì)算etaeta = 2.0 * dataMatrix[i, :] * dataMatrix[j, :].T - dataMatrix[i, :] * dataMatrix[i, :].T -\dataMatrix[j,:] * dataMatrix[j, :].Tif eta >= 0: print("eta>=0"); continue# 步驟4：更新alpha_jalphas[j] -= labelMat[j] * (Ei - Ej) / eta# 步驟5：修剪alpha_jalphas[j] = clipAlpha(alphas[j], H, L)if (abs(alphas[j] - alphaJold) < 0.00001): print("alpha_j變化太小"); continue# 步驟6：更新alpha_ialphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])# 步驟7：更新b_1和b_2b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[i, :].T - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[i, :] * dataMatrix[j, :].Tb2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[j, :].T - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[j, :] * dataMatrix[j, :].T# 步驟8：根據(jù)b_1和b_2更新bif (0 < alphas[i]) and (C > alphas[i]):b = b1elif (0 < alphas[j]) and (C > alphas[j]):b = b2else:b = (b1 + b2) / 2.0# 統(tǒng)計(jì)優(yōu)化次數(shù)alphaPairsChanged += 1# 打印統(tǒng)計(jì)信息print("第%d次迭代 樣本:%d, alpha優(yōu)化次數(shù):%d" % (iter_num, i, alphaPairsChanged))# 更新迭代次數(shù)if (alphaPairsChanged == 0):iter_num += 1else:iter_num = 0print("迭代次數(shù): %d" % iter_num)return b, alphas""" 函數(shù)說(shuō)明：分類結(jié)果可視化 """def showClassifer(dataMat, w, b):# 繪制樣本點(diǎn)data_plus = [] # 正樣本data_minus = [] # 負(fù)樣本for i in range(len(dataMat)):if labelMat[i] > 0:data_plus.append(dataMat[i])else:data_minus.append(dataMat[i])data_plus_np = np.array(data_plus) # 轉(zhuǎn)換為numpy矩陣data_minus_np = np.array(data_minus) # 轉(zhuǎn)換為numpy矩陣plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1], s=30,alpha=0.7) # 正樣本散點(diǎn)圖plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1], s=30,alpha=0.7) # 負(fù)樣本散點(diǎn)圖# 繪制直線x1 = max(dataMat)[0]x2 = min(dataMat)[0]a1, a2 = wb = float(b)a1 = float(a1[0])a2 = float(a2[0])y1, y2 = (-b - a1 * x1) / a2, (-b - a1 * x2) / a2plt.plot([x1, x2], [y1, y2])# 找出支持向量點(diǎn)for i, alpha in enumerate(alphas):if abs(alpha) > 0:x, y = dataMat[i]plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')plt.show()""" 函數(shù)說(shuō)明：計(jì)算w """def get_w(dataMat, labelMat, alphas):alphas, dataMat, labelMat = np.array(alphas), np.array(dataMat), np.array(labelMat)w = np.dot((np.tile(labelMat.reshape(1, -1).T, (1, 2)) * dataMat).T, alphas)return w.tolist()if __name__ == '__main__':dataMat, labelMat = loadDataSet('testSet.txt')b, alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)w = get_w(dataMat, labelMat, alphas)showClassifer(dataMat, w, b)

結(jié)果：

藍(lán)色實(shí)線是所求分類器，紅色圈表示支持向量機(jī)

6.3 非線性支持向量機(jī)與核函數(shù)

當(dāng)分類問(wèn)題是非線性的時(shí)候，可以使用非線性支持向量機(jī)，其主要特點(diǎn)是利用核技巧。

6.3.1 核技巧

一、非線性分類問(wèn)題

非線性問(wèn)題的解決方法：通過(guò)非線性變換，將非線性問(wèn)題變?yōu)榫€性問(wèn)題

舉例說(shuō)明：
假設(shè)二維平面x-y上存在若干點(diǎn)，其中點(diǎn)集A服從{x,y|x^2+y^2=1}，點(diǎn)集B服從{x,y|x^2+y^2=9}，那么這些點(diǎn)在二維平面上的分布是這樣的：

藍(lán)色的是點(diǎn)集A，紅色的是點(diǎn)集B，他們?cè)趚y平面上并不能線性可分，即用一條直線分割（ 雖然肉眼是可以識(shí)別的） 。采用映射(x,y)->(x,y,x^2+y^2)后，在三維空間的點(diǎn)的分布為：

用線性分類方法求解非線性問(wèn)題分為兩步：

1）使用一個(gè)變換將原空間的數(shù)據(jù)映射到新空間
2）在新空間用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型

二、核函數(shù)的定義

設(shè)χ χ為輸入空間，又設(shè)H?H為特征空間（希爾伯特空間），如果存在一個(gè)從χ χ到H?H的映射：?(x)=χ→H ?(x)=χ→H

使得所有的x,z∈χ?x,z∈χ，函數(shù)K(x,z)?K(x,z)滿足條件：K(x,z)=?(x)??(z)?K(x,z)=?(x)??(z)

則K(x,z)?K(x,z)稱為核函數(shù)，?(x)??(x)稱為映射函數(shù)。

三、核技巧在支持向量機(jī)中的應(yīng)用

6.3.2 正定核

通常所說(shuō)的核函數(shù)就是正定核函數(shù)

6.3.3 常用核函數(shù)

6.3.4 非線性支持向量分類機(jī)

利用核技巧可以將線性分類的學(xué)習(xí)方法應(yīng)用到非線性分類問(wèn)題中去，將線性支持向量機(jī)擴(kuò)展到非線性支持向量機(jī)，只需將線性支持向量機(jī)對(duì)偶形式的內(nèi)積換成核函數(shù)即可。

非線性支持向量機(jī)：
從非線性分類訓(xùn)練集，通過(guò)核函數(shù)與軟間隔最大化，或凸二次規(guī)劃(7.95)~(7.97)學(xué)習(xí)得到的分類決策函數(shù)：

稱為非線性支持向量，K(x,z)?K(x,z)是正定核函數(shù)。

非線性支持向量機(jī)學(xué)習(xí)算法：

6.3.5 編程實(shí)現(xiàn)非線性SVM

接下來(lái)，我們將使用testSetRBF.txt和testSetRBF2.txt進(jìn)行實(shí)驗(yàn)，前者作為訓(xùn)練集，后者作為測(cè)試集。

import matplotlib.pylab as plt import numpy as npdef loadDataSet(fileName):""":param fileName::return: dataMat, labelMat"""dataMat = []labelMat = []fr = open(fileName)for line in fr.readlines(): # 逐行讀取，濾除空格等lineArr = line.strip().split('\t')dataMat.append([float(lineArr[0]), float(lineArr[1])]) # 添加數(shù)據(jù)labelMat.append(float(lineArr[2])) # 添加標(biāo)簽return dataMat, labelMatdef showDataSet(dataMat,labelMat):"""數(shù)據(jù)可視化:param dataMat: 數(shù)據(jù)矩陣:param labelMat: 數(shù)據(jù)標(biāo)簽:return: 無(wú)"""#正樣本data_plus=[]#負(fù)樣本data_minus=[]for i in range(len(dataMat)):if labelMat[i]>0:data_plus.append(dataMat[i])else:data_minus.append(dataMat[i])data_plus_np=np.array(data_plus)data_minus_np=np.array(data_minus)#正樣本散點(diǎn)圖plt.scatter(np.transpose(data_plus_np)[0],np.transpose(data_plus_np)[1])#負(fù)樣本散點(diǎn)圖plt.scatter(np.transpose(data_minus_np)[0],np.transpose(data_minus_np)[1])plt.show()if __name__=='__main__':dataArr,labelArr=loadDataSet('testSetRBF.txt')showDataSet(dataArr,labelArr)

結(jié)果：

6.4 序列最小最優(yōu)化算法（SMO算法）

支持向量機(jī)問(wèn)題可以轉(zhuǎn)化為求解凸二次規(guī)劃問(wèn)題，這樣的問(wèn)題具有全局最優(yōu)解，并且有許多算法可以用于這個(gè)問(wèn)題的求解，但是當(dāng)訓(xùn)練樣本容量很大時(shí)，這些算法往往變得非常低效，以至于無(wú)法使用。

1996年，John Platt發(fā)布了一個(gè)稱為SMO的強(qiáng)大算法，用于訓(xùn)練SVM。SM表示序列最小化(Sequential Minimal Optimizaion)。Platt的SMO算法是將大優(yōu)化問(wèn)題分解為多個(gè)小優(yōu)化問(wèn)題來(lái)求解的。這些小優(yōu)化問(wèn)題往往很容易求解，并且對(duì)它們進(jìn)行順序求解的結(jié)果與將它們作為整體來(lái)求解的結(jié)果完全一致的。在結(jié)果完全相同的同時(shí)，SMO算法的求解時(shí)間短很多。

SMO算法的目標(biāo)是求出一系列alpha和b，一旦求出了這些alpha，就很容易計(jì)算出權(quán)重向量w并得到分隔超平面。

SMO算法的工作原理是：每次循環(huán)中選擇兩個(gè)alpha進(jìn)行優(yōu)化處理。一旦找到了一對(duì)合適的alpha，那么就增大其中一個(gè)同時(shí)減小另一個(gè)。這里所謂的”合適”就是指兩個(gè)alpha必須符合以下兩個(gè)條件，條件之一就是兩個(gè)alpha必須要在間隔邊界之外，而且第二個(gè)條件則是這兩個(gè)alpha還沒有進(jìn)進(jìn)行過(guò)區(qū)間化處理或者不在邊界上。

6.4.1 兩個(gè)變量二次規(guī)劃的求解方法

6.4.2 變量的選擇方法

6.4.3 SMO算法步驟

1）步驟一：計(jì)算誤差：

2）步驟二：計(jì)算上下界L和H：

3）步驟三：計(jì)算η?η

4）步驟四：更新α?j??αj

5）步驟五：根據(jù)取值范圍修剪α?j??αj

6）步驟六：更新α?i??αi

7）步驟七：更新b?1??b1和b?2??b2

8）步驟八：根據(jù)b?1??b1和b?2??b2更新b?b<script id="MathJax-Element-97" type="math/tex">b</script>

6.4.4 SMO算法優(yōu)化

啟發(fā)選擇方式：

在幾百個(gè)點(diǎn)組成的小規(guī)模數(shù)據(jù)集上，簡(jiǎn)化版SMO算法的運(yùn)行是沒有什么問(wèn)題的，但是在更大的數(shù)據(jù)集上的運(yùn)行速度就會(huì)變慢。簡(jiǎn)化版SMO算法的第二個(gè)α的選擇是隨機(jī)的，針對(duì)這一問(wèn)題，我們可以使用啟發(fā)式選擇第二個(gè)α值，來(lái)達(dá)到優(yōu)化效果。

下面這兩個(gè)公式想必已經(jīng)不再陌生：

在實(shí)現(xiàn)SMO算法的時(shí)候，先計(jì)算η，再更新a_j。為了加快第二個(gè)α_j乘子的迭代速度，需要讓直線的斜率增大，對(duì)于α_j的更新公式，其中η值沒有什么文章可做，于是只能令：

因此，我們可以明確自己的優(yōu)化方法了：

• 最外層循環(huán)，首先在樣本中選擇違反KKT條件的一個(gè)乘子作為最外層循環(huán)，然后用”啟發(fā)式選擇”選擇另外一個(gè)乘子并進(jìn)行這兩個(gè)乘子的優(yōu)化
• 在非邊界乘子中尋找使得|E_i - E_j|最大的樣本
• 如果沒有找到，則從整個(gè)樣本中隨機(jī)選擇一個(gè)樣本

6.4.5 完整版SMO算法

完整版Platt SMO算法是通過(guò)一個(gè)外循環(huán)來(lái)選擇違反KKT條件的一個(gè)乘子，并且其選擇過(guò)程會(huì)在這兩種方式之間進(jìn)行交替：

• 在所有數(shù)據(jù)集上進(jìn)行單遍掃描
• 在非邊界α中實(shí)現(xiàn)單遍掃描

非邊界α指的就是那些不等于邊界0或C的α值，并且跳過(guò)那些已知的不會(huì)改變的α值。所以我們要先建立這些α的列表，用于才能出α的更新狀態(tài)。

在選擇第一個(gè)α值后，算法會(huì)通過(guò)”啟發(fā)選擇方式”選擇第二個(gè)α值。

6.5 使用sklearn構(gòu)建SVM分類器

在第一篇文章中，我們使用了kNN進(jìn)行手寫數(shù)字識(shí)別。它的缺點(diǎn)是存儲(chǔ)空間大，因?yàn)橐Ａ羲械挠?xùn)練樣本，如果你的老板讓你節(jié)約這個(gè)內(nèi)存空間，并達(dá)到相同的識(shí)別效果，甚至更好。那這個(gè)時(shí)候，我們就要可以使用SVM了，因?yàn)樗恍枰Ａ糁С窒蛄考纯?#xff0c;而且能獲得可比的效果。

6.5.1 Sklearn.svm.SVC

官方手冊(cè)

sklearn.svm模塊提供了很多模型，其中svm.SVC是基于libsvm實(shí)現(xiàn)的。

class sklearn.svm.SVC(C=1.0, kernel=’rbf’, degree=3, gamma=’auto’, coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape=’ovr’, random_state=None)

參數(shù)說(shuō)明如下：

• C：懲罰項(xiàng)，float類型，可選參數(shù)，默認(rèn)為1.0，C越大，即對(duì)分錯(cuò)樣本的懲罰程度越大，因此在訓(xùn)練樣本中準(zhǔn)確率越高，但是泛化能力降低，也就是對(duì)測(cè)試數(shù)據(jù)的分類準(zhǔn)確率降低。相反，減小C的話，容許訓(xùn)練樣本中有一些誤分類錯(cuò)誤樣本，泛化能力強(qiáng)。對(duì)于訓(xùn)練樣本帶有噪聲的情況，一般采用后者，把訓(xùn)練樣本集中錯(cuò)誤分類的樣本作為噪聲。

• kernel：核函數(shù)類型，str類型，默認(rèn)為’rbf’。可選參數(shù)為：

  • ’linear’：線性核函數(shù)
  • ‘poly’：多項(xiàng)式核函數(shù)
  • ‘rbf’：徑像核函數(shù)/高斯核
  • ‘sigmod’：sigmod核函數(shù)
  • ‘precomputed’：核矩陣
  • precomputed表示自己提前計(jì)算好核函數(shù)矩陣，這時(shí)候算法內(nèi)部就不再用核函數(shù)去計(jì)算核矩陣，而是直接用你給的核矩陣，核矩陣需要為n*n的。

• degree：多項(xiàng)式核函數(shù)的階數(shù)，int類型，可選參數(shù)，默認(rèn)為3。這個(gè)參數(shù)只對(duì)多項(xiàng)式核函數(shù)有用，是指多項(xiàng)式核函數(shù)的階數(shù)n，如果給的核函數(shù)參數(shù)是其他核函數(shù)，則會(huì)自動(dòng)忽略該參數(shù)。

• gamma：核函數(shù)系數(shù)，float類型，可選參數(shù)，默認(rèn)為auto。只對(duì)’rbf’ ,’poly’ ,’sigmod’有效。如果gamma為auto，代表其值為樣本特征數(shù)的倒數(shù)，即1/n_features。
• coef0：核函數(shù)中的獨(dú)立項(xiàng)，float類型，可選參數(shù)，默認(rèn)為0.0。只有對(duì)’poly’ 和,’sigmod’核函數(shù)有用，是指其中的參數(shù)c。
• probability：是否啟用概率估計(jì)，bool類型，可選參數(shù)，默認(rèn)為False，這必須在調(diào)用fit()之前啟用，并且會(huì)fit()方法速度變慢。
• shrinking：是否采用啟發(fā)式收縮方式，bool類型，可選參數(shù)，默認(rèn)為True。
• tol：svm停止訓(xùn)練的誤差精度，float類型，可選參數(shù)，默認(rèn)為1e^-3。
• cache_size：內(nèi)存大小，float類型，可選參數(shù)，默認(rèn)為200。指定訓(xùn)練所需要的內(nèi)存，以MB為單位，默認(rèn)為200MB。
• class_weight：類別權(quán)重，dict類型或str類型，可選參數(shù)，默認(rèn)為None。給每個(gè)類別分別設(shè)置不同的懲罰參數(shù)C，如果沒有給，則會(huì)給所有類別都給C=1，即前面參數(shù)指出的參數(shù)C。如果給定參數(shù)’balance’，則使用y的值自動(dòng)調(diào)整與輸入數(shù)據(jù)中的類頻率成反比的權(quán)重。
• verbose：是否啟用詳細(xì)輸出，bool類型，默認(rèn)為False，此設(shè)置利用libsvm中的每個(gè)進(jìn)程運(yùn)行時(shí)設(shè)置，如果啟用，可能無(wú)法在多線程上下文中正常工作。一般情況都設(shè)為False，不用管它。
• max_iter：最大迭代次數(shù)，int類型，默認(rèn)為-1，表示不限制。
• decision_function_shape：決策函數(shù)類型，可選參數(shù)’ovo’和’ovr’，默認(rèn)為’ovr’。’ovo’表示one vs one，’ovr’表示one vs rest。
• random_state：數(shù)據(jù)洗牌時(shí)的種子值，int類型，可選參數(shù)，默認(rèn)為None。偽隨機(jī)數(shù)發(fā)生器的種子,在混洗數(shù)據(jù)時(shí)用于概率估計(jì)。

6.5.2 編寫代碼

import numpy as np import operator from os import listdir from sklearn.svm import SVCdef img2Vector(filename):"""將32*32的二進(jìn)制圖像轉(zhuǎn)換為1*1024的向量:param filename: 文件名:return: 返回的二進(jìn)制圖像的1*1024向量"""# 創(chuàng)建1*1024零向量returnVect = np.zeros((1, 1024))# 打開文件fr = open(filename)# 按行讀取for i in range(32):# 讀取一行數(shù)據(jù)lineStr = fr.readline()# 每一行的前32個(gè)元素依次添加到returnVect中for j in range(32):returnVect[0, 32 * i + j] = int(lineStr[j])# 返回轉(zhuǎn)換后的1*1024向量return returnVectdef handwritingClassTest():"""手寫數(shù)字分類測(cè)試:return: 無(wú)"""# 測(cè)試集的LabelshwLabels = []# 返回trainingDigits目錄下的文件名trainingFileList = listdir('E:/python/machine learning in action/My Code/chap 06/trainingDigits')# 返回文件夾下文件的個(gè)數(shù)m = len(trainingFileList)# 初始化訓(xùn)練的Mat矩陣，測(cè)試集trainingMat = np.zeros((m, 1024))# 從文件名中解析出訓(xùn)練的類別for i in range(m):# 獲得文件的名字fileNameStr = trainingFileList[i]# 獲得分類的數(shù)字classNumber = int(fileNameStr.split('_')[0])# 將獲得的類別添加到hwlabels中hwLabels.append(classNumber)# 將每個(gè)文件的1*1024數(shù)據(jù)存儲(chǔ)到trainingMat矩陣中trainingMat[i, :] = img2Vector('E:/python/machine learning in action/My Code/chap 06/trainingDigits/%s' % (fileNameStr))clf = SVC(C=200, kernel='rbf')clf.fit(trainingMat, hwLabels)# 返回testDigits目錄下的文件列表testFileList = listdir('testDigits')# 錯(cuò)誤檢測(cè)技術(shù)errorCount = 0.0# 測(cè)試數(shù)據(jù)的數(shù)量mTest = len(testFileList)# 從文件中解析出測(cè)試集的類別并進(jìn)行分類測(cè)試for i in range(mTest):fileNameStr = testFileList[i]classNumber = int(fileNameStr.split('_')[0])# 獲得測(cè)試集的1*1024向量，用于訓(xùn)練vectorUnderTest = img2Vector('E:/python/machine learning in action/My Code/chap 06/testDigits/%s' % (fileNameStr))# 獲得預(yù)測(cè)結(jié)果classfierResult = clf.predict(vectorUnderTest)print("分類返回結(jié)果為 %d \t 真實(shí)結(jié)果為%d " % (classfierResult, classNumber))if (classfierResult != classNumber):errorCount += 1.0print("總共錯(cuò)了%d個(gè)數(shù)據(jù) \n 錯(cuò)誤率為%f%%" % (errorCount, errorCount / mTest * 100))if __name__ == '__main__':handwritingClassTest()

結(jié)果：

6.6 SVM的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 可用于線性/非線性分類，也可以用于回歸，泛化錯(cuò)誤率低，也就是說(shuō)具有良好的學(xué)習(xí)能力，且學(xué)到的結(jié)果具有很好的推廣性。
• 可以解決小樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題，可以解決高維問(wèn)題，可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點(diǎn)問(wèn)題。
• SVM是最好的現(xiàn)成的分類器，現(xiàn)成是指不加修改可直接使用。并且能夠得到較低的錯(cuò)誤率，SVM可以對(duì)訓(xùn)練集之外的數(shù)據(jù)點(diǎn)做很好的分類決策。

缺點(diǎn)：

• 對(duì)參數(shù)調(diào)節(jié)和和函數(shù)的選擇敏感。

總結(jié)

以上是生活随笔為你收集整理的机器学习实战（六）——支持向量机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。