用MatLab实现SVM分类.doc

在当前数据挖掘和机器学习领域，最为热门的话题莫过于SVM和Boosting方法了。只要是涉及到这两个主题，那么论文就会容易被杂志和会议接受了。看来不管做什么，都讲究眼球效应啊。搞研究其实也有点类似超级女声，呵呵。以前我的论文中用的SVM Code都来自于台湾的林智仁教授的LibSVM。 真的是佩服有些大家，自己做出了重要的发现和成果，想到的不是把自己的成果保密起来（像C4.5一样），让自己独享自己的成果；而是让自己的成果最大程度的被人所利用，给后来的研究人员打下一个坚实的基础。 说实话，他的代码很好，用起来很方便，而且不同的语言版本实现都有，即使是对于初学者都很容易掌握。不过用的久了，我就想自己也实现SVM，现在的数学计算工具太多了，而且功能齐全，用起来方便。今天鼓捣了一会，终于用Matlab实现了第一个SVM。虽然比较简单，但是包含了大多数SVM的必要步骤。这个实现是线性可分支持向量分类机，不考虑非线性分类引入核函数的情况，也不考虑推广条件下引入Penalty Loss的情况。问题描述： 平面上有如下点A = 1 1.5;2 1.5;3 1.5;4 1.5;1 0.5;2 0.5;3 0.5;4 0.5及其对应的标号flag = 1 1 1 1 -1 -1 -1 -1;用SVM方法构造一个决策函数实现正确分类。如果我们在二维坐标上描点，就会发现这是个很简单的线性可分问题。实现方法，用SVM的对偶问题，转换为Matlab的有约束非线性规划问题。构建m文件：function f = ffsvm(x)A = 1 1.5;2 1.5;3 1.5;4 1.5;1 0.5;2 0.5;3 0.5;4 0.5;flag = 1 1 1 1 -1 -1 -1 -1;for i=1:1:length(A)for j=1:1:length(A)normA(i,j) = A(i,:)*A(j,:);normFlag(i,j) = flag(1,i)*flag(1,j);endendf = 0;for i=1:1:length(A)for j=1:1:length(A)f = f + 1/2*(normA(i,j)*x(i)*x(j)*normFlag(i,j);endf = f - x(i);end在命令窗口输入：Aeq = 1 1 1 1 -1 -1 -1 -1;beq = 0;lb = 00000000;调用MatLab内置优化函数fmincon；x,favl,exitflag = fmincon(ffsvm,x0,Aeq,beq,lb,)得到如下结果：Optimization terminated successfully:Magnitude of directional derivative in search directionless than 2*options.TolFun and maximum constraint violationis less than options.TolConActive Constraints:1x =0.50000.50000.50000.50000.50000.50000.50000.5000favl =-2.0000exitflag =1x的分量都不为0，说明这些点都是支持向量；计算w；w = 0 0;for i = 1:1:length(A)w = w + flag(i)*x(i)*A(i,:);end结果：w =0,2;计算b；b = 0;for i=1:1:8b= b-flag(i)*x(i)*normA(i,1);endb= flag(1) + b；结果：b = -2;最终的决策函数为：f = sign(0, 2*xT-2)可以验证，这个学习到的决策函数能够对这些平面上的点实现很好的分类；基本思路是这样的，如果要考虑引入核函数和Penalty Loss的情况，只需要修改优化函数和约束就可以实现。而且自己可以根据需求任意构造自己的SVM目标函数，然后用Lagrange方法转换为对偶形式，然后当作一个有约束线性规划问题用Matlab来解。 至于有约束线性规划问题，这是个大概半个世纪前就解决的问题，学过