今天跟大家介紹的是SVM算法原理以及實(shí)現(xiàn)，廢話不多說(shuō)，直接來(lái)看干貨吧!

一、SVM概念

SVM的全稱為Support Vector Machine，也就是我們經(jīng)常提到的支持向量機(jī)，主要被用來(lái)解決模式識(shí)別領(lǐng)域中的數(shù)據(jù)分類問(wèn)題，是一種有監(jiān)督學(xué)習(xí)算法。

具體解釋一下：

Support Vector，支持向量，指的是訓(xùn)練樣本集中的某些訓(xùn)練點(diǎn)，這些訓(xùn)練點(diǎn)非?？拷诸悰Q策面，因此是最難分類的數(shù)據(jù)點(diǎn)。SVM中最優(yōu)分類標(biāo)準(zhǔn)為：這些點(diǎn)與分類超平面之間的距離達(dá)到最大值;

Machine“機(jī)”，指的是機(jī)器學(xué)習(xí)領(lǐng)域?qū)σ恍┧惴ǖ慕y(tǒng)稱，通常我們把算法看做一個(gè)機(jī)器或?qū)W習(xí)函數(shù)。SVM是一種有監(jiān)督的學(xué)習(xí)方法，主要是針對(duì)小樣本數(shù)據(jù)的學(xué)習(xí)、分類和預(yù)測(cè)。

二、SVM的優(yōu)點(diǎn)

1、需要的樣本數(shù)量不是很大，但這并不表示SVM訓(xùn)練樣本的絕對(duì)量很少，只是說(shuō)與其他訓(xùn)練分類算法相比，在同樣的問(wèn)題復(fù)雜度情況下，SVM對(duì)樣本的需求相對(duì)是較少的。而且SVM引入了核函數(shù)，因此即使是高維的樣本，SVM也能輕松應(yīng)對(duì)。

2、結(jié)構(gòu)風(fēng)險(xiǎn)最小。這種風(fēng)險(xiǎn)指的是分類器對(duì)問(wèn)題真實(shí)模型的逼近，以及問(wèn)題真實(shí)解之間的累積誤差。

3、非線性，指的是：SVM非常擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況，通常是利用松弛變量(或者叫懲罰變量)以及核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)的，這也是SVM的精髓所在。

三、SVM的原理

1.點(diǎn)到超平面的距離公式

超平面的方程也可以寫成一下形式：

假設(shè)P(x1.x2...xn)為樣本的中的一個(gè)點(diǎn)，其中xi表示為第個(gè)特征變量。那么該點(diǎn)到超平面的距離d就可以用如下公式進(jìn)行計(jì)算：

其中||w||為超平面的2范數(shù)，也就是w向量的模長(zhǎng)，常數(shù)b類似于直線方程中的截距。

2.最大間隔的優(yōu)化模型

其中y代表數(shù)據(jù)點(diǎn)的標(biāo)簽，并且其為-1或1.若數(shù)據(jù)點(diǎn)在平面的正方向(也就是+1類)，那么就是一個(gè)正數(shù)，而如果數(shù)據(jù)點(diǎn)在平面的負(fù)方向的情況下(即-1類)，仍然是一個(gè)正數(shù)，這樣就可以保證始終大于0了。我們需要注意，如果w和b等比例放大，d的結(jié)果不會(huì)改變。令u=y(wTx+b)，所有支持向量的u為1.那么其他點(diǎn)的u大于1.我們可以通過(guò)調(diào)節(jié)w和b求到。這樣一來(lái)，上面的問(wèn)題可以簡(jiǎn)化為：

等價(jià)替換為：

這是一個(gè)有約束條件的優(yōu)化問(wèn)題，我們通常會(huì)用拉格朗日乘子法來(lái)求解。令:

四、python實(shí)現(xiàn)

#svm算法的實(shí)現(xiàn)
from numpy import*
import random
from time import*
def loadDataSet(fileName):#輸出dataArr(m*n),labelArr(1*m)其中m為數(shù)據(jù)集的個(gè)數(shù)
    dataMat=[];labelMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        lineArr=line.strip().split('\t')#去除制表符，將數(shù)據(jù)分開(kāi)
        dataMat.append([float(lineArr[0]),float(lineArr[1])])#數(shù)組矩陣
        labelMat.append(float(lineArr[2]))#標(biāo)簽
    return dataMat,labelMat

def selectJrand(i,m):#隨機(jī)找一個(gè)和i不同的j
    j=i
    while(j==i):
        j=int(random.uniform(0,m))
    return j

def clipAlpha(aj,H,L):#調(diào)整大于H或小于L的alpha的值
    if aj>H:
        aj=H
    if aj<L:
        aj=L
    return aj

def smoSimple(dataMatIn,classLabels,C,toler,maxIter):
    dataMatrix=mat(dataMatIn);labelMat=mat(classLabels).transpose()#轉(zhuǎn)置
    b=0;m,n=shape(dataMatrix)#m為輸入數(shù)據(jù)的個(gè)數(shù)，n為輸入向量的維數(shù)
    alpha=mat(zeros((m,1)))#初始化參數(shù)，確定m個(gè)alpha
    iter=0#用于計(jì)算迭代次數(shù)
    while (iter<maxIter):#當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時(shí)（外循環(huán)）
        alphaPairsChanged=0#初始化alpha的改變量為0
        for i in range(m):#內(nèi)循環(huán)
            fXi=float(multiply(alpha,labelMat).T*\
                      (dataMatrix*dataMatrix[i,:].T))+b#計(jì)算f(xi)
            Ei=fXi-float(labelMat[i])#計(jì)算f(xi)與標(biāo)簽之間的誤差
            if ((labelMat[i]*Ei<-toler)and(alpha[i]<C))or\
                    ((labelMat[i]*Ei>toler)and(alpha[i]>0)):#如果可以進(jìn)行優(yōu)化
                j=selectJrand(i,m)#隨機(jī)選擇一個(gè)j與i配對(duì)
                fXj=float(multiply(alpha,labelMat).T*\
                          (dataMatrix*dataMatrix[j,:].T))+b#計(jì)算f(xj)
                Ej=fXj-float(labelMat[j])#計(jì)算j的誤差
                alphaIold=alpha[i].copy()#保存原來(lái)的alpha(i)
                alphaJold=alpha[j].copy()
                if(labelMat[i]!=labelMat[j]):#保證alpha在0到c之間
                    L=max(0,alpha[j]-alpha[i])
                    H=min(C,C+alpha[j]-alpha[i])
                else:
                    L=max(0,alpha[j]+alpha[i]-C)
                    H=min(C,alpha[j]+alpha[i])
                if L==H:print('L=H');continue
                eta=2*dataMatrix[i,:]*dataMatrix[j,:].T-\
                    dataMatrix[i,:]*dataMatrix[i,:].T-\
                    dataMatrix[j,:]*dataMatrix[j,:].T
                if eta>=0:print('eta=0');continue
                alpha[j]-=labelMat[j]*(Ei-Ej)/eta
                alpha[j]=clipAlpha(alpha[j],H,L)#調(diào)整大于H或小于L的alpha
                if (abs(alpha[j]-alphaJold)<0.0001):
                    print('j not move enough');continue
                alpha[i]+=labelMat[j]*labelMat[i]*(alphaJold-alpha[j])
                b1=b-Ei-labelMat[i]*(alpha[i]-alphaIold)*\
                    dataMatrix[i,:]*dataMatrix[i,:].T-\
                    labelMat[j]*(alpha[j]-alphaJold)*\
                    dataMatrix[i,:]*dataMatrix[j,:].T#設(shè)置b
                b2=b-Ej-labelMat[i]*(alpha[i]-alphaIold)*\
                    dataMatrix[i,:]*dataMatrix[i,:].T-\
                    labelMat[j]*(alpha[j]-alphaJold)*\
                    dataMatrix[j,:]*dataMatrix[j,:].T
                if (0<alpha[i])and(C>alpha[j]):b=b1
                elif(0<alpha[j])and(C>alpha[j]):b=b2
                else:b=(b1+b2)/2
                alphaPairsChanged+=1
                print('iter:%d i:%d,pairs changed%d'%(iter,i,alphaPairsChanged))
        if (alphaPairsChanged==0):iter+=1
        else:iter=0
        print('iteraction number:%d'%iter)
    return b,alpha
#定義徑向基函數(shù)
def kernelTrans(X, A, kTup):#定義核轉(zhuǎn)換函數(shù)（徑向基函數(shù)）
    m,n = shape(X)
    K = mat(zeros((m,1)))
    if kTup[0]=='lin': K = X * A.T   #線性核K為m*1的矩陣
    elif kTup[0]=='rbf':
        for j in range(m):
            deltaRow = X[j,:] - A
            K[j] = deltaRow*deltaRow.T
        K = exp(K/(-1*kTup[1]**2)) #divide in NumPy is element-wise not matrix like Matlab
    else: raise NameError('Houston We Have a Problem -- \
    That Kernel is not recognized')
    return K

class optStruct:
    def __init__(self,dataMatIn, classLabels, C, toler, kTup):  # Initialize the structure with the parameters
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2))) #first column is valid flag
        self.K = mat(zeros((self.m,self.m)))
        for i in range(self.m):
            self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)

def calcEk(oS, k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
    Ek = fXk - float(oS.labelMat[k])
    return Ek

def selectJ(i, oS, Ei):
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]
    validEcacheList = nonzero(oS.eCache[:,0].A)[0]
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:   #loop through valid Ecache values and find the one that maximizes delta E
            if k == i: continue #don't calc for i, waste of time
            Ek = calcEk(oS, k)
            deltaE = abs(Ei - Ek)
            if (deltaE > maxDeltaE):
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej
    else:   #in this case (first time around) we don't have any valid eCache values
        j = selectJrand(i, oS.m)
        Ej = calcEk(oS, j)
    return j, Ej

def updateEk(oS, k):#after any alpha has changed update the new value in the cache
    Ek = calcEk(oS, k)
    oS.eCache[k] = [1,Ek]

def innerL(i, oS):
    Ei = calcEk(oS, i)
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy()
        if (oS.labelMat[i] != oS.labelMat[j]):
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])
        if L==H: print("L==H"); return 0
        eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j] #changed for kernel
        if eta >= 0: print("eta>=0"); return 0
        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) #added this for the Ecache
        if (abs(oS.alphas[j] - alphaJold) < 0.00001): print("j not moving enough"); return 0
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
        updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
        b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2
        else: oS.b = (b1 + b2)/2.0
        return 1
    else: return 0
#smoP函數(shù)用于計(jì)算超平的alpha,b
def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)):    #完整的Platter SMO
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)
    iter = 0#計(jì)算循環(huán)的次數(shù)
    entireSet = True; alphaPairsChanged = 0
    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
        alphaPairsChanged = 0
        if entireSet:   #go over all
            for i in range(oS.m):
                alphaPairsChanged += innerL(i,oS)
                print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        else:#go over non-bound (railed) alphas
            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i,oS)
                print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        if entireSet: entireSet = False #toggle entire set loop
        elif (alphaPairsChanged == 0): entireSet = True
        print("iteration number: %d" % iter)
    return oS.b,oS.alphas
#calcWs用于計(jì)算權(quán)重值w
def calcWs(alphas,dataArr,classLabels):#計(jì)算權(quán)重W
    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

#值得注意的是測(cè)試準(zhǔn)確與k1和C的取值有關(guān)。
def testRbf(k1=1.3):#給定輸入?yún)?shù)K1
    #測(cè)試訓(xùn)練集上的準(zhǔn)確率
    dataArr,labelArr = loadDataSet('testSetRBF.txt')#導(dǎo)入數(shù)據(jù)作為訓(xùn)練集
    b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, ('rbf', k1)) #C=200 important
    datMat=mat(dataArr); labelMat = mat(labelArr).transpose()
    svInd=nonzero(alphas.A>0)[0]#找出alphas中大于0的元素的位置
    #此處需要說(shuō)明一下alphas.A的含義
    sVs=datMat[svInd] #獲取支持向量的矩陣，因?yàn)橹灰猘lpha中不等于0的元素都是支持向量
    labelSV = labelMat[svInd]#支持向量的標(biāo)簽
    print("there are %d Support Vectors" % shape(sVs)[0])#輸出有多少個(gè)支持向量
    m,n = shape(datMat)#數(shù)據(jù)組的矩陣形狀表示為有m個(gè)數(shù)據(jù)，數(shù)據(jù)維數(shù)為n
    errorCount = 0#計(jì)算錯(cuò)誤的個(gè)數(shù)
    for i in range(m):#開(kāi)始分類，是函數(shù)的核心
        kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))#計(jì)算原數(shù)據(jù)集中各元素的核值
        predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b#計(jì)算預(yù)測(cè)結(jié)果y的值
        if sign(predict)!=sign(labelArr[i]): errorCount += 1#利用符號(hào)判斷類別
        ### sign（a）為符號(hào)函數(shù)：若a>0則輸出1，若a<0則輸出-1.###
    print("the training error rate is: %f" % (float(errorCount)/m))
    #2、測(cè)試測(cè)試集上的準(zhǔn)確率
    dataArr,labelArr = loadDataSet('testSetRBF2.txt')
    errorCount = 0
    datMat=mat(dataArr)#labelMat = mat(labelArr).transpose()此處可以不用
    m,n = shape(datMat)
    for i in range(m):
        kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))
        predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
        if sign(predict)!=sign(labelArr[i]): errorCount += 1
    print("the test error rate is: %f" % (float(errorCount)/m))
def main():
    t1=time()
    dataArr,labelArr=loadDataSet('testSet.txt')
    b,alphas=smoP(dataArr,labelArr,0.6,0.01,40)
    ws=calcWs(alphas,dataArr,labelArr)
    testRbf()
    t2=time()
    print("程序所用時(shí)間為%ss"%(t2-t1))

if __name__=='__main__':
    main()