中科院模式识别考题总结详细答案.docx

1、1. 简述模式的概念及其直观特性，模式识别的分类，有哪几种方法。 （6）答（1）：什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。模式的直观特性：可观察性；可区分性；相似性。答（2）：模式识别的分类：假说的两种获得方法（模式识别进行学习的两种方法）： 监督学习、概念驱动或归纳假说； 非监督学习、数据驱动或演绎假说。模式分类的主要方法： 数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。是一种非监督学习的方法，解决方

2、案是数据驱动的。 统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法，分类器是概念驱动的。 结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。 （句法模式识别） 神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。2. 什么是神经网络？有什么主要特点？选择神经网络模式应该考虑什么因素？（8 ）答（1）：所谓

3、人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机） 。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络的两种操作过程：训练学习、正常操作（回忆操作） 。答（2）：人工神经网络的特点： 固有的并行结构和并行处理； 知识的分布存储； 有较强的容错性； 有一定的自适应性；人工神经网络的局限性： 人工神经网络不适于高精度的计算； 人工神经网络不适于做类似顺序计数的工作； 人工神经网络的学习和训练往往是一个艰难的过程； 人工神经网络必须克服时间域

4、顺序处理方面的困难； 硬件限制； 正确的训练数据的收集。答（3）：选取人工神经网络模型，要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括： 网络大小； 所需输出类型； 联想记忆类型； 训练方法； 时间的限定。3. 画出句法模式识别的框图，并解释其工作原理。 （8）答（1）：句法模式识别框图如下：答（2）：句法模式识别系统的组成：图像预处理，图像分割，基元及其关系识别，句法分析。基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。句法模式识别系统

5、处理过程：基元本身包含的结构信息已不多，仅需少量特征即可识别。如果用有限个字符代表不同的基元，则由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表。假如事先用形式语言的规则从字符串中推断出能生成它的文法，则可以通过句法分析，按给定的句法（文法）来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所能描述的模式类，达到分类的目的。4. （ 1）解释线性判别函数进行模式分类的概念；（2）既然有了线性判别函数，为什么还要用非线性判别函数进行模式分类？（3）两类模式，每类包括 5 个 3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多

6、项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。 ） （8）答（1）：模式识别系统的主要作用是判别各个模式所属的类别。线性判别函数分类就是使用线性判别函数将多类样本模式分开。 一个 n 维线性判别函数的一般形式： 12 101() Tnnndxwxwxxw其中 称为权向量（或参数向量） ， 。0,.)Tn 2(,.)Tnx也可表示为：()x(dx其中， 称为增广模式向量， 称为增广12,.,)Tn0121(,.,)Tnww权向量。两类情况：判别函数 ：()dx120()Tifdxw多类情况：设模式可分成 共 M 类，则有三种划分方法：1,. 多类情况 1用线性判别函

7、数将属于 类的模式与不属于 类的模式分开，其判别函数为：ii0() iTii ifxdxwi这种情况称为 两分法，即把 M 类多类问题分成 M 个两类问题，因此共有 M 个/ii判别函数，对应的判别函数的权向量为 。,12,.niw 多类情况 2采用每对划分，即 两分法，此时一个判别界面只能分开两种类别，但不能把它|ij与其余所有的界面分开。其判别函数为： 若 ， ，则()Tijijdxw()0ijdxjiix重要性质： ijji要分开 M 类模式，共需 M(M-1)/2 个判别函数。不确定区域：若所有 ，找不到 ， 的情况。()ijdxji()0ijdx 多类情况 3（多类情况 2 的特例）

8、这是没有不确定区域的 两分法。假若多类情况 2 中的 可分解成：|ijijd，则 相当于 ， 。这()()Tijijijdxdxwx0ijd()ijxji时不存在不确定区域。此时，对 M 类情况应有 M 个判别函数：(),1,2,Tkkxw即 ， ， ，则 ，也可写成，若()ijdji1,2.jix，则 。()ma,.ikxxi该分类的特点是把 M 类情况分成 M-1 个两类问题。模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。一旦线性函数的系数 wk 被确定，这些函数就可用作模式分类的基础。对于 M 类模式的分类，多类情况 1 需要 M 个判别函数，而多

9、类情况 2 需要 M*(M-1)/2个判别函数，当 M 较大时，后者需要更多的判别式（这是多类情况 2 的一个缺点） 。采用多类情况 1 时，每一个判别函数都要把一种类别的模式与其余 M-1 种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。由于一种模式的分布要比 M-1 种模式的分布更为聚集，因此多类情况 2 对模式是线性可分的可能性比多类情况 1 更大一些（这是多类情况 2 的一个优点） 。答（2）广义线性判别函数出发点： 线性判别函数简单，容易实现； 非线性判别函数复杂，不容易实现； 若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。采用广义线性判别函数的概

10、念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。所以某些情况下使用非线性判别函数或分段线性判别函数效果更好。解（3）假设该两类模式是线性可分的，则在三维空间中一个线性平面可以将这两类模式分开，所以判别函数可以写成：1234()dxwx所以权向量需要 4 个系数。对于 n 维 x 向量，采用 r 次多项式，d(x) 的权系数 w 的项数为：()!rwnNC当 r=2， n=3 时，(2)!()10W所以，此时权向量需要 10 个系数分量。5. 设一有限态自动机 ， 定义如下：01202(,Aqq02 21021)

11、()(,)(,试求等价的正则文法，使得 L(G)=T(A)。 （10）解：设由 A 得一正则文法 ，则 ， ，(,)，NTGVPS12,NVSx0,1TV0Sq由 ，得生成式 01(,)q1Sx 由 ，得生成式 2 20, 由 ，得生成式 10(,)1x 由 ，得生成式 2q12,x 由 ，得生成式 1(,)2x 由 ，得生成式 220220,x 对比实例：当扫描字符串 1110 时，A 按以下状态序列接受该字符串 2010110 qqq用对应的正则文法 G 推导，得： 11SxSx 按有限态自动机确定正则文法给定一个有限态自动机 ，可确定一个正则文法 ，0(,)AQqF(,)NTGVPS使得

12、 L(G) = T(A)。由 ，可确定：011,.,nnQq， ， ， 。2xNVS0SqiixTV从 求 G 中的生成式 P 可按如下原则：(1) 若 ，则(,)ijqaija(2) 若 ，则1in1,iinxx6. K-均值算法聚类：K=2，初始聚类中心为 ，数据为：（ 10）12,12345678910(0,)(1,)(0,)(,)(87)9 9,xxx算法：第一步：选 个初始聚类中心， ，其中括号内的序号为寻找聚类K12(),z.,()k中心的迭代运算的次序号。可选开始的 个模式样本的向量值作为初始聚K类中心。第二步：逐个将需分类的模式样本 按最小距离准则分配给 个聚类中心中的某一xK

13、个 。即 ，则 ，其中(1)jz()min(),12,j iDkzk ()jxSk为迭代运算的次序号，第一次迭代 ， 表示第 个聚类，其聚类中k jS心为 。jz第三步：计算各个聚类中心的新的向量值， (1),2,.jzkjK求各聚类域中所包含样本的均值向量： ()1(),1,2,jj xSkjzkjN其中 为第 个聚类域 中所包含的样本个数。以均值向量作为新的聚j j类中心，可使如下聚类准则函数最小： 2()(1),jj jxSkJzjK在这一步中要分别计算 K 个聚类中的样本均值向量，所以称之为 K-均值算法。第四步：若 ，则返回第二步，将模式样本逐个重新分类，重复迭代(1)()j jzk

14、zk运算；若 ，则算法收敛，计算结束。()()j jzz7. 给出两类模式分布，每一列代表一个样本：15456x：26545试用 K-L 变换来做一维特征的提取（12） 。解：首先将所有样本看作一个整体，求出样本均值向量：5511jjj2jmx0由于均值为 0，符合 K-L 变换的最佳条件。如果均值不为 0，则所有样本要减去均值向量。由于 和 的样本数相同，所以认为他们的先验概率相同，即：1212().5P求出总体的自相关矩阵 或协方差矩阵 ：RC2125.4().TiiiPEx解特征方程 ，求出 的特征值：0I1250.4,.求出对应于特征值的特征向量 ：iiR121,选取 对应的特征向量作

15、为变换矩阵 ，由 得出变换后的一维模式：1Tyx： 1091222 x：2198. 用第二类势函数的算法进行分类（10）选择指数型势函数，取 =1，在二维情况下势函数为： )()(2212),( kkk xxxkexK这里： 1 类为 x=(0 0) T, x=(2 0) T； 2 类为 x=(1 1)T, x=(1 -1)T解：可以看出，这两类模式是线性不可分的。算法步骤如下：第一步：取 ，则(1)10,2221() 1(exp(0)()exp()Kxx第二步：取 (2)1,T因 ，e4e(4)故 2211()xpKx第三步：取 (3)2,T因 ，epe()0故2 2232(3)11(),x

16、p()exp()()Kx x后面同理，就是不断将样本带入，如果分类正确，则势函数保持不变，即：1()kkKx如果分类错误，则有两种情况： ，则(k1)(k1),0xKx1(k1)(),kkx ，则()2()()x经过迭代，全部模式都已正确分类，因此算法收敛于判别函数。得出： )2()1()()1()()( 122122121) xxxx eeed 9. 有一种病，正常为 ，不正常为 ，已知：121()0.9,().1P现对某人进行检查，结果为 ，由概率曲线查出：x12(|).,(|)0.4x风险代价矩阵为：126L对该检查者进行判决：（1） 用贝叶斯最小错误概率判别，求出判决函数和决策分界面。

17、（2） 用贝叶斯最小风险判别，求出判别函数和决策分界面。解（1）：111222(|)(|)PxPx由于1221(|)()9xlP所以 。1x解（2）：21()(|),12jijiirxLPxj由于12122(|)() 54Llx所以 。1x10. 阐述误差反传算法（BP 算法）的原理，并写出其训练步骤。答（1）： BP 算法推算过程：当加入第 k 个输入时，隐蔽层 h 结点的输入加权和为： kkihswx如果令第一层的加权矩阵为 ，则还可以表示为：1W1kTkhsx相应节点的输出为： ()()kkkhhihyFsw写成矩阵形式为：1()kkTkhysWx同样，输出层 j 结点的输入加权和为：

18、()kk kjhjhjihswFw令第二次的加权矩阵为 ，则可以写成：2221()kTkTkjhsWyx相应点的输出： ()()()kkk kjj hj hjihyFswFwx写成矩阵形式为：21()kTkjyx这里，各结点的阈值等效为一个连接的加权 或 ，这些连接由各结点连到具0hwj有固定值-1 的偏置结点，其连接加权也是可调的，同其它加权一样参与调节过程。误差函数为： jkhikihjjkkj xFTyTWE, 2, 2 )(1)(21)(为了使误差函数最小，用梯度下降法求得最优的加权，权值先从输出层开始修正，然后依次修正前层权值，因此含有反传的含义。根据梯度下降法，由隐蔽层到输出层的连

19、接的加权调节量为： ()(kkkhj jjjhjhhjEwTyFsy其中 为输出结点的误差信号：kj()()kkkkjjjjsTysjjj在 BP 算法中常采用 Sigmoid 函数：1()syFse其导数为： ()(1)Fss对应的误差为： )kkkjjjjjyTy对于输入层到隐蔽层结点连接的加权修正量 ，必须考虑将 对 求导，因ihw()EWihw此利用分层链路法，有： , ()()()kkkkhih jjjhjikjihik kjhihiyEwTyFssxFsxx 其中： ()()kkkkhhjhswFshj这样就可以根据 和 分别调整输出层和隐层的权值了。hjwi BP 训练算法实现步骤