线性分类器之感知机算法和最小平方误差算法1.问题描述对所提供的的数据“data1.m ”，分别采用感知机算法、最小平方误差算法设计分类器，分别画出决策面，并比较性能,并且讨论算法中参数设置的影响2.方法叙述2.1感知机算法1.假设已知一组容量为N 的样本集1y ，2y ，…，N y ，其中N y 为d 维增广样本向量，分别来自1ω和2ω类。

如果有一个线性机器能把每个样本正确分类，即存在一个权向量a ，使得对于任何1ω∈y ，都有y a T >0，而对一任何2ω∈y ，都有y a T<0，则称这组样本集线性可分；否则称线性不可分。

若线性可分，则必存在一个权向量a ，能将每个样本正确分类。

2.基本方法：由上面原理可知，样本集1y ，2y ，…，N y 是线性可分，则必存在某个权向量a ，使得⎪⎩⎪⎨⎧∈<∈>21y ,0y ,0ωωj j Ti i T y a y a 对一切对一切 如果我们在来自2ω类的样本j y 前面加上一个负号，即令j y =—j y ，其中2ω∈j y ，则也有y a T >0。

因此，我们令⎩⎨⎧∈∈='21y ,-y ,ωωj ji i n y y y 对一切对一切那么，我们就可以不管样本原来的类型标志，只要找到一个对全部样本ny '都满足y a T >0，N n ,,3,2,1⋯⋯=的权向量a 就行了。

此过程称为样本的规范化，ny '成为规范化增广样本向量，后面我们用y 来表示它。

我们的目的是找到一个解向量*a ，使得N n y a n T ,...,2,1,0=>为此我们首先考虑处理线性可分问题的算法。

先构造这样一个准则函数)()(y∑∈=ky Tp y aa J γδ式中kγ是被权向量a 错分类的样本集合。

y δ的取值保证因此()a J p 总是大于等于0。

即错分类时有0≤y a T (1ω∈y )，0≥y a T(2ω∈y )，此时的y δ分别为-1,1。

下一步便是求解使代价函数)(a J p 达到极小值时的解向量*a 。

这里我们采用梯度下降法。

首先对a 求梯度，这是一个纯量函数对向量的求导问题，不难看出∑∈=∂∂=∇ky p p y aa J a J γδ)()()(y梯度下降法的迭代公式为J k a k a k ∇-=+ρ)()1(，将上式代入得∑∈=+ky ky k a k a γδρy-)()1(这样，经过有限次修改，一定能找到一个解向量*a 。

其中算法在运行之前必须人为任意给定权向量)1(a ，而常量k ρ的选取也十分讲究。

2.2最小平方误差算法(MSE)感知算法是基于求解线性不等式组的算法，其目标是寻找权向量a ，使得满足n y a T>0的数目最大，从而是错分样本数数最小。

而不同的是，最小平方误差算法(以下简称MSE)，是对准则函数引进最小均方误差这一条件而建立起来的，这种算法的主要特点是在训练过程中判定训练集是否线性可分，从而对结果的收敛性做出判断。

我们把不等式组变为如下形式：n y a T =n b >0n b 为给定的任意的正常数。

将上式联立方程组可以得到：b =Ya其中Y=[Ty 1Ty 2……Ty N ]T ，为N*d 的矩阵，Ty n 为规范化增广样本向量。

通常样本数N 大于样本维度d ，故Y 为长方形阵且一般列满秩。

实际上这是方程个数多余未知数的情况，一般为矛盾方程组无精确解。

因此定义误差向量：b -e Ya =并且定义误差准则函数∑=-===Nn n n T b a a J 1222s y ||b -Ya ||||e ||)(）（然后寻找一个使得固定值J s (a)极小化的a 作为问题的解。

这就是矛盾方程组的最小二乘近似解，也就是所谓的伪逆解或者是MSE 解。

使用解析法求出伪逆解。

首先对)(s a J 求梯度：）（）（b b a a J n Nn n n T -Ya Y 2y y 2)(T 1s =-==∇∑=令0)(s =∇a J 得a *=(Y T Y)-1Y T b ，这就是式子Y a =b 的MSE 解。

可以看出，)(s a J 有唯一的极小值0，发生在Y a =b 时。

准则函数的值等于n y a T和n b 误差的平方之和，此时1,2,,i N = ，我们的目标是使这个误差的平方和最小，因此称这一准则导出的算法为最小均方误差算法。

我们可以发现，当b=[N/N1,N/N1,N/N1……N/N2,N/N2……]T (N/N1有N1个，N/N2有N2个，N=N1+N2)，MSE 解a *等价于Fisher 解。

证明略。

同样，当样本N 趋于无穷的时候，如果令b =u N ,其中u N 中元素均是1，则它以最小均方误差逼近贝叶斯判别函数。

3.算法实现3.1数据读取子函数function [x1,x2]=getts()%分别读取分类x1和x2 x1=zeros(45,2); x2=zeros(45,2);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;3.2感知机算法clear all;[x1,x2]=getts();%读取训练样本x1,x2w=[5.1 1.9 -34]';%设置权向量初值Dcost=[0;0;0];%用来存储代价函数的梯度和i=0;n=0;cost=1;%初始化循环条件while(cost~=0)i=i+1;cost=0;for j=1:45if (w'*[x1(j,:) 1]')>0Dcost=Dcost+[x1(j,1:2) 1]';% 用来存储代价函数的梯度和cost=cost+w'*[x1(j,1:2) 1]';%代价函数值endendfor k=1:55if (w'*[x2(k,:) 1]')<0Dcost=Dcost-[x2(k,1:2) 1]'; % 用来存储代价函数的梯度和cost=cost+w'*[x2(k,:) 1]'; %代价函数值endendw=w-0.001*Dcost/i;%权向量更新n=n+1;endfor 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');title('the training set');figure(2)x=0:0.01:12;y=-x*w(1)/w(2)-w(3)/w(2);%画决策面plot(r1,r2,'*',r3,r4,'o',x,y);axis([0 12 0 7]);3.2最小平方误差算法clear all;[x1,x2]=getts();X=zeros(100,3);Y=zeros(100,1);X(1:45,1:2)=x1;%获得Xa=Y中的增广样本矩阵X X(1:45,3)=1;X(46:100,1:2)=x2;X(46:100,3)=1;Y(1:45)=1;Y(46:100)=-1;w=(inv(X'*X))*X'*Y%得到伪逆解;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');title('the training set');figure(2)x=0:0.01:12;y=-x*w(1)/w(2)-w(3)/w(2);%画决策面plot(r1,r2,'*',r3,r4,'o',x,y);axis([0 12 0 7]);4.结果分析比较4.1感知机算法分类的结果Fig1.感知机算法分类的结果感知机分类器结果如上图所示，能够较好的将两类分开。