機(jī)器學(xué)習(xí)之支持向量機(jī)模型（SVM）

  • 1、支持向量機(jī)模型介紹
  • 2、支持向量機(jī)數(shù)學(xué)原理
  • 3、算法及Python
  • 4、小結(jié)

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

支持向量機(jī)（SVM）是一種二類分類模型。它的基本模型是定義在特征空間上的間隔最大的線性分類器，間隔最大使它有別于感知機(jī)；支持向量機(jī)還包括核技巧，這使它成為實(shí)質(zhì)上的非線性分類器。支持向量機(jī)的學(xué)習(xí)策略就是間隔最大化，可形式化為一個(gè)求解凸二次規(guī)劃的問題，支持向量機(jī)的學(xué)習(xí)算法是求解凸二次規(guī)劃的最優(yōu)算法。
定義一（線性可分支持向量機(jī)）：
給定線性可分訓(xùn)練數(shù)據(jù)集，通過間隔最大化或等價(jià)地求解相應(yīng)的凸二次規(guī)劃問題學(xué)習(xí)得到的分離超平面為
w^*\cdot x+b^*=0
以及相應(yīng)的分類決策函數(shù)
f(x)=sign(w^*\cdot x+b^*)
稱為線性可分支持向量機(jī)。

image.png

定義二（非線性支持向量機(jī)）：
從非線性分類訓(xùn)練集，通過核函數(shù)與軟間隔最優(yōu)化，或凸二次規(guī)劃，學(xué)習(xí)得到的分類決策函數(shù)
f(x)=sign\left( \sum_{i=1}^Na_i^*y_iK(x,x_i)+b^* \right)
稱為非線性支持向量機(jī)，K(x,z)是正定核函數(shù)。
image.png

2、支持向量機(jī)數(shù)學(xué)原理

函數(shù)間隔：對(duì)于給定的訓(xùn)練數(shù)據(jù)集和超平面(w,b)，定義超平面(w,b)關(guān)于樣本點(diǎn)(x_i,y_i)的函數(shù)間隔為
\hat{\gamma}_i = y_i(w\cdot x_i+b)
幾何間隔：對(duì)于給定的訓(xùn)練數(shù)據(jù)集和超平面(w,b)，定義超平面(w,b)關(guān)于樣本點(diǎn)(x_i,y_i)的幾何間隔為
\gamma_i = y_i\left( \frac{w}{||w||}\cdot x_i +\frac{||w||}\right)
間隔最大化
max_{w,b} \gamma
s.t.\ \ \ \ \ y_i\left( \frac{w}{||w||}\cdot x_i+\frac{||w||} \right)\geq\gamma, \ \ \ \ \ i=1,2,\cdots,N
即希望最大化超平面(w,b)關(guān)于訓(xùn)練集的幾何間隔\gamma，約束條件表示是超平面(w,b)關(guān)于每個(gè)訓(xùn)練樣本點(diǎn)的幾何間隔至少是\gamma.
可以將問題改寫為
max_{w,b} \frac{\hat{\gamma}}{||w||}
s.t.\ \ \ \ \ y_i\left( w\cdot x_i +b \right)\geq\hat{\gamma}, \ \ \ \ \ i=1,2,\cdots,N
因?yàn)榧僭O(shè)將w\cdot x+b=0中左邊乘以\lambda則對(duì)于超平面沒有影響，但是對(duì)樣本點(diǎn)的函數(shù)間隔卻有影響，因此我們可以通過調(diào)整\lambda值使\hat{\gamma}=1此時(shí)便得到線性可分支持向量機(jī)學(xué)習(xí)的最優(yōu)化問題
min_{w,b} \ \ \ \ \frac{1}{2}||w||^2
s.t \ \ \ \ y_i(w\cdot x_i +b)-1\geq0,\ \ \ \ i=1,2,\cdots,N
軟間隔最大化：
當(dāng)數(shù)據(jù)集中有一些特異點(diǎn)時(shí)，可能導(dǎo)致數(shù)據(jù)集線性不可分，此時(shí)可以對(duì)每個(gè)樣本點(diǎn)(x_i,y_i)引入一個(gè)松弛變量\xi_i\geq0,使函數(shù)間隔加上松弛變量大于等于1，這樣約束條件變?yōu)?br> y_i(w\cdot x_i+b)\geq1-\xi_i
同時(shí)對(duì)每個(gè)松弛變量支付一個(gè)代價(jià)\xi_i，目標(biāo)函數(shù)由原來的\frac{1}{2}||w||^2變?yōu)?br> \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i
這里，C>0稱為懲罰參數(shù)，一般由應(yīng)用問題決定
線性不可分的線性支持向量機(jī)的學(xué)習(xí)問題變?yōu)槿缦峦苟我?guī)劃問題（原始問題）
min_{w,b\xi} \ \ \ \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i
y_i(w\cdot x_i+b)\geq1-\xi_i，\ \ \ \ i=1,2,\cdots,N
\xi_i\geq0，\ \ \ \ i=1,2,\cdots,N
學(xué)習(xí)的對(duì)偶算法：
應(yīng)用拉格朗日對(duì)偶性，通過求解對(duì)偶問題得到原始問題的最優(yōu)解，這樣做的優(yōu)點(diǎn)是，一是對(duì)偶問題往往更容易求解；二是自然引入核函數(shù)，進(jìn)而推廣到非線性分類問題。
線性可分支持向量機(jī)對(duì)偶問題
首先構(gòu)建拉格朗日函數(shù)，為此，對(duì)每一個(gè)不等式約束引進(jìn)拉格朗日乘子\alpha_i \geq0，i=1,2,\cdots,N定義拉格朗日函數(shù)L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N\alpha_iy_i(w \cdot x_i+b)+\sum_{i=1}^N\alpha_i
其中，\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T為拉格朗日乘子向量。
根據(jù)拉格朗日對(duì)偶性，可得到對(duì)偶最優(yōu)化問題
min_a \ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i
s.t. \ \ \ \ \sum_{i=1}^N\alpha_iy_i=0
\alpha_i\geq0,\ \ \ \ i=1,2,\cdots,N
線性不可分線性支持向量機(jī)對(duì)偶問題
max_a \ \ \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i
s.t. \ \ \ \ \sum_{i=1}^N\alpha_iy_i=0
C-\alpha_i-\mu_i=0
\alpha\geq0
\mu_i\geq0,\ \ \ \ i=1,2,\cdots,N
非線性支持向量機(jī)最優(yōu)化問題對(duì)偶問題
min_a \ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i
s.t. \ \ \ \ \sum_{i=1}^N\alpha_iy_i=0
0\leq\alpha_i\leq C,\ \ \ \ i=1,2,\cdots,N

3、算法及Python實(shí)現(xiàn)

線性支持向量機(jī)學(xué)習(xí)算法
輸入：訓(xùn)練數(shù)據(jù)集T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,x_N)},其中，x_i\in \chi=R^n,y\in \Upsilon=\{-1,+1\}，i=1,2,\cdots,N;
輸出：分離超平面和分類決策函數(shù)。
（1）選擇懲罰參數(shù)C>0，構(gòu)造并求解凸二次規(guī)劃問題
min_a \ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i
s.t. \ \ \ \ \sum_{i=1}^N\alpha_iy_i=0
0\leq\alpha_i\leq C, \ \ \ \ i=1,2,\cdots,N
求得最優(yōu)解\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)T
（2）計(jì)算w^*=\sum_{i=1}^N\alpha_i^*y_ix_i
選擇\alpha^*的一個(gè)分量\alpha_j^*適合條件0<\alpha_j^*<C計(jì)算
b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)
（3）求得分離超平面
w^*\cdot x+b^*=0
分類決策函數(shù)：
f(x)=sign(w^*\cdot x+b^*)
非線性支持向量機(jī)學(xué)習(xí)算法
輸入：訓(xùn)練數(shù)據(jù)集T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,x_N)},其中，x_i\in \chi=R^n,y\in \Upsilon=\{-1,+1\}，i=1,2,\cdots,N;
輸出：分類決策函數(shù)。
1）選擇適當(dāng)?shù)暮撕瘮?shù)K(x,z)和適當(dāng)?shù)膮?shù)C，構(gòu)造并求解最優(yōu)化問題
min_a \ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i, x_j)-\sum_{i=1}^N\alpha_i
s.t. \ \ \ \ \sum_{i=1}^N\alpha_iy_i=0
0\leq\alpha_i\leq C, \ \ \ \ i=1,2,\cdots,N
求得最優(yōu)解\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)T
（2）選擇\alpha^*的一個(gè)正分量0<\alpha_j^*<C計(jì)算
b^*=y_j-\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)
（3）構(gòu)造決策函數(shù)
w^*\cdot x+b^*=0
分類決策函數(shù)：
f(x)=sign(\sum_{i=1}^N\alpha_i^*y_iK(x\cdot x_i)+b^*)
當(dāng)K(x,z)是正定核函數(shù)時(shí)，上述問題是凸二次規(guī)劃問題，解是存在的。
為了更為高效的求解凸二次規(guī)劃問題，這里介紹由Platt于1998年提出的序列最小最優(yōu)化（SMO）算法。
SMO算法
輸入：輸入：訓(xùn)練數(shù)據(jù)集T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,x_N)},其中，x_i\in \chi=R^n,y\in \Upsilon=\{-1,+1\}，i=1,2,\cdots,N，精度\varepsilon;
輸出：近似解\hat\alpha.
（1）取初值\alpha^{(0)}=0，令k=0；
（2）選取最優(yōu)化變量\alpha_1^{(k)},\alpha_1^{(k)}解析求解兩個(gè)變量的最優(yōu)化問題，求得最優(yōu)解\alpha_1^{(k+1)},\alpha_1^{(k+2)}，更新\alpha 為\alpha^{(k+1)}
（3）若在精度\varepsilon范圍內(nèi)滿足停止條件
\sum_{i=1}^N\alpha_iy_i=0
0\leq\alpha_i\leq C, \ \ \ \ i=1,2,\cdots,N
y_i \cdot g(x_i)=\begin{cases} \geq1, &\{x_i|\alpha_i=0\} \\ =1, & \{x_i|0< \alpha_i < C\} \\ \leq1,& \{x_i|\alpha_i=C\} \end{cases}
其中，
g(x_i)=\sum_{j=1}^K \alpha_jy_jK(x_j,x_i)+b
則轉(zhuǎn)（4）；否則令k=k+1，轉(zhuǎn)（2）；
（4）取\hat\alpha = \alpha^{(k+1)}。

Python代碼實(shí)現(xiàn)
SMO算法求解線性可分支持向量機(jī)代碼

from numpy import *
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])])
        labelMat.append(float(lineArr[2]))
    return dataMat,labelMat
def selectJrand(i,m):
    j = i
    while(j==i):
        j = int(random.uniform(0,m))
    return j
def clipAlpha(aj,H,L):
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj
def smoSimple(dataMatIn,classLabels,C,toler,maxIter):
    dataMatrix = mat(dataMatIn);labelMat = mat(classLabels).transpose()
    b = 0; m,n = shape(dataMatrix)
    alphas = mat(zeros((m,1)))
    iter = 0
    while(iter<maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T))+b
            Ei = fXi - float(labelMat[i])
            if ((labelMat[i]*Ei < - toler) and (alphas[i]<C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
                j = selectJrand(i,m)
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T))+b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy()
                alphaJold = alphas[j].copy()
                if(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
                eta = 2.0*dataMatrix[i,:]*dataMatrix[j,:].T-dataMatrix[i,:]*dataMatrix[i,:].T-dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >=0: 
#                     print("eta>=0"); 
                    continue
                alphas[j] -= labelMat[j] *(Ei - Ej)/eta
                alphas[j] = clipAlpha(alphas[j],H,L)
                if(abs(alphas[j]-alphaJold) < 0.000001): 
#                     print("j not moving enough"); 
                    continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold-alphas[j])
                b1 = b - Ei -labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*\
                dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej - labelMat[i]*(alphas[i]-alphaIold)*labelMat[j]*alphas[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]): b = b1
                elif (0<alphas[j]) and (C > alphas[j]): b = b2
                else: b = (b1+b2)/2.0
                alphaPairsChanged += 1
#                 print("iter:%d i:%d,pairs changed %d "%(iter,i,alphaPairsChanged))
        if(alphaPairsChanged == 0): iter += 1
        else: iter = 0
#         print("iteration number: %d"% iter)
    return b,alphas
def calcWs(alphas,dataArr,classLabels):
    X = mat(dataArr); labelMat = mat(classLabels).transpose()
    m,n = shape(X)
    w = zeros((n,1))
    for i in range(m):
        w += multiply(alphas[i]*labelMat[i],X[i,:].T)
    return w
def plotData(dataArr,labelArr,ws,b):
    import matplotlib.pyplot as plt
    fig = plt.figure()
    plt.rcParams['font.sans-serif']=['SimHei'] #用來正常顯示中文標(biāo)簽
    plt.rcParams['axes.unicode_minus']=False #用來正常顯示負(fù)號(hào)
    xPlotx,xPloty,oPlotx,oPloty = [],[],[],[]
    for i in range(len(labelArr)):
        label = labelArr[i]
        if label == 1:
            xPlotx.append(dataArr[i][0])
            xPloty.append(dataArr[i][1])
        elif label == -1:
            oPlotx.append(dataArr[i][0])
            oPloty.append(dataArr[i][1])
    plt.title("SVM")
    pPlot1,pPlot2 = plt.plot(xPlotx,xPloty,'bx',oPlotx,oPloty,'ro')
    #Plot the split line
    w0 = ws[0][0]
    w1 = ws[1][0]
    x = linspace(1,8,100)
    y = -(w0/w1)*x-b[0][0]/w1
    pSplitPlot = plt.plot(x,y,'k',lw=1)
    plt.show()

繪制線性可分支持向量機(jī)超平面，所用的數(shù)據(jù)集SVM.rar

dataArr,labelArr = loadDataSet('./SVM/testSet.txt')
# print(labelArr)
b,alphas = smoSimple(dataArr,labelArr,0.6,0.001,40)
ws = calcWs(alphas,dataArr,labelArr)
b = array(b)
plotData(dataArr,labelArr,ws,b)

繪制的圖形如下


image.png

4、小結(jié)

支持向量機(jī)是一種分類器，稱為“機(jī)”是因?yàn)樗鼤?huì)產(chǎn)生一個(gè)二值決策結(jié)果，即決策“機(jī)”。支持向量機(jī)的泛化錯(cuò)誤率較低，具有良好的學(xué)習(xí)能力，且學(xué)到的結(jié)果具有很好的推廣性，這些優(yōu)點(diǎn)使得支持向量機(jī)十分流行。John Platt引入了SMO算法，此算法可以通過每次優(yōu)化兩個(gè)alpha值來加快SVM的訓(xùn)練速度。
核方法或者說核技巧會(huì)將數(shù)據(jù)（有時(shí)是非線性數(shù)據(jù)），從一個(gè)低維空間映射到一個(gè)高維空間，可以將一個(gè)在低維空間中的非線性問題轉(zhuǎn)換為高維空間下的線性問題來求解，核方法不僅在SVM中適用，還可以用于其他算法中。而其中的徑向基函數(shù)是一個(gè)常用的度量兩個(gè)方向距離的核函數(shù)。
常用的核函數(shù)
1、多項(xiàng)式核函數(shù)(polynomial kernel function)
K(x,z)=(x\cdot z+1)^p
2、高斯核函數(shù)（Gaussian kernel function）
K(x,z)=exp\left ( - \frac{||x-z||^2}{2\sigma^2}\right)
3、字符串核函數(shù)（string kernel function）

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容