當前位置：首頁 > 编程语言 > python >内容正文

python

机器学习算法与Python实践之（四）支持向量机（SVM）实现

發布時間：2025/3/21 python 14 豆豆

生活随笔收集整理的這篇文章主要介紹了机器学习算法与Python实践之（四）支持向量机（SVM）实现小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

機器學習算法與Python實踐之（四）支持向量機（SVM）實現

zouxy09@qq.com

http://blog.csdn.net/zouxy09

? ? ? ?機器學習算法與Python實踐這個系列主要是參考《機器學習實戰》這本書。因為自己想學習Python，然后也想對一些機器學習算法加深下了解，所以就想通過Python來實現幾個比較常用的機器學習算法。恰好遇見這本同樣定位的書籍，所以就參考這本書的過程來學習了。

? ? ? ?在這一節我們主要是對支持向量機進行系統的回顧，以及通過Python來實現。由于內容很多，所以這里分成三篇博文。第一篇講SVM初級，第二篇講進階，主要是把SVM整條知識鏈理直，第三篇介紹Python的實現。SVM有很多介紹的非常好的博文，具體可以參考本文列出的參考文獻和推薦閱讀資料。在本文中，定位在于把集大成于一身的SVM的整體知識鏈理直，所以不會涉及細節的推導。網上的解說的很好的推導和書籍很多，大家可以進一步參考。

一、引入

二、線性可分SVM與硬間隔最大化

三、Dual優化問題

? ? ? ?3.1、對偶問題

? ? ? ?3.2、SVM優化的對偶問題

四、松弛向量與軟間隔最大化

五、核函數

六、多類分類之SVM

? ? ? ?6.1、“一對多”的方法

? ? ? ?6.2、“一對一”的方法

七、KKT條件分析

八、SVM的實現之SMO算法

? ? ? ?8.1、坐標下降算法

? ? ? ?8.2、SMO算法原理

? ? ? ?8.3、SMO算法的Python實現

九、參考文獻與推薦閱讀

八、SVM的實現之SMO算法

? ? ? 終于到SVM的實現部分了。那么神奇和有效的東西還得回歸到實現才可以展示其強大的功力。SVM有效而且存在很高效的訓練算法，這也是工業界非常青睞SVM的原因。

? ? ? 前面講到，SVM的學習問題可以轉化為下面的對偶問題：

? ? ? ?需要滿足的KKT條件：

? ? ? ?也就是說找到一組α_i可以滿足上面的這些條件的就是該目標的一個最優解。所以我們的優化目標是找到一組最優的α_i*。一旦求出這些α_i*，就很容易計算出權重向量w*和b，并得到分隔超平面了。

? ? ? ?這是個凸二次規劃問題，它具有全局最優解，一般可以通過現有的工具來優化。但當訓練樣本非常多的時候，這些優化算法往往非常耗時低效，以致無法使用。從SVM提出到現在，也出現了很多優化訓練的方法。其中，非常出名的一個是1982年由Microsoft Research的John C. Platt在論文《Sequential Minimal Optimization: A Fast Algorithm for TrainingSupport Vector Machines》中提出的Sequential Minimal Optimization序列最小化優化算法，簡稱SMO算法。SMO算法的思想很簡單，它將大優化的問題分解成多個小優化的問題。這些小問題往往比較容易求解，并且對他們進行順序求解的結果與將他們作為整體來求解的結果完全一致。在結果完全一致的同時，SMO的求解時間短很多。在深入SMO算法之前，我們先來了解下坐標下降這個算法，SMO其實基于這種簡單的思想的。

8.1、坐標下降（上升）法

? ? ? 假設要求解下面的優化問題：

? ? ? 在這里，我們需要求解m個變量α_i，一般來說是通過梯度下降（這里是求最大值，所以應該叫上升）等算法每一次迭代對所有m個變量α_i也就是α向量進行一次性優化。通過誤差每次迭代調整α向量中每個元素的值。而坐標上升法（坐標上升與坐標下降可以看做是一對，坐標上升是用來求解max最優化問題，坐標下降用于求min最優化問題）的思想是每次迭代只調整一個變量α_i的值，其他變量的值在這次迭代中固定不變。

? ? ? ?最里面語句的意思是固定除α_i之外的所有α_j(i不等于j)，這時W可看作只是關于α_i的函數，那么直接對α_i求導優化即可。這里我們進行最大化求導的順序i是從1到m，可以通過更改優化順序來使W能夠更快地增加并收斂。如果W在內循環中能夠很快地達到最優，那么坐標上升法會是一個很高效的求極值方法。

? ? ? 用個二維的例子來說明下坐標下降法：我們需要尋找f(x,y)=x²+xy+y²的最小值處的(x*, y*)，也就是下圖的F*點的地方。

? ? ? ?假設我們初始的點是A（圖是函數投影到xoy平面的等高線圖，顏色越深值越小），我們需要達到F*的地方。那最快的方法就是圖中黃色線的路徑，一次性就到達了，其實這個是牛頓優化法，但如果是高維的話，這個方法就不太高效了（因為需要求解矩陣的逆，這個不在這里討論）。我們也可以按照紅色所指示的路徑來走。從A開始，先固定x，沿著y軸往讓f(x, y)值減小的方向走到B點，然后固定y，沿著x軸往讓f(x, y)值減小的方向走到C點，不斷循環，直到到達F*。反正每次只要我們都往讓f(x, y)值小的地方走就行了，這樣腳踏實地，一步步走，每一步都使f(x, y)慢慢變小，總有一天，皇天不負有心人的。到達F*也是時間問題。到這里你可能會說，這紅色線比黃色線貧富差距也太嚴重了吧。因為這里是二維的簡單的情況嘛。如果是高維的情況，而且目標函數很復雜的話，再加上樣本集很多，那么在梯度下降中，目標函數對所有α_i求梯度或者在牛頓法中對矩陣求逆，都是很耗時的。這時候，如果W只對單個α_i優化很快的時候，坐標下降法可能會更加高效。

8.2、SMO算法

? ? ? ?SMO算法的思想和坐標下降法的思想差不多。唯一不同的是，SMO是一次迭代優化兩個α而不是一個。為什么要優化兩個呢？

? ? ? ?我們回到這個優化問題。我們可以看到這個優化問題存在著一個約束，也就是

? ? ? ?假設我們首先固定除α₁以外的所有參數，然后在α₁上求極值。但需要注意的是，因為如果固定α₁以外的所有參數，由上面這個約束條件可以知道，α₁將不再是變量（可以由其他值推出），因為問題中規定了：

? ? ? 因此，我們需要一次選取兩個參數做優化，比如α_i和α_j，此時α_i可以由α_j和其他參數表示出來。這樣回代入W中，W就只是關于α_j的函數了，這時候就可以只對α_j進行優化了。在這里就是對α_j進行求導，令導數為0就可以解出這個時候最優的α_j了。然后也可以得到α_i。這就是一次的迭代過程，一次迭代只調整兩個拉格朗日乘子α_i和α_j。SMO之所以高效就是因為在固定其他參數后，對一個參數優化過程很高效（對一個參數的優化可以通過解析求解，而不是迭代。雖然對一個參數的一次最小優化不可能保證其結果就是所優化的拉格朗日乘子的最終結果，但會使目標函數向極小值邁進一步，這樣對所有的乘子做最小優化，直到所有滿足KKT條件時，目標函數達到最小）。

? ? ? ?總結下來是：

重復下面過程直到收斂{

（1）選擇兩個拉格朗日乘子α_i和α_j；

（2）固定其他拉格朗日乘子α_k(k不等于i和j)，只對α_i和α_j優化w(α);

（3）根據優化后的α_i和α_j，更新截距b的值；

}

? ? ? ? 那訓練里面這兩三步驟到底是怎么實現的，需要考慮什么呢？下面我們來具體分析下：

（1）選擇α_i和α_j：

? ? ? ? 我們現在是每次迭代都優化目標函數的兩個拉格朗日乘子α_i和α_j，然后其他的拉格朗日乘子保持固定。如果有N個訓練樣本，我們就有N個拉格朗日乘子需要優化，但每次我們只挑兩個進行優化，我們就有N(N-1)種選擇。那到底我們要選擇哪對α_i和α_j呢？選擇哪對才好呢？想想我們的目標是什么？我們希望把所有違法KKT條件的樣本都糾正回來，因為如果所有樣本都滿足KKT條件的話，我們的優化就完成了。那就很直觀了，哪個害群之馬最嚴重，我們得先對他進行思想教育，讓他盡早回歸正途。OK，那我們選擇的第一個變量α_i就選違法KKT條件最嚴重的那一個。那第二個變量α_j怎么選呢？

? ? ? ?我們是希望快點找到最優的N個拉格朗日乘子，使得代價函數最大，換句話說，要最快的找到代價函數最大值的地方對應的N個拉格朗日乘子。這樣我們的訓練時間才會短。就像你從廣州去北京，有飛機和綠皮車給你選，你選啥？（就算你不考慮速度，也得考慮下空姐的感受嘛，別辜負了她們渴望看到你的期盼，哈哈）。有點離題了，anyway，每次迭代中，哪對α_i和α_j可以讓我更快的達到代價函數值最大的地方，我們就選他們。或者說，走完這一步，選這對α_i和α_j代價函數值增加的值最多，比選擇其他所有α_i和α_j的結合中都多。這樣我們才可以更快的接近代價函數的最大值，也就是達到優化的目標了。再例如，下圖，我們要從A點走到B點，按藍色的路線走c2方向的時候，一跨一大步，按紅色的路線走c1方向的時候，只能是人類的一小步。所以，藍色路線走兩步就邁進了成功之門，而紅色的路線，人生曲折，好像成功遙遙無期一樣，故曰，選擇比努力更重要！

? ? ? ?真啰嗦！說了半天，其實就一句話：為什么每次迭代都要選擇最好的α_i和α_j，就是為了更快的收斂！那實踐中每次迭代到底要怎樣選α_i和α_j呢？這有個很好聽的名字叫啟發式選擇，主要思想是先選擇最有可能需要優化（也就是違反KKT條件最嚴重）的α_i，再針對這樣的α_i選擇最有可能取得較大修正步長的α_j。具體是以下兩個過程：

1）第一個變量α_i的選擇：

? ? ? ?SMO稱選擇第一個變量的過程為外層循環。外層訓練在訓練樣本中選取違法KKT條件最嚴重的樣本點。并將其對應的變量作為第一個變量。具體的，檢驗訓練樣本(x_i, y_i)是否滿足KKT條件，也就是：

? ? ? ?該檢驗是在ε范圍內進行的。在檢驗過程中，外層循環首先遍歷所有滿足條件0<α_j<C的樣本點，即在間隔邊界上的支持向量點，檢驗他們是否滿足KKT條件，然后選擇違反KKT條件最嚴重的α_i。如果這些樣本點都滿足KKT條件，那么遍歷整個訓練集，檢驗他們是否滿足KKT條件，然后選擇違反KKT條件最嚴重的α_i。

? ? ? ?優先選擇遍歷非邊界數據樣本，因為非邊界數據樣本更有可能需要調整，邊界數據樣本常常不能得到進一步調整而留在邊界上。由于大部分數據樣本都很明顯不可能是支持向量，因此對應的α乘子一旦取得零值就無需再調整。遍歷非邊界數據樣本并選出他們當中違反KKT 條件為止。當某一次遍歷發現沒有非邊界數據樣本得到調整時，遍歷所有數據樣本，以檢驗是否整個集合都滿足KKT條件。如果整個集合的檢驗中又有數據樣本被進一步進化，則有必要再遍歷非邊界數據樣本。這樣，不停地在遍歷所有數據樣本和遍歷非邊界數據樣本之間切換，直到整個樣本集合都滿足KKT條件為止。以上用KKT條件對數據樣本所做的檢驗都以達到一定精度ε就可以停止為條件。如果要求十分精確的輸出算法，則往往不能很快收斂。

? ? ? ?對整個數據集的遍歷掃描相當容易，而實現對非邊界α_i的掃描時，首先需要將所有非邊界樣本的α_i值（也就是滿足0<α_i<C）保存到新的一個列表中，然后再對其進行遍歷。同時，該步驟跳過那些已知的不會改變的α_i值。

2）第二個變量α_j的選擇：

（2）優化α_i和α_j：

? ? ? ?選擇這兩個拉格朗日乘子后，我們需要先計算這些參數的約束值。然后再求解這個約束最大化問題。

? ? ? ?首先，我們需要給α_j找到邊界L<=α_j<=H，以保證α_j滿足0<=α_j<=C的約束。這意味著α_j必須落入這個盒子中。由于只有兩個變量(α_i, α_j)，約束可以用二維空間中的圖形來表示，如下圖：

? ? ? ?不等式約束使得(α_i,α_j)在盒子[0, C]x[0, C]內，等式約束使得(α_i, α_j)在平行于盒子[0, C]x[0, C]的對角線的直線上。因此要求的是目標函數在一條平行于對角線的線段上的最優值。這使得兩個變量的最優化問題成為實質的單變量的最優化問題。由圖可以得到，α_j的上下界可以通過下面的方法得到：

? ? ? ?我們優化的時候，α_j必須要滿足上面這個約束。也就是說上面是α_j的可行域。然后我們開始尋找α_j，使得目標函數最大化。通過推導得到α_j的更新公式如下：

? ? ? ?這里E_k可以看做對第k個樣本，SVM的輸出與期待輸出，也就是樣本標簽的誤差。

? ? ? ?而η實際上是度量兩個樣本i和j的相似性的。在計算η的時候，我們需要使用核函數，那么就可以用核函數來取代上面的內積。

? ? ? ?得到新的α_j后，我們需要保證它處于邊界內。換句話說，如果這個優化后的值跑出了邊界L和H，我們就需要簡單的裁剪，將α_j收回這個范圍：

? ? ? ?最后，得到優化的α_j后，我們需要用它來計算α_i：

? ? ? ?到這里，α_i和α_j的優化就完成了。

（3）計算閾值b：

? ? ? ?優化α_i和α_j后，我們就可以更新閾值b，使得對兩個樣本i和j都滿足KKT條件。如果優化后α_i不在邊界上（也就是滿足0<α_i<C，這時候根據KKT條件，可以得到y_ig_i(x_i)=1，這樣我們才可以計算b），那下面的閾值b1是有效的，因為當輸入x_i時它迫使SVM輸出y_i。

? ? ? ?同樣，如果0<α_j<C，那么下面的b2也是有效的：

? ? ? 如果0<α_i<C和0<α_j<C都滿足，那么b1和b2都有效，而且他們是相等的。如果他們兩個都處于邊界上（也就是α_i=0或者α_i=C，同時α_j=0或者α_j=C），那么在b1和b2之間的閾值都滿足KKT條件，一般我們取他們的平均值b=(b1+b2)/2。所以，總的來說對b的更新如下：

? ? ? ?每做完一次最小優化，必須更新每個數據樣本的誤差，以便用修正過的分類面對其他數據樣本再做檢驗，在選擇第二個配對優化數據樣本時用來估計步長。

（4）凸優化問題終止條件：

? ? ? ?SMO算法的基本思路是：如果說有變量的解都滿足此最優化問題的KKT條件，那么這個最優化問題的解就得到了。因為KKT條件是該最優化問題的充分必要條件（證明請參考文獻）。所以我們可以監視原問題的KKT條件，所以所有的樣本都滿足KKT條件，那么就表示迭代結束了。但是由于KKT條件本身是比較苛刻的，所以也需要設定一個容忍值，即所有樣本在容忍值范圍內滿足KKT條件則認為訓練可以結束；當然了，對于對偶問題的凸優化還有其他終止條件，可以參考文獻。

8.3、SMO算法的Python實現

8.3.1、Python的準備工作

? ? ? 我使用的Python是2.7.5版本的。附加的庫有Numpy和Matplotlib。而Matplotlib又依賴dateutil和pyparsing兩個庫，所以我們需要安裝以上三個庫。前面兩個庫還好安裝，直接在官網下對應版本就行。但我找后兩個庫的時候，就沒那么容易了。后來發現，其實對Python的庫的下載和安裝可以借助pip工具的。這個是安裝和管理Python包的工具。感覺它有點像ubuntu的apt-get，需要安裝什么庫，直接下載和安裝一條龍服務。

? ? ? ?首先，我們需要到pip的官網：https://pypi.python.org/pypi/pip下載對應我們python版本的pip，例如我的是pip-1.4.1.tar.gz。但安裝pip需要另一個工具，也就是setuptools，我們到https://pypi.python.org/pypi/setuptools/#windows下載ez_setup.py這個文件回來。然后在CMD命令行中執行：（注意他們的路徑）

#python ez_setup.py

這時候，就會自動下載.egg等等文件然后安裝完成。

? ? ? 然后我們解壓pip-1.4.1.tar.gz。進入到該目錄中，執行：

#python setup.py install

這時候就會自動安裝pip到你python目錄下的Scripts文件夾中。我的是C:\Python27\Scripts。

? ? ? ?在里面我們可以看到pip.exe，然后我們進入到該文件夾中：

#cd C:\Python27\Scripts

#pip install dateutil

#pip install pyparsing

這樣就可以把這些額外的庫給下載回來了。非常高端大氣上檔次！

8.3.2、SMO算法的Python實現

? ? ? ?在代碼中已經有了比較詳細的注釋了。不知道有沒有錯誤的地方，如果有，還望大家指正（每次的運行結果都有可能不同，另外，感覺有些結果似乎不太正確，但我還沒發現哪里出錯了，如果大家找到有錯誤的地方，還望大家指點下，衷心感謝）。里面我寫了個可視化結果的函數，但只能在二維的數據上面使用。直接貼代碼：

SVM.py

################################################# # SVM: support vector machine # Author : zouxy # Date : 2013-12-12 # HomePage : http://blog.csdn.net/zouxy09 # Email : zouxy09@qq.com #################################################from numpy import * import time import matplotlib.pyplot as plt # calulate kernel value def calcKernelValue(matrix_x, sample_x, kernelOption):kernelType = kernelOption[0]numSamples = matrix_x.shape[0]kernelValue = mat(zeros((numSamples, 1)))if kernelType == 'linear':kernelValue = matrix_x * sample_x.Telif kernelType == 'rbf':sigma = kernelOption[1]if sigma == 0:sigma = 1.0for i in xrange(numSamples):diff = matrix_x[i, :] - sample_xkernelValue[i] = exp(diff * diff.T / (-2.0 * sigma**2))else:raise NameError('Not support kernel type! You can use linear or rbf!')return kernelValue# calculate kernel matrix given train set and kernel type def calcKernelMatrix(train_x, kernelOption):numSamples = train_x.shape[0]kernelMatrix = mat(zeros((numSamples, numSamples)))for i in xrange(numSamples):kernelMatrix[:, i] = calcKernelValue(train_x, train_x[i, :], kernelOption)return kernelMatrix# define a struct just for storing variables and data class SVMStruct:def __init__(self, dataSet, labels, C, toler, kernelOption):self.train_x = dataSet # each row stands for a sampleself.train_y = labels # corresponding labelself.C = C # slack variableself.toler = toler # termination condition for iterationself.numSamples = dataSet.shape[0] # number of samplesself.alphas = mat(zeros((self.numSamples, 1))) # Lagrange factors for all samplesself.b = 0self.errorCache = mat(zeros((self.numSamples, 2)))self.kernelOpt = kernelOptionself.kernelMat = calcKernelMatrix(self.train_x, self.kernelOpt)# calculate the error for alpha k def calcError(svm, alpha_k):output_k = float(multiply(svm.alphas, svm.train_y).T * svm.kernelMat[:, alpha_k] + svm.b)error_k = output_k - float(svm.train_y[alpha_k])return error_k# update the error cache for alpha k after optimize alpha k def updateError(svm, alpha_k):error = calcError(svm, alpha_k)svm.errorCache[alpha_k] = [1, error]# select alpha j which has the biggest step def selectAlpha_j(svm, alpha_i, error_i):svm.errorCache[alpha_i] = [1, error_i] # mark as valid(has been optimized)candidateAlphaList = nonzero(svm.errorCache[:, 0].A)[0] # mat.A return arraymaxStep = 0; alpha_j = 0; error_j = 0# find the alpha with max iterative stepif len(candidateAlphaList) > 1:for alpha_k in candidateAlphaList:if alpha_k == alpha_i: continueerror_k = calcError(svm, alpha_k)if abs(error_k - error_i) > maxStep:maxStep = abs(error_k - error_i)alpha_j = alpha_kerror_j = error_k# if came in this loop first time, we select alpha j randomlyelse: alpha_j = alpha_iwhile alpha_j == alpha_i:alpha_j = int(random.uniform(0, svm.numSamples))error_j = calcError(svm, alpha_j)return alpha_j, error_j# the inner loop for optimizing alpha i and alpha j def innerLoop(svm, alpha_i):error_i = calcError(svm, alpha_i)### check and pick up the alpha who violates the KKT condition## satisfy KKT condition# 1) yi*f(i) >= 1 and alpha == 0 (outside the boundary)# 2) yi*f(i) == 1 and 0<alpha< C (on the boundary)# 3) yi*f(i) <= 1 and alpha == C (between the boundary)## violate KKT condition# because y[i]*E_i = y[i]*f(i) - y[i]^2 = y[i]*f(i) - 1, so# 1) if y[i]*E_i < 0, so yi*f(i) < 1, if alpha < C, violate!(alpha = C will be correct) # 2) if y[i]*E_i > 0, so yi*f(i) > 1, if alpha > 0, violate!(alpha = 0 will be correct)# 3) if y[i]*E_i = 0, so yi*f(i) = 1, it is on the boundary, needless optimizedif (svm.train_y[alpha_i] * error_i < -svm.toler) and (svm.alphas[alpha_i] < svm.C) or\(svm.train_y[alpha_i] * error_i > svm.toler) and (svm.alphas[alpha_i] > 0):# step 1: select alpha jalpha_j, error_j = selectAlpha_j(svm, alpha_i, error_i)alpha_i_old = svm.alphas[alpha_i].copy()alpha_j_old = svm.alphas[alpha_j].copy()# step 2: calculate the boundary L and H for alpha jif svm.train_y[alpha_i] != svm.train_y[alpha_j]:L = max(0, svm.alphas[alpha_j] - svm.alphas[alpha_i])H = min(svm.C, svm.C + svm.alphas[alpha_j] - svm.alphas[alpha_i])else:L = max(0, svm.alphas[alpha_j] + svm.alphas[alpha_i] - svm.C)H = min(svm.C, svm.alphas[alpha_j] + svm.alphas[alpha_i])if L == H:return 0# step 3: calculate eta (the similarity of sample i and j)eta = 2.0 * svm.kernelMat[alpha_i, alpha_j] - svm.kernelMat[alpha_i, alpha_i] \- svm.kernelMat[alpha_j, alpha_j]if eta >= 0:return 0# step 4: update alpha jsvm.alphas[alpha_j] -= svm.train_y[alpha_j] * (error_i - error_j) / eta# step 5: clip alpha jif svm.alphas[alpha_j] > H:svm.alphas[alpha_j] = Hif svm.alphas[alpha_j] < L:svm.alphas[alpha_j] = L# step 6: if alpha j not moving enough, just return if abs(alpha_j_old - svm.alphas[alpha_j]) < 0.00001:updateError(svm, alpha_j)return 0# step 7: update alpha i after optimizing aipha jsvm.alphas[alpha_i] += svm.train_y[alpha_i] * svm.train_y[alpha_j] \* (alpha_j_old - svm.alphas[alpha_j])# step 8: update threshold bb1 = svm.b - error_i - svm.train_y[alpha_i] * (svm.alphas[alpha_i] - alpha_i_old) \* svm.kernelMat[alpha_i, alpha_i] \- svm.train_y[alpha_j] * (svm.alphas[alpha_j] - alpha_j_old) \* svm.kernelMat[alpha_i, alpha_j]b2 = svm.b - error_j - svm.train_y[alpha_i] * (svm.alphas[alpha_i] - alpha_i_old) \* svm.kernelMat[alpha_i, alpha_j] \- svm.train_y[alpha_j] * (svm.alphas[alpha_j] - alpha_j_old) \* svm.kernelMat[alpha_j, alpha_j]if (0 < svm.alphas[alpha_i]) and (svm.alphas[alpha_i] < svm.C):svm.b = b1elif (0 < svm.alphas[alpha_j]) and (svm.alphas[alpha_j] < svm.C):svm.b = b2else:svm.b = (b1 + b2) / 2.0# step 9: update error cache for alpha i, j after optimize alpha i, j and bupdateError(svm, alpha_j)updateError(svm, alpha_i)return 1else:return 0# the main training procedure def trainSVM(train_x, train_y, C, toler, maxIter, kernelOption = ('rbf', 1.0)):# calculate training timestartTime = time.time()# init data struct for svmsvm = SVMStruct(mat(train_x), mat(train_y), C, toler, kernelOption)# start trainingentireSet = TruealphaPairsChanged = 0iterCount = 0# Iteration termination condition:# Condition 1: reach max iteration# Condition 2: no alpha changed after going through all samples,# in other words, all alpha (samples) fit KKT conditionwhile (iterCount < maxIter) and ((alphaPairsChanged > 0) or entireSet):alphaPairsChanged = 0# update alphas over all training examplesif entireSet:for i in xrange(svm.numSamples):alphaPairsChanged += innerLoop(svm, i)print '---iter:%d entire set, alpha pairs changed:%d' % (iterCount, alphaPairsChanged)iterCount += 1# update alphas over examples where alpha is not 0 & not C (not on boundary)else:nonBoundAlphasList = nonzero((svm.alphas.A > 0) * (svm.alphas.A < svm.C))[0]for i in nonBoundAlphasList:alphaPairsChanged += innerLoop(svm, i)print '---iter:%d non boundary, alpha pairs changed:%d' % (iterCount, alphaPairsChanged)iterCount += 1# alternate loop over all examples and non-boundary examplesif entireSet:entireSet = Falseelif alphaPairsChanged == 0:entireSet = Trueprint 'Congratulations, training complete! Took %fs!' % (time.time() - startTime)return svm# testing your trained svm model given test set def testSVM(svm, test_x, test_y):test_x = mat(test_x)test_y = mat(test_y)numTestSamples = test_x.shape[0]supportVectorsIndex = nonzero(svm.alphas.A > 0)[0]supportVectors = svm.train_x[supportVectorsIndex]supportVectorLabels = svm.train_y[supportVectorsIndex]supportVectorAlphas = svm.alphas[supportVectorsIndex]matchCount = 0for i in xrange(numTestSamples):kernelValue = calcKernelValue(supportVectors, test_x[i, :], svm.kernelOpt)predict = kernelValue.T * multiply(supportVectorLabels, supportVectorAlphas) + svm.bif sign(predict) == sign(test_y[i]):matchCount += 1accuracy = float(matchCount) / numTestSamplesreturn accuracy# show your trained svm model only available with 2-D data def showSVM(svm):if svm.train_x.shape[1] != 2:print "Sorry! I can not draw because the dimension of your data is not 2!"return 1# draw all samplesfor i in xrange(svm.numSamples):if svm.train_y[i] == -1:plt.plot(svm.train_x[i, 0], svm.train_x[i, 1], 'or')elif svm.train_y[i] == 1:plt.plot(svm.train_x[i, 0], svm.train_x[i, 1], 'ob')# mark support vectorssupportVectorsIndex = nonzero(svm.alphas.A > 0)[0]for i in supportVectorsIndex:plt.plot(svm.train_x[i, 0], svm.train_x[i, 1], 'oy')# draw the classify linew = zeros((2, 1))for i in supportVectorsIndex:w += multiply(svm.alphas[i] * svm.train_y[i], svm.train_x[i, :].T) min_x = min(svm.train_x[:, 0])[0, 0]max_x = max(svm.train_x[:, 0])[0, 0]y_min_x = float(-svm.b - w[0] * min_x) / w[1]y_max_x = float(-svm.b - w[0] * max_x) / w[1]plt.plot([min_x, max_x], [y_min_x, y_max_x], '-g')plt.show()

? ? ? ?測試的數據來自這里。有100個樣本，每個樣本兩維，最后是對應的標簽，例如：

3.542485 1.977398 ???????? -1

3.018896 2.556416 ???????? -1

7.551510 -1.580030???????? 1

2.114999 -0.004466???????? -1

……

? ? ? ?測試代碼中首先加載這個數據庫，然后用前面80個樣本來訓練，再用剩下的20個樣本的測試，并顯示訓練后的模型和分類結果。測試代碼如下：

test_SVM.py

運行結果如下：

step 1: load data... step 2: training... ---iter:0 entire set, alpha pairs changed:8 ---iter:1 non boundary, alpha pairs changed:7 ---iter:2 non boundary, alpha pairs changed:1 ---iter:3 non boundary, alpha pairs changed:0 ---iter:4 entire set, alpha pairs changed:0 Congratulations, training complete! Took 0.058000s! step 3: testing... step 4: show the result... The classify accuracy is: 100.000%

訓練好的模型圖：

九、參考文獻與推薦閱讀

[1] JerryLead的博客，作者根據斯坦福的講義給出了流暢和通俗的推導：SVM系列。

[2]嘉士伯的SVM入門系列，講得很好。

[3] pluskid的支持向量機系列，非常好。其中關于dual問題推導非常贊。

[4] Leo Zhang的SVM學習系列，博客中還包含了很多其他的機器學習算法。

[5] v_july_v的支持向量機通俗導論（理解SVM的三層境界）。結構之法算法之道blog。

[6] 李航的《統計學習方法》，清華大學出版社

[7] SVM學習——Sequential Minimal Optimization

[8] SVM算法實現（一）

[9] Sequential Minimal Optimization: A FastAlgorithm for Training Support Vector Machines

[10] SVM --從“原理”到實現

[11] 支持向量機入門系列

[12]SVM的各個版本及其多種語言實現代碼合集

[13] Karush-Kuhn-Tucker(KKT) conditions

[14] 深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT條件

總結

以上是生活随笔為你收集整理的机器学习算法与Python实践之（四）支持向量机（SVM）实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：机器学习算法与Python实践之（二）支
下一篇： k-d tree算法