3种线性分类器的设计及MATLAB建模

（张天航 空天科学技术研究院 201121250314）

1 问题描述

对“data1.m”数据，分别采用感知机算法、最小平方误差算法、线性SVM算法设计分类器，分别画出决策面，并比较性能。（注意讨论算法中参数设置的影响。）

2 方法描述

2.1 感知机算法

线性分类器的第一个迭代算法是1956年由Frank Rosenblatt提出的，即具有自学习能力的感知器（Perceptron）神经网络模型，用来模拟动物或者人脑的感知和学习能力。这个算法被提出后，受到了很大的关注。感知器在神经网络发展的历史上占据着特殊的位置：它是第一个从算法上完整描述的神经网络，是一种具有分层神经网络结构、神经元之间有自适应权相连接的神经网络的一个基本网络。

感知器的学习过程是不断改变权向量的输入，更新结构中的可变参数，最后实现在有限次迭代之后的收敛。感知器的基本模型结构如图1所示：

图1 感知器基本模型

其中，X输入，Xi表示的是第i个输入；Y表示输出；W表示权向量；w0是阈值，f是一个阶跃函数。

感知器实现样本的线性分类主要过程是：特征向量的元素x1，x2，……，xk是网络的输入元素，每一个元素与相应的权wi相乘。，乘积相加后再与阈值w0相加，结果通过f函数执行激活功能，f为系统的激活函数。因为f是一个阶跃函数，故当自变量小于0时，f= -1；当自变量大于0时，f= 1。这样，根据输出信号Y，把相应的特征向量分到为两类。

然而，权向量w并不是一个已知的参数，故感知器算法很重要的一个步骤即是寻找一个合理的决策超平面。故设这个超平面为w，满足：

引入一个代价函数，定义为：

wT*x0,x1w*x0,x2T （1）

J(w)x*wT*xxY （2）

其中，Y是权向量w定义的超平面错误分类的训练向量的子集。变量x定义为：当

x1时，x= -1；当x2时，x= +1。显然，J(w)≥0。当代价函数J(w)达到最小值0

时，所有的训练向量分类都全部正确。为了计算代价函数的最小迭代值，可以采用梯度下降法设计迭代算法，即：

w(n1)w(n)nJ(w)www(n) （3）

其中，w(n)是第n次迭代的权向量，n有多种取值方法，在本设计中采用固定非负值。由J(w)的定义，可以进一步简化（3）得到：

w(n1)w(n)nx*xxY （4）

通过（4）来不断更新w，这种算法就称为感知器算法（perceptron algorithm）。可以证明，这种算法在经过有限次迭代之后是收敛的，也就是说，根据（4）规则修正权向量w，可以让所有的特征向量都正确分类。

采用感知器算法实现data1.m的数据分类流程如图2所示：

开始初始化权向量w赋任意值迭代N代价函数为0Y结束

图2 单层感知器算法程序流程

MATLAB程序源代码如下：

function Per1()

clear all; close all;

%样本初始化

x1(1,1)=5.1418; x1(1,2)=0.5950; x1(2,1)=5.5519; x1(2,2)=3.5091; x1(3,1)=5.3836; x1(3,2)=2.8033; x1(4,1)=3.2419; x1(4,2)=3.7278; x1(5,1)=4.4427; x1(5,2)=3.8981; x1(6,1)=4.9111; x1(6,2)=2.8710; x1(7,1)=2.9259; x1(7,2)=3.4879; x1(8,1)=4.2018; x1(8,2)=2.4973; x1(9,1)=4.7629; x1(9,2)=2.5163; x1(10,1)=2.7118; x1(10,2)=2.4264; x1(11,1)=3.0470; x1(11,2)=1.5699; x1(12,1)=4.7782; x1(12,2)=3.3504; x1(13,1)=3.9937; x1(13,2)=4.8529; x1(14,1)=4.5245; x1(14,2)=2.1322; x1(15,1)=5.3643; x1(15,2)=2.2477; x1(16,1)=4.4820; x1(16,2)=4.0843; x1(17,1)=3.2129; x1(17,2)=3.0592; x1(18,1)=4.7520; x1(18,2)=5.3119; x1(19,1)=3.8331; x1(19,2)=0.4484; x1(20,1)=3.1838; x1(20,2)=1.4494; x1(21,1)=6.0941; x1(21,2)=1.8544; x1(22,1)=4.0802; x1(22,2)=6.2646; x1(23,1)=3.0627; x1(23,2)=3.6474; x1(24,1)=4.6357; x1(24,2)=2.3344; x1(25,1)=5.6820; x1(25,2)=3.0450; x1(26,1)=4.5936; x1(26,2)=2.5265; x1(27,1)=4.7902; x1(27,2)=4.4668; x1(28,1)=4.1053; x1(28,2)=3.0274; x1(29,1)=3.8414; x1(29,2)=4.2269; x1(30,1)=4.8709; x1(30,2)=4.0535; x1(31,1)=3.8052; x1(31,2)=2.6531; x1(32,1)=4.0755; x1(32,2)=2.8295; x1(33,1)=3.4734; x1(33,2)=3.1919; x1(34,1)=3.3145; x1(34,2)=1.8009; x1(35,1)=3.7316; x1(35,2)=2.6421; x1(36,1)=2.8117; x1(36,2)=2.8658; x1(37,1)=4.2486; x1(37,2)=1.4651;

x1(38,1)=4.1025; x1(38,2)=4.4063; x1(39,1)=3.9590; x1(39,2)=1.3024; x1(40,1)=1.7524; x1(40,2)=1.9339; x1(41,1)=3.4892; x1(41,2)=1.2457; x1(42,1)=4.2492; x1(42,2)=4.5982; x1(43,1)=4.3692; x1(43,2)=1.9794; x1(44,1)=4.1792; x1(44,2)=0.4113; x1(45,1)=3.9627; x1(45,2)=4.2198;

x2(1,1)=9.7302; x2(1,2)=5.5080; x2(2,1)=8.8067; x2(2,2)=5.1319; x2(3,1)=8.1664; x2(3,2)=5.2801; x2(4,1)=6.9686; x2(4,2)=4.0172; x2(5,1)=7.0973; x2(5,2)=4.0559; x2(6,1)=9.4755; x2(6,2)=4.9869; x2(7,1)=9.3809; x2(7,2)=5.3543; x2(8,1)=7.2704; x2(8,2)=4.1053; x2(9,1)=8.9674; x2(9,2)=5.8121; x2(10,1)=8.2606; x2(10,2)=5.1095; x2(11,1)=7.5518; x2(11,2)=7.7316; x2(12,1)=7.0016; x2(12,2)=5.4111; x2(13,1)=8.3442; x2(13,2)=3.6931; x2(14,1)=5.8173; x2(14,2)=5.3838; x2(15,1)=6.1123; x2(15,2)=5.4995; x2(16,1)=10.4188; x2(16,2)=4.4892; x2(17,1)=7.9136; x2(17,2)=5.2349; x2(18,1)=11.1547; x2(18,2)=4.4022; x2(19,1)=7.7080; x2(19,2)=5.0208; x2(20,1)=8.2079; x2(20,2)=5.4194; x2(21,1)=9.1078; x2(21,2)=6.1911; x2(22,1)=7.7857; x2(22,2)=5.7712; x2(23,1)=7.3740; x2(23,2)=2.3558; x2(24,1)=9.7184; x2(24,2)=5.2854; x2(25,1)=6.9559; x2(25,2)=5.8261; x2(26,1)=8.9691; x2(26,2)=4.9919; x2(27,1)=7.3872; x2(27,2)=5.8584; x2(28,1)=8.8922; x2(28,2)=5.7748; x2(29,1)=9.0175; x2(29,2)=6.3059; x2(30,1)=7.0041; x2(30,2)=6.2315; x2(31,1)=8.6396; x2(31,2)=5.9586; x2(32,1)=9.2394; x2(32,2)=3.3455; x2(33,1)=6.7376; x2(33,2)=4.0096; x2(34,1)=8.4345; x2(34,2)=5.6852;

x2(35,1)=7.9559; x2(35,2)=4.0251; x2(36,1)=6.5268; x2(36,2)=4.3933; x2(37,1)=7.6699; x2(37,2)=5.6868; x2(38,1)=7.8075; x2(38,2)=5.0200; x2(39,1)=6.6997; x2(39,2)=6.0638; x2(40,1)=5.6549; x2(40,2)=3.6590; x2(41,1)=6.9086; x2(41,2)=5.4795; x2(42,1)=7.9933; x2(42,2)=3.3660; x2(43,1)=5.9318; x2(43,2)=3.5573; x2(44,1)=9.5157; x2(44,2)=5.2938; x2(45,1)=7.2795; x2(45,2)=4.8596; x2(46,1)=5.5233; x2(46,2)=3.8697; x2(47,1)=8.1331; x2(47,2)=4.7075; x2(48,1)=9.7851; x2(48,2)=4.4175; x2(49,1)=8.0636; x2(49,2)=4.1037; x2(50,1)=8.1944; x2(50,2)=5.2486; x2(51,1)=7.9677; x2(51,2)=3.5103; x2(52,1)=8.2083; x2(52,2)=5.3135; x2(53,1)=9.0586; x2(53,2)=2.9749; x2(54,1)=8.2188; x2(54,2)=5.5290; x2(55,1)=8.9064; x2(55,2)=5.3435;

for i=1:45 r1(i)=x1(i,1);end; for i=1:45 r2(i)=x1(i,2);end; for i=1:55 r3(i)=x2(i,1);end; for i=1:55 r4(i)=x2(i,2);end;

figure(1);

plot(r1,r2,'*',r3,r4,'o');

hold on;%保持当前的轴和图像不被刷新，在该图上接着绘制下一图

x1(:,3) = 1;% 考虑到不经过原点的超平面，对x进行扩维 x2(:,3) = 1;% 使x'=[x 1]，x为2维的，故加1扩为3维

%进行初始化

w = rand(3,1);% 随机给选择向量，生成一个3维列向量 p = 1; %p0非负正实数 ox1 = -1;% 代价函数中的变量

ox2 = 1;% 当x属于w1时为-1，当x属于w2时为1 s = 1;% 标识符，当s=0时，表示迭代终止 n = 0;% 表示迭代的次数 w1 = [0;0;0];

while s %开始迭代

J = 0; %假设初始的分类全部正确 j = [0;0;0]; %j=ox*x for i = 1:45

if (x1(i,:)*w)>0 %查看x1分类是否错误，在x属于w1却被错误分类的情况下，w'x<0

w1 = w; %分类正确，权向量估计不变 else %分类错误

j = j + ox1*x1(i,:)';% j=ox*x。进行累积运算 J = J + ox1*x1(i,:)*w;% 感知器代价进行累积运算 end end

for i = 1:55

if (x2(i,:)*w)<0%查看x2分类是否错误，在x属于w2却被错误分类的情况下，w'x>0

w1 = w; %分类正确，权向量估计不变 else %分类错误

j = j + ox2*x2(i,:)';% j=ox*x。进行累积运算 J = J + ox2*x2(i,:)*w;% 感知器代价进行累积运算 end end

if J==0 %代价为0，即分类均正确 s = 0; %终止迭代 else

w1 = w - p*j;% w(t+1)=w(t)-p(ox*x)进行迭代 p=p+0.1;% 调整p

n = n+1; %迭代次数加1 end

w = w1;% 更新权向量估计 end

x = linspace(0,10,5000);% 取5000个x的点作图

y = (-w(1)/w(2))*x-w(3)/w(2);% x*w1+y*w2+w0=0,w=[w1;w2;w0] plot(x,y,'r');% 用红线画出分界面 disp(n);% 显示迭代的次数

axis([1,12,0,8])% 设定当前图中，x轴范围为1-12，为y轴范围为0-8 end

所得的结果如图3所示：

图3 感知器算法分类图

2.2 最小二乘法

基于分类判别的思想，我们期望w1类的输出为y1 = -1,w2的输出为y2 = 1。但实际的输出和期望并不总是相等的。运用最小二乘法（Least Squares Methods），可以让期望输出和真实的输出之间的均方误差最小化，即：

J(w)E[|yxT*w|2]ˆargminJ(w)ww （5）

要使得J(w)最小，需要满足正交条件（orthogonality condition）：

可以得到：

J(w)2E[x*(yxT*w)]0w

（6）

ˆRx1*E[xy]w （7）

ˆ就是求得的加权向量。其中： wE[x1*x1]E[x1*xl]RE[x*xT]E[x2*x1]E[x2*xl]x

E[xl*x1]E[xl*xl]

称为自相关矩阵；

x1yE[xy]E xly

称为期望输出和输入特征向量的互相关。

通过最小均方误差算法实现线性分类的程序流程如图4所示：

开始初始化求自相关矩阵求输入与期望输出的互相关计算w的估计值结束图4 最小均方误差算法程序流程图

MATLAB程序源代码如下：

function MSE1()

clear all; close all;

%样本初始化

%数据同上一算法，略;

hold on;% 保持当前的轴和图像不被刷新，在该图上接着绘制下图

%初始化函数

y1 = -ones(45,1);% w1类的期望输出为-1 y2 = ones(55,1);% w2类的期望输出为1

x1(:,3) = 1;% 考虑到不经过原点的超平面，对x进行扩维

（8）

（9）

x2(:,3) = 1;% 使x'=[x 1]，x为2维的，故加1扩为3维 x = [x1;x2]'; % 使x矩阵化 y = [y1;y2]; % 使y矩阵化 display(x) % 显示x矩阵 display(y) % 显示y矩阵

R = x*x'; %求出自相关矩阵

E = x*y; %求出期望输出和输入特征向量的互相关 w = inv(R)*E%求权向量估计值

x = linspace(0,10,5000);% 取5000个x的点作图

y = (-w(1)/w(2))*x-w(3)/w(2);%x*w1+y*w2+w0=0,w=[w1;w2;w0] plot(x,y,'r');% 用红线画出分界面

axis([1,12,0,8]);% 设定当前图中，x轴范围为1-12，为y轴范围为0-8 disp(w);% 显示权向量 end

所得结果如图5所示：

图5 最小二乘法分类图

2.3 支撑矢量机（SVM）

SVM是针对线性可分情况进行分析，对于线性不可分的情况，通过非线性映射算法将低维输入线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间可以采用线性算法对样本的非线性特征进行线性分析。而且，SVM是基于最优化理论的算法，在特征空间中构造最优超平面，且这个最优超平面是全局最优的，同时，支持向撑矢量机的最优超平面分类器是唯一的。

在线性可分的情况下，我们想要设计一个超平面，使得所有的训练向量正确分类：

g(x)wTxw00 （10）

由于感知器算法可能收敛于任何可能的解，显然，这样设计得到的超平面不唯一的。最优超平面是使得每一类数据与超平面的距离最近的向量与超平面之间的距离最大的这样的平面，或者说，最优超平面是使得超平面在每一个方向上与w1类、w2类中各自最近的点距离都相同。这样，我们设计的分类器的容量就更大，两类数据被错误分类的概率更小；同时当面对未知数据的分类时，最优超平面可靠度最高。

最优超平面可以通过求解二次优化问题来获得：

minJ(w)

满足约束条件：

12w2

,N

（11） （12）

yi(wTxiw0)1,i1,2,在样本数目特别大的时候，可以将二次规划问题转化为其对偶问题：

N1maxiijyiyjxiTxj2i,ji1

wiyixi0,1

*i1*w0yiwTx

（13） （14）

N （15）

满足约束条件：

yii1Ni0,i0,i1,2,N

*（16）

这里，i是拉格朗日算子，w是最优超平面的法向量，w0是最优超平面的偏移量。 在这类优化问题的求解中，根据karush-kuhn-tucker条件，求得的解必满足：

Tiywxiw01i0,i1,2,,N

*（17）

从式中我们可以发现，对于i=0这样的点对于样本分类没有任何作用，只有i>0时的样本才对分类起作用，这些样本就称为支撑矢量。

通过SVM算法实现分类的程序流程如图6所示：

开始数据初始化求解二次规划问题最优解计算权向量及松弛变量绘图，输出结果结束

图6 SVM算法程序流程图

MATLAB程序源代码如下：

function SVM() close all; clear all;

%数据初始化 略

hold on; % 保持当前的轴和图像不被刷新，在该图上接着绘制下图

y1 = ones(45,1); %对于每一个xi，yi为相应的标识器，对于w1为1,对于w2为-1 y2 =-ones(55,1); X = [x1;x2]; %x矩阵化 Y = [y1;y2]; %y矩阵化

l = zeros(100,1);% 对lambda进行初始化 A=[];

b=[]; %不存在线性不等式约束，故为空 Aeq=Y';

beq=0; %定义线性等式约束

lb=zeros(100,1); %定义上下界约束，有lambda大于等于0

lambda = fmincon('Optimization',l,A,b,Aeq,beq,lb);

%用fmincon函数来求解非线性多变量约束问题，其中Optimization为等价最优任务

w = X'*(lambda.*Y);% 求解支撑矢量

s = find(lambda > 0); %提取非0的元素位置下标构成新矩阵 sum=0; %初始化累计变量 N = length(s) ; %算出非0元素的个数 for i=1:N;

j=s(i);

sum=sum+Y(j) - X(j,:)*w;% 由条件 w'x+w0=y 隐含得到,其中y为正负1 end

w0 = sum/N;% 计算w0的值，w0是通过所有条件的均值计算得出的

x = linspace(0,10,5000);% 取5000个x点画图

y = (-w(1)/w(2))*x-w0/w(2); %x*w1+y*w2+w0=0,w=[w1;w2;w0] plot(x,y,'r');% 用红线标出分界面

axis([1,12,0,8]);% 设定当前图中，x轴范围为1-12，为y轴范围为0-8 display(w);% 显示出权向量 display(w0);% 显示出w0 end

function fl = Optimization(lambda) %用此函数来描述最优化问题

fl = (-1*ones(100,1))'*lambda+1/2*(lambda.*Y)'*X*X'*(lambda.*Y); %最优化问题的等价函数 end

SVM算法分类效果如图7所示：

图7 支撑矢量机算法分类图

3 结果比较与分析

感知机分类方法分类错误的数据个数为0个；最小二乘法分类方法分类错误的数据个数为3个，且错误较明显；支撑矢量机分类方法分类错误的数据个数为2个，错误不明显。可知，感知机分类方法的分类误差最小，最小二乘法分类方法分类误差最大。

感知机分类方法决策面的优劣程度取决于w的选取，所得的超平面可能不唯一，无法判断最优解，感知机分类方法可以再有限次的迭代内求出问题的解。

最小二乘法分类方法在处理较大的训练样本时，计算量较大，导致误差偏大。由于该方法是基于最小平方误差来进行分类的，所以不能保证最小样本错误分类数，即不

保证一定能将样本完全正确分开。

支撑矢量机分类方法可以对样本目标进行较为精准的最优分类。

对同一目标样本进行分类，感知机分类方法分类用时为0.443814 seconds，最小二乘法分类用时为0.116585 seconds，支撑矢量机分类方法分类用时2.200510 seconds。可见，使用最小二乘法分类方法的运算量最小，运算速度最快，使用支撑矢量机分类方法运算量最大，运算速度最慢。