文档介绍：SVM 算法与实现 2011 – 11 -18 报告内容? SVM 简介?求解算法-SMO 优化算法?多分类问题?系统演示 w x 0w =í à1x 0w =í Separating Surface: A+ A- SVM 算法特点? SVM 有如下主要几个特点: ?(1) 非线性映射是 SVM 方法的理论基础,SVM 利用内积核函数代替向高维空间的非线性映射; ?(2) 对特征空间划分的最优超平面是 SVM 的目标,最大化分类边际的思想是 SVM 方法的核心; ?(3) 支持向量是 SVM 的训练结果,在 SVM 分类决策中起决定作用的是支持向量。因此,模型需要存储空间小,算法鲁棒性强; ?(4) 无序任何前提假设,不涉及概率测度; ?(1) SVM 算法对大规模训练样本难以实施?由于 SVM 是借助二次规划来求解支持向量,而求解二次规划将涉及 m阶矩阵的计算(m为样本的个数),当 m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有的 SMO 算法、的 SVM 、等的 PCGC 、张学工的 CSVM 以及等的 SOR 算法?(2) 用 SVM 解决多分类问题存在困难?经典的支持向量机算法只给出了二类分类的算法,而在数据挖掘的实际应用中,一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和 SVM 决策树;再就是通过构造多个分类器的组合来解决。主要原理是克服 SVM 固有的缺点,结合其他算法的优势,解决多类问题的分类精度。如:与粗集理论结合,形成一种优势互补的多类问题的组合分类器。问题提出?线性可分的分类问题:( 令黑色的点= -1 ,白色的点= +1 ) ?所以当有一个新的点 x需要预测属于哪个分类的时候,我们用 sgn(f(x)) , 就可以预测了, sgn 表示符号函数,当 f(x) > 0 的时候, sgn(f(x)) = +1, 当 f(x) < 0 的时候 sgn(f(x)) = –1。 bxwxf r???)( +1 -1 ?我们怎样才能取得一个最优的划分直线 f(x) 呢? 最大距离 Maximum Marginal ?选择使得间隙最大的函数作为分割平面是由很多道理的,比如说从概率的角度上来说,就是使得置信度最小的点置信度最大(听起来很拗口),从实践的角度来说,这样的效果非常好,等等。最大距离 f(x)=wx+b=0 wx+b=1 wx+b=-1 (x,y) Mww yxfM??),(w???? 1),(w M 22 max ?目标函数: w min 等价于: 22 1 min w 因为单调, 并且为了计算方便 w:求解问题?数据集合: ?优化目标: ?x,y为已知数 lnllyRyxyxT)( )},( ),..., , {( 11??? 22 1 min w???????????????1,1 1,1.. ii iiybxw ybxwts liYyRx i ni,..., 1 },1,1{,?????求解?建立拉格朗日公式: ?求偏导数: