本篇内容为《机器学习实战》第 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 sysfrom 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 页。
不足之处，欢迎指正。