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

1、模式识另【题 目利用梯度下降法的分类实现专业班级学生姓名学 号二O八年三月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）步长取不同的值，可以尝

2、试变步长方法；3）采用单样本修正法和全样本修正法两种方式；4）单样本情况下不同的样本迭代次序，从 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' <=03rTi=0i<=nAYn' <0输岀权向量A输岀权向量A图1固定增量法算法流程13、运行结果3.1数据一1）在步长为1,单样本修正条件下，三种不同初始权值的分类社I洁权值加卩口口图2三种不同初始权值下的分类结果11表1三种不同初始权值下的分类对比初始权值寻

5、优结果寻优轮数0,0,01,-2,0410,10,101,-4,211100,100,1001，-27,2479对比三条输出曲线，可以发现不同的初始权值会导致出现不同的分类函数。此外，初始权值选择 的越合理，越接近寻优结果，代码的运行次数越少。因此一个合理的初始权值可以有效的提高代码效 率，提升分类结果的满意程度。2）在初始权值为0,0,0，单样本修正方法下进行的不同步长的分类kOVo仏09c.g-Dl9U00.8ae07a.7FD.706qjs-Q.505b-$ Q百-1/10 -f 0.5沁36oaU4C.4h.4-0.30J3i.0.30210.2D.20.1Q.11阳i托n|步椅出=5

6、歩圭d:=C.100.20 40.62.3as:U060.60 20.405 oe T图3三种不同步长下的分类结果表2三种不同步长下的分类结果步长dt寻优结果寻优轮数55,-10,040.10.1,-0204初值0.1，以0.689的速度线性变化0.0236,-0.0382,02步长的选取会对最后的寻优结果产生一定的影响，但更多的是影响寻优的效率。随着权向量接近越来越接近寻优结果，适当减小步长可以提升算法的运行效率。3）在初始权值0,0,0，步长dt=1条件下，单样本与多样本的分类结果对比单环丰修EQ0 3L0.8-07-1 -孑屛=00.4-0 3-0.2-a.1-1 11 IIa口.2nd

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

8、的分类160130f 1ZI110初SW盼阿口JQ图7三种不同初始权值下的分类结果OICO表3三种不同初始权值下的分类对比初始权值寻优结果寻优轮数-700,1,10-1559.9,4,9.521461-200,0,10-200.07,-3.7,9.55125,0,1-155.89,0.4.0.95555084改组数据可以明显的体现初始权值的选取对寻优结果和运行效率的影响。图8三种不同步长下的分类结果3）在初始权值为0,0,0，单样本修正方法下进行的不同步长的分类表4三种不同步长下的分类结果步长dt寻优结果寻优轮数10-156665,402,955347230.01-765.01,0.3,5.4

9、11初值0.1，以0.618的速度线性变化-765.0024,1.8111,4.80043合理的选取步长会缩短代码的运行时间。此外合理选择变步长方式可以有效的提升运行效率。4）在初始权值0,0,0，步长dt=1条件下，单样本与多样本的分类结果对比图9单样本修正与批量样本修正下的分类结果对比表5三种不同步长下的分类结果修正方式寻优结果寻优轮数单样本-765.01,0.3,5.411批量-765.02,-0.4,5.721批量修正法和单样本修正的运行效率不同，训练出来的分类函数也不同，但二者都可以成功对训练样本进行分类3.3数据三图10非线性可分数据搜寻过程 表6数据三的分类结果修正方式寻优结果寻

10、优轮数（上限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变步长，批量修正法无10000无论以哪种方式进行分类，都无法得到合适的分类结果。这表明梯度下降法是无法解决非线性问题的附录：固定增量法函数代码%固定增量法求线性判别函数%俞入变量：X1-第一类样本数据矩阵，n*m,n代表数量,m代表维度%X2-第二类样本数据矩阵,n*m,n 代表数量 ,m 代表维度%A-权向量初值%dt-步长，默认为 1% mo

11、de-0 选择单样本修正法， 1 选择批量修正法，默认为 0% dt_fix-0变步长， 1- 定步 长，默认为 1function output,N=FixedIncrement(X1,X2,A,dt,mode,dt_fix)%给定参数 dt 、 mode、 dt_fix 的默认值if nargin<4dt=1;mode=0;dt_fix=1;elseif nargin<5mode=0;dt_fix=1;elseif nargin<6dt_fix=1;end n1=size(X1,1);Y1=ones(n1,1) X1;n2=size(X2,1);Y2=ones(n2,1)

12、 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;AX=A;%记录A的变化if mode=0; % 单步修正法while Object<nfor i=1:nif A*Y(i,:)'<=0 Object=0; if dt_fix<=0 dt=dt*0.618;% end A=A+dt*Y(i,:); AX=A

13、X;A;elseObject=Object+1;endend time=time+1; if time>deadline %Error=1;break;endendelseif mode=1 % 批量修正法 while Object<n Aw=zeros(1,size(A,2); Object=0; for i=1:nif A*Y(i,:)'<=0 if dt_fix<=0 dt=dt*0.618;% end Aw=Aw+dt*Y(i,:);elseObject=Object+1;endendA=A+Aw;AX=AX;A; time=time+1; if tim

14、e>deadlineError=1;break;endendend变步长防止死循环变步长if Error>0output=zeros(1,size(A,2);% 表示没有找到合适的结果 elseoutput=A;m=size(AX,1);ColorA=copper(m);% 渐变颜色figure;scatter(X1(:,1),X1(:,2)F','r');hold on;scatter(X2(:,1),X2(:,2),'o','b');for j=1:mfun=(x1,x2) AX(j,:)*1;x1;x2;hf1=ezplot(fun,x1min*0.5,x1max*1.5,x2min*0.