模式识别复习题

1、精品1、模式识别系统的基本构成单元，并对各单元简要解释?数据获取：用计算机可以运算的符号来表示所研究的对象- 二维图像：文字、指纹、地图、照片等- 一维波形：脑电图、心电图、季节震动波形等- 物理参量和逻辑值：体温、化验数据、参量正常与否的描述?预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原?特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征- 测量空间：原始数据组成的空间- 特征空间：分类识别赖以进行的空间- 模式表示：维数较高的测量空间，维数较低的特征空间?分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别- 基本做法：在样本训练

2、集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小2、写出K-均值聚类算法的基本步骤,例子见布置的作业题.算法：第一步：选K个初始聚类中心,zi（1）,Z2（1）,ZK（1）,其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本x按最小距离准则分配给K个聚类中心中的某一个Zj(1)。假设i=j时，Dj(k)=min乂-Zi(k)|,i=1,2,K,则xeSj(k),其中k为迭代运算的次序号，第一次迭代k=i,Sj表示第j个聚类，具聚类中心为

3、Zjo第三步：计算各个聚类中心的新的向量值，Zj(k+1),j=1,2,丛1Zj(k1)x,j=1,2,|,KNjxSj(k)求各聚类域中所包含样本的均值向量：Jj=Z|x-Zj(k+1,j=1,2J|,Kx。(k)其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若Zj(k+1)#Zj(k),j=1,2,K,则返回第二步，将模式样本逐个重新分类，重复迭代运算；若Zj(k+1)=Zj(k),j=1,2,K,则算法收敛，计算结束。例子：已知x1(0,0),x2(1,0)

4、,x3(0,1),x4(1,1),x5(2,1),x6(1,2),x7(2,2),x8(3,2),x9(6,6),x10(7,6),x11(8,6),x12(6,7),x13(7,7),x14(8,7),x15(9,7)x16(7,8),x17(8,8),x18(9,8),x19(8,9),x20(9,9),用K-均值算法进行聚类分析解：选k=2,Zi=x1，Z2=x10,弟一步：选取4(1)=为=,Z2(1)=x|0第二步：根据聚类中心进行聚类，得到§(1尸%？2,%?4?5,%?7,)<85(1)=x9,xl0,x11,x12,Ulx20第三步：计算新的聚类中心感谢下载载1

5、11.2500z1Fx；1)X=8(X1X2用X8)=1.125011,、z2="7xx=X9(x9X10|11x20)=N2XS2(1)1276667、Q.3333,第四步：因Zj(2)#Zj(1),j=1,2,故回到第二步第二步：根据新的聚类中心重新进行聚类，得到S(2)-Xl,X2,X3,X4,X5,X6,X7,X8S2(2)-X9,X10，X11,X12，HIX20第三步：计算新的聚类中心Z1(3)=x.1,J1.2500X(X1X2IX8)=X02)81.1250一1一1.Z2Fx；(2)X=7X9X10用rd7.6667。3333第四步：Zj(3)=Zj(2),j=1,2

6、,所以算法收敛，得聚类中心为7.2500)7.6667),z2=1.1250；27.3333)迭代结束3、最、剪辑、压缩近邻法的基本思想最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。剪辑近邻法基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率4、设有6个5

7、维模式样本如下，按最小/大距离准则进行聚类分析(直到分成三个类别为止，距离度量采用欧氏距离）XI：0,3,1,2,0X2：1,3,0,1,0X3：3,3,0,0,1X4：1,1,0,2,0X5：3,2,1,2,1X6：4,1,1,1,0按最大距离准则进行聚类分析：第1步：将每一样本看成单独一类，得G=X,G20）=X2,G3=%g40）=M,G50）=X5,g60）=%计算各类之间的欧式距离，可得距离矩阵Dc(0)g1N。）G2g30)（0）G4N。）G5c(0)G6G10（0）G2百0g30)85娓0（0）G47T30g50)后向巡V70g60)后R4显440第2步：矩阵D（0）中最大元素为

8、而,它是G1（0）和g60）之间的距离，将他们合并为一个新类为G1=G1(0),g60),g2Jg20),g3Jg30),g4Jg40),gETg?计算聚类后的距离矩阵DG1G21)G31)G;G51)G10CG2JT40G31)760CG4忌而0G51)布8abV60第3步：由于D中距离最大者为布，它是G，与G：之间的距离，于是合并Gi和G31),得新的分类为g2)=Gi,g,g22)=g2。,g32)=gJ,g42)=g5。同样，按最大距离准则计算距离矩阵D，得G1(2)g22)g32)g42)G10g22)而0g32)而*0g42)而60第4步：由于D中距离最大者为714,它是Gi与G2

9、之间的距离，于是合并得新的分类为g)=Gi(2),g22),g23)=g32),g33)=g42)满足聚类要求，如聚为3类，聚类完毕。5、设有5个6维模式样本如下，按最小/大距离准则进行聚类分析(距离度量采用欧氏距离)XI：0,1,3,1,3,4X2：3,3,3,1,2,1X3：1,0,0,0,1,1X4：2,1,0,2,2,1X5：0,0,1,0,1,0用最小聚类准则进行系统聚类分析：第1步：将每一样本看成单独一类，得G1（0）=X1,G20）=X2,G30）=X3G40）=X4,G5°）=X5计算各类之间的欧式距离，可得距离矩阵DG1(0)G;)g30)g40)GFGE0（0）G

10、2扃0g30)后0（0）G4而VT5万0g50)病出丘0第2步：矩阵D中最小元素为V3,它是630）和650）之间的距离，将他们合并为一类，得新的分类为G1-G1,G2-G2,G3-G37G5）,G4-G4计算聚类后的距离矩阵DG：G21)G31)G41)G10G21)V230G31)疡V240CG47240第3步：由于D中距离最小者为"，它是g30与G9之间的距离，于是合并G31)和Gf),得新的分类为Gi=Gi,g22)=G22),g32)XG,Gf)同样，按最小距离准则计算距离矩阵D，得g；2)g22)g32)G1(2)0g22)0g32)声压0第4步：同理得gF=Gi(2),

11、g23)=g22),g32)满足聚类要求，如聚为2类，聚类完毕。6、一个三类问题，其判别函数如下：di(x)=-x1,d2(x)=x1+X2-I,d3(X)=X1-x2-1设这些函数是在多类情况1条件下确定的。1)绘出其判别界面和每一个模式类别的区域。2)对如下三个样本所属模式作出判决：A=(45)T，B=(-25)T，C=(2-5)T例子：一个三类问题，其判别函数如下：d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-11、设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2、设为多类情况2,并使：d12(x)=d1(x),d13(x)=d2(

12、x),d23(x)=d3(x)绘出其判别界面和多类情况2的区域。绘出其判别界面3、设d1(x),d2(x)和d3(x)是在多类情况3的条件下确定的,和每类的区域d t(x)- xl0谑类判冽修乂4 域x2 L。d2(x)<0d：4(x)>0解：(1)其判别界面和每一个模式类别的区域如图中所示:A=(45)T属于，B=(-25)T属于不确定区域，C=(2-5)T属于a(2)其判别界面和每一个模式类别的区域如图中所示:dL2(x)=d2L(i)=il=O为+门类判别区域dl2 (i) >013(r)>0dL3(x)为 +心灵判别区 域 d(x)X) d；n(x)>od

13、ZLOc)为 4J Ld23(x)=d32(i)=xl-x21=0眠(Ji)为捌;()为+起类判别区域md23(x)>0dn(x) 一(m3 ii+x2-i-o(3)其判别界面和每一个模式类别的区域如图中所示:7、已知：u: X1, X2=(1 0 1) T, (0 1 1)T,W2： X3, X4=(1 1 0) T, (0 1 0)T。给定初始增广权向量W1= (1 1 1 1) T ,C=1 。要求：1)用感知器算法求模式分类的解向量2)写出判别函数和决策面方程。解：先求四个样本的增值模式xi=(1,0,1,1) TX2 = (0,1,1,1) T的>0X3=(1,1,0,1

14、)TX4=(0,1,0,1)T假设初始权向量第一次迭代：W1TX1=(1,1,1,1)W1TX2=(1,1,1,1)W1TX3=(1,1,1,1)W1=(1,1,1,1) TT (1,0,1,1)=3>0T (0,1,1,1)=3>0T (1,1,0,1)=3>0C=1所以不修正所以不修正所以彳QEw1W2=W1-X3=(0,0,1,0)TW2TX4=(0,0,1,0)T(0,1,0,1)=0所以彳正W2第一次迭代后，权向量W3 = (0,-1,1,-1)T,再进行第2,3，次迭代如下表:W3=W2-X4=(0,-1,1,-1)T训练样本wkTx修正式修正后的权值WRI迭代次

15、数对1011+W11111Xj0111+W111111均1101+Wi-/0010x401010011-1峋101101-120Xj0111+W41-1102均11010Wf0-22-1x40101JW50-22：1Xi1011+W50-22-1Xj0111-W5+迫0-1303x31101-w.0-130x40101-w.0-130峋1011+0-130Xj0111+w.0-1304x31101-w.0-130x40101-%0-130直到在一个迭代过程中权向量相同，训练结束W6=W=(0,-1,3,0)判别函数gX=-X23X3决策面方程：g(x)=x2+3x3=0即X2-3X3=08、已

16、知：wi:Xi=(0,2)T,X3=(2,0)T,X5=(-1,-1)T2：X2=(1,1)T,X4=(0,-2)T,X6=(-2,0)T给定初始增广权向量W1=(111)T,C=1。要求：用感知器算法求模式分类的解向量Wo解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(1,1,1)T,(0,0,0)T,(2,0,1)T,(2,2,0)T,(1,1,1)T因此算法不收敛，我们可以取循环中任一权值，例如取W=(2,2,0)T则判别函数为：g(x)=2x1+2x2判别面方程为：g(x)=2x1+2x2=0所以：x1+x2=0由图看出判别面H把二类分开，但其中x2错分到1类，而x1错分到

17、2类，但大部分分类还是正确的。9、对一大批人进行癌症普查，患癌者以3类代表，正常人以2类代表。已知P(1)=0.005,当然P(2)=1-0.005=0.995.设有一种诊断癌症的试验，其结果为“阳性”和“阴性”两种反应。假设根据临床记录发现这种方法有以下统计结果：患有癌症的人试验反应为阳性的概率=0.95,即p(x=阳|n)=0.95患有癌症的人试验反应为阴性的概率=0.05,即p(x=阴|3)=0.05正常人试验反应为阳性的概率=0.01,即p(x=阳|32)=0.01精品正常人试验反应为阴性的概率=0.99,即p（x二阴|32）=0.99问：若被化验的人具有阳性反应，他患癌症的概率为多少

18、?解:p但 I x=ro)=P（x=阳|孙尸（叫）P(xdH )P (x=阳|斜)P (斜)感谢下载载P(x=K|©1)P(©1)+P(x=W|02)P(s2)0.950.005八=0.3230.950.0050.010.995因为，P(W2|x=阳尸1-P(wi|x=阳)=1-0.323=0.677P(wi|x=阳)<P(w2|x=阳)故判决：正常10、已知P(i)=0.9,P(2)=0.1,p(x|1)=0.2,p(x|2)=0.4。且有如下决策表：损失状态决策312o106c210请按最小风险贝叶斯决策进行分类解：已知条件为P(1)=0.9,P(2)=0.1,p

19、(x|1)=0.2,p(x|2)=0.4。11=0,12=6,21=1,22=0利用贝叶斯公式分别计算出1及2的后验概率P|x = 0.818Px|1P1_0.20.9Px11PlPx|2P20.20.90.40.1再计算条件风险：R：1|x=v-ijP-j|x=-12P.2|x,>1.0922jIR22x八2jPj|x=21P-1|x=0.818j1由于RO|x>R(%|x)即决策为2的条件风险小于决策为1的条件风险，因此我们采取决策行动«2,即判断待识别的细胞x为2类一一异常细胞。11、设有如下三类模式样本集CD1,2和3,其先验概率相等，求Sw和Sb1:(10)T,

20、(20)T,(11)T2:(-10)T,(01)T,(-11)T3:(-1-1)T,(0-1)T,(0-2)T解：由于本题中有三类模式，因此我们利用下面的公式：3Sb=zP(M)(mi-m0)(mi-m。);m0为C类模式分布总体的均值向量i工3即：m0=Ex-7p(i)mii1mi为第i类样本样本均值m11 12 13 |tp0 1m221 -1 +0 -1 23 10+1 +12<3 )1 -10 0m3 二3 |L-1 -1-2J -3 _4 3,m0=1 3 -33 1 .2 I _331343,19193Sb1 - P( 'i)(mi -m0)(mi -m°)

21、t i 471)J 4 19 ")7 7)41+ 一9 id9j 7 |l 9【94 4)7K -9 上9j 11 |l 9 < 944 ；4949 Z1681+8181+811649494481 J1 8181 )<81一1218144A814481 12162 1381 8113 6281 人 181 81J一一t1-11-(i)(i)TSw=P(i)*E(x-mi)(x-mi)/=-G=；(xk()-mii)(xk()-m。i13T33kd-62712试用感知器算法实现逻辑与”、“或系数自己设定）一、用感知器算法实现逻辑“与”功能真值表：x1x2T00-1(0)01

22、-1(0)10-1(0)111设8=0.05,"=0.02,叫=0.058,820=0.05,转移函数为符号函数(1) (0)(1)(0)一S1Xi1X22-1=0+0-0.05=-0.05y=sgns()=-1、1=工-y-1-(-1)=0则有孙=0.058,©21)=0.05(2) (1)(2)(1)一S2=X'1x2/一1(2) =0+0.05-0.05=0y2=sgns(2)-1、2=丁2-丫2=T-(-1)=0则有仍，=0.058,022)=0.05功能。(初始加权值、阈值和训练速率(3) (2)(3)(2).S3=X1.，1X22=0.058+0-0.0

23、5=0.008y=sgns(3)=1Q3=T3-y3=-11=-2贝U有1(3)=0.0580.02(-2)1=0.023)=0.050.02(-2)0-0.05(4)(3)(4)(3)一S4=x1,1X212-(4) =0.018+0.05-0.05=0.018y4=sgns4)=14=T4-y4=1-1=0(4)(4)_则有必=0.018,02=0.05重复上述(1)(4)缶1(0)=81(4)=0.018,'20)=黄=0.05s1=X(1"0)WP0)”(5) =0+0-0.05=-0.05y1=sgn4)-1、1=工-y1=-1-(-1)=0则有孙(1)=0.018

24、,821)=0.05仍设日=0.05, "=0.02,81(0) =0.058,-0ov(2).(1),J2)(1)rS2X.1X2v2-二(6) =0+0.050.05=0y2=sgns(2)=-1、.2=t2_y2=7_(_1)=0则有仍，=0.018,co22)=0.05(3)(2)(3)(2)tS3=X'1x22-=0.018+0-0.05=-0.032y3=sgnsG)=-1。3=丁3-'丫3-1-'(7)-0则有以(3)=0.018,©23)=0.05820)=0.05,转移函数为符号函数(1) (0)(1)(0)Si=整.,1X22=0

25、0-0.05-0.05y1=sgn4)=1、.1=T1-y1=一1一(一1)=0则有81(1)=0.058,821)=0.05c_J2)(1),J2)(1)rS2X111X21-2-(2) =00.05-0.05=0C_J4)(3),J4)(3)TS4-X11-1X2,-2-1(8)=0.018+0.05-0.05=0.018y4=sgnS4)二14=t4-y4=1-1=0则有以(4)=0.018,024)=0.05最后所得加权值为叫=0.018,。2=0.05y=sgn4)=-12=T2-y2=1-(-1)=2则有1(2)=0.0580.0220=0.058(2)2=0.050.0221=0

26、.09(3) (2)(3)(2).Ss-X1'1X22"-=0.05800.05=0.008二、用感知器算法实现逻辑“或”功能y3=sgnS3)=1真值表:'3=丁3一丫3=1一1=0x1x2T则有切，=0.058,切23)=0.09-1(0)S4=x(4),f,X4)，田(4)=0.0580.09-0.05=0.0981y4=sgns(4)=111=t4-y4=1-1=01=0.09则有孙(4)=0.058,切24)重复上述（1）（4）,(0)_1(4).1二'1二0.058,20)=,24)=0.09(1) (0)(1)(0).Si=Xi1.X2，2-uo

27、O0-0.05-0.05y=sgns1)=-1-1=T)y1=-1(1)=0则有01(1)=0.058,©21)=0.09S2=X1(2),1(1)W).U(9)=0+0.09-0.05=0.04y2=sgns2)=1则有切1(2)=0.058,822)=0.09(3) (2)(3)(2)s3=x1，1X22-(10)=0.058+00.05=0.008y3-sgns3)=1:3=T3-y3=1-'1-0则有以(3)=0.058,023)=0.09(4) (3)(4)(3)一s4=x1,，1X22_1(11)=0.058+0.09-0.05=0.098y4=sgns4)-1二

28、4=T4-y4=1-1=0则有期(4)=0.058,。24)=0.09最后所得加权值为81=0.058,82=0.09、2=丁2-y2=1-1=013.掌握BP算法.前馈与反馈网络结构与训练过程BP训练算法实现步骤m0准备：训练数据组。设网络具有m层，yj表示第m层中第j个结点的输出，yj（零层输.m.mJ.m、一.一出）等于Xj,即第j个输入。Wij表布从V、到yj的连接加权。这里，m代表层号，而不是向量的类号。1,将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。2,从训练数据组中选一数据对（Xk,Tk）,将输入向量加到输入层（m=0）,使得对所有0k漏点i

29、：y、=X、，k表不向重类3mmm.mM3.信号通过网络向前传播，即利用关系式：yjF（Sj）F（乙wjy、）i计算从第一层开始的各层内每个结点、的输出ymm,直到输出层的每个结点的输出计算完为止。4,计算输出层每个结点的误差值（利用公式（1）3jm=F（Sjm）（Tjkym）=y：（1y：）（T；y：）（对Sigmod函数）它是由实际输出和要求目标值之差获得。5.计算前面各层各结点的误差值（利用公式（2）-m-1m-1mjF（sj）._wji-:i这里逐层计算反传误差，直到将每层内每个结点的误差值算出为止。6 .利用加权修正公式mv-mm、,knew01dWij=为yi和关系wij=Wij+AWj修正所有连接权。一般0.011,称为训练速率系数。7 .返回第2步，为下一个输入向量重复上述步骤，直至网络收敛。（2）前馈网络通过许多具有简单处理能力的神经元的复合作用，使整个网络具有复杂的非线性映射能力。反馈网络通过网络神经元状态的变迁，最终稳定于某一状态，得到联想存储或神经计算的结果。感知器训练算法准备：收集一组训练对，即一组输入向量，其中每个都有一个对应的目标向量。输入：二进制值或连续值