SVM-及SMO算法实现报告课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《SVM-及SMO算法实现报告课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- SVM SMO 算法 实现 报告 课件
- 资源描述:
-
1、SVM 算法与实现2011 11-18报告内容SVM简介求解算法-SMO优化算法多分类问题系统演示wx0w=1x0w=Separating Surface:A+A-SVM算法特点SVM有如下主要几个特点:(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。因此,模型需要存储空间小,算法鲁棒性强;(4)无序任何前提假设,不涉及概率测度;(1)SVM算法对大规模训练样本难以实施由于SVM是借助二次规划
2、来求解支持向量,而求解二次规划将涉及m阶矩阵的计算(m为样本的个数),当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法(2)用SVM解决多分类问题存在困难经典的支持向量机算法只给出了二类分类的算法,而在数据挖掘的实际应用中,一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树;再就是通过构造多个分类器的组合来解决。主要原理是克服SV
3、M固有的缺点,结合其他算法的优势,解决多类问题的分类精度。如:与粗集理论结合,形成一种优势互补的多类问题的组合分类器。问题提出线性可分的分类问题:(令黑色的点=-1,白色的点=+1)所以当有一个新的点x需要预测属于哪个分类的时候,我们用sgn(f(x),就可以预测了,sgn表示符号函数,当f(x)0的时候,sgn(f(x)=+1,当f(x)ijSMO算法SMO算法由Microsoft Research的John C.Platt在1998年提出,并成为最快的二次规划优化算法,特别针对线性SVM和数据稀疏时性能更优。第一步选取一对参数,选取方法使用启发式方法(Maximal violating p
4、air)。第二步,固定除被选取的参数之外的其他参数,确定W极值。SMO算法设我们选取了初始值满足了问题中的约束条件。接下来,我们固定,这样W就是和的函数。并且和满足条件:由于其余参数都是已知固定,因此为了方便,可将等式右边标记成实数值。SMO算法进而lililjjijijiixxKyyaW111),(21)(lililjjijijilijjijlijjijixxKyyxxKyyxxKyy33112211121),(21),(21),(21liliiiiixxKyyxxKyyxxK33111212121111121),(21),(21),(21liiiixxKyyxxKxxKyy32222222
5、212121),(21),(21),(21liljjijijiliiiiliiiixxKyyxxKyyxxKyy3332223111),(21),(21),(21其中:目标函数:求偏导:带入w,v:求得:参数的求解最终参数的解为:其中:和Cnew10Cnew20?a的取值范围当a1和a2异号时,也就是一个为1,一个为-1时,他们可以表示成一条直线,斜率为1。如下图:横轴是 ,纵轴是 ,和 既要在矩形方框内,也要在直线上,因此 同理,当 和 同号时a2a1CCa1-a2=E(0,-E)(C,C-E)参数求解参数计算:参数b计算:?b的求解设 在界内,则有,带入上式得:两边同乘以 ,得b的求解 在
6、界内,则 在界内,则 、都在界内,则情况1和情况2的B值相等,任取一个;都不在界内,则 取值为情况1和情况2之间的任意值。问题?算法如何终止?对于SMO算法,其中的两个参数如何选择呢?随机?启发式规则一个自然的想法是那些违反KKT最严重的点,他们对间距贡献最大,因此可以通过该启发规则来完成调整参数的选取。(并且此种启发规则计算量小)停止条件1满足KKT条件KKT条件:|,00|,00|,0)(*CajjCajjajjybadjjjjj|,0|,0|,)(-*CajjybCajjybajjybadjjjjjjj1y|,0|,0|,)(y-j*j,当CajjbCajjbajjbadjjjj1y|,
展开阅读全文