在几百个数据点组成的小规模数据集上，简化版SMO算法的运行是没有什么问题，但是在更大的数据集上的运行速度就会变慢。完整版的platt SMO算法应用了一些能够提速的启动方法。

platt SMO算法时通过一个外循环来选择第一个alpha值的，并且其选择过程会在两种方式之间交替进行：一种方式是在所有数据集上进行单遍扫描，另一种方式则是在非边界alpha中实现单遍扫描。而所谓非边界alpha指的就是那些不等于边界0或C的alpha值。对整个数据集的扫描相当容易，而实现非边界alpha值的扫描时，首先需要建立这些alpha值的列表，然后再对这个表进行遍历。同时，该步骤会跳过那些已知的不会改变的alpha值。

在选择第一个alpha值后，算法会通过一个内循环来选择第二个alpha值。在优化过程中，会通过最大化步长的方式来获取第二个alpha值。我们会建立一个全局的缓存用来保存误差值，并从中选择使得步长或者说Ei-Ej最大的alpha值。

具体实现：

python">class optStruct:def __init__(self,dataMatIn,classLabels,C,toler):self.X=dataMatInself.labelMat=classLabelsself.C=Cself.tol=tolerself.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):#对于给定的alpha值，计算E值并返回fXk=float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T))+oS.bEk=fXk-float(oS.labelMat[k])return Ek
#内循环中的启动式方法
def selectJ(i,oS,Ei):#用于选择第二个alpha（内循环的alpha值），函数的误差值与第一个alpha值Ei和下标i有关maxK=-1maxDeltaE=0Ej=0oS.eCache[i]=[1,Ei]validEcacheList=nonzero(oS.eCache[:,0].A)[0]#构建一个非零表，包含以输入列表为目录的列表值，nonzero()语句返回的是非零E值所对应的alpha值而不是E值本身if (len(validEcacheList))>1:for k in validEcacheList:if k==i:continueEk=calcEk(oS,k)deltaE=abs(Ei-Ek)if (deltaE>maxDeltaE):#选择具有最大步长的jmaxK=kmaxDeltaE=deltaEEj=Ekreturn maxK,Ejelse: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">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)#随机选择第二个alphaalphaIold = oS.alphas[i].copy()alphaJold = oS.alphas[j].copy()# 保证alpha在0与C之间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为最优修改量，如果eta=0，需要退出循环的当前迭代过程。eta=2.0*oS.X[i,:]*oS.X[j,:].T-oS.X[i,:]*oS.X[i,:].T-oS.X[j,:]*oS.X[j,:].Tif eta>=0:print('eta>0')return 0oS.alphas[j]=oS.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 mot moving enough')return 0oS.alphas[i]=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, :].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.0else:return 0

这里函数使用了自己的数据结构。该结构在oS中传递。

并且，在alpha值改变时更新Ecache。

完整的platt SMO的外循环代码：

python">def smoP(dataMaxIn,classLabels,C,toler,maxIter,kTup=('lin',0)):#输入参数分别为：数据集、类别标签、常数C、容错率、退出前最大的循环次数#构建一个数据结构来容纳所有的数据oS=optStruct(mat(dataMaxIn),mat(classLabels).transpose(),C,toler)iter=0entireSet=TruealphaPairsChanged=0while(iter<maxIter) and ((alphaPairsChanged>0) or (entireSet)):alphaPairsChanged=0if entireSet:#遍历所有的值for i in range(oS.m):alphaPairsChanged=alphaPairsChanged+innerL(i,oS)print(iter,i,alphaPairsChanged)iter=iter+1else:#遍历非边界值nonBoundIs=nonzero((oS.alphas.A>0)*(oS.alphas.A<C))[0]for i in nonBoundIs:alphaPairsChanged=alphaPairsChanged+innerL(i,oS)print(iter,i,alphaPairsChanged)iter = iter + 1if entireSet:entireSet=Falseelif (alphaPairsChanged==0):entireSet=Trueprint(iter)return oS.b,oS.alphas

这里函数的主题是while循环，这里的退出条件比较多：当迭代次数超过指定的最大值，或者遍历这个集合都未对任意alpha对进行修改时，就退出循环。此外，如果在优化过程中存在波动就会停止。

while循环中，一开始的for循环在数据集上遍历任意可能的alpha，我们可以通过调用innerL()来选择第二个alpha，并在可能时对其进行优化处理。如果有任意一对alpha值发生改变，那么就会返回1，第二个for循环遍历所有的飞边界alpha值，也就是不在边界0或C的值。

执行代码：

python">
dataArr,labelArr=loadDataSet('testSet.txt')
# print(labelArr)
b,alphas=smoP(dataArr,labelArr,0.6,0.001,40)