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

模 式 识 别

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

现

院 系 专业班级 学生姓名 学 号

二○一八年三月

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) 单样本情况下不同的样本迭代次序，从1到n，和，从n到1。

2、算法流程

梯度下降法利用函数的极值原理来进行寻优，是一种常用的线性分类方法。 2.1算法特性

梯度下降法的运算结果和执行过程具有不定性，这是由算法本身特点所导致的。梯度下降算法往往会随着实验的重复展现不同的结果。最终的寻优结果与初始权值的选择和样本数据的迭代顺序有关。此外，在使用梯度下降法之前最好首先确定所求结果的大致位置，这样可以缩短运算时间，提高运行效率和准确程度。

2.2定步长与变步长

梯度下降的步长直接影响着算法的效率。合理选择步长dt可以极大的减轻运算压力，提高算法的精度。常用的固定增量法是按定步长的方式进行运算的，每次迭代算法以同样的速率前进，直到找到最优结果。

随着运算次数的增加，权向量越来越接近最优结果，此时适当的减小步长，可以提升算法的运行效率。除了定步长方式，本次作业还选择了线性变步长的算法，即dtk+1=a*dtk。根据黄金分隔定律，将a选为0.618，以此实现变步长的梯度下降法。

2.3固定增量法

固定增量法是一种代表性的梯度下降法，它的核心是迭代运算。每次迭代利用误分类的数据修正权向量，直到权向量满足要求或者算法运行时间达到上限。

根据修正方法的不同，固定增量法又分为单样本修正法和批量修正法。

单样本修正法是每出现一个误分类的样本就修正一次权向量。而批量修正法则是将所有样本数据都计算一次后，再根据误分类的样本修正权向量，之后再进入下次迭代。

单样本修正算法和批量修正算法的核心流程如下图所示。

单样本修正法批量样本修正法输入样本Yn、权向量A输入样本Yn、权向量A利用感知准则构建增广向量Yn’,计算样本数量n利用感知准则构建增广向量Yn’,计算样本数量n连续n组数据，存在AYn’<=0F连续n组数据，存在AYn’<=0FTi=0T向量Aw零初始化i=0Fi<=ni<=nFTFAYn’<0TFAYn’<0TA=A+dt*YnTAw=Aw+dt*Yni=i+1i=i+1A=A+Aw输出权向量A输出权向量A

图1 固定增量法算法流程

3、运行结果

3.1数据一

1）在步长为1，单样本修正条件下，三种不同初始权值的分类

图2 三种不同初始权值下的分类结果 表1三种不同初始权值下的分类对比

初始权值 [0,0,0] [10,10,10] [100,100,100]

寻优结果 [1,-2,0] [1,-4,2] [1，-27,24]

寻优轮数

4 11 79

对比三条输出曲线，可以发现不同的初始权值会导致出现不同的分类函数。此外，初始权值选择的越合理，越接近寻优结果，代码的运行次数越少。因此一个合理的初始权值可以有效的提高代码效率，提升分类结果的满意程度。

2）在初始权值为[0,0,0]，单样本修正方法下进行的不同步长的分类

图3 三种不同步长下的分类结果

表2 三种不同步长下的分类结果

步长dt 5 0.1

初值0.1，以0.689的速度线性变化

寻优结果 [5,-10,0] [0.1,-0.2,0] [0.0236,-0.0382,0]

寻优轮数

4 4 2

步长的选取会对最后的寻优结果产生一定的影响，但更多的是影响寻优的效率。随着权向量接近3）在初始权值[0,0,0]，步长dt=1条件下，单样本与多样本的分类结果对比

越来越接近寻优结果，适当减小步长可以提升算法的运行效率。

图4 单样本修正与批量样本修正下的分类结果对比

表3 三种不同步长下的分类结果

修正方式 单样本 批量

效率也因此产生差异。

寻优结果 [1,-2,0] [0.1,-0.2,0]

寻优轮数

4 5

因为算法的不同，单样本修正与批量样本修正下的寻找的分类函数会有一定的不同，代码的运算

3.2数据二

1) 在步长为0.01，单样本修正方式下，初始权值为[-700,0,0]下进行分类，以直线的形式将线性分类函数的搜索过程展现在下图当中。

图5 单样本搜寻过程

图6 批量修正搜寻过程

图5和图6分别将单样本和多样本修正法对分类函数的寻优过程呈现出来。根据两幅图像，可以

明显的发现两种寻优方式的计算轨迹是有所不同的。

2）在步长为0.01，单样本修正方式下进行的，三种不同初始权值的分类

图7 三种不同初始权值下的分类结果 表3三种不同初始权值下的分类对比

初始权值 [-700,1,10] [-200,0,10] [125,0,1]

寻优结果 [-1559.9,4,9.5] [-200.07,-3.7,9.5] [-155.89,0.4.0.955]

寻优轮数 21461 5 55084

改组数据可以明显的体现初始权值的选取对寻优结果和运行效率的影响。

3）在初始权值为[0,0,0]，单样本修正方法下进行的不同步长的分类

图8 三种不同步长下的分类结果

表4 三种不同步长下的分类结果

步长dt 10 0.01

寻优结果 [-156665,402,955] [-765.01,0.3,5.4]

寻优轮数 34723 11 3

初值0.1，以0.618的速度线性变化 [-765.0024,1.8111,4.8004]

合理的选取步长会缩短代码的运行时间。此外合理选择变步长方式可以有效的提升运行效率。

4）在初始权值[0,0,0]，步长dt=1条件下，单样本与多样本的分类结果对比

图9 单样本修正与批量样本修正下的分类结果对比

表5 三种不同步长下的分类结果

修正方式 单样本 批量

练样本进行分类。

寻优结果 [-765.01,0.3,5.4] [-765.02,-0.4,5.7]

寻优轮数 11 21

批量修正法和单样本修正的运行效率不同，训练出来的分类函数也不同，但二者都可以成功对训

3.3数据三

图10 非线性可分数据搜寻过程

表6 数据三的分类结果

修正方式

初始权值[0,0,0]，dt=0.1，单样本修正法 初始权值[0,0,0]，dt=0.1，批量修正法 初始权值[0.5,0.5,0.5]，dt=0.1，单样本修正法 初始权值[0.5,0.5,0.5]，dt=0.1变步长，批量修正法 题的。

寻优结果 寻优轮数（上限10000） 无 无 无 无

10000 10000 10000 10000

无论以哪种方式进行分类，都无法得到合适的分类结果。这表明梯度下降法是无法解决非线性问

附录：

固定增量法函数代码

%固定增量法求线性判别函数

%输入变量：X1-第一类样本数据矩阵,n*m,n代表数量,m代表维度 % X2-第二类样本数据矩阵,n*m,n代表数量,m代表维度 % A-权向量初值

% dt-步长，默认为1

% mode-0选择单样本修正法，1选择批量修正法，默认为0 % dt_fix-0变步长，1-定步长，默认为1

function [output,N]=FixedIncrement(X1,X2,A,dt,mode,dt_fix)

%给定参数dt、mode、dt_fix的默认值 if nargin<4 dt=1; mode=0; dt_fix=1; elseif nargin<5 mode=0; dt_fix=1; elseif nargin<6 dt_fix=1; end

n1=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;

AX=[A];%记录A的变化

if mode==0; %单步修正法 while Objectif A*Y(i,:)'<=0 Object=0; if dt_fix<=0

dt=dt*0.618;%变步长 end

A=A+dt*Y(i,:); AX=[AX;A]; else

Object=Object+1; end end

time=time+1;

if time>deadline %防止死循环 Error=1; break; end end

elseif mode==1 %批量修正法 while ObjectAw=zeros(1,size(A,2)); Object=0; for i=1:n

if A*Y(i,:)'<=0 if dt_fix<=0

dt=dt*0.618;%变步长 end

Aw=Aw+dt*Y(i,:); else

Object=Object+1; end end

A=A+Aw; AX=[AX;A]; time=time+1;

if time>deadline Error=1; break; end end end

if Error>0

output=zeros(1,size(A,2));%表示没有找到合适的结果 else

output=A; m=size(AX,1);

ColorA=copper(m);%渐变颜色 figure;

scatter(X1(:,1),X1(:,2),'^','r'); hold on;

scatter(X2(:,1),X2(:,2),'o','b'); for j=1:m

fun=@(x1,x2) AX(j,:)*[1;x1;x2];

hf1=ezplot(fun,[x1min*0.5,x1max*1.5,x2min*0.5,x2max*1.5]); set(hf1,'Color',ColorA(j,:)); end

fun=@(x1,x2) AX(m,:)*[1;x1;x2];

hf1=ezplot(fun,[x1min*0.5,x1max*1.5,x2min*0.5,x2max*1.5]); set(hf1,'LineWidth',1.5,'Color','b'); hold off; end

N=time;%计算的轮数