中科院-模式识别考题总结(详细答案)

1.简述模式的概念及其直观特性，模式识别的分类，有哪几种方法。（6’）答（1）：什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。模式的直观特性：可观察性；可区分性；相似性。答（2）：模式识别的分类：假说的两种获得方法（模式识别进行学习的两种方法）：监督学习、概念驱动或归纳假说；非监督学习、数据驱动或演绎假说。模式分类的主要方法：数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。是一种非监督学习的方法，解决方案是数据驱动的。统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法，分类器是概念驱动的。结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。（句法模式识别）神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。2.什么是神经网络？有什么主要特点？选择神经网络模式应该考虑什么因素？（8’）答（1）：所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络的两种操作过程：训练学习、正常操作（回忆操作）。答（2）：人工神经网络的特点：固有的并行结构和并行处理；知识的分布存储；有较强的容错性；有一定的自适应性；人工神经网络的局限性：人工神经网络不适于高精度的计算；人工神经网络不适于做类似顺序计数的工作；人工神经网络的学习和训练往往是一个艰难的过程；人工神经网络必须克服时间域顺序处理方面的困难；硬件限制；正确的训练数据的收集。答（3）：选取人工神经网络模型，要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：网络大小；所需输出类型；联想记忆类型；训练方法；时间的限定。3.画出句法模式识别的框图，并解释其工作原理。（8’）答（1）：句法模式识别框图如下：答（2）：句法模式识别系统的组成：图像预处理，图像分割，基元及其关系识别，句法分析。基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。句法模式识别系统处理过程：基元本身包含的结构信息已不多，仅需少量特征即可识别。如果用有限个字符代表不同的基元，则由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表。假如事先用形式语言的规则从字符串中推断出能生成它的文法，则可以通过句法分析，按给定的句法（文法）来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所能描述的模式类，达到分类的目的。4.（1）解释线性判别函数进行模式分类的概念；（2）既然有了线性判别函数，为什么还要用非线性判别函数进行模式分类？（3）两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）（8’）答（1）：模式识别系统的主要作用是判别各个模式所属的类别。线性判别函数分类就是使用线性判别函数将多类样本模式分开。一个n维线性判别函数的一般形式：1122101()Tnnnndxwxwxwxwwxw其中012(,,...,)Tn称为权向量（或参数向量），12(,,...,)Tnxxxx。()dx也可表示为：()Tdxwx其中，12(,,...,,1)Tnxxxx称为增广模式向量，0121(,,...,,)Tnn称为增广权向量。两类情况：判别函数()dx：120()0Tifxdxwxifx多类情况：设模式可分成12,,...,M共M类，则有三种划分方法：多类情况1用线性判别函数将属于i类的模式与不属于i类的模式分开，其判别函数为：0()0iTiiiifxdxwxifx这种情况称为/ii两分法，即把M类多类问题分成M个两类问题，因此共有M个判别函数，对应的判别函数的权向量为,1,2,...,n1iwi。多类情况2采用每对划分，即|ij两分法，此时一个判别界面只能分开两种类别，但不能把它与其余所有的界面分开。其判别函数为：()Tijijdxwx若()0ijdx，ji，则ix重要性质：ijjidd要分开M类模式，共需M(M-1)/2个判别函数。不确定区域：若所有()ijdx，找不到ji，()0ijdx的情况。多类情况3（多类情况2的特例）这是没有不确定区域的|ij两分法。假若多类情况2中的ijd可分解成：()()()()Tijijijdxdxdxwwx，则0ijd相当于()()ijdxdx，ji。这时不存在不确定区域。此时，对M类情况应有M个判别函数：(),1,2,,TkkdxwxkM即()()ijdxdx，ji，,1,2,...ijM，则ix，也可写成，若()max{(),1,2,...,}ikdxdxkM，则ix。该分类的特点是把M类情况分成M-1个两类问题。模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。一旦线性函数的系数wk被确定，这些函数就可用作模式分类的基础。对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。答（2）广义线性判别函数出发点：线性判别函数简单，容易实现；非线性判别函数复杂，不容易实现；若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。所以某些情况下使用非线性判别函数或分段线性判别函数效果更好。解（3）假设该两类模式是线性可分的，则在三维空间中一个线性平面可以将这两类模式分开，所以判别函数可以写成：1234()dxwxwxwxw所以权向量需要4个系数。对于n维x向量，采用r次多项式，d(x)的权系数w的项数为：()!!!rwnrnrNCrn当r=2，n=3时，(2)!(2)(1)102!!2WnnnNn所以，此时权向量需要10个系数分量。5.设一有限态自动机01202({0,1},{,,},,,}Aqqqqq，定义如下：021222011021(,0),(,0),(,0)(,1),(,1),(,1)qqqqqqqqqqqq试求等价的正则文法，使得L(G)=T(A)。（10’）解：设由A得一正则文法(,,)，NTGVVPS，则12{,,}NVSxx，{0,1}TV，0Sq由01(,1)qq，得生成式11Sx由02(,0)qq，得生成式20,0SSx由10(,1)qq，得生成式11xS由12(,0)qq，得生成式1120,0xxx由21(,1)qq，得生成式211xx由22(,0)qq，得生成式2220,0xxx对比实例：当扫描字符串1110时，A按以下状态序列接受该字符串201101110qqqqq用对应的正则文法G推导，得：111111111110SxSx按有限态自动机确定正则文法给定一个有限态自动机0(,,,,)AQqF，可确定一个正则文法(,,,)NTGVVPS，使得L(G)=T(A)。由0111{,,...,,},nnnQqqqqqF，可确定：121{,,,...,x,}NnnVSxxx，0Sq，iixq，TV。从求G中的生成式P可按如下原则：(1)若(,)ijqaq，则ijxax(2)若1(,)inqaq，则1,iinxaxax6.K-均值算法聚类：K=2，初始聚类中心为12,xx，数据为：（10’）12345678910{(0,0),(1,0),(0,1),(1,1),(8,7)(9,7),(8,8),(9,8),(8,9),(9,9)}xxxxxxxxxx算法：第一步：选K个初始聚类中心，12(1),z(1),...,(1)kzz，其中括号内的序号为寻找聚类中心的迭代运算的次序号。可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本{}x按最小距离准则分配给K个聚类中心中的某一个(1)jz。即()min{(),1,2,}jiDkxzkiK，则()jxSk，其中k为迭代运算的次序号，第一次迭代1k，jS表示第j个聚类，其聚类中心为jz。第三步：计算各个聚类中心的新的向量值，(1),1,2,...,jzkjK求各聚类域中所包含样本的均值向量：()1(1),1,2,,jjxSkjzkxjKN其中jN为第j个聚类域jS中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：2()(1),1,2,,jjjxSkJxzkjK在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若(1)()jjzkzk，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若(1)()jjzkzk，则算法收敛，计算结束。7.给出两类模式分布，每一列代表一个样本：1：55456545651x2：55654565452x试用K-L变换来做一维特征的提取（12’）。解：首先将所有样本看作一个整体，求出样本均值向量：55111155jj1j2jmxx0由于均值为0，符合K-L变换的最佳条件。如果均值不为0，则所有样本要减去均值向量。由于1和2的样本数相同，所以认为他们的先验概率相同，即：12()()0.5PP求出总体的自相关矩阵R或协方差矩阵C：2125.425(){}2525.4TiiiiRPExx解特征方程0RI，求出R的特征值：1250.4,0.4求出对应于特征值的特征向量iiiR：121111,1122选取1对应的特征向量作为变换矩阵，由Tyx得出变换后的一维模式：1：10991111222221x'2：10111199222222x'8.用第二类势函数的算法进行分类（10’）选择指数型势函数，取α=1，在二维情况下势函数为：])()[(2222112),(kkkxxxxxxkeexxK这里：ω1类为x①=(00)T,x②=(20)T；ω2类为x③=(11)T,x④=(1-1)T解：可以看出，这两类模式是线性不可分的。算法步骤如下：第一步：取(1)1(0,0)Tx，则2222