模式识别论文

1

1 1

1 支持向量机

支持向量机支持向量机

支持向量机

1

11

1．

．．

．1

1 1

1 线性

线性线性

线性SVM

SVMSVM

SVM

最优超平面 SVM方法是从线性可分的情况下的最优分类面

(OptimalHyperplane)提出的。设线性可分样本集为(,)iixy

，i=1，?，n；Y={+1，

-1}是类别标号，分类面方程为：

W*X + b = 0 (1)这个平面将两类样本没有错误的分开，并且使得离分类面最近

的样本到分类面的距离最大，即分类间隔最大，等价于使2||||

w最小，W为分类

面的法向量。而要求分类面对所有样本正确分类，约束条件为：

[(*)]10iiywxb

+?≥，i = 1,2,L,n (2)

因此，满足上述条件且使得ll W 最小的分类面就是最优分类面。过两类样本中

离分类面最近的点且平行于最优分类面的超平面H．、H 上的训练样本就是式(2)

中使等号成立的那些样本叫做支持向量。最优分类面可以表示为如下约束的优化

问题，

即在式(2)的约束下，求函数 211

()||||(*)

22

wwww

?== (3)

的最小值。为此，可以定义如下的拉格朗日函数： 211

(,,)||||{[(*)]1}

2n

ii

iLwbawaywxb==?+?∑ (4)

(4)式中，ia>0为拉格朗日系数。把原问题转化为如下较简单的对偶问题： 11,11

max()(|)

2nn

iijijij

iijQaaaayyxx====?∑∑ .

st 10n

ii

iya==∑ 0,ia

≥i = 1,……n。

1

11

1．

．．

．2

2 2

2 非线性

非线性非线性

非线性SVM

SVM SVM

SVM

上面讨论的是最优和广义线性分类函数，要解决一个特征空间中的最优线性

分类问题，我们只需知道这个空间中的内积运算即可。按照广义线性判别函数的

思路，要解决一个非线性问题，我们可以设法将它通过非线性变换转换为另一个

空间的线性问题，在这个变换空间求最优或最广义分类面。考虑Mercer条件：

对于任意的对称函数'(,)

Kxx，它是某个特征空间的内积运算的充分必要条件是，对与任意的()x?恒不为0，且2()xdx?∫∫，显然

这一条件不难满足 。如果用内积K(x，Y)代替最优分类面的点积，就相当于把

原特征空间变换到了某一新的特征

空间，此时的支持向量机为： 11,11

()(,)

2nn

iijijij

iijMAXQaaaayyKxx====?∑∑ 1.0n

ii

istya==∑ 0,1,....

aCin≤≤=

相应的判别函数也应变为： *

1()sgn(*(,))n

iii

ifxayKxxb==+∑。

其它的条件不变，这就是支持向量机。支持向量机的思想可以概括为：首先通过

非线性变换将输入空间变换到一个高维空间，然后就这个新空间中求取最优线性

分类面，而这种非线性变换是通过定义适当

的函数实现的，这些函数叫做核函数。

选择不同的核函数就构成不同的支持向量机，常用的有以下

三类核函数：

linear：K(x，y) = x*y；

ploy：K(x，y) = q[(x*y)+1]；

rbf：K(x，y) = 2

2||

exp{}

xyσ?

?; 2

2 2

2 支持向量机分类算法的实现

支持向量机分类算法的实现支持向量机分类算法的实现

支持向量机分类算法的实现

支持向量机算法是在训练样本的特征空间求取能把两类样本没有错误分开的最

大间隔超平面，在数学上表示为一个凸二次规划的问题。也可以说算法求解的主

要内容是通过求解二次规划(QP)问题，这个优化问题的求解是支持向量机算法的

核心，可以说支持向量机的算法就得到了实现。前面所述支持向量机算法可以表

示为在式(6)和式(7)的约束下求式(5)取最小值时的拉格朗日乘子 12(,.....,)T

nA

=???为训练样本的个数。 ()1/2TTQAAIADA=?+ (5) 0AC≤≤ (6) 0TAy= (7)

其中： 12(,,....,)T

nA

=???为n元列向量，是要求的拉格朗日乘子；(,)ijijijDyyKxx= 是一个正定矩阵； 12(,,...)T

nyyyy

=是样本的所属类别，由1

或一1组成的列向量；xi为训练样本。可以看出，求解支持向量机就是求解上

述的一个二次规划问题，求解后得到拉格朗日乘子12(,,....,)T

nA

=??? ，也就求

得了最大间隔超平面。求解这个二次规划问题需要深厚的数学功底数值计算方面

的技能，在主流程序语言中实现算法又需要专业的计算机程序设计的知识。

在MATLAB环境下求解这一问题会变得非常简单，这得益于MATLAB软件强大的优

化工具箱，提供了一个求解二次规划的函数，可以直接调用。二次规划问题

(quadratic programming)的标准形式为：

''1

min

2

fxxHx+

sub．to Axb

≤

Aeqx=beq

lbxub

≤≤

其中，H、A、Aeq为矩阵；f、b、beq、lb、ub、x为向量，其它形式的二次规划

问题都可转化为标准形式。MATLAB5．x版中的qp函数已被6．0版中的函数

quadprog取代。函数quadprog格式如下：

[x，fva1]=quadprog(H，f，A，b，Aeq，beq，lb，ub，x0)

其中H、f、A、b、Aeq、beq、lb、ub为标准形中的参数；x为求解得到的最优

值，也就是二次规划的解析解；lb、ub分别为x的下界与上界，满足不等式约bxub

≤≤；Aeq、beq满足等约束条件Aeq*x=beq；x0为设置的初值，这个值是

人为赋予x的值，一般x为零；fval为目标函数最小值，可以看出，支持向量

机算法是一个标准的二次规划问题； (,)ijijijHDyyKxx

==，根据训练样本数据

求出；f = -1；支持向量机算法没形式的不等式

约束条件，所以A、b为空矩阵；TAeqAy

= ，beq=Y，实现A Y=0等式约束；Lb=0、ub=C，实现 0AC≤≤不等

式约束；x0=0，赋予A的初始值为零。样本数据已知，c是人工赋于的值。

3

33

3．

．．

．实例说明及实验结果

实例说明及实验结果实例说明及实验结果

实例说明及实验结果

3.1实验程序代码

%定义核函数及相关参数

nu = 0.2; % nu -> (0,1] 在支持向量数与错分样本数之间进行折

衷

ker = struct('type','linear');

% 构造两类训练样本

n = 50;

randn('state',6);

x1 = randn(2,n);

y1 = ones(1,n);

x2 = 5+randn(2,n);

y2 = -ones(1,n);

figure;

plot(x1(1,:),x1(2,:),'bx',x2(1,:),x2(2,:),'k.');

axis([-3 8 -3 8]);

title('C-SVC')

hold on;

X = [x1,x2]; %训练样本，d*n的矩阵，n为样本个数，d为样本维数

Y = [y1,y2]; % 训练目标，1*n的矩阵，n为样本个数，值为+1或-1

% ------------------------------------------------------------%

% 训练支持向量机

tic

svm = svmTrain('svc_nu',X,Y,ker,nu);

t_train = toc

%寻找支持向量?

a = svm.a;

epsilon = 1e-8; %如果小于此值则认为是0

i_sv = find(abs(a)>epsilon); %支持向量下标

plot(X(1,i_sv),X(2,i_sv),'ro');

% ------------------------------------------------------------%

% 测试输出

[x1,x2] = meshgrid(-2:0.1:7,-2:0.1:7);

[rows,cols] = size(x1);

nt = rows*cols; % 2测试样本数

Xt = [reshape(x1,1,nt);reshape(x2,1,nt)];

tic

Yd = svmSim(svm,Xt); % 测试输出

t_sim = toc

Yd = reshape(Yd,rows,cols);

contour(x1,x2,Yd,[0 0],'m'); %分类面

hold off;

3.2实验结果

1

1 1

1 支持向量机

支持向量机支持向量机

支持向量机

1

11

1．

．．

．1

1 1

1 线性

线性线性

线性SVM

SVMSVM

SVM

最优超平面 SVM方法是从线性可分的情况下的最优分类面

(OptimalHyperplane)提出的。设线性可分样本集为(,)iixy

，i=1，?，n；Y={+1，

-1}是类别标号，分类面方程为：

W*X + b = 0 (1)这个平面将两类样本没有错误的分开，并且使得离分类面最近

的样本到分类面的距离最大，即分类间隔最大，等价于使2||||

w最小，W为分类

面的法向量。而要求分类面对所有样本正确分类，约束条件为：

[(*)]10iiywxb

+?≥，i = 1,2,L,n (2)

因此，满足上述条件且使得ll W 最小的分类面就是最优分类面。过两类样本中

离分类面最近的点且平行于最优分类面的超平面H．、H 上的训练样本就是式(2)

中使等号成立的那些样本叫做支持向量。最优分类面可以表示为如下约束的优化

问题，

即在式(2)的约束下，求函数 211

()||||(*)

22

wwww

?== (3)

的最小值。为此，可以定义如下的拉格朗日函数： 211

(,,)||||{[(*)]1}

2n

ii

iLwbawaywxb==?+?∑ (4)

(4)式中，ia>0为拉格朗日系数。把原问题转化为如下较简单的对偶问题： 11,11

max()(|)

2nn

iijijij

iijQaaaayyxx====?∑∑ .

st 10n

ii

iya==∑ 0,ia

≥i = 1,……n。

1

11

1．

．．

．2

2 2

2 非线性

非线性非线性

非线性SVM

SVM SVM

SVM

上面讨论的是最优和广义线性分类函数，要解决一个特征空间中的最优线性

分类问题，我们只需知道这个空间中的内积运算即可。按照广义线性判别函数的

思路，要解决一个非线性问题，我们可以设法将它通过非线性变换转换为另一个

空间的线性问题，在这个变换空间求最优或最广义分类面。考虑Mercer条件：

对于任意的对称函数'(,)

Kxx，它是某个特征空间的内积运算的充分必要条件是，对与任意的()x?恒不为0，且2()xdx?∫∫，显然

这一条件不难满足 。如果用内积K(x，Y)代替最优分类面的点积，就相当于把

原特征空间变换到了某一新的特征

空间，此时的支持向量机为： 11,11

()(,)

2nn

iijijij

iijMAXQaaaayyKxx====?∑∑ 1.0n

ii

istya==∑ 0,1,....

aCin≤≤=

相应的判别函数也应变为： *

1()sgn(*(,))n

iii

ifxayKxxb==+∑。

其它的条件不变，这就是支持向量机。支持向量机的思想可以概括为：首先通过

非线性变换将输入空间变换到一个高维空间，然后就这个新空间中求取最优线性

分类面，而这种非线性变换是通过定义适当

的函数实现的，这些函数叫做核函数。

选择不同的核函数就构成不同的支持向量机，常用的有以下

三类核函数：

linear：K(x，y) = x*y；

ploy：K(x，y) = q[(x*y)+1]；

rbf：K(x，y) = 2

2||

exp{}

xyσ?

?; 2

2 2

2 支持向量机分类算法的实现

支持向量机分类算法的实现支持向量机分类算法的实现

支持向量机分类算法的实现

支持向量机算法是在训练样本的特征空间求取能把两类样本没有错误分开的最

大间隔超平面，在数学上表示为一个凸二次规划的问题。也可以说算法求解的主

要内容是通过求解二次规划(QP)问题，这个优化问题的求解是支持向量机算法的

核心，可以说支持向量机的算法就得到了实现。前面所述支持向量机算法可以表

示为在式(6)和式(7)的约束下求式(5)取最小值时的拉格朗日乘子 12(,.....,)T

nA

=???为训练样本的个数。 ()1/2TTQAAIADA=?+ (5) 0AC≤≤ (6) 0TAy= (7)

其中： 12(,,....,)T

nA

=???为n元列向量，是要求的拉格朗日乘子；(,)ijijijDyyKxx= 是一个正定矩阵； 12(,,...)T

nyyyy

=是样本的所属类别，由1

或一1组成的列向量；xi为训练样本。可以看出，求解支持向量机就是求解上

述的一个二次规划问题，求解后得到拉格朗日乘子12(,,....,)T

nA

=??? ，也就求

得了最大间隔超平面。求解这个二次规划问题需要深厚的数学功底数值计算方面

的技能，在主流程序语言中实现算法又需要专业的计算机程序设计的知识。

在MATLAB环境下求解这一问题会变得非常简单，这得益于MATLAB软件强大的优

化工具箱，提供了一个求解二次规划的函数，可以直接调用。二次规划问题

(quadratic programming)的标准形式为：

''1

min

2

fxxHx+

sub．to Axb

≤

Aeqx=beq

lbxub

≤≤

其中，H、A、Aeq为矩阵；f、b、beq、lb、ub、x为向量，其它形式的二次规划

问题都可转化为标准形式。MATLAB5．x版中的qp函数已被6．0版中的函数

quadprog取代。函数quadprog格式如下：

[x，fva1]=quadprog(H，f，A，b，Aeq，beq，lb，ub，x0)

其中H、f、A、b、Aeq、beq、lb、ub为标准形中的参数；x为求解得到的最优

值，也就是二次规划的解析解；lb、ub分别为x的下界与上界，满足不等式约bxub

≤≤；Aeq、beq满足等约束条件Aeq*x=beq；x0为设置的初值，这个值是

人为赋予x的值，一般x为零；fval为目标函数最小值，可以看出，支持向量

机算法是一个标准的二次规划问题； (,)ijijijHDyyKxx

==，根据训练样本数据

求出；f = -1；支持向量机算法没形式的不等式

约束条件，所以A、b为空矩阵；TAeqAy

= ，beq=Y，实现A Y=0等式约束；Lb=0、ub=C，实现 0AC≤≤不等

式约束；x0=0，赋予A的初始值为零。样本数据已知，c是人工赋于的值。

3

33

3．

．．

．实例说明及实验结果

实例说明及实验结果实例说明及实验结果

实例说明及实验结果

3.1实验程序代码

%定义核函数及相关参数

nu = 0.2; % nu -> (0,1] 在支持向量数与错分样本数之间进行折

衷

ker = struct('type','linear');

% 构造两类训练样本

n = 50;

randn('state',6);

x1 = randn(2,n);

y1 = ones(1,n);

x2 = 5+randn(2,n);

y2 = -ones(1,n);

figure;

plot(x1(1,:),x1(2,:),'bx',x2(1,:),x2(2,:),'k.');

axis([-3 8 -3 8]);

title('C-SVC')

hold on;

X = [x1,x2]; %训练样本，d*n的矩阵，n为样本个数，d为样本维数

Y = [y1,y2]; % 训练目标，1*n的矩阵，n为样本个数，值为+1或-1

% ------------------------------------------------------------%

% 训练支持向量机

tic

svm = svmTrain('svc_nu',X,Y,ker,nu);

t_train = toc

%寻找支持向量?

a = svm.a;

epsilon = 1e-8; %如果小于此值则认为是0

i_sv = find(abs(a)>epsilon); %支持向量下标

plot(X(1,i_sv),X(2,i_sv),'ro');

% ------------------------------------------------------------%

% 测试输出

[x1,x2] = meshgrid(-2:0.1:7,-2:0.1:7);

[rows,cols] = size(x1);

nt = rows*cols; % 2测试样本数

Xt = [reshape(x1,1,nt);reshape(x2,1,nt)];

tic

Yd = svmSim(svm,Xt); % 测试输出

t_sim = toc

Yd = reshape(Yd,rows,cols);

contour(x1,x2,Yd,[0 0],'m'); %分类面

hold off;

3.2实验结果