.
模式识别
`
题目利用梯度下降法的分类实
现
院系
专业班级
学生姓名
学号
二○一八年三月
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固定增量法
固定增量法是一种代表性的梯度下降法，它的核心是迭代运算。每次迭代利用误分类的数据修正权向量，直到权向量满足要求或者算法运行时间达到上限。
根据修正方法的不同，固定增量法又分为单样本修正法和批量修正法。
单样本修正法是每出现一个误分类的样本就修正一次权向量。而批量修正法则是将所有样本数据都计算一次后，再根据误分类的样本修正权向量，之后再进入下次迭代。
单样本修正算法和批量修正算法的核心流程如下图所示。
单样本修正法输入样本Y n 、权向量A 利用感知准则构建增广向量Y n ’,计算样本数量n 连续n 组数据，存在AY n ’<=0
A=A+dt*Y n
AY n ’<0
i<=n
i=0
i=i+1
T
T
T
输出权向量A 批量样本修正法
输入样本Y n 、权向量A
利用感知准则构建增广向量Y n ’,计算样本数量n
连续n 组数据，存在AY n ’<=0
Aw=Aw+dt*Y n
AY n ’<0
i<=n
向量Aw 零初始化
i=0
i=i+1A=A+Aw
T
T
T
输出权向量A
F
F
F
F
F
F
图1 固定增量法算法流程
3、运行结果
3.1数据一
1）在步长为1，单样本修正条件下，三种不同初始权值的分类
图2 三种不同初始权值下的分类结果
表1三种不同初始权值下的分类对比
初始权值寻优结果寻优轮数
[0,0,0] [1,-2,0] 4
[10,10,10] [1,-4,2] 11
[100,100,100] [1，-27,24] 79 对比三条输出曲线，可以发现不同的初始权值会导致出现不同的分类函数。此外，初始权值选择的越合理，越接近寻优结果，代码的运行次数越少。因此一个合理的初始权值可以有效的提高代码效率，提升分类结果的满意程度。
2）在初始权值为[0,0,0]，单样本修正方法下进行的不同步长的分类
图3 三种不同步长下的分类结果
表2 三种不同步长下的分类结果
步长dt 寻优结果寻优轮数
5 [5,-10,0] 4
0.1 [0.1,-0.2,0] 4
初值0.1，以0.689的速度线性变化[0.0236,-0.0382,0] 2 步长的选取会对最后的寻优结果产生一定的影响，但更多的是影响寻优的效率。随着权向量接近越来越接近寻优结果，适当减小步长可以提升算法的运行效率。
3）在初始权值[0,0,0]，步长dt=1条件下，单样本与多样本的分类结果对比
图4 单样本修正与批量样本修正下的分类结果对比
表3 三种不同步长下的分类结果
修正方式寻优结果寻优轮数
单样本[1,-2,0] 4
批量[0.1,-0.2,0] 5 因为算法的不同，单样本修正与批量样本修正下的寻找的分类函数会有一定的不同，代码的运算效率也因此产生差异。
3.2数据二
1) 在步长为0.01，单样本修正方式下，初始权值为[-700,0,0]下进行分类，以直线的形式将
线性分类函数的搜索过程展现在下图当中。
图5 单样本搜寻过程
图6 批量修正搜寻过程
图5和图6分别将单样本和多样本修正法对分类函数的寻优过程呈现出来。根据两幅图像，可以明显的发现两种寻优方式的计算轨迹是有所不同的。
