第6章支持向量機(jī)

支持向量機(jī)_首頁(yè)

支持向量機(jī) 概述

支持向量機(jī)(Support Vector Machines, SVM)：是一種機(jī)器學(xué)習(xí)算法。

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

支持向量機(jī) 場(chǎng)景

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

線性可分

支持向量機(jī) 原理

SVM 工作原理

原理圖

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

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

數(shù)據(jù)可以通過(guò)畫一條直線就可以將它們完全分開，這組數(shù)據(jù)叫線性可分(linearly separable)數(shù)據(jù)，而這條分隔直線稱為分隔超平面(separating hyperplane)。
如果數(shù)據(jù)集上升到1024維呢？那么需要1023維來(lái)分隔數(shù)據(jù)集，也就說(shuō)需要N-1維的對(duì)象來(lái)分隔，這個(gè)對(duì)象叫做超平面(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. 直覺(jué)上是安全的
2. 如果我們?cè)谶吔绲奈恢冒l(fā)生了一個(gè)小錯(cuò)誤（它在垂直方向上被顛倒），這給我們最小的錯(cuò)誤分類機(jī)會(huì)。
3. CV（Computer Vision 計(jì)算機(jī)視覺(jué) - 這縮寫看著可怕?）很容易，因?yàn)樵撃Ｐ蛯?duì)任何非支持向量數(shù)據(jù)點(diǎn)的去除是免疫的。
4. 有一些理論，這是一件好事。
5. 通常它的工作非常好。

怎么尋找最大間隔

點(diǎn)到超平面的距離

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

點(diǎn)到直線的幾何距離

拉格朗日乘子法

類別標(biāo)簽用-1、1，是為了后期方便 \(lable(w^Tx+b)\) 的標(biāo)識(shí)和距離計(jì)算；如果 \(lable(w^Tx+b)>0\) 表示預(yù)測(cè)正確，否則預(yù)測(cè)錯(cuò)誤。
現(xiàn)在目標(biāo)很明確，就是要找到w和b，因此我們必須要找到最小間隔的數(shù)據(jù)點(diǎn)，也就是前面所說(shuō)的支持向量。
- 也就說(shuō)，讓最小的距離取最大.(最小的距離：就是最小間隔的數(shù)據(jù)點(diǎn)；最大：就是最大間距，為了找出最優(yōu)超平面--最終就是支持向量)
- 目標(biāo)函數(shù)：\(arg: max_{關(guān)于w, b} \left( min[lable(w^Tx+b)]\frac{1}{||w||} \right) \)
  1. 如果 \(lable*(w^Tx+b)>0\) 表示預(yù)測(cè)正確，也稱函數(shù)間隔，\(||w||\) 可以理解為歸一化，也稱幾何間隔。
  2. 令 \(lable(w^Tx+b)>=1\)，因?yàn)?～1之間，得到的點(diǎn)是存在誤判的可能性，所以要保障 \(min[lable(w^Tx+b)]=1\)，才能更好降低噪音數(shù)據(jù)影響。
  3. 所以本質(zhì)上是求 \(arg: max_{關(guān)于w, b} \frac{1}{||w||} \)；也就說(shuō)，我們約束(前提)條件是: \(lable*(w^Tx+b)=1\)
新的目標(biāo)函數(shù)求解： \(arg: max_{關(guān)于w, b} \frac{1}{||w||} \)
- => 就是求: \(arg: min_{關(guān)于w, b} ||w|| \) (求矩陣會(huì)比較麻煩，如果x只是 \(\frac{1}{2}*x^2\) 的偏導(dǎo)數(shù)，那么。。同樣是求最小值)
- => 就是求: \(arg: min_{關(guān)于w, b} (\frac{1}{2}*||w||^2)\) (二次函數(shù)求導(dǎo)，求極值，平方也方便計(jì)算)
- 本質(zhì)上就是求線性不等式的二次優(yōu)化問(wèn)題(求分隔超平面，等價(jià)于求解相應(yīng)的凸二次規(guī)劃問(wèn)題)
通過(guò)拉格朗日乘子法，求二次優(yōu)化問(wèn)題
- 假設(shè)需要求極值的目標(biāo)函數(shù) (objective function) 為 f(x,y)，限制條件為 φ(x,y)=M # M=1
- 設(shè)g(x,y)=M-φ(x,y) # 臨時(shí)φ(x,y)表示下文中 \(label*(w^Tx+b)\)
- 定義一個(gè)新函數(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)]\)
- 因?yàn)椋篭(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\)
- 相當(dāng)于求解： \(max_{關(guān)于\alpha} L(w,b,\alpha) = \frac{1}{2} *||w||^2\)
- 如果求： \(min_{關(guān)于w, b} \frac{1}{2} *||w||^2\) , 也就是要求： \(min_{關(guān)于w, b} \left( max_{關(guān)于\alpha} L(w,b,\alpha)\right)\)
現(xiàn)在轉(zhuǎn)化到對(duì)偶問(wèn)題的求解
- \(min_{關(guān)于w, b} \left(max_{關(guān)于\alpha} L(w,b,\alpha) \right) \) >= \(max_{關(guān)于\alpha} \left(min_{關(guān)于w, b}\ L(w,b,\alpha) \right) \)
- 現(xiàn)在分2步
- 先求： \(min_{關(guān)于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)關(guān)于[w, b]的偏導(dǎo)數(shù), 得到w和b的值，并化簡(jiǎn)為：L和a的方程。
- 參考：如果公式推導(dǎo)還是不懂，也可以參考《統(tǒng)計(jì)學(xué)習(xí)方法》李航-P103<學(xué)習(xí)的對(duì)偶算法>
  
  計(jì)算拉格朗日函數(shù)的對(duì)偶函數(shù)
終于得到課本上的公式： \(max_{關(guān)于\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ù)都不那么干凈, 通過(guò)引入松弛變量來(lái)允許數(shù)據(jù)點(diǎn)可以處于分隔面錯(cuò)誤的一側(cè)。
約束條件： \(C>=a>=0\) 并且 \(\sum_{i=1}^{m} a_i·label_i=0\)
這里常量C用于控制“最大化間隔”和“保證大部分點(diǎn)的函數(shù)間隔小于1.0” 這兩個(gè)目標(biāo)的權(quán)重。
常量C是一個(gè)常數(shù)，我們通過(guò)調(diào)節(jié)該參數(shù)得到不同的結(jié)果。一旦求出了所有的alpha，那么分隔超平面就可以通過(guò)這些alpha來(lái)表示。
這一結(jié)論十分直接，SVM中的主要工作就是要求解 alpha.

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

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

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

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

SMO 偽代碼大致如下：

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

SVM 開發(fā)流程

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

SVM 算法特點(diǎn)

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

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

項(xiàng)目概述

對(duì)小規(guī)模數(shù)據(jù)點(diǎn)進(jìn)行分類

開發(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

準(zhǔn)備數(shù)據(jù)

def loadDataSet(fileName):
    """
    對(duì)文件進(jìn)行逐行解析，從而得到第行的類標(biāo)簽和整個(gè)特征矩陣
    Args:
        fileName 文件名
    Returns:
        dataMat  特征矩陣
        labelMat 類標(biāo)簽
    """
    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ù): 無(wú)

訓(xùn)練算法

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

    Args:
        dataMatIn    特征集合
        classLabels  類別標(biāo)簽
        C   松弛變量(常量值)，允許有些數(shù)據(jù)點(diǎn)可以處于分隔面的錯(cuò)誤一側(cè)。
            控制最大化間隔和保證大部分的函數(shù)間隔小于1.0這兩個(gè)目標(biāo)的權(quán)重。
            可以通過(guò)調(diào)節(jié)該參數(shù)達(dá)到不同的結(jié)果。
        toler   容錯(cuò)率（是指在某個(gè)體系中能減小一些因素或選擇對(duì)某個(gè)系統(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有點(diǎn)類似權(quán)重值。)
    b = 0
    alphas = mat(zeros((m, 1)))

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

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

            # 約束條件 (KKT條件是解決最優(yōu)化問(wèn)題的時(shí)用到的一種方法。我們這里提到的最優(yōu)化問(wèn)題通常是指對(duì)于給定的某一函數(shù)，求其在指定作用域上的全局最小值)
            # 0<=alphas[i]<=C，但由于0和C是邊界值，我們無(wú)法進(jìn)行優(yōu)化，因?yàn)樾枰黾右粋€(gè)alphas和降低一個(gè)alphas。
            # 表示發(fā)生錯(cuò)誤的概率：labelMat[i]*Ei 如果超出了 toler， 才需要優(yōu)化。至于正負(fù)號(hào)，我們考慮絕對(duì)值就對(duì)了。
            '''
            # 檢驗(yàn)訓(xùn)練樣本(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)化的條件，我們就隨機(jī)選取非i的一個(gè)點(diǎn)，進(jìn)行優(yōu)化比較
                j = selectJrand(i, m)
                # 預(yù)測(cè)j的結(jié)果
                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語(yǔ)句
                # labelMat[i] != labelMat[j] 表示異側(cè)，就相減，否則是同側(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])
                # 如果相同，就沒(méi)發(fā)優(yōu)化了
                if L == H:
                    print("L==H")
                    continue

                # eta是alphas[j]的最優(yōu)修改量，如果eta==0，需要退出for循環(huán)的當(dāng)前迭代過(guò)程
                # 參考《統(tǒng)計(jì)學(xué)習(xí)方法》李航-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

                # 計(jì)算出一個(gè)新的alphas[j]值
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                # 并使用輔助函數(shù)，以及L和H對(duì)其進(jìn)行調(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]同樣進(jìn)行改變，雖然改變的大小一樣，但是改變的方向正好相反
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                # 在對(duì)alpha[i], alpha[j] 進(jìn)行優(yōu)化之后，給這兩個(gè)alpha值設(shè)置一個(gè)常數(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遍？ 因?yàn)槭?減去Σ[1~n]，正好2個(gè)變量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設(shè)為0后繼續(xù)運(yùn)行程序
        # 知道更新完畢后，iter次循環(huán)無(wú)變化，才推出循環(huán)。
        if (alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
        print("iteration number: %d" % iter)
    return b, alphas

完整代碼地址：SVM簡(jiǎn)化版，應(yīng)用簡(jiǎn)化版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)化點(diǎn)：選擇alpha的方式不同: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-complete_Non-Kernel.py

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

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

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

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

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

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

項(xiàng)目概述

你的老板要求：你寫的那個(gè)手寫識(shí)別程序非常好，但是它占用內(nèi)存太大。顧客無(wú)法通過(guò)無(wú)線的方式下載我們的應(yīng)用。
所以：我們可以考慮使用支持向量機(jī)，保留支持向量就行（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

準(zhǔn)備數(shù)據(jù)：基于二值圖像構(gòu)造向量

將 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ù)：對(duì)圖像向量進(jìn)行目測(cè)

訓(xùn)練算法：采用兩種不同的核函數(shù)，并對(duì)徑向基核函數(shù)采用不同的設(shè)置來(lái)運(yùn)行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  類別標(biāo)簽
        C   松弛變量(常量值)，允許有些數(shù)據(jù)點(diǎn)可以處于分隔面的錯(cuò)誤一側(cè)。
            控制最大化間隔和保證大部分的函數(shù)間隔小于1.0這兩個(gè)目標(biāo)的權(quán)重。
            可以通過(guò)調(diào)節(jié)該參數(shù)達(dá)到不同的結(jié)果。
        toler   容錯(cuò)率
        maxIter 退出前最大的循環(huán)次數(shù)
        kTup    包含核函數(shù)信息的元組
    Returns:
        b       模型的常量值
        alphas  拉格朗日乘子
    """

    # 創(chuàng)建一個(gè) optStruct 對(duì)象
    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

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

        # 對(duì)已存在 alpha對(duì)，選出非邊界的alpha值，進(jìn)行優(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對(duì)，就優(yōu)化非邊界alpha值，否則，就重新進(jìn)行尋找，如果尋找一遍 遍歷所有的行還是沒(méi)找到，就退出循環(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

測(cè)試算法：便攜一個(gè)函數(shù)來(lái)測(cè)試不同的和函數(shù)并計(jì)算錯(cuò)誤率

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

    # 1. 導(dǎo)入訓(xùn)練數(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 單個(gè)預(yù)測(cè)結(jié)果
        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. 導(dǎo)入測(cè)試數(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 單個(gè)預(yù)測(cè)結(jié)果
        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))

使用算法：一個(gè)圖像識(shí)別的完整應(yīng)用還需要一些圖像處理的知識(shí)，這里并不打算深入介紹

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

作者：片刻 geekidentity
GitHub地址: https://github.com/apachecn/MachineLearning
版權(quán)聲明：歡迎轉(zhuǎn)載學(xué)習(xí) => 請(qǐng)標(biāo)注信息來(lái)源于 ApacheCN

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

【機(jī)器學(xué)習(xí)實(shí)戰(zhàn)】第6章支持向量機(jī)（Support Vector Machine / SVM）

【機(jī)器學(xué)習(xí)實(shí)戰(zhàn)】第6章支持向量機(jī)（Support Vector Machine / SVM）

第6章支持向量機(jī)

支持向量機(jī) 概述

支持向量機(jī) 場(chǎng)景

支持向量機(jī) 原理

SVM 工作原理

尋找最大間隔

為什么尋找最大間隔

怎么尋找最大間隔

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

SVM 開發(fā)流程

SVM 算法特點(diǎn)

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

項(xiàng)目概述

開發(fā)流程

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

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

項(xiàng)目概述

開發(fā)流程

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

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

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

【機(jī)器學(xué)習(xí)實(shí)戰(zhàn)】第6章 支持向量機(jī)（Support Vector Machine / SVM）

第6章 支持向量機(jī)

支持向量機(jī) 概述

支持向量機(jī) 場(chǎng)景

支持向量機(jī) 原理

SVM 工作原理

尋找最大間隔

為什么尋找最大間隔

怎么尋找最大間隔

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

SVM 開發(fā)流程

SVM 算法特點(diǎn)

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

項(xiàng)目概述

開發(fā)流程

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

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

項(xiàng)目概述

開發(fā)流程

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

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

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

【機(jī)器學(xué)習(xí)實(shí)戰(zhàn)】第6章支持向量機(jī)（Support Vector Machine / SVM）

第6章支持向量機(jī)