分类器设计之线性分类器和线性SVM(含Matlab代码)

对于高维空间的两类问题，最直接的方法是找到一个最佳的分类超平面，使得分类器设计之线性分类器和线性SVM(含Matlab代码) 并且,对于所有的正负训练样本和. 因此，以上问题可以表达为：

问题P0可以转化为

两边除以\epsilon，并且做变量替换，最终得到下面的线性规化（linear programming）问题：

线性规化问题P2事实上是一个存在性问题(feasibility problem)。通过Matlab的linprog函数可以解。具体解决有很多，此处暂不作论述。只要两类问题是严格可分的，则上述问题的解就存在，并不不是唯一：空间中存在无数多个超平面能将正负样本分开。从数学上理解，P2是smooth non-strictly convex问题，本身要么没有解，要么存在多个解。

下面用Matlab程序来演示线性分类器问题（以二维数据为例）

%%
clc;
clear;
close all;
%% generate random data
shift = 3;
n = 200;
m=200;
d = 2;
sigma = 1;
x = randn(d,n)-shift;
y = randn(d,m)*sigma+shift;
%%
%show the data
figure;
plot(x(1,:),x(2,:),'rs');
hold on;
plot(y(1,:),y(2,:),'Go');
legend('Positive samples','Negative samples');

分类器设计之线性分类器和线性SVM(含Matlab代码)

%% training...
%Linear programming
for i=1:n
A(i,:) = [-x(:,i)',-1];
end
for i=1:m
A(i+n,:) = [y(:,i)',1];
end
c = ones(n+m,1)*(-1);
w = linprog(zeros(d+1,1),A,c);
hold on;
%% visualize the classification area
x1 = -shift-2:0.1:shift+2*sigma;
y1 = (-w(3)-w(1)*x1)/w(2);
plot(x1,y1,'-','LineWidth',2);
legend('Positive samples','Negative samples','Linear programming');

分类器设计之线性分类器和线性SVM(含Matlab代码)

由于采用线性规化来解线性可分问题存在无数多个解，那么哪个一解是最优的呢？我们希望找到一个超平面，使得该平面前后平移d的距离后分类碰到正负样本并且使d最大化。2*d 即为以下两个平面之间的距离:

这两个平面的距离为：

因此，线性规化问题可以进一步加强为下面的二次规划问题：

即等价于：

以上的问题是strictly convex 问题。强大的SVM分类器即由此演化而来（结合核方法VC维理论）对于两类线性可分问题，上述问题存在唯一的解。具体解法在此同样暂不讲解，有兴趣可参考wiki：http://en.wikipedia.org/wiki/Quadratic_programming

下面对同样的二维数据进行分类：

%% svm
H = eye(d+1);
H(d+1,d+1) = 0;
w = quadprog(H,zeros(d+1,1),A,c);
hold on;
x1 = -shift-2:0.1:shift+2*sigma;
y1 = (-w(3)-w(1)*x1)/w(2);
plot(x1,y1,'g-','LineWidth',2);
y1 = (-1-w(3)-w(1)*x1)/w(2);
plot(x1,y1,'g-','LineWidth',2);
y1 = (1-w(3)-w(1)*x1)/w(2);
plot(x1,y1,'g-','LineWidth',2);
legend('Positive samples','Negative samples','Linear programming','Linear SVM');

分类器设计之线性分类器和线性SVM(含Matlab代码)

从上图可见，线性SVM分类的效果要好于线性分类器。

PS：本文所有代码可在http://download.csdn.net/detail/ranchlai/6009209下载。

秒客网

分类器设计之线性分类器和线性SVM(含Matlab代码)

相关文章