前面已经对感知机和SVM进行了简要的概述，本节是SVM算法的实现过程用于辅助理解SVM算法的具体内容，然后借助sklearn对SVM工具包进行实现。
SVM算法的核心是SMO算法的实现，首先对SMO算法过程进行实现，先对一些辅助函数进行定义：
1 # 先定义一些辅助函数 2 # 选取第二变量函数 3 def select_J_rand(i, m): 4 j=i 5 while(j==i): 6 j = int(random.uniform(0, m)) 7 return j 8 9 # 定义对α进行裁剪的函数 10 def clip_alpha(aj, H, L): 11 if aj > H: 12 aj=H 13 if L > aj: 14 aj = L 15 return aj
然后实现一个简化版的SMO算法：
"""
Input：dataX, dataY, C(惩罚因子), toler（容忍度）, iter_num
Output: alpha、b
"""
def smo_simple(dataX, dataY, C, toler, iter_num): dataMatrix = mat(dataX); labelMat = dataY.transpose() # 初始化参数 b = 0; m, n = np.shape(dataMatrix) alphas = mat(np.zeros((m, 1))) iter = 0 # 当超过迭代次数停止 while iter < iter_num: # 记录α1和α2变化次数 alphaPairsChanged = 0 for i in range(m): # 计算f(xi),预测类别 fXi = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b # 计算误差 Ei = fXi - float(labelMat[i]) # 当不满足条件时，选取变量j，这里要判断α是否在[0,C]内，若超出范围则不再进行优化 if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and alphas[i] > 0): j = select_J_rand(i, m) # 计算x2的预测值y2 fXj = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j, :].T)) + b Ej = fXj - float(labelMat[j]) alpha_I_old = alphas[i].copy() alpha_J_old = alphas[j].copy() 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[i] + alphas[j] - C) H = min(C, alphas[i] + alphas[j]) if L == H: print("L == H") continue 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 alphas[j] -= labelMat[j] * (Ej - Ei)/eta alphas[j] = clip_alpha(alphas[j], H, L) # 当α2不再变化 if (abs(alphas[j]-alpha_J_old) < 0.00001): print("j not moving enough") continue # 更新α1 alphas[i] += labelMat[i] * labelMat[j] * (alpha_J_old - alphas[j]) # 计算b1和b2 b1 = b - Ei - labelMat[i] * (alphas[i] - alpha_I_old) * dataMatrix[i, :] * dataMatrix[i, :].T - labelMat[j] * (alphas[j] - alpha_J_old) * dataMatrix[i, :] * dataMatrix[j, :].T b2 = b - Ej - labelMat[i] * (alphas[i] - alpha_I_old) * dataMatrix[i, :] * dataMatrix[j, :].T - labelMat[j] * (alphas[j] - alpha_J_old) * dataMatrix[j, :] * dataMatrix[j, :].T if (alphas[i] > 0) and (alphas[i] < C): b = b1 elif (alphas[j] > 0) and (alphas[j] < C): b = b2 else: b = (b1 + b2)/2 alphaPairsChanged += 1 if alphaPairsChanged == 0: iter += 1 else: iter = 0 print("iteration number: %d"%iter) return b, alphas
SMO算法具有一定的随机性，因此每次运行的结果不一定相同。上面就是一个简单的SMO算法的实现部分，对于小批量数据可以满足需求，但当数据量过于庞大时，上面的算法的效率将会很慢，这是因为在α的选择问题上，下面提供一种改进的SMO算法，改进的SMO算法会通过一个外循环选择第一个α的值，选择方法是在遍历所有样本（数据集）和非边界α中进行扫描，所谓非边界α是指那些不等于0或者C的α值，建立这些α值的列表，在列表中进行遍历，并在扫描时跳过不再改变的α进行遍历。下面是具体实现过程
首先定义辅助函数用于存储和更新E，并建立一个数据结构存储变量
1 # 首先建立3个辅助函数用于对E进行缓存，以及1种用于存储数据的数据结构 2 # 存储变量的数据结构 3 class optStruct: 4 def __init__(self, dataX, dataY, C, toler): 5 self.X = dataX 6 self.Y = dataY 7 self.C = C 8 self.toler = toler 9 self.m = np.shape(dataX)[0] 10 self.alphas = np.mat(zeros((self.m, 1))) 11 self.b = 0 12 # cache第一列为有效性标志位，第二列为E值 13 self.eCache = np.mat(np.zeros((self.m, 2))) 14 15 # 计算E值并返回，由于频繁使用单独写成一个函数 16 def calcEk(oS, k): 17 fXk = float(np.multiply(oS.alphas, oS.labelMat).T * (oS.X * oS.X[k, :].T)) + oS.b 18 Ek = fXk - float(oS.labelMat[k]) 19 return Ek 20 21 # 用于选择第二个α的值，保证每次优化采用最大的步长 22 def select_J(i, oS, Ei): 23 maxK = -1; maxDeltaE = 0; Ej = 0 24 oS.eCache[i] = [1, Ei] 25 validEcacheList = nonzero(oS.eCache[:, 0].A)[0] 26 if len(validEcacheList) > 1: 27 for k in validEcacheList: 28 if k == i: 29 continue 30 Ek = calcEk(oS, k) 31 deltaE = abs(Ei - Ek) 32 # 选择变化最大的那个 33 if deltaE > maxDeltaE: 34 maxK = k 35 maxDeltaE = deltaE 36 Ej = Ek 37 return maxK, Ej 38 else: 39 j = select_J_rand(i, oS.m) 40 Ej = calcEk(oS, j) 41 return j, Ej 42 43 44 def updateEk(oS, k): 45 Ek = calcEk(oS, k) 46 oS.eCache[k] = [1, Ek]
接下来就是SMO算法的改进版本
1 # 与simpleSMO一致，更新的alpha存入cache中 2 def innerL(i, oS): 3 Ei = calcEk(oS, i) 4 if ((oS.labelMat[i] * Ei < -oS.toler) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i] * Ei > oS.toler) and (oS.alphas[i] > 0)): 5 j, Ej = select_J(i, oS, Ei) 6 alpha_I_old = oS.alphas[i].copy() 7 alpha_J_old = oS.alphas[j].copy() 8 if oS.labelMat[i] != oS.labelMat[j]: 9 L = max(0, oS.alphas[j] - oS.alphas[i]) 10 H = min(oS.C, oS.C+ oS.alphas[j] - oS.alphas[i]) 11 else: 12 L = min(0, oS.alphas[i] + oS.alphas[j] - oS.C) 13 H = max(oS.C, oS.alphas[i] + oS.alphas[j]) 14 if H == L: 15 return 0 16 eta = 2.0 * oS.X[i, :] * oS.X[j, :].T - oS.X[i, :] * oS.X[i, :].T - oS.X[j, :] * oS.X[j, :].T 17 if eta >= 0: 18 return 0 19 oS.alphas[j] -= oS.labelMat[j] * (Ei - Ej)/eta 20 oS.alphas[j] = clip_alpha(oS.alphas[j], H, L) 21 updateEk(oS, j) 22 if abs(oS.alphas[j] - alpha_J_old) < 0.00001: 23 return 0 24 oS.alphas[i] -= oS.labelMat[i] * oS.labelMat[j] * (oS.alphas[j] - alpha_J_old) 25 updateEk(oS, i) 26 b1 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i] - alpha_I_old) * oS.X[i, :] * oS.X[i, :].T - oS.labelMat[j] * (oS.alphas[j] - alpha_J_old) * oS.X[i, :] * oS.X[j, :].T 27 b2 = oS.b - Ej - oS.labelMat[i] * (oS.alphas[i] - alpha_I_old) * oS.X[i, :] * oS.X[j, :].T - oS.labelMat[j] * (oS.alphas[j] - alpha_J_old) * oS.X[j, :] * oS.X[j, :].T 28 if oS.alphas[i] > 0 and oS.alphas[i] < oS.C: 29 oS.b = b1 30 elif oS.alphas[j] > 0 and oS.alphas[j] < oS.C: 31 oS.b = b2 32 else: 33 os.b = (b1 + b2)/2 34 return 1 35 else: 36 return 0 37 38 39 def smoP(dataX, labelMat, C, toler, maxIter, kTup=('lin', 0)): 40 oS = optStruct(mat(dataX), mat(labelMat).transpose(), C, toler) 41 iter = 0 42 entireSet = True 43 alphaPairsChanged = 0 44 while (iter < maxIter) and alphaPairsChanged > 0 or entireSet: 45 alphaPairsChanged = 0
# 搜索第一个变量的值，采用两个方法交替进行的方式，利用entireSet变量控制 46 # 第一种遍历全体样本 47 if entireSet: 48 for i in range(oS.m): 49 alphaPairsChanged += innerL(i, oS) 50 iter += 1 51 # 第二种遍历非边界样本 52 else: 53 nonBoundIs = nonzero((oS.alphas.A > 0) * oS.alphas.A < C)[0] 54 for i in nonBoundIs: 55 alphaPairsChanged += innerL(i, oS) 56 iter += 1 57 if entireSet: 58 entireSet = False 59 elif alphaPairsChanged == 0: 60 entireSet = True 61 return oS.alphas, oS.b
获取到α的值后，则可以进一步求出模型的w和b，具体实现过程为:
1 def calW(alphas, dataArr, classLabels): 2 X = mat(dataArr) 3 labelMat = mat(classLabels).transpose() 4 m, n = shape(X) 5 w = zeros((m, 1)) 6 for i in range(m): 7 w += multiply(alphas[i] * labelMat[i], X[i, :]) 8 return w
上述即为SVM的实现过程，是对线性可分的数据的分类的实现过程，当对于非线性数据，需要运用到核函数，在实现过程中也较为简单，只需只需将（xi·xj）替换为核函数即可，具体实现过程如下
1 # 首先原先的数据结构中要计算核矩阵，将下述代码加入数据结构代码部分即可 2 self.K = mat(zeros(self.m, self.m)) 3 for i in range(self.m): 4 self.K[:, i] = kernelTrans(self.X, self.X[i, :], self.kTup)
接下来实现核转换函数
1 def kernelTrans(X, A, kTup): 2 m, n = shape(X) 3 K = mat(zeros((m, 1))) 4 if kTup['0'] == 'lin': 5 K = X * A.T 6 elif kTup[0] == 'rbf': 7 for j in range(m): 8 deltaRow = X[j, :] - A 9 K[j] = deltaRow * deltaRow.T 10 K = exp(K/(-1 * kTup[1] ** 2)) 11 else: 12 raise NameError('没有定义核函数') 13 return K
然后需要在参数计算的函数中将对应的xi*xj替换为核函数即可：
1 # 首先是innerL中 2 eta = 2.0 * oS.K[i, j] - oS.K[i, i] - oS.K[j, j] 3 b1 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i] - alpha_I_old) * oS.K[i, i] - oS.labelMat[j] * (oS.alphas[j] - alpha_J_old) * oS.K[i, j] 4 b2 = oS.b - Ej - oS.labelMat[i] * (oS.alphas[i] - alpha_I_old) * oS.K[i, j] - oS.labelMat[j] * (oS.alphas[j] - alpha_J_old) * oS.K[j, j] 5 6 # 然后是calcEk 7 fXk = float(multiply(oS.alphas, oS.labelMat).T * oS.K[:, k] + oS.b)
至此，SVM算法的实现过程基本已经完成了，接下来我们利用MNIST的数据集，对手写数字进行分类和辨识，MNIST手写辨识数据在网上就可以找到。
首先需要写一个读取数据的函数以及将函数图像转化为矩阵的函数：
1 def img2Vector(filename): 2 returnVec = zeros((1, 1024)) 3 fr = open(filename) 4 for i in range(32): 5 lineStr = fr.readline() 6 for j in range(32): 7 returnVec[0, 32*i + j] = int(lineStr[j]) 8 return returnVec
1 def loadImages(dir): 2 hwLabels = [] 3 trainingFileList = os.listdir(dir) 4 m = len(trainingFileList) 5 for i in range(m): 6 fileNameStr = trainingFileList[i] 7 fileStr = fileNameStr.split('.')[0] 8 classNumStr = int(fileStr.split('_')[0])
# 只考虑二分类问题 9 if classNumStr == 9: 10 hwLabels.append(-1) 11 else: 12 hwLabels.append(1) 13 trainingMat[i, :] = img2Vector('%s/%s' % (dir, fileNameStr)) 14 return trainingMat, hwLabels
然后编写主程序，用于分类和测试。
1 def testDigits(kTup=('rbf', 10)):
# 获取数据 2 dataArr, labelArr = loadImages('trainingDigits')
# 利用SMO算法求解出α和b 3 alphas, b = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup) 4 dataMat = mat(dataArr) 5 labelMat = mat(labelArr).transpose()
# 获取支持向量的索引 6 svInd = nonzero(alphas.A > 0)[0]
# 获取支持向量 7 svs = dataMat[svInd] 8 labelSv = labelMat[svInd] 9 m, n = shape(dataMat) 10 errorCount = 0 11 for i in range(m): 12 kernelEval = kernelTrans(svs, dataMat[i, :], kTup) 13 predict = kernelEval.T * multiply(labelSv, alphas[svInd]) + b 14 if sign(predict) != sign(labelArr[i]): 15 errorCount += 1 16 print('there are %d Support Vectors'%shape(svs)[0]) 17 print('the error rate is %f' % (errorCount / (len(labelMat)))) 18 test_dataArr, test_labelArr = loadImages('testDigits') 19 test_dataMat = mat(test_dataArr) 20 test_labelMat = mat(test_labelArr).transpose() 21 m1, n1 = shape(test_dataMat) 22 test_errorCount = 0 23 for i in range(m1): 24 kernelEval = kernelTrans(svs, test_dataMat[i, :], kTup) 25 predict = kernelEval.T * multiply(labelSv, alphas[svInd]) + b 26 if sign(predict) != sign(test_labelArr[i]): 27 errorCount += 1 28 print('the error rate is %f' % (test_errorCount / (len(test_labelMat))))
输出结果如下：
至此，上述是一个完整的SVM算法用于二分类的实现过程，核函数可以进行修改和替换，同时，对于多分类情况相当于建立多个分类器进行分类，过程这里不再赘述，接下来，使用python中sklearn包对Mnist的数据集分类实现一遍。
首先是从sklearn导入svm包，并读取数据
1 from sklearn import svm 2 train_dataArr, train_labelArr = loadImages(dir)
然后是模型的初始化，这里模型中有一些参数，其具体说明如下
1 model = svm.SVC(C=200, kernel='rbf', tol=1e-4, max_iter=-1, degree=3, gamma='auto_deprecated', coef0=0, shrinking=True, 2 probability=False, cache_size=200, verbose=False, class_weight=None, decision_function_shape='ovr') 3 """ 4 C: 惩罚因子，默认为1.0，C越大，相当于惩罚松弛变量，希望松弛变量接近0，即对误分类的惩罚增大，趋向于对训练集全分对的情况，这样对训练集测试时准确率很高，但泛化能力弱。C值小，对误分类的惩罚减小，允许容错，将他们当成噪声点，泛化能力较强。 5 tol: 容忍度阈值 6 max_iter: 迭代次数 7 kernel：核函数，包括: 8 linear(线性核)：u*v 9 poly(多项式核):(gamma * u * v + coef0)^degree 10 rbf(高斯核): exp(-gamma|u-v|^2) 11 sigmoid核: tanh(gamma*u*v + coef0) 12 degree: 多项式核中的维度 13 gamma： 核函数中的参数，默认为“auto”，选择1/n_features 14 coef： 多项式核和simoid核中的常数项，仅对这两个核函数有效 15 probability: 是否采用概率估计，默认为False 16 shrinking： 是否采用shrinking heuristic方法，默认为true 17 cache_size: 核函数的缓存大小，默认为200 18 verbose: 是否允许冗余输出 19 class_weight: 类别权重 20 decision_function_shape: 可以取'ovo'一对一和'ovr'一对其他 21 """
然后就是数据进行训练，并查看训练准确率
1 model.fit(mat(train_dataArr), mat(train_labelArr).transpose()) 2 train_score = model.score(mat(train_dataArr), mat(train_labelArr).transpose()) 3 print('训练集上的准确率为%s'%train_score) 4 5 test_dataArr, test_labelArr = loadImages('E:\资料\PythonML_Code\Charpter 5\data\\testDigits'.format(dir)) 6 test_score = model.score(mat(test_dataArr), mat(test_labelArr).transpose()) 7 print('测试集上的准确率为%f' % test_score)
最终结果为：
至此，SVM的基本内容已基本完毕，此外还有利用SVM进行线性回归的算法以及采用SVM算法进行半监督学习的算法，后面看到这一块会进一步完善这一块内容。