今天跟大家介绍的是SVM算法原理以及实现,废话不多说,直接来看干货吧!
一、SVM概念
SVM的全称为Support Vector Machine,也就是我们经常提到的支持向量机,主要被用来解决模式识别领域中的数据分类问题,是一种有监督学习算法。
具体解释一下:
Support Vector,支持向量,指的是训练样本集中的某些训练点,这些训练点非常靠近分类决策面,因此是最难分类的数据点。SVM中最优分类标准为:这些点与分类超平面之间的距离达到最大值;
Machine“机”,指的是机器学习领域对一些算法的统称,通常我们把算法看做一个机器或学习函数。SVM是一种有监督的学习方法,主要是针对小样本数据的学习、分类和预测。
二、SVM的优点
1、需要的样本数量不是很大,但这并不表示SVM训练样本的绝对量很少,只是说与其他训练分类算法相比,在同样的问题复杂度情况下,SVM对样本的需求相对是较少的。而且SVM引入了核函数,因此即使是高维的样本,SVM也能轻松应对。
2、结构风险最小。这种风险指的是分类器对问题真实模型的逼近,以及问题真实解之间的累积误差。
3、非线性,指的是:SVM非常擅长应付样本数据线性不可分的情况,通常是利用松弛变量(或者叫惩罚变量)以及核函数技术来实现的,这也是SVM的精髓所在。
三、SVM的原理
1.点到超平面的距离公式
超平面的方程也可以写成一下形式:
假设P(x1.x2...xn)为样本的中的一个点,其中xi表示为第个特征变量。那么该点到超平面的距离d就可以用如下公式进行计算:
其中||w||为超平面的2范数,也就是w向量的模长,常数b类似于直线方程中的截距。
2.最大间隔的优化模型
其中y代表数据点的标签,并且其为-1或1.若数据点在平面的正方向(也就是+1类),那么就是一个正数,而如果数据点在平面的负方向的情况下(即-1类),仍然是一个正数,这样就可以保证始终大于0了。我们需要注意,如果w和b等比例放大,d的结果不会改变。令u=y(wTx+b),所有支持向量的u为1.那么其他点的u大于1.我们可以通过调节w和b求到。这样一来,上面的问题可以简化为:
等价替换为:
这是一个有约束条件的优化问题,我们通常会用拉格朗日乘子法来求解。令:
四、python实现
#svm算法的实现 from numpy import* import random from time import* def loadDataSet(fileName):#输出dataArr(m*n),labelArr(1*m)其中m为数据集的个数 dataMat=[];labelMat=[] fr=open(fileName) 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 def selectJrand(i,m):#随机找一个和i不同的j j=i while(j==i): j=int(random.uniform(0,m)) return j def clipAlpha(aj,H,L):#调整大于H或小于L的alpha的值 if aj>H: aj=H if aj<L: aj=L return aj def smoSimple(dataMatIn,classLabels,C,toler,maxIter): dataMatrix=mat(dataMatIn);labelMat=mat(classLabels).transpose()#转置 b=0;m,n=shape(dataMatrix)#m为输入数据的个数,n为输入向量的维数 alpha=mat(zeros((m,1)))#初始化参数,确定m个alpha iter=0#用于计算迭代次数 while (iter<maxIter):#当迭代次数小于最大迭代次数时(外循环) alphaPairsChanged=0#初始化alpha的改变量为0 for i in range(m):#内循环 fXi=float(multiply(alpha,labelMat).T*\ (dataMatrix*dataMatrix[i,:].T))+b#计算f(xi) Ei=fXi-float(labelMat[i])#计算f(xi)与标签之间的误差 if ((labelMat[i]*Ei<-toler)and(alpha[i]<C))or\ ((labelMat[i]*Ei>toler)and(alpha[i]>0)):#如果可以进行优化 j=selectJrand(i,m)#随机选择一个j与i配对 fXj=float(multiply(alpha,labelMat).T*\ (dataMatrix*dataMatrix[j,:].T))+b#计算f(xj) Ej=fXj-float(labelMat[j])#计算j的误差 alphaIold=alpha[i].copy()#保存原来的alpha(i) alphaJold=alpha[j].copy() if(labelMat[i]!=labelMat[j]):#保证alpha在0到c之间 L=max(0,alpha[j]-alpha[i]) H=min(C,C+alpha[j]-alpha[i]) else: L=max(0,alpha[j]+alpha[i]-C) H=min(C,alpha[j]+alpha[i]) if L==H:print('L=H');continue eta=2*dataMatrix[i,:]*dataMatrix[j,:].T-\ dataMatrix[i,:]*dataMatrix[i,:].T-\ dataMatrix[j,:]*dataMatrix[j,:].T if eta>=0:print('eta=0');continue alpha[j]-=labelMat[j]*(Ei-Ej)/eta alpha[j]=clipAlpha(alpha[j],H,L)#调整大于H或小于L的alpha if (abs(alpha[j]-alphaJold)<0.0001): print('j not move enough');continue alpha[i]+=labelMat[j]*labelMat[i]*(alphaJold-alpha[j]) b1=b-Ei-labelMat[i]*(alpha[i]-alphaIold)*\ dataMatrix[i,:]*dataMatrix[i,:].T-\ labelMat[j]*(alpha[j]-alphaJold)*\ dataMatrix[i,:]*dataMatrix[j,:].T#设置b b2=b-Ej-labelMat[i]*(alpha[i]-alphaIold)*\ dataMatrix[i,:]*dataMatrix[i,:].T-\ labelMat[j]*(alpha[j]-alphaJold)*\ dataMatrix[j,:]*dataMatrix[j,:].T if (0<alpha[i])and(C>alpha[j]):b=b1 elif(0<alpha[j])and(C>alpha[j]):b=b2 else:b=(b1+b2)/2 alphaPairsChanged+=1 print('iter:%d i:%d,pairs changed%d'%(iter,i,alphaPairsChanged)) if (alphaPairsChanged==0):iter+=1 else:iter=0 print('iteraction number:%d'%iter) return b,alpha #定义径向基函数 def kernelTrans(X, A, kTup):#定义核转换函数(径向基函数) m,n = shape(X) K = mat(zeros((m,1))) if kTup[0]=='lin': K = X * A.T #线性核K为m*1的矩阵 elif kTup[0]=='rbf': for j in range(m): deltaRow = X[j,:] - A K[j] = deltaRow*deltaRow.T K = exp(K/(-1*kTup[1]**2)) #divide in NumPy is element-wise not matrix like Matlab else: raise NameError('Houston We Have a Problem -- \ That Kernel is not recognized') return K class optStruct: def __init__(self,dataMatIn, classLabels, C, toler, kTup): # Initialize the structure with the parameters self.X = dataMatIn self.labelMat = classLabels self.C = C self.tol = toler self.m = shape(dataMatIn)[0] self.alphas = mat(zeros((self.m,1))) self.b = 0 self.eCache = mat(zeros((self.m,2))) #first column is valid flag self.K = mat(zeros((self.m,self.m))) for i in range(self.m): self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup) def calcEk(oS, k): fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b) Ek = fXk - float(oS.labelMat[k]) return Ek def selectJ(i, oS, Ei): maxK = -1; maxDeltaE = 0; Ej = 0 oS.eCache[i] = [1,Ei] validEcacheList = nonzero(oS.eCache[:,0].A)[0] if (len(validEcacheList)) > 1: for k in validEcacheList: #loop through valid Ecache values and find the one that maximizes delta E if k == i: continue #don't calc for i, waste of time Ek = calcEk(oS, k) deltaE = abs(Ei - Ek) if (deltaE > maxDeltaE): maxK = k; maxDeltaE = deltaE; Ej = Ek return maxK, Ej else: #in this case (first time around) we don't have any valid eCache values j = selectJrand(i, oS.m) Ej = calcEk(oS, j) return j, Ej def updateEk(oS, k):#after any alpha has changed update the new value in the cache Ek = calcEk(oS, k) oS.eCache[k] = [1,Ek] def innerL(i, oS): Ei = calcEk(oS, i) if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)): j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy() if (oS.labelMat[i] != oS.labelMat[j]): L = max(0, oS.alphas[j] - oS.alphas[i]) H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i]) else: L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C) H = min(oS.C, oS.alphas[j] + oS.alphas[i]) if L==H: print("L==H"); return 0 eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j] #changed for kernel if eta >= 0: print("eta>=0"); return 0 oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta oS.alphas[j] = clipAlpha(oS.alphas[j],H,L) updateEk(oS, j) #added this for the Ecache if (abs(oS.alphas[j] - alphaJold) < 0.00001): print("j not moving enough"); return 0 oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j updateEk(oS, i) #added this for the Ecache #the update is in the oppostie direction b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j] b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j] if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1 elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2 else: oS.b = (b1 + b2)/2.0 return 1 else: return 0 #smoP函数用于计算超平的alpha,b def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)): #完整的Platter SMO oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup) iter = 0#计算循环的次数 entireSet = True; alphaPairsChanged = 0 while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)): alphaPairsChanged = 0 if entireSet: #go over all for i in range(oS.m): alphaPairsChanged += innerL(i,oS) print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)) iter += 1 else:#go over non-bound (railed) alphas nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0] for i in nonBoundIs: alphaPairsChanged += innerL(i,oS) print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)) iter += 1 if entireSet: entireSet = False #toggle entire set loop elif (alphaPairsChanged == 0): entireSet = True print("iteration number: %d" % iter) return oS.b,oS.alphas #calcWs用于计算权重值w def calcWs(alphas,dataArr,classLabels):#计算权重W X = mat(dataArr); labelMat = mat(classLabels).transpose() m,n = shape(X) w = zeros((n,1)) for i in range(m): w += multiply(alphas[i]*labelMat[i],X[i,:].T) return w #值得注意的是测试准确与k1和C的取值有关。 def testRbf(k1=1.3):#给定输入参数K1 #测试训练集上的准确率 dataArr,labelArr = loadDataSet('testSetRBF.txt')#导入数据作为训练集 b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, ('rbf', k1)) #C=200 important datMat=mat(dataArr); labelMat = mat(labelArr).transpose() svInd=nonzero(alphas.A>0)[0]#找出alphas中大于0的元素的位置 #此处需要说明一下alphas.A的含义 sVs=datMat[svInd] #获取支持向量的矩阵,因为只要alpha中不等于0的元素都是支持向量 labelSV = labelMat[svInd]#支持向量的标签 print("there are %d Support Vectors" % shape(sVs)[0])#输出有多少个支持向量 m,n = shape(datMat)#数据组的矩阵形状表示为有m个数据,数据维数为n errorCount = 0#计算错误的个数 for i in range(m):#开始分类,是函数的核心 kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))#计算原数据集中各元素的核值 predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b#计算预测结果y的值 if sign(predict)!=sign(labelArr[i]): errorCount += 1#利用符号判断类别 ### sign(a)为符号函数:若a>0则输出1,若a<0则输出-1.### print("the training error rate is: %f" % (float(errorCount)/m)) #2、测试测试集上的准确率 dataArr,labelArr = loadDataSet('testSetRBF2.txt') errorCount = 0 datMat=mat(dataArr)#labelMat = mat(labelArr).transpose()此处可以不用 m,n = shape(datMat) for i in range(m): kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1)) predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b if sign(predict)!=sign(labelArr[i]): errorCount += 1 print("the test error rate is: %f" % (float(errorCount)/m)) def main(): t1=time() dataArr,labelArr=loadDataSet('testSet.txt') b,alphas=smoP(dataArr,labelArr,0.6,0.01,40) ws=calcWs(alphas,dataArr,labelArr) testRbf() t2=time() print("程序所用时间为%ss"%(t2-t1)) if __name__=='__main__': main()
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14