1 支持向量機(jī)介紹

支持向量機(jī)（support vector machine，SVM）是有監(jiān)督學(xué)習(xí)中最有影響力的機(jī)器學(xué)習(xí)算法之一，該算法的誕生可追溯至上世紀(jì) 60 年代， 前蘇聯(lián)學(xué)者 Vapnik 在解決模式識別問題時提出這種算法模型，此后經(jīng)過幾十年的發(fā)展直至 1995 年， SVM 算法才真正的完善起來，其典型應(yīng)用是解決手寫字符識別問題。

SVM 是一種非常優(yōu)雅的算法，有著非常完善的數(shù)學(xué)理論基礎(chǔ)，其預(yù)測效果，在眾多機(jī)器學(xué)習(xí)模型中“出類拔萃”。在深度學(xué)習(xí)沒有普及之前，“支持向量機(jī)”可以稱的上是傳統(tǒng)機(jī)器學(xué)習(xí)中的“霸主”。

支持向量機(jī)是一種二分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學(xué)習(xí)策略便是間隔最大化，最終可轉(zhuǎn)化為一個凸二次規(guī)劃問題的求解。支持向量機(jī)的學(xué)習(xí)算法是求解凸二次規(guī)劃的最優(yōu)化算法。

基礎(chǔ)的SVM算法是一個二分類算法，至于多分類任務(wù)，可以通過多次使用SVM進(jìn)行解決。

1.1 線性可分

對于一個數(shù)據(jù)集合可以畫一條直線將兩組數(shù)據(jù)點分開，這樣的數(shù)據(jù)成為線性可分（linearly separable），如下圖所示：

• ?分割超平面：將上述數(shù)據(jù)集分隔開來的直線成為分隔超平面。對于二維平面來說，分隔超平面就是一條直線。對于三維及三維以上的數(shù)據(jù)來說，分隔數(shù)據(jù)的是個平面，稱為超平面，也就是分類的決策邊界。
• 間隔：點到分割面的距離，稱為點相對于分割面的間隔。數(shù)據(jù)集所有點到分隔面的最小間隔的2倍，稱為分類器或數(shù)據(jù)集的間隔。論文中提到的間隔多指這個間隔。SVM分類器就是要找最大的數(shù)據(jù)集間隔。
• 支持向量：離分隔超平面最近的那些點。

SVM所做的工作就是找這樣個超平面，能夠?qū)蓚€不同類別的樣本劃分開來，但是這種平面是不唯一的，即可能存在無數(shù)個超平面都可以將兩種樣本分開，那么我們?nèi)绾尾拍艽_定一個分類效果最好的超平面呢？
Vapnik提出了一種方法，對每一種可能的超平面，我們將它進(jìn)行平移，直到它與空間中的樣本向量相交。我們稱這兩個向量為支持向量，之后我們計算支持向量到該超平面的距離d，分類效果最好的超平面應(yīng)該使d最大。

1.2?尋找最大間隔

（1）分隔超平面

二維空間一條直線的方程為，y=ax+b，推廣到n維空間，就變成了超平面方程，即

?w是權(quán)重，b是截距，訓(xùn)練數(shù)據(jù)就是訓(xùn)練得到權(quán)重和截距。

(2)如何找到最好的參數(shù)

支持向量機(jī)的核心思想： 最大間隔化， 最不受到噪聲的干擾。如上圖所示，分類器A比分類器B的間隔（藍(lán)色陰影）大，因此A的分類效果更好。

SVM劃分的超平面：f(x) = 0，w為法向量，決定超平面方向，

假設(shè)超平面將樣本正確劃分
　　f(x) ≥ 1，y = +1
　　f(x) ≤ ?1，y = ?1

　　間隔：r=2/|w|

約束條件：

?（3）轉(zhuǎn)化為凸優(yōu)化

設(shè) f(x) 為定義在n維歐式空間中某個凸集 S 上的函數(shù)，若對于任何實數(shù)α（0 < α< 1 ）以及 S 中的不同兩點 x，y ，均有：

那么，f(x)為定義在凸集 S 上的凸函數(shù)。

?有約束的凸優(yōu)化問題：

如果f(x)，g(x)為凸函數(shù)，h(x)為仿射函數(shù)時，這是一個凸優(yōu)化的問題。

對于支持向量機(jī)：

SVM是一個凸二次規(guī)劃問題，有最優(yōu)解。

（4）拉格朗日對偶

通常我們需要求解的最優(yōu)化問題有如下幾類：

　　(i) 無約束優(yōu)化問題，可以寫為：

　　　　　　　min f(x)

　　(ii) 有等式約束的優(yōu)化問題，可以寫為：

　　　　　　　min f(x),

　　　　　　? ? s.t. h_i(x) = 0；i =1, ..., n

　　(iii) 有不等式約束的優(yōu)化問題，可以寫為：

　　　　　　　min f(x)，

　　　　　　　s.t. g_i(x) <= 0；i =1, ..., n

　　　　　　　h_j(x) = 0；j =1, ..., m
　　對于第(i)類的優(yōu)化問題，常常使用的方法就是Fermat定理，即使用求取f(x)的導(dǎo)數(shù)，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗證；如果是凸函數(shù)，可以保證是最優(yōu)解。

拉格朗日乘子法與對偶問題

　　對于第(ii)類的優(yōu)化問題，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式約束h_i(x)用一個系數(shù)與f(x)寫為一個式子，稱為拉格朗日函數(shù)，而系數(shù)稱為拉格朗日乘子。通過拉格朗日函數(shù)對各個變量求導(dǎo)，令其為零，可以求得候選值集合，然后驗證求得最優(yōu)值。

?例如給定橢球：

?求這個橢球的內(nèi)接長方體的最大體積。

我們將這個轉(zhuǎn)化為條件極值問題，即在條件

下，求f(x,y,z)=8xyz的最大值。

首先定義拉格朗日函數(shù)F(x)

λk是各個約束條件的待定系數(shù)

然后解變量的偏導(dǎo)方程：

如果有i個約束條件，就應(yīng)該有i+1個方程。求出的方程組的解就可能是最優(yōu)化值（極值），將結(jié)果帶回原方程驗證即可得解。

回到上面的題目，通過拉格朗日乘數(shù)法將問題轉(zhuǎn)化為：

?對F(x,y,z,λ)求偏導(dǎo)得：

聯(lián)立前面三個方程得到bx=ay和az=cx，代入第四個方程解得：

最大體積為：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-517089.html

KKT條件

對于第(iii)類的優(yōu)化問題，常常使用的方法就是KKT條件（Karush-Kuhn-Tucker）。同樣地，我們把所有的等式、不等式約束與f(x)寫為一個式子，也叫拉格朗日函數(shù)，系數(shù)也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個條件稱為KKT條件。

原始含有不等式約束問題描述為：

　????????????????min? f(x)，

　　　　　 s.t.? g(x)≤0

含有不等式約束的KKT條件為如下式（記為式①）所示：

?注意：KKT條件是非線性規(guī)劃最優(yōu)解的必要條件

• KKT條件描述型理解

　?。╥）當(dāng)最優(yōu)解 x* 滿足g(x*) <0時，最優(yōu)解位于可行域內(nèi)部，此時不等式約束無效，λ=0。

　　（ii）當(dāng)最優(yōu)解 x*滿足g(x*) = 0時，最優(yōu)解位于可行域的邊界，此時不等式約束變?yōu)榈仁郊s束，g(x)=0。

　?。╥ii）同時根據(jù)幾何意義，λ必<0（根據(jù)梯度可得）。

　　根據(jù)上述討論，由于我們所需的是必要條件，故將上述幾種情況進(jìn)行并集操作，可得最優(yōu)解時的必要條件，即（記為式②）：
　　　　　　　　　　?xL=?f+λ?g=0

　　　　　　　　　　 g(x)≤0

　　　　　　　　　　 λ≥0

　　　　　　　　　　 λg(x)=0

　　（iv）當(dāng)有多個不等式約束時，可推廣至式①形式。

KKT條件要求強(qiáng)對偶，形式如下：

?前兩條為x*滿足的原問題的約束。第三條表示對偶變量滿足的約束，第四條為互補(bǔ)松弛條件，第五條表示拉格朗日函數(shù)在x*處取得極小值（即x*是最優(yōu)解，滿足拉格朗日函數(shù)極小的條件）

?1.3 線性不可分

對于線性不可分的數(shù)據(jù)集，我們無法找到這樣一種直線，將不同類型的樣本分割開來，SVM的方法好像就不適用了。但是Vapnik提出了一種觀點，我們所認(rèn)為的線性不可分，只是在當(dāng)前維度下線性不可分，并不代表它在高維空間中線性不可分。比如有一組樣本在二維空間線性不可分，但是在三維空間中，我們是有可能找到這樣一條直線將其分隔開來的，Vapnik還認(rèn)為，當(dāng)維數(shù)趨于無窮時，一定存在這樣一條線，可以將不同類型的樣本分割開來。

Cover定理：

在提升維度后，原本非線性的數(shù)據(jù)點變得線性可分，這在數(shù)學(xué)上是有嚴(yán)格證明的，即Cover定理。Cover定理可以定性地描述為：將復(fù)雜的模式分類問題非線性地投射到高維空間將比投射到低維空間更可能是線性可分的，當(dāng)空間的維數(shù)D越大時，在該空間的N個數(shù)據(jù)點間的線性可分的概率就越大。

或者再通俗的說，這個定理描述的是線性可分的概率，如果能把數(shù)據(jù)從低維空間映射到高維空間，我們就很可能在高維空間把數(shù)據(jù)做線性可分。對于在N維空間中線性不可分的數(shù)據(jù)，在N+1維以上的空間會有更大可能變成線性可分的。

所以人們就努力的尋找一種映射，這映射能將樣本從原始空間(低維數(shù)據(jù))轉(zhuǎn)變到高維特征空間，從而把低維空間中線性不可分的兩類點變成線性可分的。這種映射?(X) 又可稱為“特征構(gòu)建”，映射后的向量可稱之為“特征向量”。

首先，輸入的數(shù)據(jù)樣本集為一組N個m0維的向量x1,x1,...,xN，每個樣本都被歸類到兩個類C1和C2之一。定義一組實值函數(shù)（也就是輸入一個向量輸出一個實數(shù)的函數(shù)）φ1(x),φ2(x),...,φm1(x)，用來將輸入數(shù)據(jù)映射到一個m1維的空間，將它們組成一個向量：

這個函數(shù)向量?的輸出可被認(rèn)為是被映射到高維空間之后的輸入數(shù)據(jù)x。φi(x)稱為隱藏函數(shù)，其組成的向量?所在的空間稱為隱藏空間或特征空間。如果有那么個m1維的向量w，使得這個成立：?

也就是說被?映射到另一個高維空間的數(shù)據(jù)樣本們成了線性可分的，就說這個把x分類到C1和C2的分法是?可分的。
對于x來說， wT?(x)=0就是一個分類曲面。

于是模式可分性的Cover定理在這就包含這兩部分：

• 隱藏函數(shù)的非線性轉(zhuǎn)換。
• 高維的特征空間（這個高維是相對原始數(shù)據(jù)的維度來說的，由隱藏函數(shù)的個數(shù)決定）。

?

異或問題

異或問題因為是個典型的線性不可分問題。其點(0,0)和(1,1)歸于類0，點(0,1)和點(1,0)歸于類1。然后我們要拿一組隱藏函數(shù)將這些點映射到零一空間里。在這里使用高斯隱藏函數(shù)。因為問題簡單，所以只用了兩個隱藏函數(shù)，維度沒有增加：

?其中 t1=(1,1)， t2=(0,0)。也就是拿樣本點跟這兩點的幾何距離作為高斯函數(shù)的自變量。轉(zhuǎn)換結(jié)果如下：

映射后的數(shù)據(jù)如圖所示，原來線性不可分的數(shù)據(jù)，已經(jīng)變成了線性可分

?

1.3 核函數(shù)

映射可以看作是一種拉伸，把低維數(shù)據(jù)拉伸到了高維。雖然現(xiàn)在我們到了高維空間號稱線性可分，但是有幾個困難：

• 不知道什么樣的映射函數(shù)是完美的。
• 難以在各種映射函數(shù)中找到一個合適的。
• 高維空間計算量比較大。這樣就會產(chǎn)生維災(zāi)難，計算內(nèi)積是不現(xiàn)實的。

幸運(yùn)的是，在計算中發(fā)現(xiàn)，我們需要的只是兩個向量在新的映射空間中的內(nèi)積結(jié)果，而映射函數(shù)到底是怎么樣的其實并不需要知道。于是這樣就引入了核函數(shù)的概念。

核函數(shù)事先在低維上計算，而將實質(zhì)上的分類效果表現(xiàn)在了高維上，也就是

• 包含映射，內(nèi)積，相似度的邏輯。

• 消除掉把低維向量往高維映射的過程。

• 避免了直接在高維空間內(nèi)的復(fù)雜計算。

即核函數(shù)除了能夠完成特征映射，而且還能把特征映射之后的內(nèi)積結(jié)果直接返回。即把高維空間得內(nèi)積運(yùn)算轉(zhuǎn)化為低維空間的核函數(shù)計算。

注意，核函數(shù)只是將完全不可分問題，轉(zhuǎn)換為可分或達(dá)到近似可分的狀態(tài)。

在實際中，我們會經(jīng)常遇到線性不可分的樣例，此時，我們的常用做法是把樣例特征映射到高維空間中去，但如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個維度大小是會高到可怕的，此時就需要使用核函數(shù)。核函數(shù)雖然也是將特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)會先在低維上進(jìn)行計算，而將實質(zhì)上的分類效果表現(xiàn)在高維上，避免了直接在高維空間中的復(fù)雜計算。

?如下圖所示的兩類數(shù)據(jù)，這樣的數(shù)據(jù)本身是線性不可分的，當(dāng)我們將二維平面的坐標(biāo)值映射一個三維空間中，映射后的結(jié)果可以很明顯地看出，數(shù)據(jù)是可以通過一個平面來分開的。

?

核函數(shù)方法處理非線性問題的基本思想：按一定的規(guī)則進(jìn)行映射，使得原來的數(shù)據(jù)在新的空間中變成線性可分的，從而就能使用之前推導(dǎo)的線性分類算法進(jìn)行處理。計算兩個向量在隱式映射過后的空間中的內(nèi)積的函數(shù)叫做核函數(shù)

核函數(shù)是這樣的一種函數(shù)：

仍然以二維空間為例，假設(shè)對于變量x和y，將其映射到新空間的映射函數(shù)為φ，則在新空間中，二者分別對應(yīng)φ(x)和φ(y)，他們的內(nèi)積則為<φ(x),φ(y)>。

我們令函數(shù)Kernel(x,y)=<φ(x),φ(y)>=k(x,y)，

可以看出，函數(shù)Kernel(x,y)是一個關(guān)于x和y的函數(shù)！而與φ無關(guān)！這是一個多么好的性質(zhì)！我們再也不用管φ具體是什么映射關(guān)系了，只需要最后計算Kernel(x,y)就可以得到他們在高維空間中的內(nèi)積。

我們則稱Κ(x,y)為核函數(shù)，φ(x)為映射函數(shù)。

我們大致能夠得到核函數(shù)如下性質(zhì)：

• 核函數(shù)給出了任意兩個樣本之間關(guān)系的度量，比如相似度。
• 每一個能被叫做核函數(shù)的函數(shù)，里面都藏著一個對應(yīng)拉伸的函數(shù)。這些核函數(shù)的命名通常也跟如何做拉伸變換有關(guān)系。
• 核函數(shù)和映射本身沒有直接關(guān)系。選哪個核函數(shù)，實際上就是在選擇用哪種方法映射。通過核函數(shù)，我們就能跳過映射的過程。
• 我們只需要核函數(shù)，而不需要那個映射，也無法顯式的寫出那個映射。
• 選擇核函數(shù)就是把原始數(shù)據(jù)集上下左右前后拉扯揉捏，直到你一刀下去正好把所有的 0 分到一邊，所有的 1 分到另一邊。這個上下左右前后拉扯揉捏的過程就是kernel.

核函數(shù)存在的條件

?

定理表明，只要一個對稱函數(shù)所對應(yīng)的核矩陣半正定，那么它就可以作為核函數(shù)使用。事實上，對于一個半正定核矩陣，總能找到一個與之對應(yīng)的映射?。換言之，任何一個核函數(shù)都隱式定義了一個稱為“再生核希爾伯特空間”的特征空間
?

常見的核函數(shù)

通過前面的介紹，核函數(shù)的選擇，對于非線性支持向量機(jī)的性能至關(guān)重要。但是由于我們很難知道特征映射的形式，所以導(dǎo)致我們無法選擇合適的核函數(shù)進(jìn)行目標(biāo)優(yōu)化。于是“核函數(shù)的選擇”稱為支持向量機(jī)的最大變數(shù)，我們常見的核函數(shù)有以下幾種：

此外，還可以通過函數(shù)組合得到，例如：

對于非線性的情況，SVM 的處理方法是選擇一個核函數(shù) κ(?,?)，通過將數(shù)據(jù)映射到高維空間，來解決在原始空間中線性不可分的問題。由于核函數(shù)的優(yōu)良品質(zhì)，這樣的非線性擴(kuò)展在計算量上并沒有比原來復(fù)雜多少，這一點是非常難得的。當(dāng)然，這要歸功于核方法——除了 SVM 之外，任何將計算表示為數(shù)據(jù)點的內(nèi)積的方法，都可以使用核方法進(jìn)行非線性擴(kuò)展。

1.4 正則化與軟間隔

?針對樣本不是完全能夠劃分開的情況，可以允許支持向量機(jī)在一些樣本上出錯，為此要引入“軟間隔”的概念。

引入正則化強(qiáng)度參數(shù)C（正則化：在一定程度上抑制過擬合，使模型獲得抗噪聲能力，提升模型對未知樣本的預(yù)測性能的手段），損失函數(shù)重新定義為：

?上式為采用hinge損失的形式，再引入松弛變量ξi≥0，重寫為：

?支持向量：

?由此可以看出，軟間隔支持向量機(jī)的最終模型僅與支持向量有關(guān)，即通過采用hinge損失函數(shù)仍保持了稀疏特性。

2 SVM的優(yōu)缺點及應(yīng)用場景

2.1 SVM的優(yōu)缺點

（1）SVM的優(yōu)點：

• 高效的處理高維特征空間：SVM通過將數(shù)據(jù)映射到高維空間中，可以處理高維特征，并在低維空間中進(jìn)行計算，從而有效地處理高維數(shù)據(jù)。

• 適用于小樣本數(shù)據(jù)集：SVM是一種基于邊界的算法，它依賴于少數(shù)支持向量，因此對于小樣本數(shù)據(jù)集具有較好的泛化能力。

• 可以處理非線性問題：SVM使用核函數(shù)將輸入數(shù)據(jù)映射到高維空間，從而可以解決非線性問題。常用的核函數(shù)包括線性核、多項式核和徑向基函數(shù)（RBF）核。

• 避免局部最優(yōu)解：SVM的優(yōu)化目標(biāo)是最大化間隔，而不是僅僅最小化誤分類點。這使得SVM在解決復(fù)雜問題時能夠避免陷入局部最優(yōu)解。

• 對于噪聲數(shù)據(jù)的魯棒性：SVM通過使用支持向量來定義決策邊界，這使得它對于噪聲數(shù)據(jù)具有一定的魯棒性。

（2）SVM的缺點：

• 對大規(guī)模數(shù)據(jù)集的計算開銷較大：SVM的計算復(fù)雜度隨著樣本數(shù)量的增加而增加，特別是在大規(guī)模數(shù)據(jù)集上的訓(xùn)練時間較長。

• 對于非線性問題選擇合適的核函數(shù)和參數(shù)較為困難：在處理非線性問題時，選擇適當(dāng)?shù)暮撕瘮?shù)和相應(yīng)的參數(shù)需要一定的經(jīng)驗和領(lǐng)域知識。

• 對缺失數(shù)據(jù)敏感：SVM在處理含有缺失數(shù)據(jù)的情況下表現(xiàn)不佳，因為它依賴于支持向量的定義。

• 難以解釋模型結(jié)果：SVM生成的模型通常是黑盒模型，難以直觀地解釋模型的決策過程和結(jié)果。

SVM在處理小樣本數(shù)據(jù)、高維特征空間和非線性問題時表現(xiàn)出色，但對于大規(guī)模數(shù)據(jù)集和缺失數(shù)據(jù)的處理相對困難。同時，在模型的解釋性方面也存在一定的挑戰(zhàn)。

2.2 SVM的應(yīng)用場景

SVM在許多其他領(lǐng)域也有廣泛的應(yīng)用，特別是在分類和回歸問題中。它的靈活性和強(qiáng)大的泛化能力使其成為機(jī)器學(xué)習(xí)中的重要工具之一。主要應(yīng)用場景總結(jié)如下：

• 文本分類：SVM可以用于對文本進(jìn)行分類，如垃圾郵件分類、情感分析和文檔分類等。

• 圖像識別：SVM可用于圖像分類、目標(biāo)識別和人臉識別等任務(wù)。它可以通過提取圖像的特征向量，并將其作為輸入來訓(xùn)練SVM模型。

• 金融領(lǐng)域：SVM可用于信用評分、風(fēng)險評估和股票市場預(yù)測等金融任務(wù)。

• 醫(yī)學(xué)診斷：SVM可以應(yīng)用于醫(yī)學(xué)圖像分析，如疾病檢測、癌癥診斷和醫(yī)學(xué)影像分類等。

• 視頻分類：SVM可以用于視頻分類、行為識別和運(yùn)動檢測等任務(wù)，通過提取視頻幀的特征并將其輸入SVM模型進(jìn)行分類。

• 推薦系統(tǒng)：SVM可以用于個性化推薦和用戶分類等推薦系統(tǒng)任務(wù)，通過分析用戶行為和特征來預(yù)測用戶的興趣和偏好。

3 基于SVM實現(xiàn)鳶尾花分類預(yù)測

3.1 數(shù)據(jù)集介紹

Iris 鳶尾花數(shù)據(jù)集是一個經(jīng)典數(shù)據(jù)集，在統(tǒng)計學(xué)習(xí)和機(jī)器學(xué)習(xí)領(lǐng)域都經(jīng)常被用作示例。數(shù)據(jù)集內(nèi)包含 3 類共 150 條記錄，每類各 50 個數(shù)據(jù)，每條記錄都有 4 項特征：花萼長度、花萼寬度、花瓣長度、花瓣寬度，可以通過這4個特征預(yù)測鳶尾花卉屬于（iris-setosa, iris-versicolour, iris-virginica）三種中的哪一品種。

數(shù)據(jù)內(nèi)容：

     sepal_len  sepal_wid  petal_len  petal_wid  label
0          5.1        3.5        1.4        0.2      0
1          4.9        3.0        1.4        0.2      0
2          4.7        3.2        1.3        0.2      0
3          4.6        3.1        1.5        0.2      0
4          5.0        3.6        1.4        0.2      0
..         ...        ...        ...        ...    ...
145        6.7        3.0        5.2        2.3      2
146        6.3        2.5        5.0        1.9      2
147        6.5        3.0        5.2        2.0      2
148        6.2        3.4        5.4        2.3      2
149        5.9        3.0        5.1        1.8      2

3.2 代碼實現(xiàn)

（1）原生代碼實現(xiàn)

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split



def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target

    df.columns = ['sepal_len', 'sepal_wid', 'petal_len', 'petal_wid', 'label']
    print(df)

    data = np.array(df.iloc[:100, [0, 1, -1]])

    for i in range(len(data)):
        if data[i,-1] == 0:
            data[i,-1] = -1

    return data[:,:2], data[:,-1]


class SVM:
    def __init__(self, max_iter=100, kernel='poly'):
        self.max_iter = max_iter
        self._kernel = kernel

    def init_args(self, features, labels):
        self.m, self.n = features.shape
        self.X = features
        self.Y = labels
        self.b = 0.0

        # 將Ei保存在一個列表里
        self.alpha = np.ones(self.m)
        self.E = [self._E(i) for i in range(self.m)]
        # 松弛變量
        self.C = 1.0

    def _KKT(self, i):
        y_g = self._g(i)*self.Y[i]
        if self.alpha[i] == 0:
            return y_g >= 1
        elif 0 < self.alpha[i] < self.C:
            return y_g == 1
        else:
            return y_g <= 1

    # g(x)預(yù)測值，輸入xi（X[i]）
    def _g(self, i):
        r = self.b
        for j in range(self.m):
            r += self.alpha[j]*self.Y[j]*self.kernel(self.X[i], self.X[j])
        return r

    # 核函數(shù)
    def kernel(self, x1, x2):
        if self._kernel == 'linear':
            return sum([x1[k]*x2[k] for k in range(self.n)])
        elif self._kernel == 'poly':
            return (sum([x1[k]*x2[k] for k in range(self.n)]) + 1)**2

        return 0

    # E（x）為g(x)對輸入x的預(yù)測值和y的差
    def _E(self, i):
        return self._g(i) - self.Y[i]

    def _init_alpha(self):
        # 外層循環(huán)首先遍歷所有滿足0<a<C的樣本點，檢驗是否滿足KKT
        index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]
        # 否則遍歷整個訓(xùn)練集
        non_satisfy_list = [i for i in range(self.m) if i not in index_list]
        index_list.extend(non_satisfy_list)

        for i in index_list:
            if self._KKT(i):
                continue

            E1 = self.E[i]
            # 如果E2是+，選擇最小的；如果E2是負(fù)的，選擇最大的
            if E1 >= 0:
                j = min(range(self.m), key=lambda x: self.E[x])
            else:
                j = max(range(self.m), key=lambda x: self.E[x])
            return i, j

    def _compare(self, _alpha, L, H):
        if _alpha > H:
            return H
        elif _alpha < L:
            return L
        else:
            return _alpha

    def fit(self, features, labels):
        self.init_args(features, labels)

        for t in range(self.max_iter):
            # train
            i1, i2 = self._init_alpha()

            # 邊界
            if self.Y[i1] == self.Y[i2]:
                L = max(0, self.alpha[i1]+self.alpha[i2]-self.C)
                H = min(self.C, self.alpha[i1]+self.alpha[i2])
            else:
                L = max(0, self.alpha[i2]-self.alpha[i1])
                H = min(self.C, self.C+self.alpha[i2]-self.alpha[i1])

            E1 = self.E[i1]
            E2 = self.E[i2]
            # eta=K11+K22-2K12
            eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel(self.X[i2], self.X[i2]) - 2*self.kernel(self.X[i1], self.X[i2])
            if eta <= 0:
                # print('eta <= 0')
                continue

            alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E2 - E1) / eta
            alpha2_new = self._compare(alpha2_new_unc, L, H)

            alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)

            b1_new = -E1 - self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) * (alpha1_new-self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2], self.X[i1]) * (alpha2_new-self.alpha[i2])+ self.b
            b2_new = -E2 - self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) * (alpha1_new-self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2], self.X[i2]) * (alpha2_new-self.alpha[i2])+ self.b

            if 0 < alpha1_new < self.C:
                b_new = b1_new
            elif 0 < alpha2_new < self.C:
                b_new = b2_new
            else:
                # 選擇中點
                b_new = (b1_new + b2_new) / 2

            # 更新參數(shù)
            self.alpha[i1] = alpha1_new
            self.alpha[i2] = alpha2_new
            self.b = b_new

            self.E[i1] = self._E(i1)
            self.E[i2] = self._E(i2)
        return 'train done!'

    def predict(self, data):
        r = self.b
        for i in range(self.m):
            r += self.alpha[i] * self.Y[i] * self.kernel(data, self.X[i])

        return 1 if r > 0 else -1

    def score(self, X_test, y_test):
        right_count = 0
        for i in range(len(X_test)):
            result = self.predict(X_test[i])
            if result == y_test[i]:
                right_count += 1
        return right_count / len(X_test)

    def _weight(self):
        # linear model
        yx = self.Y.reshape(-1, 1)*self.X
        self.w = np.dot(yx.T, self.alpha)
        return self.w


X, y = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)


svm = SVM(max_iter=800)
print(svm.fit(X_train, y_train))
print(svm.score(X_train, y_train))
print(svm.score(X_test, y_test))

（2）基于sklearn的代碼實現(xiàn)

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split


def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    data = np.array(df.iloc[:100, [0, 1, -1]])
    for i in range(len(data)):
        if data[i,-1] == 0:
            data[i,-1] = -1
    return data[:,:2], data[:,-1]


X, y = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)


plt.scatter(X[:50,0],X[:50,1], label='0')
plt.scatter(X[50:,0],X[50:,1], label='1')
plt.show()


model = SVC()
model.fit(X_train, y_train)

SVC(C=1.0, break_ties=False, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape='ovr', degree=3, gamma='scale', kernel='rbf',
    max_iter=-1, probability=False, random_state=None, shrinking=True,
    tol=0.001, verbose=False)


print('train accuracy: ' + str(model.score(X_train, y_train)))
print('test accuracy: ' + str(model.score(X_test, y_test)))

?3.3 運(yùn)行結(jié)果

（1）數(shù)據(jù)分布展示：

?（2）訓(xùn)練集和測試集上的準(zhǔn)確性

train accuracy: 1.0
test accuracy: 0.96

4 完整代碼

代碼下載地址：代碼下載

?

到了這里，關(guān)于機(jī)器學(xué)習(xí)之支持向量機(jī)（SVM）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！