第6章支持向量機

支持向量機_首頁

支持向量機概述

支持向量機(Support Vector Machines, SVM)：是一種機器學習算法。

支持向量(Support Vector)就是離分隔超平面最近的那些點。
機(Machine)就是表示一種算法，而不是表示機器。

支持向量機場景

要給左右兩邊的點進行分類
明顯發(fā)現(xiàn)：選擇D會比B、C分隔的效果要好很多。

線性可分

支持向量機原理

SVM 工作原理

原理圖

對于上述的蘋果和香蕉，我們想象為2種水果類型的炸彈。（保證距離最近的炸彈，距離它們最遠）

尋找最大分類間距
轉(zhuǎn)而通過拉格朗日函數(shù)求優(yōu)化的問題

數(shù)據(jù)可以通過畫一條直線就可以將它們完全分開，這組數(shù)據(jù)叫線性可分(linearly separable)數(shù)據(jù)，而這條分隔直線稱為分隔超平面(separating hyperplane)。
如果數(shù)據(jù)集上升到1024維呢？那么需要1023維來分隔數(shù)據(jù)集，也就說需要N-1維的對象來分隔，這個對象叫做超平面(hyperlane)，也就是分類的決策邊界。

分隔超平面

尋找最大間隔

為什么尋找最大間隔

摘錄地址：http://slideplayer.com/slide/8610144  (第12條信息)
Support Vector Machines: Slide 12 Copyright ? 2001, 2003, Andrew W. Moore Why Maximum Margin? 
denotes +1 denotes -1 f(x,w,b) = sign(w. x - b) The maximum margin linear classifier is the linear classifier with the, um, maximum margin. 
This is the simplest kind of SVM (Called an LSVM) Support Vectors are those datapoints that the margin pushes up against 

1.Intuitively this feels safest. 
2.If we’ve made a small error in the location of the boundary (it’s been jolted in its perpendicular direction) this gives us least chance of causing a misclassification. 
3.CV is easy since the model is immune to removal of any non-support-vector datapoints. 
4.There’s some theory that this is a good thing. 
5.Empirically it works very very well. 

* * *

1. 直覺上是安全的
2. 如果我們在邊界的位置發(fā)生了一個小錯誤（它在垂直方向上被顛倒），這給我們最小的錯誤分類機會。
3. CV（Computer Vision 計算機視覺 - 這縮寫看著可怕?）很容易，因為該模型對任何非支持向量數(shù)據(jù)點的去除是免疫的。
4. 有一些理論，這是一件好事。
5. 通常它的工作非常好。

怎么尋找最大間隔

點到超平面的距離

分隔超平面函數(shù)間距: \(y(x)=w^Tx+b\)
分類的結果： \(f(x)=sign(w^Tx+b)\) (sign表示>0為1，<0為-1，=0為0)
點到超平面的幾何間距: \(d(x)=(w^Tx+b)/||w||\) （||w||表示w矩陣的二范式=> \(\sqrt{w*w^T}\), 點到超平面的距離也是類似的）

點到直線的幾何距離

拉格朗日乘子法

類別標簽用-1、1，是為了后期方便 \(lable(w^Tx+b)\) 的標識和距離計算；如果 \(lable(w^Tx+b)>0\) 表示預測正確，否則預測錯誤。
現(xiàn)在目標很明確，就是要找到w和b，因此我們必須要找到最小間隔的數(shù)據(jù)點，也就是前面所說的支持向量。
- 也就說，讓最小的距離取最大.(最小的距離：就是最小間隔的數(shù)據(jù)點；最大：就是最大間距，為了找出最優(yōu)超平面--最終就是支持向量)
- 目標函數(shù)：\(arg: max_{關于w, b} \left( min[lable(w^Tx+b)]\frac{1}{||w||} \right) \)
  1. 如果 \(lable*(w^Tx+b)>0\) 表示預測正確，也稱函數(shù)間隔，\(||w||\) 可以理解為歸一化，也稱幾何間隔。
  2. 令 \(lable(w^Tx+b)>=1\)，因為0～1之間，得到的點是存在誤判的可能性，所以要保障 \(min[lable(w^Tx+b)]=1\)，才能更好降低噪音數(shù)據(jù)影響。
  3. 所以本質(zhì)上是求 \(arg: max_{關于w, b} \frac{1}{||w||} \)；也就說，我們約束(前提)條件是: \(lable*(w^Tx+b)=1\)
新的目標函數(shù)求解： \(arg: max_{關于w, b} \frac{1}{||w||} \)
- => 就是求: \(arg: min_{關于w, b} ||w|| \) (求矩陣會比較麻煩，如果x只是 \(\frac{1}{2}*x^2\) 的偏導數(shù)，那么。。同樣是求最小值)
- => 就是求: \(arg: min_{關于w, b} (\frac{1}{2}*||w||^2)\) (二次函數(shù)求導，求極值，平方也方便計算)
- 本質(zhì)上就是求線性不等式的二次優(yōu)化問題(求分隔超平面，等價于求解相應的凸二次規(guī)劃問題)
通過拉格朗日乘子法，求二次優(yōu)化問題
- 假設需要求極值的目標函數(shù) (objective function) 為 f(x,y)，限制條件為 φ(x,y)=M # M=1
- 設g(x,y)=M-φ(x,y) # 臨時φ(x,y)表示下文中 \(label*(w^Tx+b)\)
- 定義一個新函數(shù): F(x,y,λ)=f(x,y)+λg(x,y)
- a為λ（a>=0），代表要引入的拉格朗日乘子(Lagrange multiplier)
- 那么： \(L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]\)
- 因為：\(label(w^Tx+b)>=1, \alpha>=0\) , 所以 \(\alpha[1-label(w^Tx+b)]<=0\) , \(\sum_{i=1}^{n} \alpha_i * [1-label(w^Tx+b)]<=0\)
- 相當于求解： \(max_{關于\alpha} L(w,b,\alpha) = \frac{1}{2} *||w||^2\)
- 如果求： \(min_{關于w, b} \frac{1}{2} *||w||^2\) , 也就是要求： \(min_{關于w, b} \left( max_{關于\alpha} L(w,b,\alpha)\right)\)
現(xiàn)在轉(zhuǎn)化到對偶問題的求解
- \(min_{關于w, b} \left(max_{關于\alpha} L(w,b,\alpha) \right) \) >= \(max_{關于\alpha} \left(min_{關于w, b}\ L(w,b,\alpha) \right) \)
- 現(xiàn)在分2步
- 先求： \(min_{關于w, b} L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]\)
- 就是求L(w,b,a)關于[w, b]的偏導數(shù), 得到w和b的值，并化簡為：L和a的方程。
- 參考：如果公式推導還是不懂，也可以參考《統(tǒng)計學習方法》李航-P103<學習的對偶算法>
  
  計算拉格朗日函數(shù)的對偶函數(shù)
終于得到課本上的公式： \(max_{關于\alpha} \left( \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i, j=1}^{m} label_i·label_j·\alpha_i·\alpha_j·<x_i, x_j> \right) \)
約束條件： \(a>=0\) 并且 \(\sum_{i=1}^{m} a_i·label_i=0\)

松弛變量(slack variable)

我們知道幾乎所有的數(shù)據(jù)都不那么干凈, 通過引入松弛變量來允許數(shù)據(jù)點可以處于分隔面錯誤的一側。
約束條件： \(C>=a>=0\) 并且 \(\sum_{i=1}^{m} a_i·label_i=0\)
這里常量C用于控制“最大化間隔”和“保證大部分點的函數(shù)間隔小于1.0” 這兩個目標的權重。
常量C是一個常數(shù)，我們通過調(diào)節(jié)該參數(shù)得到不同的結果。一旦求出了所有的alpha，那么分隔超平面就可以通過這些alpha來表示。
這一結論十分直接，SVM中的主要工作就是要求解 alpha.

SMO 高效優(yōu)化算法

SVM有很多種實現(xiàn)，最流行的一種實現(xiàn)是： 序列最小優(yōu)化(Sequential Minimal Optimization, SMO)算法。
下面還會介紹一種稱為核函數(shù)(kernel)的方式將SVM擴展到更多數(shù)據(jù)集上。
注意：SVM幾何含義比較直觀，但其算法實現(xiàn)較復雜，牽扯大量數(shù)學公式的推導。

序列最小優(yōu)化(Sequential Minimal Optimization, SMO)

創(chuàng)建作者：John Platt
創(chuàng)建時間：1996年
SMO用途：用于訓練 SVM
SMO目標：求出一系列 alpha 和 b,一旦求出 alpha，就很容易計算出權重向量 w 并得到分隔超平面。
SMO思想：是將大優(yōu)化問題分解為多個小優(yōu)化問題來求解的。
SMO原理：每次循環(huán)選擇兩個 alpha 進行優(yōu)化處理，一旦找出一對合適的 alpha，那么就增大一個同時減少一個。
- 這里指的合適必須要符合一定的條件
  1. 這兩個 alpha 必須要在間隔邊界之外
  2. 這兩個 alpha 還沒有進行過區(qū)間化處理或者不在邊界上。
- 之所以要同時改變2個 alpha；原因是我們有一個約束條件： \(\sum_{i=1}^{m} a_i·label_i=0\)；如果只是修改一個 alpha，很可能導致約束條件失效。

SMO 偽代碼大致如下：

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

SVM 開發(fā)流程

收集數(shù)據(jù)：可以使用任意方法。
準備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)。
分析數(shù)據(jù)：有助于可視化分隔超平面。
訓練算法：SVM的大部分時間都源自訓練，該過程主要實現(xiàn)兩個參數(shù)的調(diào)優(yōu)。
測試算法：十分簡單的計算過程就可以實現(xiàn)。
使用算法：幾乎所有分類問題都可以使用SVM，值得一提的是，SVM本身是一個二類分類器，對多類問題應用SVM需要對代碼做一些修改。

SVM 算法特點

優(yōu)點：泛化（由具體的、個別的擴大為一般的，就是說：模型訓練完后的新樣本）錯誤率低，計算開銷不大，結果易理解。
缺點：對參數(shù)調(diào)節(jié)和核函數(shù)的選擇敏感，原始分類器不加修改僅適合于處理二分類問題。
使用數(shù)據(jù)類型：數(shù)值型和標稱型數(shù)據(jù)。

課本案例（無核函數(shù)）

項目概述

對小規(guī)模數(shù)據(jù)點進行分類

開發(fā)流程

收集數(shù)據(jù)

文本文件格式：

3.542485    1.977398    -1
3.018896    2.556416    -1
7.551510    -1.580030   1
2.114999    -0.004466   -1
8.127113    1.274372    1

準備數(shù)據(jù)

def loadDataSet(fileName):
    """
    對文件進行逐行解析，從而得到第行的類標簽和整個特征矩陣
    Args:
        fileName 文件名
    Returns:
        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])])
        labelMat.append(float(lineArr[2]))
    return dataMat, labelMat

分析數(shù)據(jù): 無

訓練算法

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    """smoSimple

    Args:
        dataMatIn    特征集合
        classLabels  類別標簽
        C   松弛變量(常量值)，允許有些數(shù)據(jù)點可以處于分隔面的錯誤一側。
            控制最大化間隔和保證大部分的函數(shù)間隔小于1.0這兩個目標的權重。
            可以通過調(diào)節(jié)該參數(shù)達到不同的結果。
        toler   容錯率（是指在某個體系中能減小一些因素或選擇對某個系統(tǒng)產(chǎn)生不穩(wěn)定的概率。）
        maxIter 退出前最大的循環(huán)次數(shù)
    Returns:
        b       模型的常量值
        alphas  拉格朗日乘子
    """
    dataMatrix = mat(dataMatIn)
    # 矩陣轉(zhuǎn)置 和 .T 一樣的功能
    labelMat = mat(classLabels).transpose()
    m, n = shape(dataMatrix)

    # 初始化 b和alphas(alpha有點類似權重值。)
    b = 0
    alphas = mat(zeros((m, 1)))

    # 沒有任何alpha改變的情況下遍歷數(shù)據(jù)的次數(shù)
    iter = 0
    while (iter < maxIter):
        # w = calcWs(alphas, dataMatIn, classLabels)
        # print("w:", w)

        # 記錄alpha是否已經(jīng)進行優(yōu)化，每次循環(huán)時設為0，然后再對整個集合順序遍歷
        alphaPairsChanged = 0
        for i in range(m):
            # print 'alphas=', alphas
            # print 'labelMat=', labelMat
            # print 'multiply(alphas, labelMat)=', multiply(alphas, labelMat)
            # 我們預測的類別 y[i] = w^Tx[i]+b; 其中因為 w = Σ(1~n) a[n]*lable[n]*x[n]
            fXi = float(multiply(alphas, labelMat).T*(dataMatrix*dataMatrix[i, :].T)) + b
            # 預測結果與真實結果比對，計算誤差Ei
            Ei = fXi - float(labelMat[i])

            # 約束條件 (KKT條件是解決最優(yōu)化問題的時用到的一種方法。我們這里提到的最優(yōu)化問題通常是指對于給定的某一函數(shù)，求其在指定作用域上的全局最小值)
            # 0<=alphas[i]<=C，但由于0和C是邊界值，我們無法進行優(yōu)化，因為需要增加一個alphas和降低一個alphas。
            # 表示發(fā)生錯誤的概率：labelMat[i]*Ei 如果超出了 toler， 才需要優(yōu)化。至于正負號，我們考慮絕對值就對了。
            '''
            # 檢驗訓練樣本(xi, yi)是否滿足KKT條件
            yi*f(i) >= 1 and alpha = 0 (outside the boundary)
            yi*f(i) == 1 and 0<alpha< C (on the boundary)
            yi*f(i) <= 1 and alpha = C (between the boundary)
            '''
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):

                # 如果滿足優(yōu)化的條件，我們就隨機選取非i的一個點，進行優(yōu)化比較
                j = selectJrand(i, m)
                # 預測j的結果
                fXj = float(multiply(alphas, labelMat).T*(dataMatrix*dataMatrix[j, :].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy()
                alphaJold = alphas[j].copy()

                # L和H用于將alphas[j]調(diào)整到0-C之間。如果L==H，就不做任何改變，直接執(zhí)行continue語句
                # labelMat[i] != labelMat[j] 表示異側，就相減，否則是同側，就相加。
                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])
                # 如果相同，就沒發(fā)優(yōu)化了
                if L == H:
                    print("L==H")
                    continue

                # eta是alphas[j]的最優(yōu)修改量，如果eta==0，需要退出for循環(huán)的當前迭代過程
                # 參考《統(tǒng)計學習方法》李航-P125~P128<序列最小最優(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]值
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                # 并使用輔助函數(shù)，以及L和H對其進行調(diào)整
                alphas[j] = clipAlpha(alphas[j], H, L)
                # 檢查alpha[j]是否只是輕微的改變，如果是的話，就退出for循環(huán)。
                if (abs(alphas[j] - alphaJold) < 0.00001):
                    print("j not moving enough")
                    continue
                # 然后alphas[i]和alphas[j]同樣進行改變，雖然改變的大小一樣，但是改變的方向正好相反
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                # 在對alpha[i], alpha[j] 進行優(yōu)化之后，給這兩個alpha值設置一個常數(shù)b。
                # w= Σ[1~n] ai*yi*xi => b = yj- Σ[1~n] ai*yi(xi*xj)
                # 所以：  b1 - b = (y1-y) - Σ[1~n] yi*(a1-a)*(xi*x1)
                # 為什么減2遍？ 因為是 減去Σ[1~n]，正好2個變量i和j，所以減2遍
                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))
        # 在for循環(huán)外，檢查alpha值是否做了更新，如果在更新則將iter設為0后繼續(xù)運行程序
        # 知道更新完畢后，iter次循環(huán)無變化，才推出循環(huán)。
        if (alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
        print("iteration number: %d" % iter)
    return b, alphas

完整代碼地址：SVM簡化版，應用簡化版SMO算法處理小規(guī)模數(shù)據(jù)集: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-simple.py

完整代碼地址：SVM完整版，使用完整 Platt SMO算法加速優(yōu)化，優(yōu)化點：選擇alpha的方式不同: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-complete_Non-Kernel.py

核函數(shù)(kernel) 使用

對于線性可分的情況，效果明顯
對于非線性的情況也一樣，此時需要用到一種叫核函數(shù)(kernel)的工具將數(shù)據(jù)轉(zhuǎn)化為分類器易于理解的形式。

利用核函數(shù)將數(shù)據(jù)映射到高維空間

使用核函數(shù)：可以將數(shù)據(jù)從某個特征空間到另一個特征空間的映射。（通常情況下：這種映射會將低維特征空間映射到高維空間。）
如果覺得特征空間很裝逼、很難理解。
可以把核函數(shù)想象成一個包裝器(wrapper)或者是接口(interface)，它能將數(shù)據(jù)從某個很難處理的形式轉(zhuǎn)換成為另一個較容易處理的形式。
經(jīng)過空間轉(zhuǎn)換后：低維需要解決的非線性問題，就變成了高維需要解決的線性問題。
SVM 優(yōu)化特別好的地方，在于所有的運算都可以寫成內(nèi)積(inner product: 是指2個向量相乘，得到單個標量或者數(shù)值)；內(nèi)積替換成核函數(shù)的方式被稱為核技巧(kernel trick)或者核"變電"(kernel substation)
核函數(shù)并不僅僅應用于支持向量機，很多其他的機器學習算法也都用到核函數(shù)。最流行的核函數(shù)：徑向基函數(shù)(radial basis function)
徑向基函數(shù)的高斯版本，其具體的公式為：

徑向基函數(shù)的高斯版本

項目案例: 手寫數(shù)字識別的優(yōu)化（有核函數(shù)）

項目概述

你的老板要求：你寫的那個手寫識別程序非常好，但是它占用內(nèi)存太大。顧客無法通過無線的方式下載我們的應用。
所以：我們可以考慮使用支持向量機，保留支持向量就行（knn需要保留所有的向量），就可以獲得非常好的效果。

開發(fā)流程

收集數(shù)據(jù)：提供的文本文件

00000000000000001111000000000000
00000000000000011111111000000000
00000000000000011111111100000000
00000000000000011111111110000000
00000000000000011111111110000000
00000000000000111111111100000000
00000000000000111111111100000000
00000000000001111111111100000000
00000000000000111111111100000000
00000000000000111111111100000000
00000000000000111111111000000000
00000000000001111111111000000000
00000000000011111111111000000000
00000000000111111111110000000000
00000000001111111111111000000000
00000001111111111111111000000000
00000011111111111111110000000000
00000111111111111111110000000000
00000111111111111111110000000000
00000001111111111111110000000000
00000001111111011111110000000000
00000000111100011111110000000000
00000000000000011111110000000000
00000000000000011111100000000000
00000000000000111111110000000000
00000000000000011111110000000000
00000000000000011111110000000000
00000000000000011111111000000000
00000000000000011111111000000000
00000000000000011111111000000000
00000000000000000111111110000000
00000000000000000111111100000000

準備數(shù)據(jù)：基于二值圖像構造向量

將 32*32的文本轉(zhuǎn)化為 1*1024的矩陣

def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect

def loadImages(dirName):
    from os import listdir
    hwLabels = []
    print(dirName)
    trainingFileList = listdir(dirName)  # load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]  # take off .txt
        classNumStr = int(fileStr.split('_')[0])
        if classNumStr == 9:
            hwLabels.append(-1)
        else:
            hwLabels.append(1)
        trainingMat[i, :] = img2vector('%s/%s' % (dirName, fileNameStr))
    return trainingMat, hwLabels

分析數(shù)據(jù)：對圖像向量進行目測

訓練算法：采用兩種不同的核函數(shù)，并對徑向基核函數(shù)采用不同的設置來運行SMO算法

def kernelTrans(X, A, kTup):  # calc the kernel or transform data to a higher dimensional space
    """
    核轉(zhuǎn)換函數(shù)
    Args:
        X     dataMatIn數(shù)據(jù)集
        A     dataMatIn數(shù)據(jù)集的第i行的數(shù)據(jù)
        kTup  核函數(shù)的信息

    Returns:

    """
    m, n = shape(X)
    K = mat(zeros((m, 1)))
    if kTup[0] == 'lin':
        # linear kernel:   m*n * n*1 = m*1
        K = X * A.T
    elif kTup[0] == 'rbf':
        for j in range(m):
            deltaRow = X[j, :] - A
            K[j] = deltaRow * deltaRow.T
        # 徑向基函數(shù)的高斯版本
        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

def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)):
    """
    完整SMO算法外循環(huán)，與smoSimple有些類似，但這里的循環(huán)退出條件更多一些
    Args:
        dataMatIn    數(shù)據(jù)集
        classLabels  類別標簽
        C   松弛變量(常量值)，允許有些數(shù)據(jù)點可以處于分隔面的錯誤一側。
            控制最大化間隔和保證大部分的函數(shù)間隔小于1.0這兩個目標的權重。
            可以通過調(diào)節(jié)該參數(shù)達到不同的結果。
        toler   容錯率
        maxIter 退出前最大的循環(huán)次數(shù)
        kTup    包含核函數(shù)信息的元組
    Returns:
        b       模型的常量值
        alphas  拉格朗日乘子
    """

    # 創(chuàng)建一個 optStruct 對象
    oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler, kTup)
    iter = 0
    entireSet = True
    alphaPairsChanged = 0

    # 循環(huán)遍歷：循環(huán)maxIter次 并且 （alphaPairsChanged存在可以改變 or 所有行遍歷一遍）
    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
        alphaPairsChanged = 0

        #  當entireSet=true or 非邊界alpha對沒有了；就開始尋找 alpha對，然后決定是否要進行else。
        if entireSet:
            # 在數(shù)據(jù)集上遍歷所有可能的alpha
            for i in range(oS.m):
                # 是否存在alpha對，存在就+1
                alphaPairsChanged += innerL(i, oS)
                # print("fullSet, iter: %d i:%d, pairs changed %d" % (iter, i, alphaPairsChanged))
            iter += 1

        # 對已存在 alpha對，選出非邊界的alpha值，進行優(yōu)化。
        else:
            # 遍歷所有的非邊界alpha值，也就是不在邊界0或C上的值。
            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

        # 如果找到alpha對，就優(yōu)化非邊界alpha值，否則，就重新進行尋找，如果尋找一遍 遍歷所有的行還是沒找到，就退出循環(huán)。
        if entireSet:
            entireSet = False  # toggle entire set loop
        elif (alphaPairsChanged == 0):
            entireSet = True
        print("iteration number: %d" % iter)
    return oS.b, oS.alphas

測試算法：便攜一個函數(shù)來測試不同的和函數(shù)并計算錯誤率

def testDigits(kTup=('rbf', 10)):

    # 1. 導入訓練數(shù)據(jù)
    dataArr, labelArr = loadImages('input/6.SVM/trainingDigits')
    b, alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup)
    datMat = mat(dataArr)
    labelMat = mat(labelArr).transpose()
    svInd = nonzero(alphas.A > 0)[0]
    sVs = datMat[svInd]
    labelSV = labelMat[svInd]
    # print("there are %d Support Vectors" % shape(sVs)[0])
    m, n = shape(datMat)
    errorCount = 0
    for i in range(m):
        kernelEval = kernelTrans(sVs, datMat[i, :], kTup)
        # 1*m * m*1 = 1*1 單個預測結果
        predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b
        if sign(predict) != sign(labelArr[i]): errorCount += 1
    print("the training error rate is: %f" % (float(errorCount) / m))

    # 2. 導入測試數(shù)據(jù)
    dataArr, labelArr = loadImages('input/6.SVM/testDigits')
    errorCount = 0
    datMat = mat(dataArr)
    labelMat = mat(labelArr).transpose()
    m, n = shape(datMat)
    for i in range(m):
        kernelEval = kernelTrans(sVs, datMat[i, :], kTup)
        # 1*m * m*1 = 1*1 單個預測結果
        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))

使用算法：一個圖像識別的完整應用還需要一些圖像處理的知識，這里并不打算深入介紹

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-complete.py

作者：片刻 geekidentity
GitHub地址: https://github.com/apachecn/MachineLearning
版權聲明：歡迎轉(zhuǎn)載學習 => 請標注信息來源于 ApacheCN

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【機器學習實戰(zhàn)】第6章支持向量機（Support Vector Machine / SVM）

【機器學習實戰(zhàn)】第6章支持向量機（Support Vector Machine / SVM）

第6章支持向量機

支持向量機概述

支持向量機場景

支持向量機原理

SVM 工作原理

尋找最大間隔

為什么尋找最大間隔

怎么尋找最大間隔

SMO 高效優(yōu)化算法

SVM 開發(fā)流程

SVM 算法特點

課本案例（無核函數(shù)）

項目概述

開發(fā)流程

核函數(shù)(kernel) 使用

項目案例: 手寫數(shù)字識別的優(yōu)化（有核函數(shù)）

項目概述

開發(fā)流程

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【機器學習實戰(zhàn)】第6章 支持向量機（Support Vector Machine / SVM）

第6章 支持向量機

支持向量機 概述

支持向量機 場景

支持向量機 原理

SVM 工作原理

尋找最大間隔

為什么尋找最大間隔

怎么尋找最大間隔

SMO 高效優(yōu)化算法

SVM 開發(fā)流程

SVM 算法特點

課本案例（無核函數(shù)）

項目概述

開發(fā)流程

核函數(shù)(kernel) 使用

項目案例: 手寫數(shù)字識別的優(yōu)化（有核函數(shù)）

項目概述

開發(fā)流程

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【機器學習實戰(zhàn)】第6章支持向量機（Support Vector Machine / SVM）

第6章支持向量機

支持向量機概述

支持向量機場景

支持向量機原理