利用梯度下降法的分类实现

1、模式识别题目利用梯度下降法的分类实现院系专业班级学生姓名学号1、问题重述利用Matlab软件编写梯度下降法函数，利用该函数对以下三组数据进行分类1)数据一：第一类：(0,0)(0,1)第二类：(1,0)(1,1)2)数据二：第一类：(90,150)(90,160)(80,150)(60,140)第二类：(60,105)(50,80)(50,90)(80,125)3)数据三：第一类：(0,0)(1,1)第二类：(1,0)(0,1)要求在以下不同情况下进行测试，并对结果进行对比分析。1)初始权值取3种不同的值；2)步长取不同的值，可以尝试变步长方法；3)采用单样本修正法和全样本修正法两种方式；4)

2、单样本情况下不同的样本迭代次序，从1到n,和，从n到1。2、算法流程梯度下降法利用函数的极值原理来进行寻优，是一种常用的线性分类方法。2.1 算法特性梯度下降法的运算结果和执行过程具有不定性，这是由算法本身特点所导致的。梯度下降算法往往会随着实验的重复展现不同的结果。最终的寻优结果与初始权值的选择和样本数据的迭代顺序有关。止匕外，在使用梯度下降法之前最好首先确定所求结果的大致位置，这样可以缩短运算时间，提高运行效率和准确程度。2.2 定步长与变步长梯度下降的步长直接影响着算法的效率。合理选择步长dt可以极大的减轻运算压力，提高算法的精度。常用的固定增量法是按定步长的方式进行运算的，每次迭代算法

3、以同样的速率前进，直到找到最优结果。随着运算次数的增加，权向量越来越接近最优结果，此时适当的减小步长，可以提升算法的运行效率。除了定步长方式，本次作业还选择了线性变步长的算法，即dtk+1=a*dtk。根据黄金分隔定律,将a选为0.618,以此实现变步长的梯度下降法。2.3 固定增量法固定增量法是一种代表性的梯度下降法，它的核心是迭代运算。每次迭代利用误分类的数据修正权向量，直到权向量满足要求或者算法运行时间达到上限。根据修正方法的不同，固定增量法又分为单样本修正法和批量修正法。单样本修正法是每出现一个误分类的样本就修正一次权向量。而批量修正法则是将所有样本数据都计算一次后，再根据误分类的样本

4、修正权向量，之后再进入下次迭代。单样本修正算法和批量修正算法的核心流程如下图所示。单样本修正法输入样本Yn、权向量A利用感知准则构建增广向量Yn',计算样本数量n连续n组数据，存在AYn，=0，i=0i<=n输出权向量AAX'<0TA=A+dt*Yni=i+1批量样本修正法输出权向量A图1固定增量法算法流程3、运行结果3.1数据1）在步长为141,单样本修正条件下，三种不同初始权值的分类初始权值中口口口0.0,6OfC0.4I-2,1二口0.20.5图2三种不同初始权值下的分类结果表1三种不同初始权值下的分类对比初始权值寻优结果寻优轮数0,0,01,-2,0410,

5、10,101,-4,211100,100,1001,-27,2479对比三条输出曲线，可以发现不同的初始权值会导致出现不同的分类函数。此外，初始权值选择的越合理，越接近寻优结果，代码的运行次数越少。因此一个合理的初始权值可以有效的提高代码效率，提升分类结果的满意程度。2）在初始权值为0,0,0,单样本修正方法下进行的不同步长的分类b01£0.90.9D.80.6口.707D.60.60.5l/W-xl后田0.5040.40.30.30.20.2U10.1lisynt步长出=010.204Q.0.9103.0236-0.BE2M=0.1111变步长。皿=口1邺）=061Edt（k-1）

6、0.20.40.6OS1%图3三种不同步长下的分类结果表2三种不同步长下的分类结果Xdt寻优结果寻优轮数55,-10,040.10.1,-0.2,04初值0.1,以0.689的速度线性变化0.0236,-0.0382,02步长的选取会对最后的寻优结果产生一定的影响，但更多的是影响寻优的效率。随着权向量接近越来越接近寻优结果，适当减小步长可以提升算法的运行效率。3）在初始权值0,0,0,步长dt=1条件下，单样本与多样本的分类结果对比图4单样本修正与批量样本修正下的分类结果对比表3三种不同步长下的分类结果修止方式寻优结果寻优轮数单样本1,-2,04批量0.1,-0.2,05因为算法的不同，单样本

7、修正与批量样本修正下的寻找的分类函数会有一定的不同，代码的运算效率也因此产生差异3.2数据二1）在步长为0.01,单样本修正方式下，初始权值为-700,0,0下进行分类，以直线的形式将线性分类函数的搜索过程展现在下图当中。图5和图6分别将单样本和多样本修正法对分类函数的寻优过程呈现出来。根据两幅图像，可以明显的发现两种寻优方式的计算轨迹是有所不同的2）在步长为0.01,单样本修正方式下进行的，三种不同初始权值的分类图7三种不同初始权值下的分类结果表3三种不同初始权值下的分类对比初始权值寻优结果寻优轮数-700,1,10-1559.9,4,9.521461-200,0,10-200.07,-3.

8、7,9.55125,0,1-155.89,0.4.0.95555084改组数据可以明显的体现初始权值的选取对寻优结果和运行效率的影响。3）在初始权值为0,0,0,单样本修正方法下进行的不同步长的分类图8三种不同步长下的分类结果表4三种不同步长下的分类结果Xdt寻优结果寻优轮数10-156665,402,955347230.01-765.01,0.3,5.411初值0.1,以0.618的速度线性变化-765.0024,1.8111,4.80043合理的选取步长会缩短代码的运行时间。此外合理选择变步长方式可以有效的提升运行效率。4）在初始权值0,0,0,步长dt=1条件下，单样本与多样本的分类结果

9、对比图9单样本修正与批量样本修正下的分类结果对比表5三种不同步长下的分类结果修正方式寻优结果寻优轮数单样本-765.01,0.3,5.411批量-765.02,-0.4,5.721批量修正法和单样本修正的运行效率不同，训练出来的分类函数也不同，但二者都可以成功对训练样本进行分类3.3数据三图10非线性可分数据搜寻过程表6数据三的分类结果寻优结果寻优轮数（上限10000）初始权值0,0,0,dt=0.1,单样本修正法无10000初始权值0,0,0,dt=0.1,批量修正法无10000初始权值0.5,0.5,0.5,dt=0.1,单样本修正法无10000初始权值0.5,0.5,0.5,dt-0.1

10、变步长，批量修正法无10000无论以哪种方式进行分类，都无法得到合适的分类结果。这表明梯度下降法是无法解决非线性问题的附录:固定增量法函数代码9值定增量法求线性判别函数%俞入变量：X1-第一类样本数据矩阵，n*m,n代表数量,m代表维度%X2-第二类样本数据矩阵，n*m,n代表数量，m代表维度%A-权向量初值%dt-步长，默认为1%mode-0选择单样本修正法，1选择批量修正法，默认为0%dt_fix-0变步长，1-定步长，默认为1functionoutput,N=FixedIncrement(X1,X2,A,dt,mode,dt_fix)%合定参数dt、modedt_fix的默认值ifnar

11、gin<4dt=1;mode=0;dt_fix=1;elseifnargin<5mode=0;dt_fix=1;elseifnargin<6dt_fix=1;endn1=size(X1,1);Y1=ones(n1,1)X1;n2=size(X2,1);Y2=ones(n2,1)X2;Y=Y1;-Y2;%增广矩阵n=n1+n2;x1min=min(abs(Y(:,2);x1max=max(abs(Y(:,2);x2min=min(abs(Y(:,3);x2max=max(abs(Y(:,3);Error=0;time=0;deadline=10000;%上限Object=0;A

12、X=A;%记录A的变化ifmode=0;%单步修正法whileObject<nfori=1:nifA*Y(i,:)'<=0Object=0;ifdt_fix<=0dt=dt*0.618;%变步长endA=A+dt*Y(i,:);AX=AX;A;elseObject=Object+1;endendtime=time+1;iftime>deadline%防止死循环Error=1;break;endendelseifmode=1%批量修正法whileObject<nAw=zeros(1,size(A,2);Object=0;fori=1:nifA*Y(i,:)&

13、#39;<=0ifdt_fix<=0dt=dt*0.618;%变步长endAw=Aw+dt*Y(i,:);elseObject=Object+1;endendA=A+Aw;AX=AX;A;time=time+1;iftime>deadlineError=1;break;endendendifError>0output=zeros(1,size(A,2);%表示没有找到合适的结果elseoutput=A;m=size(AX,1);ColorA=copper(m);%渐变颜色figure;scatter(X1(:,1),X1(:,2),'A','r');holdon;scatter(X2(:,1),X2(:,2),'o','b');forj=1:mfun=(x1,x2)AX(j,:)*1;x1;x2;hf1=ezplot(fun,x1min*0.5,x1max*1.5,x