SVM-算法实现

SVM算法与实现2011–11-18报告内容SVM简介求解算法-SMO优化算法多分类问题系统演示wx0w=íà1x0w=íSeparatingSurface:A+A-SVM算法特点SVM有如下主要几个特点：(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。因此，模型需要存储空间小，算法鲁棒性强；(4)无序任何前提假设，不涉及概率测度；(1)SVM算法对大规模训练样本难以实施由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的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。bxwxfr)(+1-1我们怎样才能取得一个最优的划分直线f(x)呢？最大距离MaximumMarginal选择使得间隙最大的函数作为分割平面是由很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大（听起来很拗口），从实践的角度来说，这样的效果非常好，等等。最大距离f(x)=wx+b=0wx+b=1wx+b=-1(x,y)MwwyxfM),(1),(wM22max目标函数：wmin等价于：221minw因为单调，并且为了计算方便w：求解问题数据集合：优化目标：x，y为已知数lnllyRyxyxT)()},(),...,,{(11221minw1,11,1..iiiiybxwybxwtsliYyRxini,...,1},1,1{,求解建立拉格朗日公式：求偏导数：求解：对偶问题)(minmax)(maxmin,,xfxfbwaabw求解将两式带回L(w,b,a)得到对偶问题的表达式iiiiiijijjjiiiabyaxwyaxyaxyaabwL,21),,()1)((21),,(2bxwyawabwLiii求解问题数据集合：优化目标：x，y为已知数lnllyRyxyxT)()},(),...,,{(11liljjiijiliaxxyy11j1i),(K21maxliiyts1i0..liYyRxini,...,1},1,1{,核函数线性不可分的情况我们可以为分错的点加上一点惩罚，对一个分错的点的惩罚函数就是这个点到其正确位置的距离：软间隔C-SVMC是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确软支持向量机求解构造拉格朗日公式：求偏导数：求解问题数据集合：优化目标：其中C为人为设定，x，y为已知数lnllyRyxyxT)()},(),...,,{(11liljjiijiliaxxyy11j1i),(K21maxliiyts1i0..liCi,...,1,0liYyRxini,...,1},1,1{,问题？实际上在处理大型问题时，由于存储和计算两方面的要求，这些算法往往会失效。这些算法都要存储与训练集相应的核矩阵，然而存储核矩阵所需要的内存是随着训练集中训练点数L的平凡增长的。例如，当训练点数目超过4000时，存储核函数矩阵需要多达128兆。求解方法：坐标上升法固定除之外的所有参数，这时W可看作只是关于的函数，那么直接对求导优化即可。可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。lililjjiijiaxxyy11i1j),(K21miniii问题？固定以外的所有参数，那么将不再是变量（可以由其他值推出），因为问题中规定了因此，我们最少一次需要选取两个参数做优化，比如和，此时可以由和其他参数表示出来。=ijSMO算法SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。第一步选取一对参数，选取方法使用启发式方法（Maximalviolatingpair）。第二步，固定除被选取的参数之外的其他参数，确定W极值。SMO算法设我们选取了初始值满足了问题中的约束条件。接下来，我们固定，这样W就是和的函数。并且和满足条件：由于其余参数都是已知固定，因此为了方便，可将等式右边标记成实数值。SMO算法进而lililjjijijiixxKyyaW111),(21)(lililjjijijilijjijlijjijixxKyyxxKyyxxKyy33112211121),(21),(21),(21liliiiiixxKyyxxKyyxxK33111212121111121),(21),(21),(21liiiixxKyyxxKxxKyy32222222212121),(21),(21),(21liljjijijiliiiiliiiixxKyyxxKyyxxKyy3332223111),(21),(21),(21其中：目标函数：求偏导：带入w,v：求得：参数的求解最终参数的解为：其中：和Cnew10Cnew20？a的取值范围当a1和a2异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图：横轴是，纵轴是，和既要在矩形方框内，也要在直线上，因此同理，当和同号时a2a1CCa1-a2=E(0,-E)(C,C-E){{参数求解参数计算：参数b计算：？b的求解设在界内，则有，带入上式得：两边同乘以，得b的求解在界内，则在界内，则、都在界内，则情况1和情况2的B值相等，任取一个；都不在界内，则取值为情况1和情况2之间的任意值。问题？算法如何终止？对于SMO算法，其中的两个参数如何选择呢？随机？启发式规则一个自然的想法是那些违反KKT最严重的点，他们对间距贡献最大，因此可以通过该启发规则来完成调整参数的选取。（并且此种启发规则计算量小）停止条件1满足KKT条件KKT条件：}|{,0}0|{,0}0|{,0)(*CajjCajjajjybadjjjjj}|{,}0|{,}0|{,)(-***CajjybCajjybajjybadjjjjjjj1y}|{,}0|{,}0|{,)(y-j***j，当CajjbCajjbajjbadjjjj1y}|{,}0|{,}0|{,)(y-j***j，当CajjbCajjbajjbadjjjj}1,|{}0|{}1y,0|{,}1,|{}0|{}1y,0|{,)(y-j*j*jjjjjjjjjjyCajCajajjbyCajCajajjbad并设代入得：左移：分别乘以yi：统一：}1,|{}0|{}1y,0|{,}1,|{}0|{}1y,0|{,)(y-j*j*jjjjjjjjjjyCajCajajjbyCajCajajjbad等价于：bbb满足：不满足：0)()(**aMam如果对于：可以判断：停止条件2停止条件3启发式选择算法其他求解方法选块算法分解算法分解算法工作集的选取相关软件问题OntheAlgorithmicImplementationofMulticlassKernel-basedVectorMachinesGrammer&singer多分类支持向量机基本思想Grammer-singer多分类支持向量机的出发点是直接用超平面把样本空间划分成M个区域，其中每个区域对应一个类别的输入。如下例，用从原点出发的M条射线把平面分成M个区域，下图画出了M=3的情形：问题描述设训练点集为：则存在着使得训练点满足下式：lnllyRyxyxT)()},(),...,,{(11likYyRxini,...,1},...3,2,1{,k}{\},...,3,2,1{,1),(),(iiriyykrxwxwi引进记号：kjkjjk,0,1},...,3,2,1{,1),(),(krxwxwyririyi1)),((iryxwwi1)),((iryxwwirywwi2213232221ksrsrww2最优化问题根据最大间隔原则：其中：，进而最优化问题可转化为：,1),(),(..yririyxwxwtsiksrsrww2minlikr,...,3,2,1;,...,3,2,1krrksrsrwkww122,1),(),(..yririyxwxwtsikrrw1221minlikr,...,3,2,1;,...,3,2,1最优化问题添加松弛变量其中：,1),(),(..iyririyxwxwtsiliikrrCw11221minlikr,...,3,2,1;,...,3,2,10}1{max,iiyryirrixwxwii引入拉格朗日函数likriryiriyriiixwxw11,,]1),(),[(liikrrkC),,,...,,(0)(,1,1,,1,ilryiirikjjilryiiirirxaaxawLwilryiiriilryiirikrrirxaxaaw,1,,1,1,)(01,kjjiaCLCakjji1,iliriryilryiriilryirirxaCxaxaCwiii)()(1,,,1,,1,，设riryriaCi,,,ilirirxw1,则