matlab-线性分类器的设计doc

线性分类器设计1问题描述对“data1.m”数据，分别采用感知机算法、最小平方误差算法、线性SVM算法设计分类器，分别画出决策面，并比较性能。（注意讨论算法中参数设置的影响。）2方法描述2.1感知机算法线性分类器的第一个迭代算法是1956年由FrankRosenblatt提出的，即具有自学习能力的感知器（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，满足：12*0,*0,TTwxxwxx（1）引入一个代价函数，定义为：()**TxxYJwwx（2）其中，Y是权向量w定义的超平面错误分类的训练向量的子集。变量x定义为：当1x时，x=-1；当2x时，x=+1。显然，J(w)≥0。当代价函数J(w)达到最小值0时，所有的训练向量分类都全部正确。为了计算代价函数的最小迭代值，可以采用梯度下降法设计迭代算法，即：()()(1)()nwwnJwwnwnw（3）其中，w(n)是第n次迭代的权向量，n有多种取值方法，在本设计中采用固定非负值。由J(w)的定义，可以进一步简化（3）得到：(1)()*nxxYwnwnx（4）通过（4）来不断更新w，这种算法就称为感知器算法（perceptronalgorithm）。可以证明，这种算法在经过有限次迭代之后是收敛的，也就是说，根据（4）规则修正权向量w，可以让所有的特征向量都正确分类。采用感知器算法实现data1.m的数据分类流程如图2所示：开始初始化权向量w赋任意值代价函数为0迭代结束NY图2单层感知器算法程序流程MATLAB程序源代码如下：functionPer1()clearall;closeall;%样本初始化x1(1,1)=0.1;x1(1,2)=1.1;x1(2,1)=6.8;x1(2,2)=7.1;x1(3,1)=-3.5;x1(3,2)=-4.1;x1(4,1)=2.0;x1(4,2)=2.7;x1(5,1)=4.1;x1(5,2)=2.8;x1(6,1)=3.1;x1(6,2)=5.0;x1(7,1)=-0.8;x1(7,2)=-1.3;x1(8,1)=0.9;x1(8,2)=1.2;[8.44.1;4.2-4.30.01.61.9-3.2-4.0-6.13.7-2.2]x2(1,1)=7.1;x2(1,2)=;x2(2,1)=-1.4;x2(2,2)=;x2(3,1)=4.5;x2(3,2)=;x2(4,1)=6.3;x2(4,2)=;x2(5,1)=4.2;x2(5,2)=;x2(6,1)=1.4;x2(6,2)=;x2(7,1)=2.4;x2(7,2)=;x2(8,1)=2.5;x2(8,2)=;fori=1:8r1(i)=x1(i,1);end;fori=1:8r2(i)=x1(i,2);end;fori=1:8r3(i)=x2(i,1);end;fori=1:8r4(i)=x2(i,2);end;figure(1);plot(r1,r2,'*',r3,r4,'o');holdon;%保持当前的轴和图像不被刷新，在该图上接着绘制下一图x1(:,3)=1;%考虑到不经过原点的超平面，对x进行扩维x2(:,3)=1;%使x'=[x1]，x为2维的，故加1扩为3维%进行初始化w=rand(3,1);%随机给选择向量，生成一个3维列向量p=1;%p0非负正实数ox1=-1;%代价函数中的变量ox2=1;%当x属于w1时为-1，当x属于w2时为1s=1;%标识符，当s=0时，表示迭代终止n=0;%表示迭代的次数w1=[0;0;0];whiles%开始迭代J=0;%假设初始的分类全部正确j=[0;0;0];%j=ox*xfori=1:45if(x1(i,:)*w)0%查看x1分类是否错误，在x属于w1却被错误分类的情况下，w'x0w1=w;%分类正确，权向量估计不变else%分类错误j=j+ox1*x1(i,:)';%j=ox*x。进行累积运算J=J+ox1*x1(i,:)*w;%感知器代价进行累积运算endendfori=1:55if(x2(i,:)*w)0%查看x2分类是否错误，在x属于w2却被错误分类的情况下，w'x0w1=w;%分类正确，权向量估计不变else%分类错误j=j+ox2*x2(i,:)';%j=ox*x。进行累积运算J=J+ox2*x2(i,:)*w;%感知器代价进行累积运算endendifJ==0%代价为0，即分类均正确s=0;%终止迭代elsew1=w-p*j;%w(t+1)=w(t)-p(ox*x)进行迭代p=p+0.1;%调整pn=n+1;%迭代次数加1endw=w1;%更新权向量估计endx=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-8end所得的结果如图3所示：图3感知器算法分类图2.2最小二乘法基于分类判别的思想，我们期望w1类的输出为y1=-1,w2的输出为y2=1。但实际的输出和期望并不总是相等的。运用最小二乘法（LeastSquaresMethods），可以让期望输出和真实的输出之间的均方误差最小化，即：2()[|*|]ˆargmin()TwJwEyxwwJw（5）要使得J(w)最小，需要满足正交条件（orthogonalitycondition）：()2[*(*)]0TJwExyxww（6）可以得到：1ˆ*[]xwRExy（7）ˆw就是求得的加权向量。其中：1112121[*][*][*][*][*][*][*]llTxlllExxExxExxExxRExxExxExx（8）称为自相关矩阵；1[]lxyExyExy（9）称为期望输出和输入特征向量的互相关。通过最小均方误差算法实现线性分类的程序流程如图4所示：开始初始化求自相关矩阵求输入与期望输出的互相关计算w的估计值结束图4最小均方误差算法程序流程图MATLAB程序源代码如下：functionMSE1()clearall;closeall;%样本初始化%数据同上一算法，略;holdon;%保持当前的轴和图像不被刷新，在该图上接着绘制下图%初始化函数y1=-ones(45,1);%w1类的期望输出为-1y2=ones(55,1);%w2类的期望输出为1x1(:,3)=1;%考虑到不经过原点的超平面，对x进行扩维x2(:,3)=1;%使x'=[x1]，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-8disp(w);%显示权向量end所得结果如图5所示：图5最小二乘法分类图2.3支撑矢量机（SVM）SVM是针对线性可分情况进行分析，对于线性不可分的情况，通过非线性映射算法将低维输入线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间可以采用线性算法对样本的非线性特征进行线性分析。而且，SVM是基于最优化理论的算法，在特征空间中构造最优超平面，且这个最优超平面是全局最优的，同时，支持向撑矢量机的最优超平面分类器是唯一的。在线性可分的情况下，我们想要设计一个超平面，使得所有的训练向量正确分类：0()0Tgxwxw（10）由于感知器算法可能收敛于任何可能的解，显然，这样设计得到的超平面不唯一的。最优超平面是使得每一类数据与超平面的距离最近的向量与超平面之间的距离最大的这样的平面，或者说，最优超平面是使得超平面在每一个方向上与w1类、w2类中各自最近的点距离都相同。这样，我们设计的分类器的容量就更大，两类数据被错误分类的概率更小；同时当面对未知数据的分类时，最优超平面可靠度最高。最优超平面可以通过求解二次优化问题来获得：21min()2Jww（11）满足约束条件：0()1,1,2,,TiiywxwiN（12）在样本数目特别大的时候，可以将二次规划问题转化为其对偶问题：1,1max2NTiijijijiijyyxx（13）*10,1Niiiiwyx（14）*0Tiwywx（15）满足约束条件：10,0,1,2,NiiiiyiN（16）这里，i是拉格朗日算子，*w是最优超平面的法向量，*0w是最优超平面的偏移量。在这类优化问题的求解中，根据karush-kuhn-tucker条件，求得的解必满足：010,1,2,,TiiiywxwiN（17）从式中我们可以发现，对于i=0这样的点对于样本分类没有任何作用，只有i0时的样本才对分类起作用，这些样本就称为支撑矢量。通过SVM算法实现分类的程序流程如图6所示：开始数据初始化求解二次规划问题最优解计算权向量及松弛变量绘图，输出结果结束图6SVM算法程序流程图MATLAB程序源代码如下：functionSVM()closeall;clearall;%数据初始化略holdon;%保持当前的轴和图像不被刷新，在该图上接着绘制下图y1=ones(45,1);%对于每一个xi，yi为相应的标识器，对于w1为1,对于w2为-1y2=-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大于等于0lambda=fmincon('Optimization',l,A,b,Aeq,beq,lb);%用fmincon函数来求解非线性多变量约束问题，其中Optimization为等价最优任务w=X'*(lambda.*Y);%求解支撑矢量s=find(lambda0);%提取非0的元素位置下标构成新矩阵sum=0;%初始化累计变量N=length(s);%算出非0元素的个数fori=1:N;j=s(i);sum=sum+Y(j)-X(j,:)*w;%由条件w