支持向量机(SVM)算法及实践(2)

参考书籍《机器学习实战》

SMO高效优化算法

1996年,platt发布了一个称为SMO的强大算法用于训练SVM。SMO表示序列最小优化。直接的好处就是把一个大问题分解成很多容易解决的小问题,通过解决这些小问题使问题整体的解决速度变快了。SMO算法的工作原理是:每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha,就增大一个减小另一个。这里的“合适”指两个alpha必须要符合一定的条件,条件之一就是这两个alpha必须要在间隔边界之外,第二个条件指两个alpha没有进行过区间化处理或者不在边界上。

应用简化版SMO算法处理小规模数据集

platt SMO算法较为复杂,所以在第一个例子中先展示简化代码,之后再研究完整代码。简化版会首先在数据集上遍历每个alpha,然后在剩下的alpha集合中随机选择另一个alpha建立alpha对重要的一点是,我们要同时改变两个alpha。因为改变一个alpha可能会导致约束条件失效。
为此,构建辅助函数,用于在某个区间范围内随机选择一个整数,以及在数值太大时对其调整。将以下代码加入SVM.py中

#coding=utf-8
def loadDataSet(fileName):
    dataMat=[]
    labelMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        lineArr=line.strip().split('\t')
        dataMat.append([float(lineArr[0]),float(lineArr[1])])
        labelMat.append(float(lineArr[2]))
    return dataMat,labelMat

def selectJrand(i,m):
    j=i
    while(j==i):
        j=int(random.uniform(0,m))
    return j

def clipAlpha(aj,H,L):
    if aj>H:#最大值不能超过H
        aj=H
    if L>aj:#最小值不能小于L
        aj=L
    return aj

selectJrand中i时alpha的下标,m是所有alpha的数目,clipAlpha用于调整大于H或者小于L的alpha值。输入代码验证:

import SVM
dataArr,labelArr=svm.loadDataSet('testSet.txt')
print labelArr

接下来就可以使用SMO算法的第一个版本了。
SMO伪代码为:
当迭代次数小于最大迭代次数时(外循环)
    对数据集中的每个数据向量(内循环):
        如果该数据向量可以被优化:
            随机选择另外一个数据向量
            同时优化两个向量
            如果两个向量都不能被优化,退出内循环
    如果所有向量都没被优化,增加迭代数目,继续下一次循环

打开SVM.py,输入如下代码:

#coding=utf-8
from numpy import *
def loadDataSet(fileName):
    dataMat=[]
    labelMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        lineArr=line.strip().split('\t')
        dataMat.append([float(lineArr[0]),float(lineArr[1])])
        labelMat.append(float(lineArr[2]))
    return dataMat,labelMat

def selectJrand(i,m):#产生一个0-m且不等于i的随机数
    j=i
    while(j==i):
        j=int(random.uniform(0,m))
    return j

def clipAlpha(aj,H,L):
    if aj>H:#最大值不能超过H
        aj=H
    if L>aj:#最小值不能小于L
        aj=L
    return aj

def smoSimple(dataMatIn,classLabels,C,toler,maxIter):#训练集,标签,常数C,容错率,迭代次数
    dataMatrix=mat(dataMatIn)
    labelMat=mat(classLabels).transpose()
    b=0
    m,n=shape(dataMatrix)#训练集数,向量维数
    alphas=mat(zeros((m,1)))#默认全0的alpha参数
    iter=0
    while(iter<maxIter):#迭代
        alphaPairsChanged=0#记录本轮alpha是否优化
        for i in range(m):#对每一个训练样本
            fXi=float(multiply(alphas,labelMat).T*\
                (dataMatrix*dataMatrix[i,:].T))+b
            Ei=fXi-float(labelMat[i])#第一个a的误差
            if(labelMat[i]*Ei<-toler) and (alphas[i]<C) \
                or ((labelMat[i]*Ei>toler)) and (alphas[i]>0):
                j=selectJrand(i,m)#随机选另一个训练样本
                fXj=float(multiply(alphas,labelMat).T*\
                    (dataMatrix*dataMatrix[j,:].T))+b
                Ej=fXj-float(labelMat[j])#第二个a的误差
                alphaIold=alphas[i].copy()
                alphaJold=alphas[j].copy()
                if(labelMat[i]!=labelMat[j]):#一个是正样本,一个是负样本
                    L=max(0,alphas[j]-alphas[i])#a一定小于C,则L最大为C,最小为0
                    H=min(C,C+alphas[j]-alphas[i])#同理,H最大为C,最小为0
                else:#两个都是正样本或负样本
                    L=max(0,alphas[j]+alphas[i]-C)
                    H=min(C,alphas[j]+alphas[i])
                if L==H:
                    #print "L==H"
                    continue
                eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - \
                    dataMatrix[i,:]*dataMatrix[i,:].T - \
                    dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >= 0:
                    #print "eta>=0"
                    continue
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                alphas[j] = clipAlpha(alphas[j],H,L)
                if (abs(alphas[j]-alphaJold) < 0.00001):
                    #print "j not moving enough"
                    continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - \
                    labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - \
                    labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]):
                    b = b1
                elif (0 < alphas[j]) and (C > alphas[j]):
                    b = b2
                else:
                    b = (b1 + b2)/2.0
                alphaPairsChanged += 1
            #print "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
        if (alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
        #print "iteration number: %d" % iter
    return b,alphas

smo函数会不断选择两个alpha参数,尝试改变它们的值,并要求在改变的过程中满足约束条件,直到迭代次数满足或alpha不再改变。
输入以下代码测试:

import SVM
dataArr,labelArr=SVM.loadDataSet('testSet6.txt')
b,alphas=SVM.smoSimple(dataArr,labelArr,0.6,0.001,40)
print b
print alphas[alphas>0]


将这些点在圆图中标记出来:

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据