实现步骤: 自己动手实现 SVM以上都为推导部分，实现代码主要围绕对目标函数的优化求解上，即序列最小优化算法部分。
清单 1. alpha1 选择1
2
3
4
5
6
| yI = diyObj.yMat[alphaI]
EI = calcE(alphaI, diyObj)
diyObj.E[alphaI] = [1, EI]
# if alpha1 violates KKT
if((yI * EI > diyObj.toler and diyObj.alphas[alphaI] > 0) or
(yI * EI < - diyObj.toler and diyObj.alphas[alphaI] < diyObj.C)):
|
选择违背 KKT 条件推导结果的 alpha 作为 alpha1，本代码中 diyObj.toler 取值为 0.0001。
清单 2. alpha2 选择1
2
3
4
5
6
7
8
| for j in nonzeroEIndex:
if alphaI == j: continue
EJtemp = calcE(j, diyObj)
deltaE = abs(EI - EJtemp)
if(deltaE > maxDelta):
maxDelta = deltaE
alphaJ = j
EJ = EJtemp
|
alpha2 的选择遵循步长最大化，即 E 值与 alpha1 的 E 值相差最大的 alpha 选为 alpha2。
清单 3. alpha1,alpha2,b 求解1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| alpha1old = diyObj.alphas[alphaI].copy()
alpha2old = diyObj.alphas[alphaJ].copy()
eta = diyObj.K[alphaI,alphaI] + diyObj.K[alphaJ, alphaJ] - 2 * diyObj.K[alphaI, alphaJ]
if eta <= 0: return 0
alpha2newUnclip = alpha2old + yJ * (EI - EJ) / eta
if(yI == yJ):
L = max(0, alpha1old + alpha2old - diyObj.C)
H = min(diyObj.C, alpha1old + alpha2old)
else:
L = max(0, alpha2old - alpha1old)
H = min(diyObj.C, diyObj.C - alpha1old + alpha2old)
if L == H: return 0
alpha2new = clipAlpha(alpha2newUnclip, L, H)
if abs(alpha2new - alpha2old) < 0.00001: return 0
alpha1new = alpha1old + yI * yJ * (alpha2old - alpha2new)
b1new = - EI - yI * diyObj.K[alphaI,alphaI] * (alpha1new - alpha1old) \
- yJ * diyObj.K[alphaJ, alphaI] * (alpha2new - alpha2old) + diyObj.b
b2new = - EJ - yI * diyObj.K[alphaI,alphaJ] * (alpha1new - alpha1old) \
- yJ * diyObj.K[alphaJ, alphaJ] * (alpha2new - alpha2old) + diyObj.b
b = calcb(b1new, b2new)
|
先算出 alpha 取值的上下界，求出 alpha2 后用上下界进行裁剪。用裁剪后的 alpha2 新值计算 alpha1 新值。b 的取值由 b1 和 b2 综合决定。
清单 4. 核函数1
2
3
4
5
6
7
8
9
10
| def transfer2Kernel(X, Xi, kernelParam):
m = shape(X)[0]
Ktemp = mat(zeros((m, 1)))
if kernelParam[0]=="rbf":
for i in range(m):
xdelta = X[i,:] - Xi
Ktemp = xdelta * xdelta.T
Ktemp = exp(-Ktemp/kernelParam[1]**2)
else: raise NameError("undefined kernel name!")
return Ktemp
|
本代码中使用高斯核完成从低维到高维的映射。
代码下载 (code downloads)本文所有 SVM 实现代码可在文末下载。
本文数据集简介图 6. 数据集样例 数据集是献血中心关于某人是否在 2007 年三月献血的数据。前四列分别代表距离上次献血的月份数、总献血次数、总献血毫升数、距离第一次献血的月份数。最后一列代表是否在 2007 年三月献血，1 代表是，-1 代表否。本数据集共 748 条。
应用示例: 应用实现的 SVM 解决实际问题清单 5. 用 SVM 解决实际问题1
2
3
4
5
6
7
8
9
10
11
| dataMat,yMat = loadDataset("bloodTransfusion.txt")
alphas,b = smo(dataMat, yMat, 200, 0.0001,100, ("rbf",20))
#yi of testData: 1,1,1,-1,-1,-1,-1,1,1,-1
testData = [[2,50,12500,98],[0,13,3250,28],[1,16,4000,35],[1,24,6000,77],[4,4,1000,4]
,[1,12,3000,35],[4,23,5750,58],[2,7,1750,14],[2,10,2500,28],[1,13,3250,47]]
m, n = shape(testData)
testmat = mat(testData)
for i in range(m):
kernelEval = transfer2Kernel(mat(dataMat), testmat[i,:],("rbf",20))
predict = kernelEval.T * multiply(mat(yMat).transpose(), alphas) + b
print(sign(predict))
|
用 bloodTransfusion 数据集训练 SVM 模型，得到该模型的 alpha 矩阵和 b 值。然后将 10 条测试数据输入模型中，输出结果为 10 条测试数据对应的预测值。
表 1. 应用本文实现的 SVM 对 10 条数据进行预测的结果示例特征值预测值真实值 [2,50,12500,98] 1 1 [0,13,3250,28] 1 1 [1,16,4000,35] -1 1 [1,24,6000,77] -1 -1 [4,4,1000,4] -1 -1 [1,12,3000,35] -1 -1 [4,23,5750,58] -1 -1 [2,7,1750,14] -1 1 [2,10,2500,28] 1 1 [1,13,3250,47] -1 -1
从表中可以看出，8 条数据分类正确，2 条数据分类有误。要想提高模型准确度，可以修改模型参数如最大迭代数、C 惩罚系数、高斯核参数等。
总结本文首先介绍了机器学习的体系框架，接着详细深入地讲解了 SVM 的基本原理，分别为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数和序列最小优化等。通过代码样例，介绍了在自己动手实现 SVM 模型时的思路。最后，用献血中心的数据展示了如何应用 SVM 解决实际问题。本文的内容不算高深，读者如果能静下心来细读，将会有很大收获。如若文中有纰漏的地方，欢迎广大读者留言指正，也很期待在接下来的机器学习系列文章中继续和志同道合的读者相遇。 |
