在幾百個點組成的小規模數據集上，簡化版SMO算法的運行是沒有什麼問題的，但是在更大的數據集上的運行速度就會變慢。剛才已經討論了簡化版SMO算法，下面我們就討論完整版的Platt SMO算法。在這兩個版本中，實現alpha的更改和代數運算的優化環節一模一樣。在優化過程中，唯一的不同就是選擇alpha的方式。完整版的Platt SMO算法應用了一些能夠提速的啟發方法。或許讀者已經意識到，上一節的例子在執行時存在一定的時間提升空間。
Platt SMO算法是通過一個外循環來選擇第一個alpha值的，並且其選擇過程會在兩種方式之間進行交替：一種方式是在所有數據集上進行單遍掃瞄，另一種方式則是在非邊界alpha中實現單遍掃瞄。而所謂非邊界alpha指的就是那些不等於邊界0或C的alpha值。對整個數據集的掃瞄相當容易，而實現非邊界alpha值的掃瞄時，首先需要建立這些alpha值的列表，然後再對這個表進行遍歷。同時，該步驟會跳過那些已知的不會改變的alpha值。
在選擇第一個alpha值後，算法會通過一個內循環來選擇第二個alpha值。在優化過程中，會通過最大化步長的方式來獲得第二個alpha值。在簡化版SMO算法中，我們會在選擇j之後計算錯誤率Ej。但在這裡，我們會建立一個全局的緩存用於保存誤差值，並從中選擇使得步長或者說Ei-Ej最大的alpha值。
在講述改進後的代碼之前，我們必須要對上節的代碼進行清理。下面的程序清單中包含1個用於清理代碼的數據結構和3個用於對E進行緩存的輔助函數。我們可以打開一個文本編輯器，輸入如下代碼：
程序清單6-3 完整版Platt SMO的支持函數
class optStruct:
def __init__(self,dataMatIn, classLabels, C, toler):
self.X = dataMatIn
self.labelMat = classLabels
self.C = C
self.tol = toler
self.m = shape(dataMatIn)[0]
self.alphas = mat(zeros((self.m,1)))
self.b = 0
#❶ 誤差緩存
self.eCache = mat(zeros((self.m,2)))
def calcEk(oS, k):
fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T)) + oS.b
Ek = fXk - float(oS.labelMat[k])
return Ek
def selectJ(i, oS, Ei):
#❷ 內循環中的啟髮式方法
maxK = -1; maxDeltaE = 0; Ej = 0
oS.eCache[i] = [1,Ei]
validEcacheList = nonzero(oS.eCache[:,0].A)[0]
if (len(validEcacheList)) > 1:
for k in validEcacheList:
if k == i: continue
Ek = calcEk(oS, k)
deltaE = abs(Ei - Ek)
#❸（以下兩行）選擇具有最大步長的j
if (deltaE > maxDeltaE):
maxK = k; maxDeltaE = deltaE; Ej = Ek
return maxK, Ej
else:
j = selectJrand(i, oS.m)
Ej = calcEk(oS, j)
return j, Ej
def updateEk(oS, k):
Ek = calcEk(oS, k)
oS.eCache[k] = [1,Ek]
首要的事情就是建立一個數據結構來保存所有的重要值，而這個過程可以通過一個對像來完成。這裡使用對象的目的並不是為了面向對象的編程，而只是作為一個數據結構來使用對象。在將值傳給函數時，我們可以通過將所有數據移到一個結構中來實現，這樣就可以省掉手工輸入的麻煩了。而此時，數據就可以通過一個對像來進行傳遞。實際上，當完成其實現時，可以很容易通過Python的字典來完成。但是在訪問對像成員變量時，這樣做會有更多的手工輸入操作，對比一下myObject.X和myObject[\'X\']就可以知道這一點。為達到這個目的，需要構建一個僅包含init方法的optStruct類。該方法可以實現其成員變量的填充。除了增加了一個m×2的矩陣成員變量eCache之外❶，這些做法和簡化版SMO一模一樣。eCache的第一列給出的是eCache是否有效的標誌位，而第二列給出的是實際的E值。
對於給定的alpha值，第一個輔助函數calcEk能夠計算E值並返回。以前，該過程是採用內嵌的方式來完成的，但是由於該過程在這個版本的SMO算法中出現頻繁，這裡必須要將其單獨拎出來。
下一個函數selectJ用於選擇第二個alpha或者說內循環的alpha值❷。回想一下，這裡的目標是選擇合適的第二個alpha值以保證在每次優化中採用最大步長。該函數的誤差值與第一個alpha值Ei和下標i有關。首先將輸入值Ei在緩存中設置成為有效的。這裡的有效（valid）意味著它已經計算好了。在eCache 中，代碼nonzero(oS.eCache[:,0].A)[0]構建出了一個非零表。NumPy函數nonzero返回了一個列表，而這個列表中包含以輸入列表為目錄的列表值，當然讀者可以猜得到，這裡的值並非零。nonzero語句返回的是非零E值所對應的alpha值，而不是E值本身。程序會在所有的值上進行循環並選擇其中使得改變最大的那個值❸。如果這是第一次循環的話，那麼就隨機選擇一個alpha值。當然，也存在有許多更複雜的方式來處理第一次循環的情況，而上述做法就能夠滿足我們的目的。
程序清單6-3的最後一個輔助函數是updateEk，它會計算誤差值並存入緩存當中。在對alpha值進行優化之後會用到這個值。
程序清單6-3中的代碼本身的作用並不大，但是當和優化過程及外循環組合在一起時，就能組成強大的SMO算法。
接下來將簡單介紹一下用於尋找決策邊界的優化例程。打開文本編輯器，添加下列清單中的代碼。在前面，讀者已經看到過下列代碼的另外一種形式。
程序清單6-4 完整Platt SMO算法中的優化例程
def innerL(i, oS):
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)):
#❶ 第二個alpha選擇中的啟髮式方法
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 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 0
oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
oS.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 0
oS.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,:].T
b2 = 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,:].T
if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1
elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2
else: oS.b = (b1 + b2)/2.0
return 1
else: return 0
程序清單6-4中的代碼幾乎和程序清單6-2中給出的smoSimple函數一模一樣，但是這裡的代碼已經使用了自己的數據結構。該結構在參數oS中傳遞。第二個重要的修改就是使用程序清單6-3中的selectJ而不是selectJrand來選擇第二個alpha的值❶。最後，在alpha值改變時更新Ecache❷。程序清單6-5將給出把上述過程打包在一起的代碼片段。這就是選擇第一個alpha值的外循環。打開文本編輯器將下列代碼加入到svmMLiA.py文件中。
程序清單6-5 完整版Platt SMO的外循環代碼
def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=(\'lin\', 0)):
oS = optStruct(mat(dataMatIn),mat(classLabels).transpose,C,toler)
iter = 0
entireSet = True; alphaPairsChanged = 0
while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
alphaPairsChanged = 0
#❶ 遍歷所有的值
if entireSet:
for i in range(oS.m):
alphaPairsChanged += innerL(i,oS)
print \"fullSet, iter: %d i:%d, pairs changed %d\" %(iter,i,alphaPairsChanged)
iter += 1
#❷ 遍歷非邊界值
else:
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
if entireSet: entireSet = False
elif (alphaPairsChanged == 0): entireSet = True
print \"iteration number: %d\" % iter
return oS.b,oS.alphas
程序清單6-5給出的是完整版的Platt SMO算法，其輸入和函數smoSimple完全一樣。函數一開始構建一個數據結構來容納所有的數據，然後需要對控制函數退出的一些變量進行初始化。整個代碼的主體是 while循環，這與smoSimple有些類似，但是這裡的循環退出條件更多一些。當迭代次數超過指定的最大值，或者遍歷整個集合都未對任意alpha對進行修改時，就退出循環。這裡的maxIter變量和函數smoSimple中的作用有一點不同，後者當沒有任何alpha發生改變時會將整個集合的一次遍歷過程計成一次迭代，而這裡的一次迭代定義為一次循環過程，而不管該循環具體做了什麼事。此時，如果在優化過程中存在波動就會停止，因此這裡的做法優於smoSimple函數中的計數方法。
while循環的內部與smoSimple中有所不同，一開始的for循環在數據集上遍歷任意可能的alpha❶。我們通過調用innerL來選擇第二個alpha，並在可能時對其進行優化處理。如果有任意一對alpha值發生改變，那麼會返回 1。第二個for循環遍歷所有的非邊界alpha值，也就是不在邊界0或C上的值❷。
接下來，我們對for循環在非邊界循環和完整遍歷之間進行切換，並打印出迭代次數。最後程序將會返回常數b和alpha值。
為觀察上述執行效果，在Python提示符下輸入如下命令：
>>> dataArr,labelArr = svmMLiA.loadDataSet(\'testSet.txt\')
>>> b,alphas = svmMLiA.smoP(dataArr, labelArr, 0.6, 0.001, 40)
non-bound, iter: 2 i:54, pairs changed 0
non-bound, iter: 2 i:55, pairs changed 0
iteration number: 3
fullSet, iter: 3 i:0, pairs changed 0
fullSet, iter: 3 i:1, pairs changed 0
fullSet, iter: 3 i:2, pairs changed 0
類似地，讀者也可以檢查b和多個alpha的值。那麼，相對於簡化版SMO算法，上述方法是否更快？基於前面給出的設置在我自己簡陋的筆記本上運行10次算法，然後求平均值，最後得到的結果是0.78秒。而在同樣的數據集上，smoSimple函數平均需要14.5秒。在更大規模的數據集上結果可能更好，另外也存在很多方法可以進一步提升其運行速度。
如果修改容錯值結果會怎樣？如果改變C的值又如何呢？在6.2節末尾曾經粗略地提到，常數C給出的是不同優化問題的權重。常數C一方面要保障所有樣例的間隔不小於1.0，另一方面又要使得分類間隔要盡可能大，並且要在這兩方面之間平衡。如果C很大，那麼分類器將力圖通過分隔超平面對所有的樣例都正確分類。這種優化的運行結果如圖6-5所示。與圖6-4相比，會發現圖6-5中的支持向量更多。如果回想一下，就會記得圖6-4實際來自於簡化版算法，該算法是通過隨機的方式選擇alpha對的。這種簡單的方式也可以工作，但是效果卻不如完整版本好，後者覆蓋了整個數據集。讀者可能還認為選出的支持向量應該始終最接近分隔超平面。給定C的設置，圖中畫圈的支持向量就給出了滿足算法的一種解。如果數據集非線性可分，就會發現支持向量會在超平面附近聚集成團。
圖6-5 在數據集上運行完整版SMO算法之後得到的支持向量，其結果與圖6-4稍有不同
讀者可能會想，剛才我們花了大量時間來計算那些alpha值，但是如何利用它們進行分類呢？這不成問題，首先必須基於alpha值得到超平面，這也包括了w的計算。下面列出的一個小函數可以用於實現上述任務：
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
上述代碼中最重要的部分是for循環，雖然在循環中實現的僅僅是多個數的乘積。看一下前面計算出的任何一個alpha，就不會忘記大部分alpha值為0。而非零alpha所對應的也就是支持向量。雖然上述for循環遍歷了數據集中的所有數據，但是最終起作用的只有支持向量。由於對w計算毫無作用，所以數據集的其他數據點也就會很容易地被捨棄。
為了使用前面給出的函數，輸入如下命令：
>>> ws=svmMLiA.calcWs(alphas,dataArr,labelArr)
>>> ws
array([[ 0.65307162],
[-0.17196128]])
現在對數據進行分類處理，比如對說第一個數據點分類，可以這樣輸入：
>>> datMat=mat(dataArr)
>>> datMat[0]*mat(ws)+b
matrix([[-0.92555695]])
如果該值大於0，那麼其屬於1類；如果該值小於0，那麼則屬於-1類。對於數據點0，應該得到的類別標籤是-1，可以通過如下的命令來確認分類結果的正確性：
>>> labelArr[0]
還可以繼續檢查其他數據分類結果的正確性：
>>> datMat[2]*mat(ws)+b
matrix([[ 2.30436336]])
>>> labelArr[2]
1.0
>>> datMat[1]*mat(ws)+b
matrix([[-1.36706674]])
>>> labelArr[1]
-1.0
讀者可將該結果與圖6-5進行比較以確認其有效性。
我們現在可以成功訓練出分類器了，我想指出的就是，這裡兩個類中的數據點分佈在一條直線的兩邊。看一下圖6-1，大概就可以得到兩類的分隔線形狀。但是，倘若兩類數據點分別分佈在一個圓的內部和外部，那麼會得到什麼樣的分類面呢？下一節將會介紹一種方法對分類器進行修改，以說明類別區域形狀不同情況下的數據集分隔問題。