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

157 Views

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

基于最大间隔分割数据

支持向量机
优点:泛化错误率低,计算开销不大,结果易解释
缺点:对参数调节和核函数选择敏感,原始分类器不加修改仅适用于处理二分类问题。
使用数据类型:数值型和标称型数据

考虑6-1中A-D4个方框的数据点分布,能否画出一条直线将两组数据点分开呢?再看看图6-2,两组数据又能不能用一条直线分开呢?

上述将数据集分隔开的直线称为分割超平面。在上面给出的例子中,由于数据点都在二维平面上,所以此时分割超平面就只是一条直线。但是,如果所给的数据集是三维的,那么此时分隔数据的就是一个平面。

我们希望能采用这种方式来构建分类器,即如果数据点离决策边界越远,那么最后的结果就越可信。图6-2中B-D的三条直线,他们都能分开数据,那么B和C的直线是否比D的直线更好呢。

支持向量就是离分割超平面最近的那些点。接下来要试着最大化支持向量到分隔面的距离,需要找到问题的优化求解方法。

寻找最大间隔

图6-3,分割超平面的形式可以写成wx+b,点A到平面的距离为|wA+b|/||w||

分类器求解的优化问题

输入数据给分类器一个类别标签,类似于Sigmoid的函数,不同之处在于sigmoid给出函数取值为0或1,而SVM中取值为-1或+1。

计算数据点到分隔面的距离时,间隔通过label*(wx+b),这样无论是平面哪一侧的点,结果都会是一个正数。
现在的目标就是找出分类其定义的w和b。为此,我们必须找到具有最小间隔的数据点,而这些数据点就是前面提到的支持向量。一旦找到具有最小间隔的数据点,我们就需要将其最大化。
通过引入拉格朗日乘子法,我们可以给予约束条件来表述原来的问题,优化目标函数可以写成
约束条件为:

之前的前提建立在数据100%线性可分的情况下。但是这几乎是不可能的。为解决这个问题,引入松弛变量,允许一些数据点处于分隔面的错误一侧,这样,约束条件改为:

C用于控制“最大化间隔”和“保证大部分的店的函数间隔小于1.0”这两个目标的权重。C作为参数,调节C得到不同的结果。一旦球出了所有的lapha,那么分割超平面就可以通过这些alpha表达。SVM的主要工作就是求出这些alpha。

SVM应用的一般框架

SVM的一般流程
(1)收集数据:可以使用任意方法
(2)准备数据:需要数值型数据
(3)分析数据:有助于可视化超平面
(4)训练算法:SVM大部分时间都源自训练,该过程主要实现两个参数的调优
(5)测试算法:十分简单的计算过程就可以实现
(6)使用算法:几乎所有的分类问题都可以使用SVM,但SVM应用于多分类时要对SVM稍作修改


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
        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:
                continue
            eta = 2.0 * dataMatrix[i,:] * dataMatrix[j,:].T - dataMatrix[i,:] * dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
            if eta >= 0:
                continue
            alphas[j] -= labelMat[j] * (Ei - Ej) / eta
            alphas[j] = clipAlpha(alphas[j],H,L)
            if (abs(alphas[j] - alphaJold) < 0.00001): 
                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
            if (alphaPairsChanged == 0):
                iter += 1
            else:
                iter = 0
    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]


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

留下回复

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