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

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

基于最大间隔分割数据

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

考虑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]

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