支持向量机(SVM) | 核技巧于SMO算法的实现

2024-02-10 15:08
文章标签 算法 实现 技巧 支持 向量 svm smo

本文主要是介绍支持向量机(SVM) | 核技巧于SMO算法的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01 核技巧

关于支持向量机，我们有这样的共识：

  1. 支持向量机是一种分类器，之所以叫“机”是因为它会产生一个二值决策结果，是一种决策机；
  2. 支持向量机的泛化误差较低，即，有良好的学习能力，且学到的模型具有很好的推广性，因此被认为是监督学习中最好的定式算法；
  3. 支持向量机通过求解一个二次优化问题来最大化分类间隔，在过去，训练SVM常采用非常复杂且低效的二次规划求解方法；1998年，Platt提出SMO算法，通过每次只优化两个alpha值来加快SVM训练速度。

在这篇文章中，我用python3实现了SMO算法，但是呢还有一个问题没有解决：

对于非线性数据集(比如圆环状分布的数据集)，该如何分类呢？

我们可以将输入空间的样本特征映射到高维特征空间，使得原本非线性的数据集变得线性可分，这就是“核技巧”，核技巧的一个形象过程，如下图所示：

本文将利用核技巧，改进之前写的SMO算法，用于分类非线性数据集，一起来看看吧～

02 核函数

核函数可以自己构造，不过实际应用中我们常使用已有的核函数，不同的核函数适用于不同分布的数据集，典型的几个核函数如下：

其中，高斯径向基函数适用于圆环状分布的数据集，本文将利用径向基函数对数据进行核技巧处理。

03 算法实现

整体逻辑与SMOpro一致，差别只在于用K(x,xi)替换了X,Xi内积

3.1辅助函数
def loadDataSet(filename):#filename是待读取文件的文件名或路径+文件名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,labelMatdef randPickj(i,m):#i是alphai的i值，整数; m是alpha个数; j不能等于ij=iwhile j==i:j=int(np.random.uniform(0,m))return jdef clipAlpha(aj,H,L):if aj>H:aj=Hif aj<L:aj=Lreturn aj
3.2 核转换函数(关键点)
# X为数据集特征矩阵，A为X[i,:]
# kTup为元组类型，第一个参数表示所用核函数类型，第二个参数表示径向基函数对应的到达率(大小与支持向量对分离超平面的影响程度正相关)
def kernelTrans(X,A,kTup):m,n=X.shapeK=np.mat(np.zeros((m,1)))if kTup[0]=="lin": #核函数类型为 线性函数K=X*A.Telif kTup[0]=="rbf": #核函数为 径向基函数for j in range(m): #遍历每个样本deltaRow=X[j,:]-A #Xj-XiK[j]=deltaRow*deltaRow.T #||Xj-Xi||**2K=np.exp(K/-kTup[1]**2) #径向基函数公式else:raise NameError("Kernel not recognized")return K

#这里构造一个对象，目的是将此对象作为一个数据结构来使用
class optStruct:def __init__(self,data,label,C,toler,kTup):#全局变量self.X=dataself.labelMatrix=labelself.C=Cself.toler=tolerself.m=data.shape[0] #m为样本数#初始化alpha矩阵、b、Es矩阵self.alphas=np.mat(np.zeros((self.m,1)))self.Es=np.mat(np.zeros((self.m,2))) #缓存误差，两列，第一列表示当前Ei是否有效，第二列表示当前的Ei值self.b=0#核技巧增加项，初始化K矩阵(K矩阵用于存放K(xi,xj)，维度为m*m)self.K=np.mat(np.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):gxk=float(np.multiply(oS.alphas,oS.labelMatrix).transpose()*oS.K[:,k]+oS.b)Ek=gxk-float(oS.labelMatrix[k])return Ek#选择相较ai具有最大步长(即Ei-Ej)的aj的函数
def selectJ(oS,i,Ei):maxK=-1;maxDeltaE=0;Ej=0 #DeltaE表示Ei-Ej,k表示DeltaE最大的样本点索引值，最终会将Ek赋值给EjoS.Es[i]=[1,Ei] #使Es矩阵第i位有效validEsList=np.nonzero(oS.Es[:,0].A)[0] #将Es矩阵中有效的Ei对应的索引值选出来，作为挑选j的池子if len(validEsList)>1:for k in validEsList:if k==i:continueEk=calcEk(oS,k)deltaE=abs(Ei-Ek)if deltaE>maxDeltaE:maxDeltaE=deltaE;maxK=k;Ej=Ekreturn maxK,Ejelse: #若validEsList只有一个Ei有效(初次循环)，则随机选取一个jj=randPickj(i,oS.m)Ej=calcEk(oS,j)return j,Ejdef updateEk(oS,k):Ek=calcEk(oS,k)oS.Es[k]=[1,Ek]
3.3 内循环
def innerL(i,oS):Ei=calcEk(oS,i)#判断Ei是否是违反KKT条件超过toler的点，若是再继续挑选jif (oS.labelMatrix[i]*Ei<-oS.toler and oS.alphas[i]<oS.C) or (oS.labelMatrix[i]*Ei>oS.toler and oS.alphas[i]>0):j,Ej=selectJ(oS,i,Ei)alphaIold=oS.alphas[i].copy();alphaJold=oS.alphas[j].copy()#计算L，Hif oS.labelMatrix[i]!=oS.labelMatrix[j]:L=max(0,oS.alphas[j]-oS.alphas[i]) #这里alpha[i]仍然等于alphaIoldH=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 #第一个跳出条件(跳出本次内循环，遍历下一个alpha进行更新)#计算etaeta=oS.K[i,i]+oS.K[j,j]-2.0*oS.K[i,j]if eta==0:print ("eta=0")return 0 #第二个跳出条件(因为eta=0不好处理，且出现情况较少，因此这里咱不处理，直接跳出)#根据统计学习方法中的结果公式得到alphaj的解析解，并更新Ej值oS.alphas[j]=oS.alphas[j]+oS.labelMatrix[j]*(Ei-Ej)/etaoS.alphas[j]=clipAlpha(oS.alphas[j],H,L)updateEk(oS,j) #更新Ej值#检验alphaj与alphaJold是否有足够大的改变，若改变不够大，说明与alpha旧值没有什么差异，跳出本次内循环if abs(oS.alphas[j]-alphaJold)<0.00001:print ("j not moving enough")return 0 #第三个跳出条件#约束条件让我们可以根据alphaJ求出alphaIoS.alphas[i]=oS.alphas[i]+oS.labelMatrix[i]*oS.labelMatrix[j]*(alphaJold-oS.alphas[j])updateEk(oS,i) #更新Ei值#更新b值,根据alpha是否在0～C决定更新的b值b1=-Ei-oS.labelMatrix[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i]\-oS.labelMatrix[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]+oS.bb2=-Ej-oS.labelMatrix[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]\-oS.labelMatrix[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]+oS.b#若ai或aj在(0,C)之间，则取b=bi或b=bj，若ai aj都不在(0,C)之间，取均值if oS.alphas[i]>0 and oS.alphas[i]<oS.C:oS.b=b1elif oS.alphas[j]>0 and oS.alphas[j]<oS.C:oS.b=b2else:oS.b=(b1+b2)/2.0return 1 #若执行到这里都没有return0跳出，说明已经完成了一个alpha对的更新，返回一个1else:return 0 #若ai不足够违反KKT条件，则return0跳出本次内循环
3.4 外循环
def SMOpro(data,label,C,toler,maxIter,kTup):oS=optStruct(np.mat(data),np.mat(label).transpose(),C,toler,kTup)iter=0;entireSet=True;alphaPairsChanged=0#当迭代次数达到上限(这里的迭代次数只要完成一次循环遍历就+1，不论该次循环遍历是否修改了alpha对)，或全集再无可修改的alpha对时，循环停止，计算完成while (iter<maxIter) and (entireSet or alphaPairsChanged>0):alphaPairsChanged=0if entireSet: #全集遍历for i in range(oS.m):alphaPairsChanged+=innerL(i,oS)print ("fullset, iter:%d i:%d, pairsChanged: %d" %(iter,i,alphaPairsChanged))iter+=1 #这里的迭代次数只要完成一次循环遍历就+1，不论该次循环遍历是否修改了alpha对else: #边界遍历boundIs=np.nonzero((oS.alphas.A>0)*(oS.alphas.A<oS.C))[0] #选择0<alpha<C的样本点的索引值(即边界点)for i in boundIs:alphaPairsChanged+=innerL(i,oS)print ("bound, iter:%d i:%d, pairsChanged: %d" %(iter,i,alphaPairsChanged))iter+=1#控制遍历往返于全集遍历和边界遍历if entireSet:entireSet=False #若本轮是全集遍历，则下一轮进入边界遍历(下一轮while条件中的entire是False)elif alphaPairsChanged==0:entireSet=True  #若本轮是边界遍历，且本轮遍历未修改任何alpha对，则下一轮进入全集遍历print ("iteration number: %d" %iter)return oS.b,oS.alphas

04 测试

我们用两个圆环分布的数据集测试这个利用了核技巧的SMO算法，数据集分布如下：

4.1 参数训练函数
def testRBF(C,toler,maxIter,kTup):#训练参数data,label=loadDataSet("testSetRBF.txt")b,alphas=SMOpro(data,label,C,toler,maxIter,kTup)print (b,"\n",alphas[alphas>0])#找到支持向量dataMat=np.mat(data);labelMat=np.mat(label).transpose()svInd=np.nonzero(alphas.A>0)[0] #返回alpha>0的点的索引(即，支持向量点位置)svs=dataMat[svInd];labelSV=labelMat[svInd] #支持向量样本点特征和类型print ("There are %d Support Vectors" %svs.shape[0])#模型对于训练集的预测误差m,n=dataMat.shape;errorCount=0for i in range(m):kernelEval=kernelTrans(svs,dataMat[i,:],kTup) #只映射支持向量到特征空间predict=kernelEval.T*np.multiply(labelSV,alphas[svInd])+b #wiX+bif np.sign(predict)!=np.sign(label[i]): #sign(x)为判别函数，X>0输出1，否则输出-1errorCount+=1print ("The training error rate is {0}%".format(float(errorCount)/m))#模型对于测试集的预测误差data2,label2=loadDataSet("testSetRBF2.txt")dataMat2=np.mat(data2);labelMat2=np.mat(label2).transpose()svInd2=np.nonzero(alphas.A>0)[0] #返回alpha>0的点的索引(即，支持向量点位置)svs2=dataMat2[svInd2];labelSV2=labelMat2[svInd2] #支持向量样本点特征和类型print ("There are %d Support Vectors" %svs2.shape[0])m2,n2=dataMat2.shape;errorCount2=0for i in range(m2):kernelEval2=kernelTrans(svs2,dataMat2[i,:],kTup) #只映射支持向量到特征空间predict2=kernelEval2.T*np.multiply(labelSV2,alphas[svInd2])+b #wiX+bif np.sign(predict2)!=np.sign(label2[i]): #sign(x)为判别函数，X>0输出1，否则输出-1errorCount2+=1print ("The training error rate is {0}%".format(100.0*float(errorCount2)/m2))return b,alphas,svInd,svInd2
4.2 训练&绘图
b,alphas,svInd,svInd2=testRBF(20,0.001,1000,("rbf",0.4))
plotBestFit(svInd,"testSetRBF.txt")
plotBestFit(svInd2,"testSetRBF2.txt")

得到如下输出：

直观点，我们来看看反应在图中是怎样的效果，第一张为训练集分类效果，第二张为测试集分类效果 (橙色、绿色点为支持向量)：
训练集
测试集

可以看到：

  1. 径向基函数的到达率(k1)有一个最优值
    1.1 k1越大，支持向量对分离超平面影响越大，支持向量点可能越少，容易引起欠拟合，决策边界很差
    1.2 k1越小，支持向量对分离超平面影响越小，支持向量点可能越多，容易引起过拟合(极端-所有样本点都是支持向量>>KNN)
  2. 本来想用支持向量点来象征非线性数据集的分离超平面位置，但发现支持向量在图中看起来很杂乱，不过属于正常，因为支持向量是分离超平面两侧的样本点

05 总结

本文就之前写的SMO算法进行了改进，加入了核技巧可选项，可以处理非线性数据集。

这里使用的核函数是径向基函数，适用于圆环状分布的数据集，对于其他分布形状的数据集，可以增加其他核函数来处理，不过道理是一样的：将输入空间的样本特征映射到高维特征空间，使得原本非线性的数据集变得线性可分。

下期主攻AdaBoost集成算法啦，加油吧～

06 参考

  1. 《统计学习方法》 李航 Chapter7
  2. 《机器学习实战》 Peter Harrington Chapter6

这篇关于支持向量机(SVM) | 核技巧于SMO算法的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/697425。

相关文章

Java实现时间与字符串互相转换详解

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串（一）使用预定义格式（二）自定义格式二、字符串解析为日期（一）解析ISO格式字符串（二）解析自定义
阅读更多...
opencv图像处理之指纹验证的实现

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、
阅读更多...
SpringKafka消息发布之KafkaTemplate与事务支持功能

SpringKafka消息发布之KafkaTemplate与事务支持功能

《SpringKafka消息发布之KafkaTemplate与事务支持功能》通过本文介绍的基本用法、序列化选项、事务支持、错误处理和性能优化技术,开发者可以构建高效可靠的Kafka消息发布系统,事务支... 目录引言一、KafkaTemplate基础二、消息序列化三、事务支持机制四、错误处理与重试五、性能优
阅读更多...
Springboot处理跨域的实现方式(附Demo)

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》：本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.
阅读更多...
Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE？1.2 SSE 的优点1.3 适用场景2. Spring WebFlu
阅读更多...
基于SpringBoot实现文件秒传功能

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.
阅读更多...
SpringBoot日志配置SLF4J和Logback的方法实现

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一：初识日志三、案例二：使用Lombok输出日志四、案例三：配置Logback一
阅读更多...
Python如何使用__slots__实现节省内存和性能优化

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景：内存吃得满满的类__slots__：你的内存管理小助手举个大概的例子：看看效果如何？1.
阅读更多...
Python+PyQt5实现多屏幕协同播放功能

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述：突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专
阅读更多...
Python实现无痛修改第三方库源码的方法详解

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2