模式识别作业2

模式识别作业2

模式识别作业⼆

硕⾃171班杨晓丹21722160251题⽬

数据：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）2、不同情况下的结果测试：

1）初始权值取3种不同的值

2）步长取不同的值，可以尝试变步长⽅法

3）采⽤单样本修正法和全样本修正法两种⽅式

4）单样本情况下不同的样本迭代次序，从1到n，和，从n到1

3、第2组数据可以画画每次迭代后的分类线试试

2实验原理与⽅案

2.1算法原理

本次实验采⽤感知器模型对样本进⾏分类，将两组样本标准化为增⼴矩阵y，并寻找出ay>0的权向量a。定义感知函数如下:∑

J P(a)=

(?a T y)(1)

y?y h

式中y h是被权向量a错误分类的样本。存在错误的样本数是，感知函数的值⼤于0，当样本全部被正确分类时，感知函数的值为0。所以⽬标是通过改变权向量使感知函数的

值为0。对感知函数求导得：ay ?a =

∑

y?y h

y(2)则可得到梯度下降法的迭代公式:a(k+1)=a(k)+ρk

∑

y?y h

y(3)经过多次迭代后，若所有样本满⾜ay>0，则得到⼀个线性分类器。

若样本为⼆维，可将权向量视为三维空间中的向量，将y k视为超平⾯的法向量，则式ay>0表明在超平⾯法向量⽅向⼀侧的权向量满⾜解向量的要求，所有超平⾯法向量⽅向围成的空间就是解向量的解空间。迭代的过程就是权向量加上法向量，使权向量向解区移动的过程。2.2单步长梯度下降法计算流程

1.将样本标准化为增⼴矩阵Y

2.将增⼴矩阵中的列向量y k依次与权向量相乘，若Ay k不⼤于0，则迭代权向量A(k+

1)=A(k)+ρy k，若Ay k为正，则继续计算下⼀个向量，直⾄完成⼀轮相乘。

3.若⼀轮相乘的结果均为正，则找到解向量，否则重复步骤2、3。

2.3多步法梯度下降法计算流程

1.将样本标准化为增⼴矩阵Y

2.将增⼴矩阵与权向量相乘，即X=AY，若x h的结果不⼤于0，则对应的列向量y h

为误分类样本。3.将⼀轮计算中所有的误分类样本与权向量相加，即A(k+1)=A(k)+ρk ∑

y?y h

y

4.若X中的元素均⼤于0，则得到解向量，否则重复步骤2、3、4。

2.4变步长梯度下降法计算流程

1.将样本标准化为增⼴矩阵Y

2.将增⼴矩阵与权向量相乘，即X=AY，若x h的结果不⼤于0，则对应的列向量y h

为误分类样本。3.计算步长ρ=max(10e?k,0.1)

4.将⼀轮计算中所有的误分类样本与权向量相加，即A(k+1)=A(k)+ρk ∑

y?y h

y

5.若X中的元素均⼤于0，则得到解向量，否则重复步骤2、3、4。

2.5实验⽅案

1.⽤感知器求解样本的解向量，并改变权向量的初始值、步长、样本的顺序，观察权向

量的变化趋势、迭代次数。2.采⽤单样本修正法及全样本修正法求解解向量，⽐较两种⽅法的优劣。

3.采⽤变步长算法求解解向量，⽐较与定步长算法的优劣。

3实验过程3.1样本⼀

三维图中平⾯为增⼴矩阵列向量对应的超平⾯，红点为权向量在空间中的迭代过程，黄⾊三⾓点为解向量。

⼆维图中圆点代表第⼀类样本，X点代表第⼆类样本，蓝线为迭代中的权向量，红线为解向量。3.1.1改变权向量初始值

分别取权向量[-1-10]，[-1-20]，[-1-30]。

权向量变化图表明，初值为[-1-10]时，第⼀次迭代权向量超出解区，之后权向量贴在解区边缘，总共6次迭代进⼊解区。

初值为[-1-20]时，迭代过程中权向量贴着解区间，在四次迭代后权向量进⼊解区。

初值为[-1-30]时，权向量在两次迭代后进⼊解区。分类线总是沿着使错误分类样本被正确分类的⽅向移动。

3.1.2改变步长

分别改变步长的值为0.2，2，4。步长为0.2时，权向量缓慢到达解区间中，迭代次数为7次，分类线变化缓慢。步长为2时，权向量迅速到达解区中，迭代次数为2次，分类线变化迅速。步长为4时，权向量变化较⼤，两次越过解区，迭代次数为4次，分类线变化较激烈。

3.1.3变步长算法

步长变化为ρ=max (10?exp (?i ),0.1)。变步长算法的步长在开始时较⼤，随后逐渐减⼩，权向量可以迅速接近解区，然后细调。该⽅法迭代次数为3次，与步长为1的多步法相⽐，迭代次数少了2次。

ρ0ρ1ρ2ρ33.6788 1.35340.49790.1832A0

A1

A2A3-5.0000 2.3576-0.34910.1488-2.0000-2.0000-4.7067-4.70670.0000 3.6788 2.3254 2.3254A0Y

A1Y

A2Y A3Y -5.0000 2.3576-0.34910.1488-5.0000 6.0364 1.9763 2.47427.0000-0.3576 5.0558 4.55807.0000

-4.0364

2.7304

2.2325

3.1.4

改变样本次序

将样本的顺序颠倒，迭代的次数为2次，迭代结果也发⽣了变化。

3.1.5⼩结

1.权向量的初始值对迭代的次数和结果均有影响，⼀般权向量离解区较近时迭代次数较少。

2.步长的选择影响迭代次数。若步长选取较⼩，权向量向解区移动较慢，迭代次数较多。若步长选取较⼤，权向量向解区移动的时候可能会越过解区，在解区两侧来回震荡，迭代次数也较多。3.与多步法相⽐，单步法计算量较少。(样本⼆中更明显，也许样本数量越多计算量差距越⼤）

4.若参数设置合适，变步长算法的迭代次数⼀般⽐定步长算法少。

5.步长与初始权向量相同时，改变样本顺序会影响迭代次数与结果。A0tho迭代⽅法迭代次数A

[-1-10]1多步法3[1-31]

[-1-20]1多步法4[1-40]

[-1-30]1多步法1[1-31]

[-1-10]1单步法3[1-30]

[-1-20]1单步法2[1-30]

[-1-30]1单步法1[1-31]

[-1-20]0.2单步法6[0.2-20.4]

[-1-20]2单步法1[1-20]

[-1-20]4单步法3[3-60]

3.2样本⼆改变权函数的初值、迭代的步长、观察迭代次数与迭代结果。

样本⼆与样本⼀相⽐有特殊之处。改变样本的步长，迭代次数⼏乎没发⽣变化，得到的解函数结果也与步长成正⽐。略微改变权向量的初值，对迭代次数的影响也不⼤。当设置权向量的第⼀个元素为⼀较⼤值时，迭代次数减⼩了很多。A0ρ迭代次数A

[000]0.187871[-1558.849.5]

[000]187776[-155884095]

[000]1087776[-155880400950]

[10000]188250[-155884095]

[01000]187788[-155884095]

[0098]185938[-153384093][-2000000]188[-20012-10150]

3.2.1迭代次数问题探究权函数的变化趋势如下图所⽰：

由上图可知，权函数的k2,k3在迭代⼀定次数后围绕定值上下波动，⽽k1则不断下降直⾄完成分类。

权函数k2,k3放⼤图如下所⽰：

由上图可知，k2与k3的值陷⼊了⼀个周期性的循环之中，原因可能是每次错误分类样本的值与k2,k3存在⼀定的线性关系，⽽增⼴矩阵中的1和-1，与样本的数相⽐起来太⼩，所以迭代的次数较慢。3.2.2迭代⽅法的改进

将步长由⼀个标量变为三个量，即迭代⽅程改为:∑

A(k+1)=A(k)+[ρ1,ρ2,...,ρn].?

y(4)

y?y h

设权向量初始值为A0=[000],步长ρ=[10000]，迭代次数为1103次，得到的解向量为A=[?187000135]。3.3样本三

样本三为线性不可分类型的样本，程序迭代100000次后，未找到A使AY>0。线性分类器不能对⾮线性可分的样本进⾏分类。4总结

1.权函数的初始值影响迭代次数与结果，若初始值与结果偏离较⼤，则迭代次数较多，

若靠近解区间，则迭代次数较少。2.步长选择合适时，迭代次数较少。若步长较⼩，算法迭代次数较多，若步长较⼤，则

算法容易在解区附近震荡，迭代次数会增多。在特殊情况下，步长的设定不影响迭代的次数。3.单步法的权函数迭代次数多于多步法，但与样本相乘的次数少于多步法，在样本较多

的情况下计算量会少于多步法。样本的顺序会对单步法的迭代次数与结果产⽣影响。4.变步长算法在参数合适时迭代次数少于定步长算法。

5.分别对k1,k2,k3设置合适的步长ρ1，ρ2，ρ3能减少迭代次数。

6.线性分类器只能对线性可分的样本进⾏分类。