首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》6.4 利用完整Platt SMO算法加速优化

关灯直达底部

在几百个点组成的小规模数据集上,简化版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.XmyObject[/'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,大概就可以得到两类的分隔线形状。但是,倘若两类数据点分别分布在一个圆的内部和外部,那么会得到什么样的分类面呢?下一节将会介绍一种方法对分类器进行修改,以说明类别区域形状不同情况下的数据集分隔问题。