在几百个点组成的小规模数据集上，简化版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, Ejdef 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 0non-bound, iter: 2 i:55, pairs changed 0iteration number: 3fullSet, iter: 3 i:0, pairs changed 0fullSet, iter: 3 i:1, pairs changed 0fullSet, 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)>>> wsarray([[ 0.65307162], [-0.17196128]]) 现在对数据进行分类处理，比如对说第一个数据点分类，可以这样输入：
>>> datMat=mat(dataArr)>>> datMat[0]*mat(ws)+bmatrix([[-0.92555695]]) 如果该值大于0，那么其属于1类；如果该值小于0，那么则属于-1类。对于数据点0，应该得到的类别标签是-1，可以通过如下的命令来确认分类结果的正确性：
>>> labelArr[0]还可以继续检查其他数据分类结果的正确性：
>>> datMat[2]*mat(ws)+bmatrix([[ 2.30436336]])>>> labelArr[2]1.0>>> datMat[1]*mat(ws)+bmatrix([[-1.36706674]])>>> labelArr[1]-1.0 读者可将该结果与图6-5进行比较以确认其有效性。
我们现在可以成功训练出分类器了，我想指出的就是，这里两个类中的数据点分布在一条直线的两边。看一下图6-1，大概就可以得到两类的分隔线形状。但是，倘若两类数据点分别分布在一个圆的内部和外部，那么会得到什么样的分类面呢？下一节将会介绍一种方法对分类器进行修改，以说明类别区域形状不同情况下的数据集分隔问题。