本篇内容为《机器学习实战》第 6 章 支持向量机部分程序清单。所用代码为 python3。
支持向量机
优点：泛化错误率低，计算开销不大，结果易解释。
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二分类问题。
适用数据类型：数值型和标称型数据。
1996 年，John Platt 发布了一个称为SMO的强大算法，用于训练 SVM。SMO表示序列最小优化 (Sequential Minimal Optimization)。
SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha，那么就增大其中一个同时减小另一个。这里的“合适”是指两个alpha必须要符合一定的条件，第一个条件是这两个alpha必须要在间隔边界之外，第二个条件是这两个alpha还没有进行过区间化处理或者不在边界上。
应用简化版 SMO 算法处理小规模数据集
下面给出简化版的SMO算法程序清单。
该SMO函数的伪代码如下：
创建一个alpha向量并将其初始化为 0 向量
当迭代次数小于最大迭代次数时（外循环）
···对数据集中的每个数据向量（内循环）：
······如果该数据向量可以被优化：
·········随机选择另外一个数据向量
·········同时优化这两个向量
·········如果两个向量都不能被优化，退出内循环
···如果所有向量都没被优化，增加迭代数目，继续下一次循环
程序清单 6-1 SMO算法中的辅助函数
# coding=utf-8
# import sys
from numpy import *
def loadDataSet():
dataMat = []
labelMat = []
fr = open('testSet.txt')
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
# i 是第一个 alpha 的下标， m 是所有 alpha 的数目
# 只要函数值不等于输入值 i，函数就会进行随机选择
def selectJrand(i, m):
j = i
while (j == i):
j = int(random.uniform(0, m))
return j
# 用于调整大于 H 或小于 L 的 alpha 值
def clipAlpha(aj, H, L):
if aj > H:
aj = H
if L > aj:
aj = L
return aj
在 python 提示符下，执行代码并得到结果：
>>> import svmMLiA
>>> dataArr, labelArr = svmMLiA.loadDataSet()
>>> labelArr
[-1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0]
可以看出，这里采用的类别标签是 -1 和 1。
程序清单 6-2 简化版SMO算法
# 参数：数据集，类别标签，常数C，容错率，退出前最大的循环次数
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
dataMatrix = mat(dataMatIn)
# 由于转置了类别标签，我们得到的是一个列向量而不是列表
labelMat = mat(classLabels).transpose()
b = 0
m,n = shape(dataMatrix)
# 构建一个 alpha 列矩阵，矩阵中元素都初始化为0
alphas = mat(zeros((m, 1)))
# iter 变量存储的是在没有任何 alpha 改变的情况下便利数据集的次数
# 当这个变量达到输入值 maxIter 时，函数结束运行并退出
iter = 0
while(iter < maxIter):
# 每次循环当中，将 alphaPairsChanged 先设为0，在对整个集合顺序遍历
# 变量 alphaPairsChanged 用于记录 alpha 是否已经进行优化
alphaPairsChanged = 0
for i in range(m):
# 计算 fXi，即我们预测的类别
fXi = float(multiply(alphas, labelMat).T * (dataMatrix*dataMatrix[i,:].T) + b)
# 与真实值比对，计算误差 Ei
Ei = fXi - float(labelMat[i])
# 如果误差很大，可以对该数据实例所对应的 alpha 值进行优化
# 不论正间隔还是负间隔都会被测试
# 检查 alpha 值，保证其不能等于 0 或 C
if((labelMat[i]*Ei < -toler) and (alphas[i] < C)\
or (labelMat[i]*Ei > toler) and (alphas[i] > 0)):
# 用辅助函数 selectJrand 随机选择第二个 alpha 值，即 alpha[j]
j = selectJrand(i,m)
# 同样计算误差
fXj = float(multiply(alphas, labelMat).T * (dataMatrix*dataMatrix[j,:].T)) + b
Ej = fXj - float(labelMat[j])
alphaIold = alphas[i].copy()
alphaJold = alphas[j].copy()
# 计算 L 和 H，调整 alpha 到 0 与 C 之间
if(labelMat[i] != labelMat[j]):
L = max(0, alphas[j] - alphas[i])
H = min(C, C + alphas[j] - alphas[i])
else:
L = max(0, alphas[j] + alphas[i] - C)
H = min(C, alphas[j] + alphas[i])
if L==H:
print('L == H')
continue
# eta 是 alpha[j] 的最优修改量
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
# 计算出一个新的 alpha[j]，并进行调整
alphas[j] -= labelMat[j] * (Ei - Ej) / eta
alphas[j] = clipAlpha(alphas[j], H, L)
# 检查 alpha[j] 是否有轻微改变，是的话则退出 for 循环
if(abs(alphas[j] - alphaJold) < 0.00001):
print('j not moving enough')
continue
# 对 alpha[i] 进行和 alpha[j] 同样的改变
# 改变的大小一样，方向正好相反
alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])
# 对 alpha[i] 和 alpha[j] 进行优化之后，给它们设置一个常数项 b
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(alphaPairsChanged == 0):
iter += 1
else:
iter = 0
print('iteration number: %d' % iter)
return b, alphas
在 python 提示符下，执行代码并得到结果：
b, alphas = svmMLiA.smoSimple(dataArr, labelArr, 0.6, 0.001, 40)再执行：
>>> for i in range(100):
... if alphas[i] > 0.0:
... print(dataArr[i], labelArr[i])
...
[3.542485, 1.977398] -1.0
[7.108772, -0.986906] 1.0
[4.658191, 3.507396] -1.0
[7.40786, -0.121961] 1.0
[3.457096, -0.082216] -1.0
[5.286862, -2.358286] 1.0
[6.080573, 0.418886] 1.0
[6.543888, 0.433164] 1.0
[1.966279, -1.840439] -1.0
所输出的数据点即为支持向量。
注：以上给出的仅是简化版SMO算法的实现，关于完整的SMO算法加速优化并应用核函数，请参照《机器学习实战》第 99 页。
不足之处，欢迎指正。
