模式识别复习题.doc

《模式识别复习题.doc》由会员分享，可在线阅读，更多相关《模式识别复习题.doc（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date模式识别复习题模式识别试题库模式识别试题库一、基本概念题1.1 模式识别的三大核心问题是： 、 、 。1.2、模式分布为团状时，选用 聚类算法较好。 1.3 欧式距离具有 。 马式距离具有 。 （1）平移不变性 （2）旋转不变性 （3）尺度缩放不变性 （4）不受量纲影响的特性1.4 描述模式相似的测度有： 。（1）距离测度 （2）模糊测度 （3）相似测度 （4）匹配测

2、度1.5 利用两类方法处理多类问题的技术途径有：（1） ；（2） ；（3） 。其中最常用的是第 个技术途径。 1.6 判别函数的正负和数值大小在分类中的意义是： ， 。1.7 感知器算法 。 （1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 1.8 积累位势函数法的判别界面一般为 。 （1）线性界面；（2）非线性界面。1.9 基于距离的类别可分性判据有： 。 （1） （2） （3） 1.10 作为统计判别问题的模式分类，在（ ）情况下，可使用聂曼-皮尔逊判决准则。1.11 确定性模式非线形分类的势函数法中，位势函数K(x,xk)与积累位势函数K(x)的关系为（ ）。1.12 用作确

3、定性模式非线形分类的势函数法，通常，两个n维向量x和xk的函数K(x,xk)若同时满足下列三个条件，都可作为势函数。（ ）；（ ）； K(x,xk)是光滑函数，且是x和xk之间距离的单调下降函数。1.13 散度Jij越大，说明wi类模式与wj类模式的分布（ ）。当wi类模式与wj类模式的分布相同时，Jij=（ ）。1.14 若用Parzen窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是（ ），h1过大可能产生的问题是（ ）。1.15 信息熵可以作为一种可分性判据的原因是： 。1.16作为统计判别问题的模式分类，在（ ）条件下，最小损失判决规则与最小错误判决规则是等价的。1.17

4、 随机变量l()=p( |w1)/p( |w2)，l( )又称似然比，则El( )|w2=（ ）。在最小误判概率准则下，对数似然比Bayes判决规则为（ ）。 1.18 影响类概率密度估计质量的最重要因素是（ ）。1.19 基于熵的可分性判据定义为，JH越（ ），说明模式的可分性越强。当P(wi| ) =（ ）(i=1,2,c)时，JH取极大值。 1.20 Kn近邻元法较之于Parzen窗法的优势在于（ ）。上述两种算法的共同弱点主要是（ ）。1.21 已知有限状态自动机Af=(，Q，d，q0，F)，=0，1；Q=q0，q1；d：d(q0，0)= q1，d(q0，1)= q1，d(q1，0)=

5、q0，d(q1，1)=q0；q0=q0；F=q0。现有输入字符串：(a) 00011101011，(b) 1100110011，(c) 101100111000，(d)0010011，试问，用Af对上述字符串进行分类的结果为（ ）。1.22 句法模式识别中模式描述方法有： 。（1）符号串 （2）树 （3）图 （4）特征向量1.23设集合X=a,b,c,d上的关系， R=(a,a),(a,b),(a,d),(b,b),(b,a),(b,d),(c,c),(d,d),(d,a),(d,b)，则a,b,c,d生成的R等价类分别为 （ aR= ，bR= ，cR= ，dR= ）。1.24 如果集合X上的

6、关系R是传递的、（ ）和（ ）的，则称R是一个等价关系。1.25一个模式识别系统由那几部分组成？画出其原理框图。1.26 统计模式识别中，模式是如何描述的。1.27 简述随机矢量之间的统计关系：不相关，正交，独立的定义及它们之间的关系。1.28 试证明，对于正态分布，不相关与独立是等价的。1.29 试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。1.30 试证明，多元正态随机矢量的分量的线性组合是一正态随机变量。 第二部分 分析、证明、计算题第二章 聚类分析2.1 影响聚类结果的主要因素有那些？2.2 马氏距离有那些优点？2.3 如果各模式类呈现链状分布，衡量其类间距离用最小距离还是用

7、最大距离？为什么？2.4 动态聚类算法较之于简单聚类算法的改进之处何在？层次聚类算法是动态聚类算法吗？比较层次聚类算法与c-均值算法的优劣。2.5 ISODATA算法较之于c-均值算法的优势何在？2.6 简述最小张树算法的优点。2.7 证明马氏距离是平移不变的、非奇异线性变换不变的。2.8 设，类、 的重心分别为 、 ，它们分别有样本 、 个。将和 合并为 ，则 有 个样本。另一类 的重心为 。试证明 与 的距离平方是 2.9 （1）设有M类模式wi，i=1,2,.,M，试证明总体散布矩阵ST是总类内散布矩阵SW与类间散布矩阵SB之和，即STSWSB。（2）设有二维样本：x1=(-1,0)T，

8、x2=(0,-1)T，x3=(0,0)T，x4=(2,0)T和x5=(0,2)T。试选用一种合适的方法进行一维特征特征提取yi = WTxi 。要求求出变换矩阵W，并求出变换结果yi ，(i=1,2,3,4,5)。（3）根据（2）特征提取后的一维特征，选用一种合适的聚类算法将这些样本分为两类，要求每类样本个数不少于两个，并写出聚类过程。2.10 （1）试给出c-均值算法的算法流程图;（2）试证明c-均值算法可使误差平方和准则最小。其中，k是迭代次数；是 的样本均值。 2.11 现有2k+1个一维样本，其中k个样本在x=-2处重合，另k个样本在x=0处重合，只有1个在x=a0处。若a=2(k+1

9、)，证明，使误差平方和准则Jc最小的两类划分是x=0处的k个样本与x=a处的1个样本为一类，其余为另一类。这里， c NjJc = (xi-mj)2 j=1 i=1其中，c为类别数，Nj是第j类的样本个数，xiwj，i=1,2,.,Nj，mj是第j类的样本均值。2.12 有样本集，试用谱系聚类算法对其分类。2.13 设有样本集S=，证明类心 到S中各样本点距离平方和 为最小时，有 。 2.14 假设s为模式矢量集X上的距离相似侧度，有且当时， 。证明d是距离差异性测度。 2.15 证明欧氏距离满足旋转不变性。提示：运用Minkowski不等式，对于两矢量和 ，满足2.16证明： （a）如果s是

10、类X上的距离相似侧度，那么对于 ， 也是类X上的距离测度。 （b）如果d是类X上的距离差异性测度，那么对于， 也是类X上的距离差异性测度 2.17 假设是连续单调递增函数，满足 d是类X上的距离差异性测度且。证明 也是类X上的距离差异性测度。 2.18 假设s为类X上的距离相似侧度，有， 是连续单调递增函数，满足 证明是X上的距离相似侧度。 2.19 证明：对于模式矢量集X上任意两个矢量和 有 2.20 （a）证明公式中 的最大最小值分别是和 。（b）证明当时，公式 中 2.21 假设d是模式矢量集X上的差异性测度，是相应相似测度。 证明 其中和 是分别根据s和d所定义的。 的定义来自于下面公

11、式，其中第一个集合只含有一个矢量。提示：平均亲近函数 ，其中 和 分别是集合 和 的势。即使 是测度，显然 不是测度。在公式中， 和 中的所有矢量都参与计算。 2.22 假设。证明 。 2.23 考虑一维空间的两矢量，和 ， ，定义距离 为 这个距离曾被提议作为欧氏距离的近似值。 （a）证明是距离。 （b）比较和 的计算复杂度。 224 若定义下列准则函数其中是 中 个样本的均值向量， 是总散布矩阵，（1）证明对数据的非奇异线形变换具有不变性。（2）证明把中的样本 转移到 中去，则使 改变为（3）写出使最小化的迭代程序。 225 证明对于C-均值算法，聚类准则函数满足使算法收敛的条件。（即若，

12、则有 ） 226 令是点到聚类的相似性度量，式中 和 是聚类 的均值和协方差矩阵，若把一点从 转移到 中去，计算由公式所示 的变化值。 第三章 判别域代数界面方程法3.1 证明感知器算法在训练模式是线性可分的情况下，经过有限次迭代后可以收敛到正确的解矢量。 3.2（1）试给出LMSE算法（H-K算法）的算法流程图;（2）试证明X#e(k)=0，这里, X#是伪逆矩阵；e(k)为第k次迭代的误差向量;（3）已知两类模式样本w1：x1=(-1,0)T, x2=(1,0)T；w2：x3=(0,0)T，x4=(0,-1)T。试用LMSE算法判断其线性可分性。3.3 设等式方程组，其中：属于 的样本作为

13、 的前 行，属于 的样本作为 的后 行。证明：当余量矢量 时，MSE解等价于Fisher解。 3.4 已知二维样本：=(-1,0)T， =(0,-1)T，=(0,0)T， =(2,0)T和 =(0,2)T， ， 。试用感知器算法求出分类决策函数，并判断 =(1,1)T属于哪一类？ 3.4. 已知模式样本 x1=(0,0)T,x2=(1,0)T,x3=(-1,1)T分别属于三个模式类别，即， x1w1,x2w2,x3w3，（1）试用感知器算法求判别函数gi(x)，使之满足，若xiwi 则gi(x)0，i=1,2,3；（2）求出相应的判决界面方程，并画出解区域的示意图。给定校正增量因子C=1，初始

14、值可以取：w1(1)=(4,-9,-4)T，w2(1)=(4,1,-4,)T，w3(1)=(-4,-1,-6)T。3.5 已知w1：(0,0)T,w2：(1,1)T,w3：(-1,1)T。用感知器算法求该三类问题的判别函数，并画出解区域。3.6 试证明：（1）从到超平面 的距离 是在 的约束条件下，使 达到极小的解。（2）在超平面上的投影是 。 3.7 设有一维空间二次判别函数，试将其映射成广义齐次线性判别函数 。 3.8 对二维线性判别函数（1）将判别函数写成的形式，并画出 的几何图形；（2）将其映射成广义齐次线性判别函数 ；（3）指出上述X空间实际是Y空间的一个子空间，且对X子空间的划分与

15、原空间中 对原X空间的划分相同，并在图上表示出来。 3.9 指出在Fisher线性判别中，的比例因子对Fisher判别结果无影响的原因。 3.10 证明两向量外积组成的矩阵一般是奇异的。3.11 证明，在几何上，感知器准则函数值正比于被错分类样本到决策面的距离之和。3.12解释为什么感知器函数是一个连续分段的线性分类器。3.13如果在感知器算法中，那么在 步之后，这个算法收敛，其中 ， 。3.14证明感知器算法的正确分类和错误分类在有限个反复的运算以后是收敛的3.15 考虑一种情况，在类中包含两个特征向量， 。类 中包含 和 两个向量。根据感知器算法，其中 ， ，设计一个线性分离器来区分这两类

16、3.16在上一章2。12问题中两分类问题中，取, , .对于每一类产生50个向量。为了确保对于这两类的线性分离，对于向量1，1类确保 ，对于0，0向量类。下面的步骤就是使用这些向量去设计一个线性分类器使用(3.21)中的感知器算法。在收敛以后，画出相关的判定线3.17 假如2.12问题中是多类分类问题，每一类有100个样本点。根据LMS算法使用这些数据去设计一个线性分类器。当所有的点被带入这个算法中进行计算的时候，画出这个算法收敛的相关超平面。其中，然后使用 。观察这个结果3.18 证明，使用KESLER构造器，经过前面3。21感知器算法的有限步正确与错误分类计算后，对于一个，变为 3.19

17、证明理想权重向量的误差平方和趋渐进于MSE的解。3.20使用均方误差和的原则解问题3.6并设计一个线性分类器。3.21证明设计一个M类的线性分类器，有最佳误差平方和。分类器减少到M等价个有相应的效果。3.22证明，假如x,y服从联合高斯分布，对于x条件下y的分布是 ， 3.23 取M类分类器按照参数函数的形式存在，目的是估计参数 ，使得分类器根据输入向量x能够产生期望的响应输出值 。假设在每一类中x是随机分布，分类器的输出根据相关期望响应值的不同而不同。按照高斯已知变量的一个高斯分布，假设所有的输出都是相同的。证明按照误差平方和的原则，ML估计是产生一个等价的估计值。提示：在已知的类别当中取出

18、N个训练样本值。对于他们中的每一个形成。 是第k类中第i个样本点的期望响应值。 服从正态0均值，方差为 的分布。这个似然函数使用 3.24在二类分类问题中，贝叶斯最佳判定截面是通过给出，证明MSE中训练一个判定界面 ，目的是对两类进行有效判别，相关的，它等价于在MSE最优感知中，它等价于 的渐进函数形式g(.).3.25 假设在两类分类问题中有服从联合分布的特征向量，他们在有共同的方差。设计一个线性MSE分类器，证明在2.11问题中的贝叶斯分类器和这个结果的MSE分类器仅仅通过一个阈值就可以区分。简化起见，仅仅考虑等概率的类的情况。提示：计算MSE超平面，增加x的维数，它的解按照下列方式提供，

19、相关的R和在MSE分类器中按照下列的形式给出 第四章 统计判决4.1 使用最小最大损失判决规则的错分概率是最小吗？为什么？4.2 当Si=s2I时，先验概率对决策超平面的位置影响如何？4.3 假设在某个地区的细胞识别中正常和异常 两类的先验概率分别为 正常状态 ： 异常状态： 现有一待识的细胞，其观测值为，从类条件概率密度分布曲线上查得 并且已知损失系数为l11=0，l12=1，l21=6，l22=0。试对该细胞以以下两种方法进行分类：基于最小错误概率准则的贝叶斯判决；基于最小损失准则的贝叶斯判决。请分析两种分类结果的异同及原因。4.4 试用最大似然估计的方法估计单变量正态分布的均值和方差 。

20、4.5 已知两个一维模式类别的类概率密度函数为 x 0x1p(x|w1)= 2-x1x2 0 其它 x-1 1x q，则判xw1，这里，q是使e1=e成立的似然比判决门限。注：这就是Neyman-Pearson判决准则， 它类似于贝叶斯最小风险准则。提示：该问题等价于用Langrange乘子法，使q=q(e1-e)+e2最小化。4.17二维三类问题，假设每一类都服从同一正态分布，且特征向量的的协方差矩阵为 各类的均值向量分别是， ， 。（1）用贝叶斯最小错误概率分类器将向量分类。（2）画出距离向量的等马氏距离曲线图（略图）。 4.18. 在两类三维空间分类问题中，每一类中的特征向量都服从正态分

21、布，协方差矩阵为 这两类的各自的均值向量分别为和 。试推导相应的线性决策函数和决策界面方程。 4.19在两类等概率分类问题中，每一类中的特征向量的协方差矩阵均为S，相关的均值向量为， ，证明对于贝叶斯最小错误概率分类器，错误概率分布是 其中，是这两个均值向量之间的马氏距离。该函数是 的增函数。 提示：对数似然比是一个随机变量，且服从高斯分布： ， ；和 ， 。据此计算错误概率。4.20证明假设每个向量都遵循高斯概率密度函数分布，在（2。19）的最大似然概率检测等价于 这里是 和x之间关于 矩阵的的马氏距离。4.21如果，证明上个问题成为 ，这里 。4.22在二维两类问题中，每一类都服从以下分布

22、： 其中 ， 假设 ，设计一个贝叶斯分类器，满足（a） 错误分类概率最小（b） 具有损失矩阵L的平均风险最小 使用一个伪随机的数值产生器，从每一个类中得到100个特征向量。按照上面的概率密度函数。使用这个分类器去分类已经产生的向量。对于每个事例中的错误概率是多少？用重复这个实验。4.23重复上面的实验，特征向量服从以下分布： 而且 并且， 提示：一个高斯随机向量的线性变换仍然是一个高斯随机向量。注意 4.24二维两类问题，假设两类服从同一正态分布，其协方差矩阵为，均值向量分别为 。试用贝叶斯分类器对向量 进行分类。4.25假设在两类一维问题中服从高斯分布 ，服从a到b之间的均匀分布。证明贝叶斯

23、错误概率的上限为，其中，并且y服从高斯分布。4.26证明随机向量的均值是。4.27在掷硬币的游戏实验中，正面（1）出现的概率是q，反面出现的概率是（1-q）。设，i=1,2,，N是这个实验的结果， ，证明q 的最大似然估计是 提示：似然函数是：证明ML结果是下列方程的解 4.28随机变量x服从高斯分布，m未知。给定该变量的N个观测值，设L（m）为m的对数似然函数：。试求该随机变量的Cramer-Rao界： 。将该结果与m的ML估计值的方差进行比较，有何结论？假如这个未知参数是方差，结论又如何？。 4.29证明假如似然函数是高斯函数有未知的均值，和协方差矩阵 ，然后ML估计如下给出 4.30随机

24、变量x 服从Erlang分布，概率密度函数为 其中u(x)是一个阶跃函数 假设x的N个观测值x1，xN ，证明的最大似然估计为 4.31随机变量x是服从正态分布，其中未知参数 服从Rayleigh分布，其概率密度函数为 试证明的最大后验概率估计为 其中， , 4.32. 证明对于对数正态分布 最大似然估计为 4.33若已知一个随机变量x的均值和方差： ， 试证明，该随机变量概率密度函数的最大熵估计服从高斯分布 4.34P为一个随机点x位于某区间h的概率。给定x的N个观测值，其中有k个落入区间h的概率服从二项式分布： 证明，并且它的方差为 而且这个概率估计P=k/N是无偏的和渐进一致的。第五章

25、特征提取与选择5.1 设有M类模式wi，i=1,2,.,M，试证明总体散布矩阵St是总类内散布矩阵Sw与类间散布矩阵Sb之和，即StSwSb。5.2 下面哪个矩阵可以用在二维空间线性变换中，并保持马氏距离的特性？请解释原因。； ； 5.3 Bhattacharyya可分性判据定义为式中W表示特征空间。试证明，在最小误判概率准则判决下，最小最小误判概率有 。 5.4 令xi，i=1，2，3为独立的二值特征，且p(xi=1|w1)=ai ，p(xi=1|w2)=bi ，两类的先验概率相等，且ai，bi满足以下条件：（1）ai b2 - a2b3 - a3 。试证明各特征分别使用时之错误概率e(xi

26、)满足：e(x1) e(x2) e(x3) 。5.5 按上题条件，试证明当两个特征合用时，其错误概率为请找出使之条件。 5.6 同上题，如果给定试计算。 5.7 已知以下两类模式w1：(0,0,0)T，(1,0,0)T，(1,0,1)T，(1,1,0)Tw2：(0,0,1)T，(0,1,0)T，(0,1,1)T，(1,1,1)T试用K-L变换分别把特征空间维数降到d=2和d=1，并作图画出样本在该特征空间中的位置。5.8 令和 分别是 类（i=1,2）的协方差矩阵和先验概率。假设对数据进行了白化变换，即，使 。这里， ，I是单位矩阵。试证明矩阵 和 所产生的K-L坐标轴是相同的。若用 表示矩阵

27、 的本征值矩阵，求证 。 定第六章 句法模式识别6.1 句法模式识别中，模式类是如何描述的。6.2 文法G=(VN,VT,P,S)中起始符S可以是非终止符吗？6.3试给出能产生不含子串011的0，1字符串的全体的正则文法Gn，画出Gn对应的有限状态自动机的状态转移图。设x=10010，试根据CYK算法导出对x的最左剖析。6.4 已知文法G=(VN,VT,P,S)，VN=S,D，VT=a,d,(,),+，-,*,其中，a,d为图形描述语言（PDL）的基元：a：；d：；“+，-，*，”为基元链接运算：“+”为头接尾；“”为尾尾相接；“-”为头头相接；“*”为头接和尾接；“”为反向；“（，）”为运算顺序控制符。试写出描述字母“E”的PDL句子及相应的产生式P。-