支持向量機（SVM）

簡介

支持向量機（Support Vector Machine，SVM），是常見的一種判別方法。在機器學習領域，是一個監督學習模型，通常用來進行模式識別、分類及回歸分析。與其他算法相比，支持向量機在學習復雜的非線性方程時提供了一種更為清晰、更加強大的方式。
支持向量機是20世紀90年代中期發展起來的基于統計學習理論的一種機器學習方法，通過尋求結構化風險最小來提高學習機泛化能力，實現經驗風險和置信范圍的最小化，從而達到在統計樣本量較少的情況下，也能獲得良好統計規律的目的。
通俗來講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機的學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。

原理

幾個概念

線性可分

如圖，數據之間分隔得足夠開，很容易在圖中畫出一條直線將這一組數據分開，這組數據就被稱為線性可分數據。

分隔超平面
上述將數據集分隔開來的直線稱為分隔超平面，由于上面給出的數據點都在二維平面上，所以此時的分隔超平面是一條直線。如果給出的數據集點是三維的，那么用來分隔數據的就是一個平面。因此，更高維的情況可以以此類推，如果數據是100維的，那么就需要一個99維的對象來對數據進行分隔，這些統稱為超平面。
間隔
如圖片所示，這條分隔線的好壞如何呢？我們希望找到離分隔超平面最近的點，確保它們離分割面的距離盡可能遠。在這里點到分隔面的距離稱為間隔。間隔盡可能大是因為如果犯錯或在有限數據上訓練分類器，我們希望分類器盡可能健壯。
支持向量
離分隔超平面最近的那些點是支持向量。

求解

接下來就是要求解最大支持向量到分隔面的距離，需要找到此類問題的求解方法。如圖，分隔超平面可以寫成$w^{T}x+b$。要計算距離，值為$\frac{|w^{T}A+b|}{||w||}$。這里的向量w和常數b一起描述了所給數據的超平面。
對$w^{T}x+b$使用單位階躍函數得到$f(w^{T}x+b)$,其中當$u<0$時，$f(u)$輸出-1，反之則輸出+1。這里使用-1和+1是為了教學上的方便處理，可以通過一個統一公式來表示間隔或數據點到分隔超平面的距離。間隔通過$label\times \frac{|w^{T}x+b|}{||w||}$來計算。如果數據處在正方向（+1）類里面且離分隔超平面很遠的位置時，$w^{T}x+b$是一個很大的正數。同時$label\times \frac{|w^{T}x+b|}{||w||}$也會是一個很大的正數。如果數據點處在負方向（-1）類且離分隔超平面很遠的位置時，由于此時類別標簽為-1，$label\times \frac{|w^{T}x+b|}{||w||}$仍然是一個很大的正數。
為了找到具有最小間隔的數據點，就要找到分類器中定義的$w$和$b$，最小間隔的數據點也就是支持向量。一旦找到支持向量，就需要對該間隔最大化，可以寫作$$\underset{w,b}{\max }\left(\underset{n}{\min }(label\times \frac{|w^{T}x+b|}{||w||})\right)$$
但是直接求解上述問題是非常困難的，所以這里引入拉格朗日乘子法，可以把表達式寫成下面的式子：
$$\max \_\alpha \left[\sum \_{i=1}^m\alpha \frac{1}{2}\sum \_{i,j=1}^{m}labe{l}^{(i)}\times \alpha \_i\times \alpha \_j(x^{(i)},x^{(j)})\right]$$
其中$\times$表示，兩個向量的內積。約束條件為$$C\ge \alpha \ge 0$$ $$\sum _{i?1}^m\alpha \_i\times labe{l}^{(i)}=0$$
這里的常數C用于控制最大化間隔和保證大部分點的函數間隔小于1.0這兩個目標的權重。因為所有數據都可能有干擾數據，所以通過引入所謂的松弛變量，允許有些數據點可以處于分隔面錯誤的一側。
根據上式可知，只要求出所有的 $\alpha$，那么分隔面就可以通過$\alpha$來表達，SVM的主要工作就是求$\alpha$。這樣一步步解出分隔面，那么分類問題游刃而解。

算法優勢

• 泛化錯誤率低，具有良好的學習能力。
• 幾乎所有分類問題都可以使用SVM解決。
• 節省內存開銷。

實戰

實現手寫識別系統

為了簡單起見，這里的手寫識別只針對0到9的數字，為了方便，圖像轉為了文本。目錄trainingDigits中含有2000個例子，用于訓練，目錄testDigits含有900個例子，用于測試。

雖然手寫識別可以用KNN實現而且效果不錯，但是KNN畢竟太占內存了，而且要保證性能不變的同時使用較少的內存。而對于SVM，只需要保留很少的支持向量就可以實現目標效果。

• 流程
  • 準備數據
  • 分析數據
  • 使用SMO算法求出$\alpha$和$b$
  • 訓練算法
  • 測試算法
  • 使用算法

代碼實現

# -*- coding=UTF-8 -*- from numpy import *def clipAlpha(aj, H, L):'''輔助函數，調整a的范圍:param aj::param H::param L::return:'''if aj > H:aj = Hif L > aj:aj = Lreturn ajdef kernelTrans(X, A, kTup):'''修改kernel:param X::param A::param kTup::return:'''m, n = shape(X)K = mat(zeros((m, 1)))if kTup[0] == 'lin':K = X * A.Telif kTup[0] == 'rbf':for j in range(m):deltaRow = X[j, :] - AK[j] = deltaRow*deltaRow.T# numpy中除法意味著對矩陣展開計算而不是matlab的求矩陣的逆K = exp(K/(-1*kTup[1]**2))# 如果遇到無法識別的元組，程序拋出異常else:raise NameError('Houston We Have a Problem -- That Kernel is not recognized')return Kclass optStruct:'''保存所有重要值，實現對成員變量的填充'''def __init__(self,dataMatIn, classLabels, C, toler, kTup): # Initialize the structure with the parametersself.X = dataMatInself.labelMat = classLabelsself.C = Cself.tol = tolerself.m = shape(dataMatIn)[0]self.alphas = mat(zeros((self.m,1)))self.b = 0self.eCache = mat(zeros((self.m,2))) #誤差緩存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):'''計算E值 計算誤差:param oS::param k::return:'''fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)Ek = fXk - float(oS.labelMat[k])return Ekdef selectJrand(i, m):''':param i: a的下標:param m: a的總數:return:'''j = iwhile (j == i):# 簡化版SMO，alpha隨機選擇j = int(random.uniform(0, m))return jdef selectJ(i, oS, Ei):'''選擇第二個a的值以保證每次優化的最大步長（內循環）:param i::param oS::param Ei::return:'''maxK = -1maxDeltaE = 0Ej = 0oS.eCache[i] =[1, Ei]validEcacheList = nonzero(oS.eCache[:, 0].A)[0]if(len(validEcacheList)) > 1:for k in validEcacheList:if k == i:continueEk = calcEk(oS, k)deltaE = abs(Ei-Ek)if(deltaE > maxDeltaE):maxK = kmaxDeltaE = deltaEEj = Ekreturn maxK, Ejelse:j = selectJrand(i, oS.m)Ej = calcEk(oS, j)return j, Ejdef updateEk(oS, k):'''計算誤差值并存入緩存中:param oS::param k::return:'''Ek = calcEk(oS, k)oS.eCache[k] = [1,Ek]def innerL(i, oS):'''選擇第二個a:param i::param oS::return:'''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 0eta = 2.0 * oS.K[i, j] - oS.K[i, i] - oS.K[j, j]if eta >= 0:print("eta>=0")return 0oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/etaoS.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 0oS.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.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 = b1elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):oS.b = b2else:oS.b = (b1 + b2)/2.0return 1else:return 0def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)):'''實現platt smo算法:param dataMatIn::param classLabels::param C::param toler::param maxIter::param kTup::return:'''oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler, kTup)iter = 0entireSet = True; alphaPairsChanged = 0while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):alphaPairsChanged = 0if entireSet:for i in range(oS.m):alphaPairsChanged += innerL(i, oS)print("fullSet, iter: %d i:%d, pairs changed %d" % (iter, i, alphaPairsChanged))iter += 1else: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 += 1if entireSet:entireSet = Falseelif (alphaPairsChanged == 0):entireSet = Trueprint("迭代次數: %d" % iter)return oS.b, oS.alphasdef img2vector(filename):'''二值化圖像轉為向量32*32轉為1*1024:param filename: 文件名:return: 向量'''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 returnVectdef loadImages(dirName):'''導入數據集:param dirName::return:'''from os import listdirhwLabels = []trainingFileList = listdir(dirName)m = len(trainingFileList)trainingMat = zeros((m, 1024))for i in range(m):fileNameStr = trainingFileList[i]fileStr = fileNameStr.split('.')[0]classNumStr = int(fileStr.split('_')[0])# 這里是二分類問題，只分類數字1和9，數字分類結果為9時返回-1if classNumStr == 9:hwLabels.append(-1)else:hwLabels.append(1)trainingMat[i, :] = img2vector('%s/%s' % (dirName, fileNameStr))return trainingMat, hwLabelsdef testDigits(kTup=('rbf', 10)):'''測試算法，使用smop訓練:param kTup: 核函數:return:'''dataArr, labelArr = loadImages('data/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("有 %d 支持向量" % shape(sVs)[0])m, n = shape(datMat)errorCount = 0for i in range(m):kernelEval = kernelTrans(sVs, datMat[i, :], kTup)predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + bif sign(predict) != sign(labelArr[i]):errorCount += 1print("訓練數據錯誤率是: %f" % (float(errorCount)/m))dataArr, labelArr = loadImages('data/testDigits')errorCount = 0datMat = mat(dataArr)labelMat = mat(labelArr).transpose()m,n = shape(datMat)for i in range(m):kernelEval = kernelTrans(sVs, datMat[i, :], kTup)predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + bif sign(predict) != sign(labelArr[i]):errorCount += 1print("測試數據錯誤率是: %f" % (float(errorCount)/m))def loadDataSet(filename):'''加載數據集:param filename: 文件名:return:'''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, labelMatif __name__ == '__main__':testDigits(('rbf', 20))

補充說明

參考書《Python3數據分析與機器學習實戰》，具體數據集和代碼可以查看我的GitHub，歡迎star或者fork。

總結

以上是生活随笔為你收集整理的机器学习-分类之支持向量机(SVM)原理及实战的全部內容，希望文章能夠幫你解決所遇到的問題。

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