机器学习实验

1、机器学习实训实验报告（三）专业班级学号姓名实验项目名称：支持向量机：以SOM算法优化求解实验内容：1、理解支持向量机的概念，以及相关理论知识2、了解SMO算法概念，及在支持向量机上的应用3、理解核函数概念，理解核函数将数据映射到高维空间实验过程：算法分析：SMO算法：1、概述SMO算法在支持向量机中用来 求解、对偶问题，即 而蓦EL 喝街辨妙（况的）-切 在这个问题中，变量是拉格朗日 乘子a，一个a i对应一个样本点 （xi,yi），变量总数等于样本数量 N。SMO算法是一个启发式的算法， 它的基本思路是：如果所有变量的解都满足KKT 条件，即：g 2 oJ 以3J（耳）一 1 十）=。AA

2、o6 0 0如果所有变量的解都慢着KKT 条件，那么这个最优化问题的解 就得到了，因为KKT条件是这个 最优化问题的充分必要条件。否则选择两个变量，固定其他变 量，针对这两个变量构建一个二 次规划问题，这个二次规划问题 的关于这两个变量的解应该更接 近原始二次规划问题的解，重要 的是，这两个变量可以通过解析 方法来求解。整个SMO算法有 两大部分组成，第一部分就是选 择这两个变量的启发式的方法， 第二部分是求解这两个变量的解 析方法。源程序代码：from time import sleepimport matplotlib.pyplot as pltimport numpy as npimpo

3、rt randomimport typesfrom numpy import *#函数说明:读取数据def loadDataSet(fileName):dataMat = ; labelMat =fr = open(fileName)for line in fr.readlines(): #逐行读取，滤除空格等lineArr = line.strip().split(t)dataMat.append(float(lineArr0), float(lineArr1) #添 加数据labelMat.append(float(lineArr 2) #添加标签return dataMat,labelM

4、at#函数说明:随机选择alphadef selectJrand(i, m):j = i#选择一个不等于i的jwhile (j = i):j = int(random.uniform(0, m)return j#函数说明:修剪alphadef clipAlpha(aj,H,L): #选取大于 H 小于 L 的 ajif aj H:aj = Hif L aj:aj = Lreturn aj#函数说明:简化版SMO算法def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#转换为numpydataMatrix=np.mat(dataMat

5、In);labelMat=np.mat(classLabels).tr anspose()#初始化b参数，统计dataMatrix的维度,m为个数，n为维数b = 0; m,n = np.shape(dataMatrix)2、第一个变量选择SMO称第一个变量的选择过程 为外层循环，外层循环要选择一 个违反KKT条件的变量，具体来 说，若ai=0，那么由 ai+gi=C 可知 gi=C 又因为心卓=0，所以卓=卓=0 也就是说要满足KKT条件要满 足yif(xi) N1同样的推导过程可以得到。 5 。T 茹/(四)=10 Q, = G T 策 J(g) 1若变量违反了 KKT条件，我们就 选择它

6、为第一个变量，在检验过程中，外层循环首先在 所有变量中遍历，遇到违反KKT 条件的变量就接着选择第二个变 量，然后在整个集合上遍历一次 后，然后在所有非边界变量上遍历所 谓非边界变量，就是指满足 0aiC的变量，为什么要这么遍历呢， 因为随着多次子优化过程，边界 变量倾向于留在边界，而非边界 变量倾向于波动，这一步启发式 的选择算法是基于节省时间考虑 的，并且算法会一直在非边界变 量集合上遍历，直到所有非边界 变量都满足KKT条件 (self-consistent)随后算法继续在整个集合上遍历 寻找违反KKT条件的变量作为 优化的第一个变量，要注意的是， 算法在整个集合上最多只连续遍 历一次，

7、但在非边界变量集合上 可能连续遍历多次3、第二个变量选择上面说了第一个变量的选择方 法，然后是第二个变量的选择方 法SMO称选择第二个变量的过程 为内层循环，第二个变量的选择 标准是希望a2有尽可能大的变 ,一。磨出, ,化，由上面 的计算公式可以知道，依赖于E1-E2/nPlatt原文说的是计算Kernel函数 太耗时了，所以就以|E1-E2|E1- E2|的最大值做为选择标准，但是#初始化alpha参数，设为0alphas = np.mat(np.zeros(m,1)#初始化迭代次数iter_num = 0#最多迭代matIter次(外循环)while (iter_num maxIter)

8、:alphaPairsChanged = 0 #初始化for i in range(m):#步骤1：计算fxi和标签的误差EifXi=float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrixi,:.T) + bEi = fXi - float(labelMati)#if语句：优化alpha，更设定一定的容错率。if (labelMati*Ei -toler) and (alphasi toler) and (alphasi 0):#随机选择另一个与alpha_i成对优化的alpha_jj = selectJrand(i,m)#步骤1

9、：计算误差EjfXj=float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrixj,:.T) + bEj = fXj - float(labelMatj)#保存原来的aplpha值alphalold = alphasi.copy(); alphaJold = alphasj.copy();#步骤2：计算上下界L和H，保证alhas在0 到c之间if (labelMati != labelMatj):L = max(0, alphasj - alphasi)H = min(C, C + alphasj - alphasi)else:L

10、= max(0, alphasj + alphasi - C)H = min(C, alphasj + alphasi)if L=H: print(L=H); continue#步骤3：计算etaeta = 2.0 * dataMatrixi,:*dataMatrixj,:.T - dataMatrixi,:*dataMatrixi,:.T - dataMatrixj,:*dataMatrixj,:.Tif eta = 0: print(eta=0”); continue#步骤4：更新alpha_jalphasj -= labelMatj*(Ei - Ej)/eta#步骤5：修剪alpha_j

11、alphasj = clipAlpha(alphasj,H,L)if (abs(alphasj - alphaJold) 0.00001): print(alpha_j 变化太小);continue#步骤6：更新alpha_ialphasi += labelMatj*labelMati*(alphaJold - alphasj)#步骤7：更新b_1和6_2b1= b - Ei-labelMati*(alphasi-alphaIold)*dataMatrixi,:*dataMatrixi,:.T - labelMatj*(alphasj-alphaJold)*dataMatrixi,:*data

12、Matrixj,:.Tb2 = b - Ej- labelMati*(alphasi-alphaIold)*dataMatrixi,:*dataMatrixj,:.T - labelMatj*(alphasj-alphaJold)*dataMatrixj,:*dataMatrixj,:.T#步骤8：根据b_1和6_2更新bif (0 alphasi): b = b1这里核矩阵应该是可以预处理出 来的。至此两个要优化的变量就选择了 出来但是这里还有一个小问题，如果 n为零，那么就会出现问题，也 就是说，如果有两个变量的特征 完全相同，那么会造成n为零， 这是要重新选择第二个变量。具体方法是，首先

13、在非边界元素 上遍历，注意这里要随机选择位 置，这是为了防止从头开始的话 算法偏好靠前的元素，如果非边 界元素上找不到使得nn大于零 的第二个变量，就在整个集合上 再遍历一次，如果这次也找不到， 那么就放弃第一个已经选择的变 量。调试过程中的关键问题及修改:elif (0 alphas。): b = b2 else: b = (bl + b2)/2.0#统计优化次数alphaPairsChanged += 1#打印统计信息print(iter:%d i:%d,pairs changed%d %(iter_num,i,alphaPairsChanged)#更新迭代次数if (alphaPairs

14、Changed = 0): iter_num += 1else: iter_num = 0print(”迭代次数:%d % iter_num)return b,alphasclass optStruct:def _init_(self, dataMatIn, classLabels, C, toler, kTup):self.X = dataMatIn #数据矩阵self.labelMat = classLabels #数据标签self.C = Cself.tol = toler # 容错率self.m = np.shape(dataMatIn)0 # 数据矩阵行数self.alphas =

15、np.mat(np.zeros(self.m,1) # 根据矩阵彳亍数初始化alpha参数为0self.b = 0 # 初始化 b=0self.eCache = np.mat(np.zeros(self.m,2)#根据矩阵行数初始化误差缓存，第一列为是否有效的标 志位，第二列为实际的误差E的值。self.K = np.mat(np.zeros(self.m,self.m) #初始化核 Kfor i in range(self.m): #计算所有数据的核Kself.K:,i = kernelTrans(self.X, self.Xi,:, kTup)#函数说明：计算误差def calcEk(oS

16、, k):fXk=float(np.multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.Xk,:.T)+oS.b)Ek = fXk - float(oS.labelMatk)return Ek#函数说明：内循环启发方式def selectJ(i, oS, Ei):maxK = -1; maxDeltaE = 0; Ej = 0 #初始化oS.eCachei = 1,Ei #根据Ei更新误差缓存validEcacheList = np.nonzero(oS.eCache:,0.A)0 # 返回误 差不为0的数据的索引值if (len(validEcacheLis

17、t) 1: #有不为 0 的误差 for k in validEcacheList: #遍历，找到最大的 Ek if k = i: continue #不计算i,浪费时间 Ek = calcEk(oS, k) #计算 Ek deltaE = abs(Ei - Ek) # 计算 IEi-Ekl if (deltaE maxDeltaE): #找到 maxDeltaE maxK = k; maxDeltaE = deltaE; Ej = Ekreturn maxK, Ej#返回 maxK,Ejelse:#没有不为0的误差j = selectJrand(i, oS.m) #随机选择 alpha j

18、的索引值Ej = calcEk(oS, j) #计算 Ej return j, Ej#函数说明：计算Ek,并更新误差缓存def updateEk(oS, k):Ek=calcEk(oS,k)#计算EkoS.eCachek=1,Ek#更新误差缓存#函数说明：优化的SOM算法def innerL(i, oS):#步骤1：计算误差EiEi = calcEk(oS, i)#优化alpha，设定一定的容错率。if (oS.labelMati * Ei -oS.tol) and (oS.alphasi oS.tol) and (oS.alphasi 0):#使用内循环启发方式2选择alpha_j，并计算E

19、jj,Ej = selectJ(i, oS, Ei)#保存更新前的aplpha值，使用深拷贝alphalold = oS.alphasi.copy(); alphaJold = oS.alphasj.copy();#步骤2：计算上下界L和Hif (oS.labelMati != oS.labelMatj):L = max(0, oS.alphasj - oS.alphasi)H = min(oS.C, oS.C + oS.alphasj - oS.alphasi) else:L = max(0, oS.alphasj + oS.alphasi - oS.C)H = min(oS.C, oS.a

20、lphasj + oS.alphasi)if L = H:print(L=H)return 0#步骤3：计算etaeta = 2.0 * oS.Ki,j - oS.Ki,i - oS.Kj,jif eta = 0:print(eta=0)return 0#步骤4：更新alpha_joS.alphasj -= oS.labelMatj * (Ei - Ej)/eta#步骤5：修剪alpha_joS.alphasj = clipAlpha(oS.alphasj,H,L)#更新Ej至误差缓存updateEk(oS, j)if (abs(oS.alphasj - alphaJold) 0.00001)

21、: print(alpha_j 变化太小”) return 0#步骤6：更新alpha_ioS.alphasi += oS.labelMatj*oS.labelMati*(alphaJold - oS.alphasj)#更新误差缓存updateEk(oS, i)#步骤7：更新b_1和b_2bl=oS.b-Ei-oS.labelMati*(oS.alphasi-alphaIold)*oS.Ki,i-oS.labelMatj*(oS.alphasj-alphaJold)*oS.Ki,jb2=oS.b-Ej-oS.labelMati*(oS.alphasi-alphaIold)*oS.Ki,j-oS

22、.labelMatj*(oS.alphasj-alphaJold)*oS.Kj,j#步骤8：根据b_1和b_2更新bif (0 oS.alphasi): oS.b = b1 elif (0 oS.alphasj): oS.b = b2 else: oS.b = (b1 + b2)/2.0 return 1else:return 0#函数说明：完整的线性SMO算法，用于计算超平的alpha,bdef smoP(dataMatIn, classLabels, C, toler, maxIter, kTup = (lin,0): oS=optStruct(np.mat(dataMatIn),np.m

23、at(classLabels).transpose(), C, toler, kTup)#初始化数据结构iter = 0#初始化当前迭代次数entireSet = True; alphaPairsChanged = 0while (iter 0) or (entireSet):#遍历整个数据集都alpha也没有更新或者超过最大迭代 次数，则退出循环alphaPairsChanged = 0if entireSet: #遍历整个数据集for i in range(oS.m):alphaPairsChanged += innerL(i,oS) #使用优化的 SMO算法print(全样本遍历:第%d

24、次迭代样本:%d, alpha 优化次数:d” % (iter,i,alphaPairsChanged)iter += 1else:#遍历非边界值nonBoundIs = np.nonzero(oS.alphas.A 0) * (oS.alphas.A 0)0# 获得支持向量sVs = datMatsvIndlabelSV = labelMatsvInd;print(支持向量个数:d” % np.shape(sVs)0)m,n = np.shape(datMat)errorCount = 0for i in range(m):kernelEval = kernelTrans(sVs,datMa

25、ti,:,(rbf, k1) #计算各个点的核算各个点的核predict=kernelEval.Tnp.multiply(labelSV,alphassvInd) + b#根据支持向量的点，#根据支持向量的点，计算超平面，返回预测结果if np.sign(predict) != np.sign(labelArri): errorCount += 1#返回数组中各元素的正负符号，用1和-1表示，并统计 错误个数print(训练集错误率：.2f% % (float(errorCount)/m)*100)#打印错误率dataArr,labelArr=loadDataSet(C:/Users/asus

26、/Desktop/machinelearninginaction/Ch06/testSetRBF2.txt)#加载测试集errorCount = 0 datMat = np.mat(dataArr);labelMatnp.mat(labelArr).transpose() m,n = np.shape(datMat) for i in range(m):kernelEval = kernelTrans(sVs,datMati,:,(rbf, k1) #计算各个点的核predict=kernelEval.T * np.multiply(labelSV,alphassvInd) + b#根据支持向

27、量的点，计算超平面，返回预测结果if np.sign(predict) != np.sign(labelArri): errorCount += 1#返回数组中各元素的正负符号，用1和-1表示，并统计 错误个数print(测试集错误率：.2f% % (float(errorCount)/m)*100)#打印错误率”基于SVM数字识别”#转换为向量def img2vector(filename):returnVect = zeros(1,1024)fr = open(filename)for i in range(32):lineStr = fr.readline()for j in range

28、(32):returnVect0,32*i+j = int(lineStrj)return returnVect#加载图像def loadlmages(dirName):from os import listdirhwLabels =trainingFileList = listdir(dirName)# 加载训练集m = len(trainingFileList)trainingMat = zeros(m,1024)for i in range(m):fileNameStr = trainingFileListifileStr = fileNameStr.split(.)0#关闭 txtcl

29、assNumStr = int(fileStr.split(_)0)if classNumStr = 9: #二分类hwLabels.append(-1)else:hwLabels.append(1)trainingMati,: = img2vector(%s/%s % (dirName, fileNameStr)return trainingMat, hwLabelsdef testDigits(kTup = (rbf, 10):dataArr,labelArr=loadImages(C:/Users/asus/Desktop/trainingDigits)#加载训练b, alphas =

30、smoP(dataArr, labelArr, 200, 0.0001, 1000, kTup) #根据训练集计算b和alphasdatMat=np.mat(dataArr);labelMat=np.mat(labelArr).transpose()svInd = np.nonzero(alphas.A 0)0# 获得支持向量sVs = datMatsvIndlabelSV = labelMatsvInd;print(支持向量个数:d” % np.shape(sVs)0)m,n = np.shape(datMat)errorCount = 0for i in range(m):kernelEv

31、al = kernelTrans(sVs,datMati,:,kTup) #计算各if namemain”简化版的som #dataMat,labelMat个点的核predict=kernelEval.Tnp.multiply(labelSV,alphassvInd) + b#根据支持向量的点，计算超平面，返回预测结果if np.sign(predict) != np.sign(labelArri): errorCount += 1#返回数组中各元素的正负符号，用1和-1表示，并统计 错误个数print(训练集错误率：.2f% % (float(errorCount)/m)*100)#打印错误

32、率dataArr,labelArr= loadImages(C:/Users/asus/Desktop/testDigits)errorCount = 0datMat=mat(dataArr); labelMat = mat(labelArr).transpose()m,n = shape(datMat)for i in range(m):kernelEval = kernelTrans(sVs,datMati,:,kTup) predict=kernelEval.T * multiply(labelSV,alphassvInd) + b if sign(predict)!=sign(labe

33、lArri): errorCount += 1 if sign(predict)!=sign(labelArri): errorCount += 1print(测试集错误率：.2f% % (float(errorCount)/m)*100)#打印错误率完整的线性SMO算法”loadDataSet(C:/Users/asus/Desktop/machinelearninginaction/Ch06/t estSet.txt)#b,alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)”完整的线性SMO算法”#dataArr,labelArr l

34、oadDataSet(C:/Users/asus/Desktop/machinelearninginaction/Ch06/t estSet.txt)#b,alphas = smoP(dataArr, labelArr, 0.6, 0.001, 40)测试函数”#testRbf()”基于SVM数字识别”testDigits(rbf, 20)6-1 IXS.UI kJ. l-M , II 1 4 A J. ja V，U JU U _!.VI IUIL_ I. LabelMat-1.0 da tMa t =rp. ma t (5a z a Ar i) datMat LUJ trip, mat (ws) +b matrlz (-0. 92555695) datMat E1 +np. mat(ws)+b matriz(El. 36706674) datMat2 4np. mat(ws)+b matriz(2. 30436335)T I 1 V . -. -) wz-cd1cA3(d1p?：3, datc.iVri.、匚、/ w-array( 0.65307162, -0. 17L9&L23)第醇策密勺弋4-疽勺弋弋-.