模式识别复习题

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

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

3、类中心的新的向量值，zj(k+1）,j=1，2,，K求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数.以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K均值算法.第四步：若，j=1,2，,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若，j=1,2,K，则算法收敛，计算结束.例子：已知x1（0, 0)， x2(1，0)， 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) ，

4、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均值算法进行聚类分析解：选，, 第一步：选取第二步:根据聚类中心进行聚类,得到第三步：计算新的聚类中心第四步：因，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到第三步:计算新的聚类中心第四步：，所以算法收敛，得聚类中心为 迭代结束。3、最、剪辑、压缩近邻法的基本思想。最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点"，即所有样本的距离，并以最近邻者的类别

5、作为决策。剪辑近邻法基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选,可以实现既减少样本数又提高正确识别率的双重目的.压缩近邻法：利用现有样本集,逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。4、设有 6个 5维模式样本如下,按最小/大距离准则进行聚类分析（直到分成三个类别为止，距离度量采用欧氏距离） x1: 0， 3， 1, 2, 0 x2： 1, 3, 0, 1， 0 x3: 3, 3， 0, 0, 1 x4： 1, 1， 0, 2， 0 x5:

6、3， 2, 1， 2， 1 x6: 4, 1, 1， 1, 0按最大距离准则进行聚类分析：第1步：将每一样本看成单独一类,得计算各类之间的欧式距离，可得距离矩阵000000第2步：矩阵中最大元素为，它是和之间的距离，将他们合并为一个新类为计算聚类后的距离矩阵00000第3步:由于中距离最大者为，它是与之间的距离,于是合并和，得新的分类为同样，按最大距离准则计算距离矩阵，得0000第4步：由于中距离最大者为，它是与之间的距离，于是合并得新的分类为满足聚类要求，如聚为3类，聚类完毕。5、设有 5个 6维模式样本如下,按最小/大距离准则进行聚类分析（距离度量采用欧氏距离） x1: 0， 1，3， 1

7、， 3， 4 x2: 3, 3， 3, 1，2,1 x3: 1， 0， 0, 0， 1,1 x4： 2， 1， 0, 2， 2，1 x5: 0, 0， 1， 0, 1,0 用最小聚类准则进行系统聚类分析：第1步:将每一样本看成单独一类，得计算各类之间的欧式距离，可得距离矩阵00000第2步：矩阵中最小元素为，它是和之间的距离,将他们合并为一类，得新的分类为计算聚类后的距离矩阵0000第3步：由于中距离最小者为,它是与之间的距离，于是合并和，得新的分类为同样，按最小距离准则计算距离矩阵,得000第4步：同理得满足聚类要求，如聚为2类，聚类完毕。6、一个三类问题,其判别函数如下： d1(x）=-x

8、1， d2(x）=x1+x21， d3(x)=x1-x2-1 设这些函数是在多类情况1条件下确定的.1） 绘出其判别界面和每一个模式类别的区域。2） 对如下三个样本所属模式作出判决：A =（4 5）T ， B =(-2 5)T ， C =（2 -5)T 例子：一个三类问题，其判别函数如下：d1(x)=-x1， d2（x）=x1+x21, d3（x）=x1-x211、设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2、设为多类情况2，并使：d12(x）= d1(x), d13(x）= d2（x）, d23(x）= d3（x).绘出其判别界面和多类情况2的区域。3、设d

9、1(x)， d2（x）和d3（x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域解：（1）其判别界面和每一个模式类别的区域如图中所示:A =（4 5)T 属于1 ， B =(2 5)T 属于不确定区域 ， C =(2 5）T属于3.（2）其判别界面和每一个模式类别的区域如图中所示：(3）其判别界面和每一个模式类别的区域如图中所示:7、已知：1: x1， x2=（1 0 1）T， (0 1 1)T，2： x3， x4=(1 1 0)T, （0 1 0）T。给定初始增广权向量 w1=(1 1 1 1)T ， C=1.要求:1） 用感知器算法求模式分类的解向量w。 2) 写出判别函数和决策

10、面方程.解：先求四个样本的增值模式 x1=（1,0，1，1） T x2=（0,1,1,1) T x3=(1,1,0，1) T x4=（0,1，0，1） T假设初始权向量 w1=（1,1,1，1) T C=1第一次迭代： w1 T x1=（1，1,1，1) T (1,0,1，1）=3>0 所以不修正 w1 T x2=(1，1,1，1） T (0，1，1，1）=30 所以不修正 w1 T x3=(1,1，1，1） T (1,1,0,1）=3>0 所以修正w1 w2=w1-x3=（0,0，1，0） T w2 T x4=（0，0，1,0） T (0，1,0,1) =0 所以修正w2 w3=

11、w2x4=（0，-1，1，1） T第一次迭代后，权向量w3=（0,-1，1，-1)T,再进行第2,3,次迭代如下表：直到在一个迭代过程中权向量相同，训练结束.w6=w=(0,-1，3,0） 判别函数决策面方程：即8、已知：1: X1 =(0，2）T , X3 =（2,0）T , X5 =（1，-1）T 2: X2 =(1，1）T , X4 =(0,2）T， X6 =（-2,0）T给定初始增广权向量 w1=(1 1 1）T , C=1。要求：用感知器算法求模式分类的解向量w.解：此为线性不可分问题，利用感知器法求权向量权向量产生循环（1， 1， 1） T， （0， 0, 0） T， （2， 0，

12、 1） T， (2， 2, 0） T,(1， 1, 1) T因此算法不收敛，我们可以取循环中任一权值，例如取W=（2,2,0） T则判别函数为： g（x）= 2x1+2x2判别面方程为： g(x）= 2x1+2x20 所以： x1+x20由图看出判别面H把二类分开，但其中x2错分到1类，而x1错分到2类,但大部分分类还是正确的.9、 对一大批人进行癌症普查，患癌者以1类代表，正常人以2类代表。已知P(1）=0.005，当然P(2）=1-0。005=0.995.设有一种诊断癌症的试验，其结果为“阳性”和“阴性"两种反应。假设根据临床记录发现这种方法有以下统计结果:患有癌症的人试验反应为

13、阳性的概率=0。95,即p(x=阳1)=0。95患有癌症的人试验反应为阴性的概率=0。05，即p（x=阴1)=0。05正常人试验反应为阳性的概率=0.01，即p(x=阳|2)=0.01正常人试验反应为阴性的概率=0.99，即p（x=阴2)=0.99 问：若被化验的人具有阳性反应,他患癌症的概率为多少？解：因为,P(w2|x=阳)= 1-P（w1x=阳)=10。323=0。677 P(w1x=阳)<P(w2x=阳)故判决： 正常。10、已知P（1)=0.9，P(2)=0。1, p(x1)=0。2,p（x|2)=0.4. 且有如下决策表： 损失 状态 决策 1 2 106 210 请按最小风

14、险贝叶斯决策进行分类。解：已知条件为P（1）=0.9，P（2）=0。1， p(x|1)=0。2，p（x2)=0.4。利用贝叶斯公式分别计算出1及2的后验概率再计算条件风险： 由于即决策为2的条件风险小于决策为1的条件风险,因此我们采取决策行动,即判断待识别的细胞x为2类异常细胞。11、设有如下三类模式样本集1，2和3,其先验概率相等，求Sw 和Sb1 ：（1 0）T, (2 0) T, (1 1） T2 ：(1 0）T, (0 1） T， (1 1) T3 :（-1 -1）T， (0 -1) T， (0 2) T解：由于本题中有三类模式，因此我们利用下面的公式:=,即：为第i类样本样本均值12

15、 试用感知器算法实现逻辑“与”、“或"功能。（初始加权值、阈值和训练速率系数自己设定)一、用感知器算法实现逻辑“与"功能真值表：x1x2T001(0）011（0）10-1（0）111设，,，转移函数为符号函数（1） 则有，（2） 则有，（3） 则有 （4） 则有，重复上述(1）(4) ，（5） 则有，（6） 则有，（7） 则有，（8） 则有，最后所得加权值为，2、 用感知器算法实现逻辑“或”功能真值表：x1x2T00-1（0）011101111仍设，转移函数为符号函数（1) 则有，（2) 则有 (3） 则有,（4) 则有，重复上述（1）(4） ，(5） 则有,（9） 则有，

16、（10） 则有,（11） 则有，最后所得加权值为，13。 掌握BP算法。 前馈与反馈网络结构与训练过程。l BP训练算法实现步骤准备:训练数据组.设网络具有m层，表示第m层中第j个结点的输出,（零层输出）等于xj，即第j个输入.表示从到的连接加权。这里,m代表层号，而不是向量的类号。1. 将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。2. 从训练数据组中选一数据对（xk, Tk)，将输入向量加到输入层（m=0），使得对所有端点i：，k表示向量类号3. 信号通过网络向前传播，即利用关系式：计算从第一层开始的各层内每个结点i的输出，直到输出层的每个结点的输出计算

17、完为止。4. 计算输出层每个结点的误差值（利用公式（1）（对Sigmod函数）它是由实际输出和要求目标值之差获得.5. 计算前面各层各结点的误差值(利用公式（2)这里逐层计算反传误差,直到将每层内每个结点的误差值算出为止。6. 利用加权修正公式和关系修正所有连接权。一般= 0。011，称为训练速率系数。7. 返回第2步,为下一个输入向量重复上述步骤，直至网络收敛。(2）前馈网络通过许多具有简单处理能力的神经元的复合作用，使整个网络具有复杂的非线性映射能力.反馈网络通过网络神经元状态的变迁,最终稳定于某一状态，得到联想存储或神经计算的结果。l 感知器训练算法准备：收集一组训练对，即一组输入向量，

18、其中每个都有一个对应的目标向量。输入：二进制值或连续值(1+1）输出:目标向量(二进制值）训练步骤：1. 将所有网络加权随机置为较小的值（均匀分布随机数）2. 加入一个输入量），计算各结点的输入加权和：3. 将信号通过符号函数,得：计算每个结点的输出误差值：4. 调节各加权值：5. 重复步骤25，直到所有误差达到所要求的最小值（如零值）为止.Hopfield网络6. 学习过程假设共有p个模式，即网络面临的学习任务为集合x1, x2, ， xp，其中。先考虑Hopfield网络对一个模式学习和回忆的情况。a) 对一个模式的学习,此时p=1，即学习任务集合只有一个模式x1.设网络权矩阵为W，对于初始模式x1，若网络稳定，则应有：x1 = sgn(x1W)，x1为网络的不动点上式展开可写成:，其中(1）式(1)可用于神经网络状态的任何更新方式。由sgn函数的性质，若条件（即式（1）左右两边同号）满足,则式（1)成立，从而有：因，则由