支持向量機(jī)的理論支持在此不細(xì)說(shuō)，可以參考李航的《統(tǒng)計(jì)學(xué)習(xí)》，還有西瓜書(shū)。

簡(jiǎn)化版SMO算法處理小規(guī)模數(shù)據(jù)集

SMO算法是一種啟發(fā)式算法。此簡(jiǎn)化版首先在數(shù)據(jù)集上遍歷每一個(gè)alpha，然后在剩下的alpha集合中隨機(jī)選擇另一個(gè)alpha，從而建立alpha對(duì)。

# -*- coding: utf-8 -*- from numpy import * from time import sleep# SMO算法的輔助函數(shù) def loadDataSet(fileName): #加載并預(yù)處理數(shù)據(jù)集dataMat = []; labelMat = []fr = open(fileName,'r')for line in fr.readlines():lineArr = line.strip().split('\t') # 以制表符分割dataMat.append([float(lineArr[0]), float(lineArr[1])]) #提取前兩個(gè)元素存入data.Mat中labelMat.append(float(lineArr[2])) # [].append(),最終的形式是矩陣return dataMat,labelMatdef selectJrand(i,m): # 該輔助函數(shù)用于在某個(gè)區(qū)間范圍內(nèi)隨機(jī)選擇一個(gè)整數(shù)j=i # m是所有alpha的數(shù)目，i是第一個(gè)alpha的下標(biāo)while (j==i):j = int(random.uniform(0,m)) # random.uniform(0,m)用于生成指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)return jdef clipAlpha(aj,H,L): # 該輔助函數(shù)用于在數(shù)值太大時(shí)對(duì)其進(jìn)行調(diào)整if aj > H: aj = Hif L > aj:aj = Lreturn aj# 簡(jiǎn)化版SMO算法 def smoSimple(dataMatIn, classLabels, C, toler, maxIter): # 參數(shù)：數(shù)據(jù)集，類(lèi)別標(biāo)簽，常數(shù)c，容錯(cuò)率，循環(huán)次數(shù)dataMatrix = mat(dataMatIn) # mat()轉(zhuǎn)換成矩陣類(lèi)型labelMat = mat(classLabels).transpose() #轉(zhuǎn)置之前是列表，轉(zhuǎn)置后是一個(gè)列向量b = 0; m,n = shape(dataMatrix) # 得到行，列數(shù)，m行，n列alphas = mat(zeros((m,1))) # zeros(shape, dtype=float, order='C'),所以也可以寫(xiě)作zeros((10,1),)iter = 0 # 該變量存儲(chǔ)的是在沒(méi)有任何alpha改變時(shí)遍歷數(shù)據(jù)集的次數(shù)while (iter < maxIter): # 限制循環(huán)迭代次數(shù)，也就是在數(shù)據(jù)集上遍歷maxIter次，且不再發(fā)生任何alpha修改，則循環(huán)停止alphaPairsChanged = 0 # 每次循環(huán)時(shí)先設(shè)為0，然后再對(duì)整個(gè)集合順序遍歷，該變量用于記錄alpha是否已經(jīng)進(jìn)行優(yōu)化for i in range(m): # 遍歷每行數(shù)據(jù)向量，m行# 該公式是分離超平面，我們預(yù)測(cè)值fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b #print 'fxi:',fxiEi = fXi - float(labelMat[i]) # 預(yù)測(cè)值和真實(shí)輸出之差 # 如果誤差很大就對(duì)該數(shù)據(jù)對(duì)應(yīng)的alpha進(jìn)行優(yōu)化，正負(fù)間隔都會(huì)被測(cè)試，同時(shí)檢查alpha值 if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)): j = selectJrand(i,m) # 隨機(jī)選擇不等于i的0-m的第二個(gè)alpha值fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + bEj = fXj - float(labelMat[j])alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();if (labelMat[i] != labelMat[j]): # 這里是對(duì)SMO最優(yōu)化問(wèn)題的子問(wèn)題的約束條件的分析L = max(0, alphas[j] - alphas[i]) # L和H分別是alpha所在的對(duì)角線端點(diǎn)的界H = min(C, C + alphas[j] - alphas[i]) # 調(diào)整alphas[j]位于0到c之間else:L = max(0, alphas[j] + alphas[i] - C)H = min(C, alphas[j] + alphas[i])if L==H: print "L==H"; continue # L=H停止本次循環(huán)# 是一個(gè)中間變量：eta=2xi*xi-xixi-xjxj，是alphas[j]的最優(yōu)修改量eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T \- dataMatrix[j,:]*dataMatrix[j,:].Tif eta >= 0: print "eta>=0"; continue # eta>=0停止本次循環(huán)，這里是簡(jiǎn)化計(jì)算alphas[j] -= labelMat[j]*(Ei - Ej)/eta # 沿著約束方向未考慮不等式約束時(shí)的alpha[j]的解alphas[j] = clipAlpha(alphas[j],H,L) # 此處是考慮不等式約束的alpha[j]解if (abs(alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; continue # 如果該alpha值不再變化，就停止該alpha的優(yōu)化alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j]) # 更新alpha[i]# 完成兩個(gè)alpha變量的更新后，都要重新計(jì)算閾值bb1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T \- labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]* dataMatrix[j,:].T #李航統(tǒng)計(jì)學(xué)習(xí)7.115式b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T \- labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T #李航統(tǒng)計(jì)學(xué)習(xí)7.116式if (0 < alphas[i]) and (C > alphas[i]): b = b1elif (0 < alphas[j]) and (C > alphas[j]): b = b2 else: b = (b1 + b2)/2.0 # alpha[i]和alpha[j]是0或者c,就取中點(diǎn)作為balphaPairsChanged += 1 # 到此的話說(shuō)明已經(jīng)成功改變了一對(duì)alphaprint "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)if (alphaPairsChanged == 0): iter += 1 # 如果alpha不再改變迭代次數(shù)就加1else: iter = 0 print "iteration number: %d" % iterreturn b,alphas# 主函數(shù) dataArr,labelArr=loadDataSet('testSet.txt') # 因?yàn)樵谕晃募A下，就不用寫(xiě)絕對(duì)路徑 #print dataArr b,alphas=smoSimple(dataArr, labelArr, 0.6, 0.001, 40) print 'b:',b print 'alphas[alphas>0]:',alphas[alphas>0] # 數(shù)組過(guò)濾 print shape(alphas[alphas>0]) # 得到支持向量的個(gè)數(shù) for i in range(100): # 得到是支持向量的數(shù)據(jù)點(diǎn)if alphas[i]>0.0: print dataArr[i],labelArr[i]

其中要注意的python語(yǔ)法：

• 數(shù)組和矩陣的轉(zhuǎn)換

In [17]:type(dataArr) # 轉(zhuǎn)換之前是list的類(lèi)型 Out[17]: listIn [18]:mat(dataArr) # 轉(zhuǎn)換之后是矩陣類(lèi)型 Out[18]: matrix([[ 3.542485, 1.977398],[ 3.018896, 2.556416],[ 7.55151 , -1.58003 ],..., [ 2.912122, -0.202359],[ 1.731786, 0.589096],[ 2.387003, 1.573131]])

• Python自帶的copy()，deepcopy()，numpy的copy（）之間的區(qū)別

>>> import copy >>> origin = [1, 2, [3, 4]] >>> cop1 = copy.copy(origin) # 淺拷貝 >>> cop2 = copy.deepcopy(origin) # 深拷貝 >>> cop1 == cop2 True >>> cop1 is cop2 False #cop1 和 cop2 看上去相同，但已不再是同一個(gè)object >>> origin[2][0] = "hey!" >>> origin [1, 2, ['hey!', 4]] >>> cop1 [1, 2, ['hey!', 4]] >>> cop2 [1, 2, [3, 4]] #把origin內(nèi)的子list [3, 4] 改掉了一個(gè)元素，觀察 cop1 和 cop2

可以看到 cop1，也就是 shallow copy 跟著 origin 改變了。而 cop2 ，也就是 deep copy 并沒(méi)有變。
似乎 deep copy 更加符合我們對(duì)「復(fù)制」的直覺(jué)定義: 一旦復(fù)制出來(lái)了，就應(yīng)該是獨(dú)立的了。如果我們想要的是一個(gè)字面意義的「copy」，那就直接用 deep_copy 即可。

注意：這里指的是python自帶的copy( )函數(shù)，copy.copy(object)是淺拷貝，而numpy的copy( )函數(shù)，即object.copy( )是深拷貝的效果。

from numpy import * In [26]:origin Out[26]: matrix([[1, 2], [3, 4]])In [28]:origin[0][0,1] Out[28]: 2In [29]:origin[0][0,0] Out[29]: 1 In [31]:old=origin[0][0,1].copy()In [32]:origin[0][0,1]=5In [33]:origin[0][0,1] Out[33]: 5In [34]:old Out[34]: 2

分類(lèi)圖示：

在園圈中的就是支持向量

代碼中的公式含義：

（1）

fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b

fxi對(duì)應(yīng)的是《統(tǒng)計(jì)學(xué)習(xí)》中7.104的g(x)：

g(x)=∑i=1Nα?iyixi?x+b?
其代表的是分離超平面
（2）

Ei = fXi - float(labelMat[i])

Ei=g(xi)?yi
表示預(yù)測(cè)值和真實(shí)輸出之差
（3）

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])

L和H是alphas的所在對(duì)角線端點(diǎn)的界：
如果y1≠y2則L=max(0,αoldj?αoldi),H=min(c,c+αoldj?αoldi)
如果y1=y2則L=max(0,αoldj+αoldi?c),H=min(c,αoldj+αoldi)
（4）

eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T \- dataMatrix[j,:]*dataMatrix[j,:].T

對(duì)應(yīng)

η=2xj?xi?xi?xi?xj?xj
表示的是alphas[j]的最優(yōu)修改量，是一個(gè)中間變量
（5）

alphas[j] -= labelMat[j]*(Ei - Ej)/eta

對(duì)應(yīng)

αnew,uncj=αoldj?yj(Ei?Ej)η
是沿著約束方向未考慮不等式約束時(shí)的alpha[j]的解

（6）

alphas[j] = clipAlpha(alphas[j],H,L)

此處是考慮不等式約束的alpha[j]解：

αnewj=???????Hαnew,uncjLαnew,uncj>HL?αnew,uncj?Hαnew,uncj<L
得到了第一個(gè)變量的值
（7）

alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])

αnewi=αoldi+y1y2(αoldj?αnewj)

（8）

b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T \- labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]* dataMatrix[j,:].T

得到的是b：

bnew1=bold?Ei?yixi?xi(αnewi?αoldi)?y2xj?xi(αnewj?αoldj)+bold

代碼中的主要公式大概就這些。

運(yùn)行結(jié)果：

j not moving enough j not moving enough iteration number: 1 j not moving enough j not moving enough ..., j not moving enough iteration number: 38 j not moving enough j not moving enough iteration number: 39 j not moving enough j not moving enough iteration number: 40 b: [[-3.83495394]] alphas[alphas>0]: [[ 0.15601002 0.14181599 0.06893826 0.36676427]] (1L, 3L) [4.658191, 3.507396] -1.0 [3.457096, -0.082216] -1.0 [6.080573, 0.418886] 1.0

“不忘初心，方得始終”搞了那么多代碼和公式，不要沉浸進(jìn)去而不知道最后要求的是什么？SMO算法的目標(biāo)是求出一系列的α和b，而此時(shí)運(yùn)行得到的就是那些支持向量和相對(duì)應(yīng)的參數(shù)α，還有b，由此也就得到了分離超平面，就是：

∑i=1Nα?iyixi?x+b?=0
分類(lèi)決策函數(shù)可以寫(xiě)成：
f(x)=sign(∑i=1Nα?iyixi?x+b?)
由此驗(yàn)證了在決定分離超平面時(shí)只有支持向量起作用。如果移動(dòng)支持向量將改變所求的解；但如果在間隔邊界以外移動(dòng)其他實(shí)例點(diǎn)，甚至去掉這些點(diǎn)，則解不會(huì)改變。
由于SMO算法的隨機(jī)性，每次的運(yùn)行結(jié)果可能不同。

還有一點(diǎn)要注意：就是優(yōu)化結(jié)束的同時(shí)必須確保合適的時(shí)機(jī)結(jié)束循環(huán)，如果程序執(zhí)行到for循環(huán)的最后一行都不執(zhí)行continue語(yǔ)句，那么就成功地改變了一對(duì)α值，同時(shí)可以增加alphaPairsChanged的值，在for循環(huán)之外，需要檢查α值是否有更新，如果有更新則將iter設(shè)為0后繼續(xù)運(yùn)行程序。只有在所有的數(shù)據(jù)集上遍歷maxIter次，且不再發(fā)生任何α的修改后，程序才停止并退出while循環(huán)。

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

在完整版的SMO算法中，實(shí)現(xiàn)alpha的更改和代數(shù)運(yùn)算的優(yōu)化環(huán)節(jié)一模一樣，在優(yōu)化過(guò)程中，唯一不同的是選擇alpha的方式，完整版的應(yīng)用了一些能夠提速的啟發(fā)式方法。

# -*- coding: utf-8 -*- """ Created on Wed Oct 18 20:53:40 2017@author: LiLong """ from numpy import * from time import sleep# SMO算法的輔助函數(shù) def loadDataSet(fileName): #加載并預(yù)處理數(shù)據(jù)集dataMat = []; labelMat = []fr = open(fileName,'r')for line in fr.readlines():lineArr = line.strip().split('\t') # 以制表符分割dataMat.append([float(lineArr[0]), float(lineArr[1])]) #提取前兩個(gè)元素存入data.Mat中labelMat.append(float(lineArr[2])) # [].append(),最終的形式是矩陣return dataMat,labelMat# 完整版platt SMO 算法的支持函數(shù) # 建立一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)保存所有的重要值 class optStruct:def __init__(self,dataMatIn, classLabels, C, toler): self.X = dataMatInself.labelMat = classLabelsself.C = Cself.tol = tolerself.m = shape(dataMatIn)[0] # 有多少行數(shù)據(jù)self.alphas = mat(zeros((self.m,1)))self.b = 0self.eCache = mat(zeros((self.m,2))) # 誤差緩存，第一列是ecache是否有效的標(biāo)志位，第二列是實(shí)際的E值def clipAlpha(aj,H,L):if aj > H: aj = Hif L > aj:aj = Lreturn ajdef selectJrand(i,m): # 該輔助函數(shù)用于在某個(gè)區(qū)間范圍內(nèi)隨機(jī)選擇一個(gè)整數(shù)j=i # m是所有alpha的數(shù)目，i是第一個(gè)alpha的下標(biāo)while (j==i):j = int(random.uniform(0,m)) # random.uniform(0,m)用于生成指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)return j# 計(jì)算E值并返回,E值是函數(shù)對(duì)輸入xi的預(yù)測(cè)值與真實(shí)輸出的差 def calcEk(oS, k): fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T))+ oS.bEk = fXk - float(oS.labelMat[k])return Ek# 用于選擇合適的第二個(gè)alpha值以保證每次優(yōu)化中采用最大步長(zhǎng)，是內(nèi)循環(huán)的啟發(fā)式方法 def selectJ(i, oS, Ei): # 該函數(shù)的誤差值與第一個(gè)alpha值Ei和下標(biāo)i有關(guān)maxK = -1; maxDeltaE = 0; Ej = 0oS.eCache[i] = [1,Ei] # 設(shè)置有效，有效意味著它已經(jīng)計(jì)算好了validEcacheList = nonzero(oS.eCache[:,0].A)[0] # 構(gòu)建出一個(gè)非零表，返回的列表中包含以輸入列表為目錄的列表值if (len(validEcacheList)) > 1:for k in validEcacheList: if k == i: continue # 跳出本次循環(huán)Ek = calcEk(oS, k) # 傳遞對(duì)象和k，計(jì)算誤差值deltaE = abs(Ei - Ek)if (deltaE > maxDeltaE): # 選擇具有最大步長(zhǎng)的jmaxK = k; maxDeltaE = deltaE; Ej = Ek # 會(huì)在所有的值上循環(huán)，并選擇其中使得改變最大的那個(gè)值return maxK, Ejelse: # 在這種情況下（第一次，我們沒(méi)有任何有效的eCache值 ），隨機(jī)選擇一個(gè)alpha值j = selectJrand(i, oS.m) Ej = calcEk(oS, j)return j, Ejdef updateEk(oS, k): # alpha改變時(shí)更新緩存中的值Ek = calcEk(oS, k) oS.eCache[k] = [1,Ek]# 完整platt SMO算法中的優(yōu)化例程 def innerL(i, oS): Ei = calcEk(oS, i) # 計(jì)算誤差值 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) # 第二個(gè)alpha選擇中的啟發(fā)式方法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 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.X[i,:]*oS.X[i,:].T \- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[i,:]*oS.X[j,:].Tb2 = 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,:].Tif (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 1 # 如果有任意一對(duì)alpha發(fā)生改變，那么就會(huì)返回1，其他返回0else: return 0 # 完整版platt SMO的外循環(huán)代碼 def smoP(dataMatIn, classLabels, C, toler, maxIter): # 建立一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)容納所有的數(shù)據(jù)oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler) iter = 0entireSet = True; alphaPairsChanged = 0 # 退出循環(huán)的變量的一些初始化# 迭代次數(shù)超過(guò)指定的最大值或者遍歷整個(gè)集合都未對(duì)任意的alpha對(duì)進(jìn)行修改時(shí)就退出循環(huán)while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)): alphaPairsChanged = 0 if entireSet: for i in range(oS.m): # 一開(kāi)始在數(shù)據(jù)集上遍歷任意可能的alpha # 選擇第二個(gè)alpha，并在可能時(shí)對(duì)其進(jìn)行優(yōu)化處理,有任一一對(duì)alpha發(fā)生變化化了alphaPairsChanged+1alphaPairsChanged += innerL(i,oS)print "fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)iter += 1else: # 遍歷所有的非邊界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 += 1if entireSet: entireSet = False # 在非邊界循環(huán)和完整遍歷之間進(jìn)行切換elif (alphaPairsChanged == 0): entireSet = True print "iteration number: %d" % iterreturn oS.b,oS.alphas # 分類(lèi)超平面的w計(jì)算 def calcWs(alphas,dataArr,classLabels):X = mat(dataArr); labelMat = mat(classLabels).transpose()m,n = shape(X)w = zeros((n,1))for i in range(m):w += multiply(alphas[i]*labelMat[i],X[i,:].T)return w# 主函數(shù) dataArr,labelArr=loadDataSet('testSet.txt') b,alphas=smoP(dataArr,labelArr,0.6,0.001,40) print 'b:',b print 'alphas:',alphas # 輸出w和b ws=calcWs(alphas,dataArr,labelArr) print 'ws:',ws datmat=mat(dataArr) result=datmat[0]*mat(ws)+b # 進(jìn)行分類(lèi) print 'result',result

一些Python的技巧：
nonzero的用法
matrix.A用法

In [5]:a=mat(zeros((3,2))) In [6]:a Out[6]: matrix([[ 0., 0.],[ 0., 0.],[ 0., 0.]]) In [7]:nonzero(a[:,0].A)[0] Out[7]: array([], dtype=int64) In [8]:a[:,0].A Out[8]: array([[ 0.],[ 0.],[ 0.]]) In [15]: a=mat([[0,1],[1,0],[0,1]]) In [16]: a[:,0].A Out[16]: array([[0],[1],[0]]) In [19]: nonzero(a[:,0].A)[0] Out[19]: array([1], dtype=int64) In [20]: a=mat([[0,1],[1,0],[1,1]])In [21]: a[:,0].A Out[21]: array([[0],[1],[1]])In [22]: nonzero(a[:,0].A)[0] Out[22]: array([1, 2], dtype=int64) >>> from numpy import * >>> aa=[0,1,2,3,4,10,6,7,8,0] >>> b=mat(aa) >>> b matrix([[ 0, 1, 2, 3, 4, 10, 6, 7, 8, 0]]) >>> b.A array([[ 0, 1, 2, 3, 4, 10, 6, 7, 8, 0]]) >>> b.A>3 array([[False, False, False, False, True, True, True, True, True,False]], dtype=bool) >>> b.A<4 array([[ True, True, True, True, False, False, False, False, False,True]], dtype=bool) >>> (b.A>3)*(b.A<4) array([[False, False, False, False, False, False, False, False, False,False]], dtype=bool) >>> nonzero((b.A>3)*(b.A<4)) (array([], dtype=int64), array([], dtype=int64)) >>> nonzero((b.A>3)*(b.A<4))[0] array([], dtype=int64) >>>

SMO中拉格朗日乘子的啟發(fā)式選擇方法：
所謂的啟發(fā)式選擇方法主要思想是每次選擇拉格朗日乘子的時(shí)候，優(yōu)先選擇樣本前面系數(shù)0<ai<c作優(yōu)化（論文中稱(chēng)為無(wú)界樣例），因?yàn)樵诮缟?#xff08;ai為0或C）的樣例對(duì)應(yīng)的系數(shù)ai一般不會(huì)更改。

這條啟發(fā)式搜索方法是選擇第一個(gè)拉格朗日乘子用的，那么這樣選擇的話，是否最后會(huì)收斂。可幸的是Osuna定理告訴我們只要選擇出來(lái)的兩個(gè)ai中有一個(gè)違背了KKT條件，那么目標(biāo)函數(shù)在一步迭代后值會(huì)減小。違背KKT條件不代表0<ai<c=0后，先對(duì)所有樣例進(jìn)行循環(huán)，循環(huán)中碰到違背KKT條件的（不管界上還是界內(nèi)）都進(jìn)行迭代更新。等這輪過(guò)后，如果沒(méi)有收斂，第二輪就只針對(duì)0<ai<c，選擇第二個(gè)乘子能夠最大化|E1?E2|。即當(dāng)E1為正時(shí)選擇負(fù)的絕對(duì)值最大的E2，反之，選擇正值最大的E2。

最后的收斂條件是在界內(nèi)（0<ai<c只在極小的范圍內(nèi)變動(dòng)。

參考：

http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html#3793878

運(yùn)行結(jié)果：

L==H fullSet, iter: 0 i:0, pairs changed 0 L==H fullSet, iter: 0 i:1, pairs changed 0 fullSet, iter: 0 i:2, pairs changed 1 L==H ..., j not moving enough fullSet, iter: 2 i:97, pairs changed 0 fullSet, iter: 2 i:98, pairs changed 0 fullSet, iter: 2 i:99, pairs changed 0 iteration number: 3 b: [[-2.89901748]] alphas: [[ 0.06961952][ 0. ][ 0. ]..., [ 0. ][ 0. ][ 0. ]] ws: [[ 0.65307162][-0.17196128]] result [[-0.92555695]]

得到α和b后就可以進(jìn)行分類(lèi)了：
sign(∑i=1Nα?iyixi?x+b?)

完整版的SMO算法和簡(jiǎn)化版的幾點(diǎn)區(qū)別：

• while的循環(huán)退出條件更多一些
• maxiter變量的簡(jiǎn)化版的作用不同，簡(jiǎn)化版的是當(dāng)沒(méi)有任何alpha發(fā)生變化時(shí)會(huì)將整個(gè)集合的一次遍歷過(guò)程計(jì)成一次迭代，而完整版的的一次迭代計(jì)成定義為一次循環(huán)過(guò)程，而不管該循環(huán)具體做了什么事
• while循環(huán)內(nèi)部和簡(jiǎn)化版的有所不同
• 速度有很大提升

支持向量機(jī)有些復(fù)雜，以后在應(yīng)用中再進(jìn)一步學(xué)習(xí)！！

總結(jié)

以上是生活随笔為你收集整理的支持向量机—SMO算法源码分析（1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。