模式识别论文--结束版本

1、模式识别论文一结束版本线性判决器的设计与实现一模式识别课程论文1判别函数分类器的设计与实现1判别函数分类器判别函数分类器判别函数分类器判别函数分类器1.1判别函数概念判别函数概念判别函数概念判别函数概念直接用来对模式进行分类的准则函数。若分属于3 1, 3 2的两类模式可用一方程d(x)二0来划分，那么称d(x)为判别函数，或称判决函数、决 策函数。如，一个二维的两类判别问题，模式分布如图示，这些分属于3 1,3 2两类的模式可用一直线方程d(x)=o来划分。0)(32211=+=wxwxwdx 式中：21, xx 为坐标变量。图1-1两类二维模式的分布将某一未知模式x代入：32211)(wx

2、wxwd+二x若0)(>xd,则 loex类；）«xd,贝ij2oex类;若0）（二xd,则21ooggxx或或拒绝维数二3时：判别边界为一平面。0）（二xd 2x lx 0 is 2s +线性判决器的设计与实现一模式识别课程论文2维数>3 dt：判别边界为一超平面。1.2判别函数正负值的确定判别函数正负值的确定判别函数正负值的确定判别函数正负值的确定判别界面的正负侧，是在训练判别函数的权 值吋确定的。图1-2判别函数正负的确定d(x)表示的是一种分类的标准，它可以是1、2、3维的，也可以是 更高维的。1.3确定判别函数的两个因素确定判别函数的两个因素确定判别函数的两个因

3、素确定判别函数的两个因素1)判决函数d(x)的儿何性质。它可以是 线性的或非线性的函数，维数在特征提取时已经确定。已知三维线性分类 判决函数的性质就确定了判决函数的形式:4332211）（wxwxwxwd+二x非线性判决函数，其示意图如下图所示1 32 32x1x00）（二xd +线性判决器的设计与实现一模式识别课程论文图1-3非线性判决函数图示2)判决函数d(x)的系数，由所给模式样木确定的。2感知感知感知感知器器器器算法算法算法算法设计与实现设计与实现设计与实现设计与实现对一种分类学习机模型的称呼，属于有关机器学习的仿 生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念(rewa

4、rd-punishment concept) ”得到广泛应用。2.1感器算法感器算法感器算法感器算法原理原理原理原理及特点及特点及特点及特点2. 1. 1感知器算法原理感知器算法原理感知器算法原理感知器算法原理两类线性可分的模式类21, 3 3,设xwxdt)(二其中, t121,+二nnwwwwlw, t,nxxxl二x应具有性质(2-1)对样本进行规范化处理，即3 2类样本全部乘以(一1),则有：2)-(20) (t>=xwxd?99e<e>二 21t,0,0)(3xwx若若d 2x1x02x lx 0线性判决器的设计与实现一模式识别课程论文4感知器算法通过对已知类别的训

5、练样本集的学习，寻找一个满足上 式的权向量。感知器算法步骤：(1) 选择n个分属于31和3 2类的模式样木构成训练样木集 xi, : xn构成增广向量形式，并进行规范化处理。任取 权向量初始值w(l),开始迭代。迭代次数k二1。(2) 用全部训练样木进行一轮迭代，计算wt(k)xi的值，并修正权向量。分两种情况，更新权向量的值：1.0,若 0wtikxw分类器对第i个模式做了错误分类，权向量校正为:()()ickkxww+二+1c：正的校正增量。2.若(),0t>ikxw分类正确，权向量不变：()okkww二+1,统一写为：00 00 (),01,0tkkkkkkck99+二9+99ww

6、xwwxwx(2-3)(3) 分析分类结果：只要有一个错误分类，冋到(2),直至对所有 样本止确分类。感知器算法是一种赏罚过程：分类正确吋，对权向量“赏”这里用“不罚”,即权向量不变；分类错误吋，对权向 量“罚”对其修改，向正确的方向转换。2. 1.2感知算法特点感知算法特点感知算法特点感知算法特点一收敛性收敛性收敛性收敛性 收敛性：经过算法的有限次迭代运算后，求出了一个使所有 样木都能正确分类的w,则称算法是收敛的。感知器算法是在模式类别线性可分条件 下才是收敛的。线性判决器的设计与实现一模式识别课程论文52. 1. 3感知器算法用于多类情况感知器算法用于多类情况感知器算法用于多类情况 感知

7、器算法用于多类情况采用多类情况3的方法时，应有:co ex,则(),)(ijddjih?>xx mj, 1l=对于m类模式应存在m个判决函数：midi,l,l=,算法主要内容：设有m中模式类别：mo3 3,21l设其权向量初值为：omjj, 1, 1l二w训练样木为增广向量形式，但不需要规范化处理。第k次迭代吋，一个属于3 i类的模式样本x被送入分类器，计算所有判别函数0 ()mjkkdjj,l,tl=xw(2-4)分二种情况修改权向量: 若0 ()mjijkdkdji,2, 1;,l=?，则权向量不变;()()mjkkjj,2, 1, 1l二二+ww 若第l个权向量使ookdkdliw

8、,则相应的权向量作调整，即：0 00 00 0?9999h 二+?二+二+lijkkckk ckkjj11 11,111wwxwwxww(2-5)c为正的校正增量只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法 收敛。2.2实例说明 实例说明实例说明实例说明为了说明感知器算法的具体实现，下面举出实例加以说明：已知两类训练样本:13t10,0=xt21,0=x :23t30,1 二xt41,1 二x用感知器算法求出将模式分为两类的权向量解和判别函数。解：所有样木写成增广向量形式；进行规范化处理，属于32的样本 乘以(-线性判决器的设计与实现一模式识别课程论文1)t11,o, 0=xt

9、21,1,0二x t31,0, 1?二x t41,1, 1?二 x任取w(l)=0,取c=l,迭代过程为:第一轮：0,00, 0, 0)1(1t 二9999999999二 xwt,0,0)l()2(,0=+=wxww 故1,1101,0, 0)2(2t 二9999999=xwt1,o, 0)203(, 0=>ww 故-l,1-01-1,0, 0)3(3t 二9999999=xwt30,0, 1-)3 ()4(, 0=+=xww 故1,1-1-1-0, 0, 1-)4 (4t 二999999=xwto, 0, 1-)4 ()5(, 0=>ww 故 有两个 wt(k)xi wo 的情况

10、(错判), 进行第二轮迭代。第二轮：jt11t1,0, 1-)5()6 (,00)5 (+w二xwwxw 故t2t1,0, l-(6)7(,01)6(=>=wwxw 故t33to,0, 2-) 7 () 8 (, 00) 7 (=+=xwwxw 故tto ,0, 2-) 8 () 9 (, 02) 8 (=wwxw 故 第三轮:t11t1,0, 2-)9() 10(, 00)9(二+二w二xwwxw 故(10)11(,01)10(2twwxw二二故)11()12(,01)11(3twwxw二二故)12()13(,01)12(4twwxw二二故 第四轮:)13()14(,01)13(1tw

11、wxw二二故线性判决器的设计与实现一模式识别课程论文7)15(,01)14(2twwxw二二故)15()16(,01)15(3twwxw二二故)16()17(,01)16(4twwxw二二故该轮迭代的分类结果全部止确，故解向量t1,o, 2?=w相应的判别函数为：12)(1+二xdx图2-1判决函数示意图判别界面d(x)二0如图示。当c、w(l)取其他值吋，结果可能不一样, 所以感知器算法的解不是单值的。2. 3 mat lab的感知器算法的感知器算法的感知器算法的感知器算法设计与设计与设计与设计与实现实现实现实现本设计是按照线性函数判决函数的感知算法思想结合数字识 别，来进行设计，通过训练数

12、字样木(每个数字样本都大于120),结合个人写字习惯, 记录测试结果,最后通过mat lab编码來实现感知器的数字识别。2. 3. 1 matlab代码设计代码设计代码设计代码设计function y=jiangcheng(sample)clc;load templet pattern; 2x ()0121 二+?二xdx ()0, 13x ()l,02x () 1, 14x lx 1 o g 2e ()0,01x 线性判决器的设计与实现一模式识别课程论文8w二zeros (26, 10);d=;maxpos=0;maxval=0;f 二1；n= ;m二;%依次输入样本for j二1:100f

13、or i二1:10f 二1；pattern(i) feature(26, j)=1;for k=l:10m二pattern(i). feature(:, j);d (k) =w (:, k) *m;end%判断是否为最大值，如果是，f二1,否则f二0；for二1:10if k二iif d(i)<=d(k)i 二0;endendend%修正权值if ffor k=l:10if k二二iw(:, k) =w(:, k) +pattern(i) feature(:, j);elsew(:, k) =w(:, k)-pattern(i). feature(:, j);endendendenden

14、dsample(26)=1;h=;%计算各类别的判别函数for k=l:10h(k)=w(:k)'*sample'endmaxval, maxpos=max(h);y=maxpos-l;线性判决器的设计与实现一模式识别课程论文92. 3. 2 mat lab实现实现实现实现首先通过，手写输入0-9个数字的训练样例各130个，如下图所示：图2-2数字训练样品训练样木准备好后，进行数字识别测试,其测验如下:图2-3数字测验结果正确样例图2-4数字测试不正确样例线性判决器的设计与实现一模式识 别课程论文102. 3. 3设计设计设计设计结果分析结果分析结果分析结果分析通过多次手写验证

15、测试，有65%通过，其结果如节显示， 由于模式识别的算法复杂，步骤较多，实现起来有一定的难度。为了使样品库少一些, 将精力着重放在算法的理解及编程实现上，此次设计用的是6x6的设计模板，这 个比较小，其对测试结果的正确性起着确定性的作用。故增大设计模板以及提高 算法的精确度可以使计算更为准确。3增量校正算法增量校正算法增量校正算法增量校正算法设计与实现设计与实现设计与实现设计与实现3. 1增量校正算法原理增量校正算法原理增量校正算法原理增量校正算法原理增量校正算法采用绝对偏差的平均值为最小的 原则，这时准则函数取为|)(|), (xwxrexwjt(3-1)式中iiwxwxixr£?

16、二，1,0)(3-2)上式对iw进行偏微分，可得)(sgnxwxrxejt 11wi?9 二99(3-3)式中xwxrxwxrtiit 11t iixwxr$？二?) (, 1 )(,1(3-4)(sgn由于 )(sgn ),( xwxrx wxwft 1199(3-5)因而算法方程为)()()(sgn) () ()1 (kxkwkxrkxkwkwtiikii?+二+(i (3-6)线性判决器的设计与实现一模式识别课程论文11wi的初值w(l)是可以任意选取的，上式也可以写成？9+<+三？)(d 0 0, 0( )(d 0 0, () 0 1(kxrkxkwkxkw kxrkxkwkxk

17、w 11tiki1tikikwei(3-7)算法的每一步都要校正权向量。而感知器算法只在某一个模式样品被 错误分类时才校正。由式(3-7)或式(5-40)看出，算法每一步得的校正 值都正比于增量ka ,故称为增量校正算法。对于多类问题來说，判别函数为)()(kwxdt 11=(3-8)如果iwxe,则 1 ) () (=xrkwxdit ii 而 0 ) 0 (=xrkwxdjii 3.2实例说明实例说明实例说明实例说明为了说明该算法的实现过程，这里举出如下例了，给定两类样晶：ttttw)0, 1,1(, )1, 0,1(, )0, 0,1(, )0, 0,0(:1ttttw)l, 1, 1(

18、,)1, 1,0(,)0, 1,0(,)1,0,0(:2现在用增量校正算法计算判别函数。在进行迭代运算之前，各样品的 特征向量经过增1： ttttw)l,0, 1,1 (,)1,1, 0,1 (,)1,0, 0, 1(, )1, 0,0, 0(:1ttttw) 1, 1, 1, 1(,)1, 1, 1,0(,)1,0, 1,0(,)1, 1,0,0(:2以w二0, kq二1/k进彳亍讨论。a) 令 t(0, 0, 0, 1)=x(1), ) 1 () 1 () 1 (sgn) 1 () 1 ()2(, x(1) 1 lxwxrxwwt?+= e a o 0 为 la=l, )l(xr=l 和)

19、l(xr> ) 1 () 1 (xwt因而 t(0, 0, 0,1) 0w(l)w(2)=+=b) 令 t(1,o, 0,1)二x ，)2()2()2(sgn )2()2()3(,1)2(,21,x (2) 221xwxrxwxrt?+= e a a 3因线性判决器的设计与实现 模式识别课程论文12为)2()2()2(xwxrt=因此)21,0, 0,21()1,0, 0, 1(1-w(2)w(3)?=tc) 令 t(l, 0,1,1)二x (3), ) 3 () 3 () 3 (sgn ) 3 () 3 () 4 (, 1) 3 (, x (3) 21xwxrxwwxrt?+=g a

20、3因为)3()3()3(xwxrt>因此tt)6531()1, 1,0, 1(31w(3)w(4)?二+二按照同样的步骤把一下的样品逐个输入。当输入样晶2wxw 时,0)(二kxri,以此确定函数)0 0(sgnkxkwkxrt?的符号，由此决定修正量的方向。一直进行到第15步,即k=15, 151=ka ,得到可以令人满意的结果，这吋tw)619. 0, 216. 0, 239. 0, 233. 0 () 16 (? 因此判别方程为:119. 0216. 0239. 0233. 02121)| () (321 二+?二？二？二xxxxwxwpxdt 3. 3 实现步骤 实现步骤实现步骤

21、实现步骤设各个权矢量的初始值为0,即0)0()0()0()0 (9210=wwwwlo 输入第k次样品)(kx,计算)()()(kxkwkdt 11=0 若0)k(rl)k(r,) (ii=exxwkxi,否则则。 计算）1 (+kwi , ?99二+)(d 0 0, 0( )1(d 0 0,()() 1(kxrkxkwkxkw kxrkxkwkxkw 11tiki1ikikwaq其中，k/lk二 u o 循环执行第二步，直到属于iw类的所有样品都满足条件：1jxdxdjih?)，()(线性判决器的设计与实现一模式识别课程论 文133. 4 mat 1 a.b实现增量校正算法实现增量校正算法实

22、现增量校正算法实现增量校正算法增量校正判决器实现与感知器算法的验证平台是 一样的，都是通过足够的数字样品训练，再通过增量校正算法来实现数字识别的测试。3.4.1mat 1 a.b的增量校正算法设计 的增量校正算法设计的增量校正算法设计的增量校正算法设计 其mat lab编码实现如下:function y=zengliangjiaozheng(sample) clc;load templet pattern;w二zeros(26, 10);d=;maxposo;maxval=0;r=;flag=l;numl=0：num2=0;f 二1；n= ;m二;while flagflag-o;num2二n

23、um2+l;forj=l:20for i二1:10numl=numl+l;%初始化向量当前类别r(i)为1r=0 00000000 0;r 二 1 ；f二1；pattern(i) feature(26, j)二1;for k=l:10m二pattern(i). feature(:, j);d(k)二w(:, k)*m;end%判断是否为最大值，不是则flag为1for k=l:10if qiif d(i)<=d(k)线性判决器的设计与实现一模式识别 课程论文14flag=l;endendend%修正权值for k=l:10if r(k)>d(k)w(:, k) =w(:, k) +

24、pattern(i). feature (:, j)/numl:elsew(:, k) =w(:, k)-pattern(i). feature(:, j)/numl;endendendendif num2>400flag=o;endendsample (26)=1;h=;%计算判别函数%计算各类别的判别函数for k=l:10h (k) =w (: k) '*sa.mple，;endmaxval, maxpos=max(h);y=maxpos-l; 3.4.2 matlab设计的数字验证平台的实现设计的数字验证平台的实现设计的数字验证平台的实现设计的数字验证平台的实现 在测试之

25、前需要足够的样木训练，以便 建立足够信息的样品库，训练示意图如下：线性判决器的设计与实现一模式识别课程论文图3-1数字训练示意图在随机测试屮，有70%的数字测试是通过的，下面把测试过程屮正确 的与不正确的分别以图形的形式展现出来：图3-2测试通过样例图3-3未通过测试样例线性判决器的设计与实现一模式识别课 程论文163. 4. 3设计结果分析设计结果分析设计结果分析设计结果分析增量校正算法与感知器算法最大的不同是，其每一步 都修改权值，而感知器只在发生错误的吋候修改权值，相对算法更加复杂，但是准确度比感 知器算法高。模糊k-均值判决器设计与实现一模式识别课程论 文17模糊k-均值判决器设计与实

26、现1模糊模糊模糊模糊k值算法原理 值算法原理值算法原理 值算法原理模糊k-均值算法基本思想：首先设定一些类及每个样本 对各类的隶属度；然后通过迭代，不断调整隶属度至收敛。模糊k值算法实现的步骤如下：(1) 确定模式类数k, 1<k<n, n为样本个数。(2) 根据先验知识确定样木从属于各类的隶属度()oiju ,建立初始隶属度矩阵()()ooiju=u, i为类别编号、矩阵的行号，j为样本编号、矩阵的列号。矩阵u(0)每列元素之和等于1。4321xxxx ()?999999. 03. 02.01.01. 07. 08. 09. 0ou 213 3(1-1)(3) 求各类的聚类中心o

27、liz, l为迭代次数。()()2；,2,11二二工工二二 mkilllnjm 1jjjm 1jilluuxz(1-2)例如，3个样本时：m mmmmni 11 11 111321321321 u nu p u +xxxz这是与一般0 ()e =可以看出：各聚类中心的计算必须用到全部的n个样木,k-均值算法的区别之一。(4) 计算新的隶属度矩阵u (l+1),矩阵元素计算如下:9 二mpj 1jijddli12)(1lp(1-3)2,2, 1,2, 12二二ninjkill模糊k-均值判决器设计与实现模 式识别课程论文式中，ijd是第l次迭代完成吋，第j个样本到第i类聚类中心oliz的距离。

28、例当有两个聚类中心吋，样本j对两个类别隶属度的计算：0 ()12121)0(12111?+二 mm jj<2+-ojddddu(1-4)可见：ijd越大，(0)1+lijy 越小。()()£ =9 二+kmpj 1jijddli12)(1in(1-5)为避免分母为零，特规定:若0二ijd,则(0)(0)(0)ipllpjijh二+二二+01, iip p(5)回到(3)求聚类中心，重复至收敛。收敛条件:(0)() ) e u 卩 wwww?99 ?+llijijjilmax, , e为规定的参数。(6)根据隶属度矩阵u(l+1)进行聚类:)onjllpjkpi j, 2, 1,

29、 olmaxllll二二+二+w w u u则 ij3 gx 类。4321xxxx如：0?999999. 03. 02.01.01.07. 08. 09.0ou 213 32实例说明 实例说明实例说明实例说明设有4个二维样本，分别是t10,0=x, t21,0-x t31,3-x, t利用模糊k-均值算法把它们聚为两类。解：(1)根据要求n二4, k=2o模糊k-均值判决器设(2)根据先验知识确定初始隶属度矩阵: 计与实现一模式识别课程论文194321xxxx ()?9999999. 03. 02.01.01.07. 08. 09.0ou 21 g) g)由u(0)可知，倾向于xi、x2、x3

30、 为一类,x4 为一类。()0oz二二 njm 1j 1jillli1» uxz 4321xxxx ()?9999 二9. 03. 02.01.01. 07. 08. 09. 0ou 21 33其中： t10,0-x t21,0=x t31,3=x t(3)计算聚类中心()01z> 002z,取 m二2,有()231.0137.0108.009.0(022221?9999?x+?9999?x+?99?x+?9999?x二 z ?99999 二+=09.0(2222 ()1.0(02222999?x+99999?x+?99?x+?9999?x=z ?99999 二+一84. 18

31、4.2 )9. 03.02.01.0(2222 ()()刀二9 二+kpmpj 1jijddli12)(o77o5oo匸84. 184.202z其中： t10,0=x t21,0-x t31,3二x模糊k-均值判决器设计与实现一模式识别课程论文20 t(4)计算新的隶属度矩阵u(l)。取呼2,分别计算) l(ijp o如对x3有：14. 5)59.01 ()77. 03(22213 二?+?二 d73.0)84. 11() 84. 23(22223 二?+?二 d得()12.073.014. 514. 523b345dddu类似地,321xxxx9999可得到u(l)中其它元素，有40 0?9

32、9. 088. 008. 008. 001.012. 092. 092. 0)l(lijuu21 g) g)若满足收敛条件()(0) ) e u 卩 wwww?99 ?+llijijjilmax,则迭代结束，否则返回(3)计算聚类中心。假设此吋满足收敛条件，迭代结束，贝u根据u进行聚类。)1()1(2111li 口 >>q, )l()l(2212u u>»>,1211, co coee/.xx ) 1 () 1 (1323m m>»>q, )l()l(1424u u>»>,2423, 3 3 e g .xx 3 ma

33、tlab 的模糊的模糊的模糊的模糊k-均值均值均值均值设计与设计与设计与设计与实现实现实现实现 本代码设计用随机函数randn与矩阵乘法函数结合一起产生4 组3列的矩阵数据样品，作为模糊k均值分类的对象，再设计simple_kmeans函数 实现k均值算法功能，即整个设计分两大步：第一步，产生分类的对象数据 一mat 1 ab 测试；第二步，模糊k均值算法的实现一对应matlab代码设计。()88.0)73.073.014.573.0(11122321322323=+二 ddddu模糊k-均值判决器设计与实现一模式识别课程论文213. 1 mat lab代码设计代码设计代码设计代码设计 fun

34、ction means, nmeans = simple_kmeans (x, k, maxerr) ndata., dims二 size (x) : dist 二 zeros (1, k) ;% initialprototype assignment (arbitrary) for i二1:ktmeans(i,:)二x(i, :) ; end means (k,:)二 mean(x(k:ndata, :) ; cmp 二 1 + maxerr; while (cmp > maxerr) % sums (class) and data counters (nclass) initiali

35、zation class = zeros(k, dims); nclass = zeros (k,1);% groups each elements to the nearestprototype for i=l:ndatafor j=l:k%euclidean distance from data to each prototypedist (j)二 norm(x(i, :)-means(j, :)2end% find indicesof minimum distanceindex_min 二find(dist-min(dist);% if there are multiple mindista.nces, decide randomlyindex_min 二index.min(ce订(length(index_min)*rand);class(index_min,:)二 class(index_min, :) + x(i,:);nclass(indexmin)二 nclass(indexjnin) + 1; end for i二1:kclass(i, :) = class(i, :) / nclass(i):end%compare results with previous