機(jī)器學(xué)習(xí)實戰(zhàn)

支持向量機(jī)（SVM）被認(rèn)為是最好的現(xiàn)成分類器，意味著在數(shù)據(jù)上應(yīng)用基本形式的SVM分類器就可以得到低錯誤率的結(jié)果寇僧。SVM能夠?qū)τ?xùn)練集之外的數(shù)據(jù)點做出很好的分類決策艾蓝。這里介紹最流行的一種是實現(xiàn)即序列最小化算法摹量。

基于最大間隔分隔數(shù)據(jù)

A

B

上面兩組圖中能夠都畫出一條直線將圓形點和方形點進(jìn)行區(qū)分？
B組圖中能夠很容易的畫出這樣的一條直線將數(shù)據(jù)集分開瞄勾，這樣的數(shù)據(jù)叫做線性可分?jǐn)?shù)據(jù)糊昙。這樣的一條直線稱為分隔超平面辛掠。在上線給出的例子當(dāng)中谢谦，由于數(shù)據(jù)點是二維的释牺，所以分隔超平面是一條直線。如果是數(shù)據(jù)是三維的則這分隔超平面是一個面回挽。我們希望找到距離分隔超平面最近的點没咙，確保它們離分隔面的距離盡可能給你的遠(yuǎn)。這里點到分隔面的距離被稱為間隔千劈。

支持向量機(jī) 就是離分隔超平面最近的那些點祭刚。

我們就是要找到最大化支持向量到分隔面的距離，需要找到此問題的優(yōu)化求解方法墙牌。

尋找最大間隔

圖3

圖3中和都是可以分隔數(shù)據(jù)的超平面涡驮，但是怎么求解最佳分隔直線呢？
分隔超平面的形式可以定義為的形式喜滨，要計算圖中點到超平面的距離需要給出點到分隔面的法線或垂線的長度捉捅，即。
其中

W:
X: 訓(xùn)練實例
b: bias

圖4

假設(shè)現(xiàn)在是二維的情況下
X = (x1, X2)虽风。
則超平面方程是 ：

則所有超平面右上方的點滿足：
所有超平面左下方的點滿足：

這樣我們可以定義個函數(shù)是的,當(dāng)u<0時f(u)輸出-1棒口，反之輸出+1寄月。當(dāng)計算數(shù)據(jù)點到分隔面的距離并確定分隔面的位置時，間隔通過來計算无牵。如果數(shù)據(jù)點處于正方向并且里分隔超平面很遠(yuǎn)的位置時漾肮，會是一個很大的正數(shù)，同時也會是一個很大的正數(shù)茎毁。而如果數(shù)據(jù)點處于負(fù)方向并且離分隔超平面很遠(yuǎn)的位置時克懊，此時由于類別標(biāo)簽為-1，怎任然是個很大的正數(shù)七蜘。
現(xiàn)在需要找出其中w和b保檐。為此我們需要找到具有最小間隔的數(shù)據(jù)點，而這些數(shù)據(jù)點也是前面提到的支持向量崔梗。一旦找到具有最小間隔的數(shù)據(jù)點夜只，我們就需要對該間隔最大化。

• 代碼示例

//引入numpy
from numpy import *
//讀取文件數(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])])
        labelMat.append(float(lineArr[2]))
    return dataMat,labelMat
#隨機(jī)數(shù)獲取
def selectJrand(i,m):
    j = i;
    while(j==i):
        j = int(random.uniform(0,m))
    return j
//參數(shù)矯正
def clipAlpha(aj,H,L):
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj



'''
創(chuàng)建一個Alpha向量并將其初始化為0向量
當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時(外循環(huán))
    對數(shù)據(jù)集中的每個數(shù)據(jù)向量(內(nèi)循環(huán))：
        如果該向量可以被優(yōu)化:
            隨機(jī)選擇另一個數(shù)據(jù)向量
            同時優(yōu)化這兩個向量
            如果兩個向量都不能被優(yōu)化蒜魄，退出內(nèi)循環(huán)
如果所有向量都沒有被優(yōu)化扔亥，增加迭代數(shù)目，繼續(xù)下一次循環(huán)

'''
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):
        #每次循環(huán)都將alphaPairsChanged設(shè)為0.在對整個集合順序遍歷谈为。用于記錄alpha是否優(yōu)化
        alphaPairsChanged = 0
        for i in range(m):
            #計算fXi這就是我們預(yù)測的類別 然后基于這個實例的預(yù)測結(jié)果和真是結(jié)果的對比 就可以計算Ei誤差
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions
            #如果誤差很大就需要對該實例對應(yīng)的alpha值進(jìn)行優(yōu)化
            #if語句中不管是正間隔還是負(fù)間隔都會被測試旅挤，并且在該if語句中，也同時檢查alpha的值伞鲫，以保證其不能等于0或C粘茄。
            #由于后面alpha小于0或者大于C時將會被調(diào)整為0或C，所有一旦在該if語句中等于這兩個值的話秕脓，就不需要再優(yōu)化了
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
                #隨機(jī)選擇一個值
                j = selectJrand(i,m)
                #計算誤差
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                #計算兩個alpha的誤差
                alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();
                #計算L和H 用于將alpha[j]調(diào)整到0到C之間
                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
                #alpha[j]的最優(yōu)修改量
                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] 如果輕微改變則結(jié)束循環(huán)
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                alphas[j] = clipAlpha(alphas[j],H,L)
                if (abs(alphas[j] - alphaJold) < 0.00001): print( "j not moving enough"); continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#update i by the same amount as j
                                                                        #the update is in the oppostie direction
                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)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[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

if __name__ == '__main__':
    dataMat,labelMat = loadDataSet('svn.txt')
    b,alphas = smoSimple(dataMat,labelMat,0.6,0.001,40)
    for i in range(100):
        if alphas[i]>0:
            print(dataMat[i],labelMat[i])

[4.658191, 3.507396] -1.0
[3.457096, -0.082216] -1.0
[6.080573, 0.418886] 1.0

• sklearn示例

from sklearn import svm
if __name__ == '__main__':
    dataMat,labelMat = loadDataSet('svn.txt')
    #SVC有很多參數(shù)提供調(diào)試選擇柒瓣，達(dá)到最優(yōu)的解
    clf = svm.SVC(kernel='linear')
    clf.fit(dataMat,labelMat)
    print(clf)
    print(clf.support_vectors_)

SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
  decision_function_shape=None, degree=3, gamma='auto', kernel='linear',
  max_iter=-1, probability=False, random_state=None, shrinking=True,
  tol=0.001, verbose=False)
[[ 4.658191  3.507396]
 [ 3.457096 -0.082216]
 [ 6.080573  0.418886]]

利用完整Platte SMO算法加速優(yōu)化

'''
用一個對象來保存一些重要的值
'''
class optStruct:
    def __init__(self,dataMatIn,classLabels,C,toler):
        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)))
'''
對于給定的alpha值 calcEk能夠計算E值并返回 真實值與預(yù)測值之間的誤差
'''
def calcEk(oS,k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T))+oS.b
    Ek = fXk - float(oS.labelMat[k])
    return Ek
'''
用于選擇第二個alpha值以保證在每次優(yōu)化中采用最大的步長
'''
def selectJ(i,oS,Ei):
    maxK = -1;maxDeltaE = 0;Ej = 0
    oS.eCache[i] = [1,Ei]
    #返回非零E值對應(yīng)的alpha值
    validEcacheList = nonzero(oS.eCache[:,0].A)[0] #.A是什么操作
    if(len(validEcacheList)) > 1:
        for k in validEcacheList:
            if k == i:continue
            Ek = calcEk(oS,k)
            deltaE = abs(Ei-Ek)
            if(deltaE > maxDeltaE):
                #選擇使得該變量最大的那個值
                maxK = k;maxDeltaE = deltaE;Ej = Ek
        return maxK,Ej
    else:
        j = selectJrand(i,oS.m)
        Ej = calcEk(oS,j)
    return j,Ej
#計算誤差值并存入緩存中
def updateEk(oS,k):
    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)
        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.X[i,:]*oS.X[j,:].T - oS.X[i,:]*oS.X[i,:].T - oS.X[j,:]*oS.X[j,:].T
        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)
        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])
        updateEk(oS,i)
        b1 = oS.b - Ei - oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T \
             - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[i,:]*oS.X[j,:].T
        b2 = oS.b - Ej - oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[j,:].T \
             - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[j,:]*oS.X[j,:].T
        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
def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)):  # full Platt SMO
    oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler)
    iter = 0
    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