模式识别考试(共6页)

1、一分别说明用统计决策法和句法方法进行模式识别(m sh sh bi)的一般过程，并比较两种方法各有什么特点。（10分）答：（1）统计(tngj)决策法：特点(tdin)：基于模式的定量描述与统计规律的识别方法，是模式识别最经典、最成熟的方法，目前广泛应用于模式识别。原理：样本观测值特征概率统计决策准则分类过程：学习样本数据获取预处理特征提取统计分析分类准则 待识样本数据获取预处理特征提取识别分类分类结果（2）句法方法：特点：基于模式的空间结构特征的定性描述与形式语言学的方法，广泛应用于字符识别、图像识别等领域。原理：样本基元字符串形式语言文法分类过程：学习样本数据获取预处理基元提取文法推断文法

2、 待识样本数据获取预处理基元提取句法分析分类结果二设两类模式是线性可分的，其线性判别函数为：g(x)=wtx+w0 其中特征向量x=x1, x2, x3, , xnt, 权向量w=w1, w2, w3, , wnt 试分别说明线性判别函数中权向量w，阀值w0及g(x)在n维特征空间的几何意义。两类模式的判别界满足什么条件？（10分）答：（1）权向量W的几何意义为权向量方向，与判别界（即g(x)=0）上任一向量正交，即W决定了判别界的方向。（2）阀值W0的几何意义为原点到判别界的距离。若W00，则原点位于判别界的正面；反之，位于反面。（3）判别函数g(x)的几何意义为一点X到判别面的距离。若在判

3、别面的正面，则g(x)0, 若在判别面的反面，则g(x)0，判别界上g(x)=0。对于原点x=0，则g(x)=g(0)= W0。（4）两类模式的判别(pnbi)界应满足的条件：在n维空间中，可以用线性判别界将待识别样本进行正确分类。待识别样本在判别面的一侧都属于模式(msh)一；反之属于模式二。三请分别说明基于(jy)最小错误概率和基于最小风险的Bayes决策方法的基本原理，两种方法有何联系？（10分）答：（1）最小错误概率：若P(Wi/X)=MAXP(Wj/X)，j=1,2,c,则判X属于Wi类。（2）最小风险：若Ri(X)=MINRj(X), j=1,2,c,则判X属于Wi类。（3）联系：

4、(0-1)损失条件下，两者是等价的。答2：1、基于最小错误概率的Bayes决策方法：(1) 根据先验概率求出每一类样本的后验概率；(2) 根据后验概率进行判别，若：或， 其中，.则判：类。 2、基于最小风险的Bayes决策：(1) 定义一个风险函数，其中，定义为损失。 (2) 当待识样本到来时，将其判为各类所带来的风险分别为：。 (3) 基于最小风险判别分类：若：或，其中，则判：类。3、两种方法的联系：(1)在二类问题中，若，即对称损失，则最小风险Bayes决策与最小错误概率Bayes决策是等价的。(2) 在一般的多类问题中，当在01损失函数的情况下，最小风险的Bayes决策和最小错误概率的B

5、ayes决策的结果也是相同的。四、解：对于一维正态分布待估参数为其中 可记为:似然函数：令：即：得：解得：五请给出感知准则(zhnz)梯降法求线性判别函数权向量w的原理及算法(sun f)过程。（10分）解：（一）(以二类(r li)模式为例) 感知准则梯降法求线性判别函数权向量的原理：函数在某点的梯度是一个向量，它的方向与过点的等量面的法线方向重合，指向增加的一方，是准则函数变化率最大的方向。反之，负梯度的方向则是函数减少得最快的方向。所以在求准则函数的极小值时，沿负梯度方向搜索有可能最快地找到极小值。（二）算法过程：任意选取初始解向量遍历所有样本，计算找出选择后，被错分类的样本（即的样本）

6、令，直到，否则重复第步。六、为什么要进行特征选择与特征提取？特征选择的基本原则是什么？简述K-L变换的基本原理。（10分）答：（1）特征选择：从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的的过程。特征提取：通过映射或变换的方法把高维的特征向量变换为低维的特征向量，新的特征向量包含水量了原有匐体特征的信息。特征选择与特征提取是模式识别的重要环节，直接影响到模式分类器的设计和性能。特征选取择和提取的基本任务是如何从许多特征中找出那些最有效的特征。（2）特征选择的原则(yunz)（Feature choice）选择反映模式本质特性的参数(cnsh)作为特征使样本(yngbn)类间距离

7、较大、类内距离较小与类别信息不相关的变换（平移、旋转、尺度变换）具有不变性尽量选择相关性小的特征尽可能不受噪声的干扰（3）K-L变换的基本原理：将n维特征向量X，通过特征变换得到另一m维特征向量，使用特征向量Y(mn)，Y与原X量的均方误差最小七什么是聚类分析？常用的聚类分析方法有哪些？简述K-均值算法的基本原理及算法过程。解：（一）聚类分析直观地可认为是根据各个特征的模式特征的相似度进行分类，相似的归为一类，不相似的归为另一类，或者可以认为它是空间中包含相对密度点联系区域，由相对低密度点区域讲其他相对高密度点区域分开。聚类分析是一种无教师的分类方法。（二）常用聚类分析方法有：合并聚类法、近邻

8、聚类法、C-均值、动态聚类法、ISODATA算法、顺序聚类法。还有k-means、k-medoids、STING等。（三）K-均值算法的基本原理：首先确定需要的群数k，选k个代表点，用这些点作为教师，再对样本集X中各个样本x找出相距最近的代表点，将x归到这个最近的代表点的群中去。这样，第一次迭代就用近邻法将样本集X初步分为k群。下一次迭代就在这个基础上以上次迭代所得的各群的均值向量作为X的代表点，再次用近邻法则将X分为k群，直至分群稳定。（四）k-均值算法的算法过程：指定群数k，选取k个代表点，作为k群的群心将每个样本归入与之最近的群心所代表的群计算k个群的重心，以得到的重心作为新的代表点转步

9、骤，全部样本重新分群，如分群结果不变，则算法停止，否则继续步骤-。八已知语言L ( G )的 正样本集（学习样本）S+为： S+=1101，11，001，0011 试用正样文法和余码文法的推断方法推出其对应的有限态文法，并画出其状态图，说明余码文法的优点，并用余码文法的状态图分析句子X=110010是否属于该语言？（10分）解：(1)正样文法(wnf)：VT=0,1P: S1A11A111A12A120A13A131 S1A21A211 S0A31A310A32A321 S0A41A410A42A421A43A431则：VN=S,A11,A12,A13,A21,A31,A32,A41,A42,

10、A43 (2)余码文法(wnf)：VTC=0,1 PC: D0U1=01,011=U2U10U2D1U1=101,1=U3U11U3 D0U2=1,11=U4U20U4D1U3=01=U5U31U5D1U4=1=U6U41U6D0U5=1=U7U50U7D1U6=U61D1U7=U71则：VNC=U1,U2,U3,U4,U5,U6,U7(3)余码文法的优点：较简单(jindn)，非终止符和代换式数少。(4) X=110010不属于该语言：由状态图不难推断出无论怎么导最终结果也导不出0. SA11A21A31A41A42U7U6U4U5U3U2A43A13A32A12TTSC110001101110110011011正样文法状态图余码文法状态图内容总结（1）一分别说明用