《模式识别》试题库.doc

1、模式识别试题库一、基本概念题1.1 模式识别的三大核心问题是： 、 、 。1.2、模式分布为团状时，选用 聚类算法较好。 1.3 欧式距离具有 。 马式距离具有 。 （1）平移不变性 （2）旋转不变性 （3）尺度缩放不变性 （4）不受量纲影响的特性1.4 描述模式相似的测度有： 。（1）距离测度 （2）模糊测度 （3）相似测度 （4）匹配测度1.5 利用两类方法处理多类问题的技术途径有：（1） ；（2） ；（3） 。其中最常用的是第 个技术途径。 1.6 判别函数的正负和数值大小在分类中的意义是： ， 。1.7 感知器算法 。（1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 1.8

2、 积累位势函数法的判别界面一般为 。（1）线性界面；（2）非线性界面。1.9 基于距离的类别可分性判据有： 。（1）1wBTrS（2） BWS（3） BWS1.10 作为统计判别问题的模式分类，在（ ）情况下，可使用聂曼-皮尔逊判决准则。1.11 确定性模式非线形分类的势函数法中，位势函数 K(x,xk)与积累位势函数 K(x)的关系为（ ）。1.12 用作确定性模式非线形分类的势函数法，通常，两个 n 维向量 x 和 xk的函数 K(x,xk)若同时满足下列三个条件，都可作为势函数。（ ）；（ ）； K(x,x k)是光滑函数，且是 x 和 xk之间距离的单调下降函数。1.13 散度 Jij

3、越大，说明 i类模式与 j类模式的分布（ ）。当 i类模式与 j类模式的分布相同时，J ij=（ ）。1.14 若用 Parzen 窗法估计模式的类概率密度函数，窗口尺寸 h1 过小可能产生的问题是（ ），h1 过大可能产生的问题是（ ）。1.15 信息熵可以作为一种可分性判据的原因是： 。1.16 作为统计判别问题的模式分类，在（ ）条件下，最小损失判决规则与最小错误判决规则是等价的。1.17 随机变量 l(x)=p( 1)/p( x2)，l( )又称似然比，则 El( x)2=（ ）。在最小误判概率准则下，对数似然比 Bayes 判决规则为（ ）。 1.18 影响类概率密度估计质量的最重要

4、因素是（ ）。1.19 基于熵的可分性判据定义为)|(log)|(1xPxEJiciixH，J H越（ ），说明模式的可分性越强。当 P(i| x) =（ ）(i=1,2,c)时，J H取极大值。 1.20 Kn 近邻元法较之于 Parzen 窗法的优势在于（ ）。上述两种算法的共同弱点主要是（ ）。1.21 已知有限状态自动机 Af=(，Q，q0，F)，=0 ，1；Q=q0，q1；：(q0，0)= q1，(q0，1)= q1，(q1，0)=q0，(q1，1)=q0；q0=q0；F=q0。现有输入字符串：(a) 00011101011，(b) 1100110011，(c) 1011001110

5、00，(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 上的关系 R 是传递的、（ ）和（ ）的，则称 R 是一个等价关系。1.25 一个模式识别系统由那几部分组成？画出其原理框图。1.26 统计

6、模式识别中，模式是如何描述的。1.27 简述随机矢量之间的统计关系：不相关，正交，独立的定义及它们之间的关系。1.28 试证明，对于正态分布，不相关与独立是等价的。1.29 试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。1.30 试证明，多元正态随机矢量 X的分量的线性组合是一正态随机变量。 第二部分 分析、证明、计算题第二章 聚类分析2.1 影响聚类结果的主要因素有那些？2.2 马氏距离有那些优点？2.3 如果各模式类呈现链状分布，衡量其类间距离用最小距离还是用最大距离？为什么？2.4 动态聚类算法较之于简单聚类算法的改进之处何在？层次聚类算法是动态聚类算法吗？比较层次聚类算法与

7、c-均值算法的优劣。2.5 ISODATA 算法较之于 c-均值算法的优势何在？2.6 简述最小张树算法的优点。2.7 证明马氏距离是平移不变的、非奇异线性变换不变的。2.8 设，类 p、 q的重心分别为 px、 q，它们分别有样本 pn、 q个。将和 q合并为 l，则 l有 ln个样本。另一类 k的重心为 kx。试证明 k与 l的距离平方是 2222 pqlkqlkplkl DnnDn2.9 （1）设有 M 类模式 i，i=1,2,.,M，试证明总体散布矩阵 ST是总类内散布矩阵 SW与类间散布矩阵 SB之和，即 STS WS B。（2）设有二维样本：x1=(-1,0) T，x2=(0,-1

8、) 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-均值算法可使误差平方和准则)( )()1)(kjix kjiTkjicjk zxzJ 最小。其中，k 是迭代次数；)(kjz是 )(kj的样本均值。 2.11 现有 2k+1 个一维样本，其中 k

9、 个样本在 x=-2 处重合，另 k 个样本在 x=0 处重合，只有 1 个在x=a0 处。若 a=2(k+1)，证明，使误差平方和准则 Jc 最小的两类划分是 x=0 处的 k 个样本与 x=a 处的1 个样本为一类，其余为另一类。这里，c NjJc = (ximj)2j=1 i=1其中，c 为类别数，Nj 是第 j 类的样本个数，xij，i=1,2,.,Nj，mj 是第 j 类的样本均值。2.12 有样本集01,54,10，试用谱系聚类算法对其分类。2.13 设有样本集 S= ,.21nx，证明类心 z到 S 中各样本点距离平方和 ni iTizx1)()(为最小时，有 iz1。 2.14

10、 假设 s 为模式矢量集 X 上的距离相似侧度，有 ,0(,)xys且当 0a时， (,)/(,)dxya。证明 d 是距离差异性测度。 2.15 证明欧氏距离满足旋转不变性。提示：运用 Minkowski 不等式，对于两矢量T1,lx和 miniaxmm(),(),(),()sssssavgeand，满足1/ 1/ 1/1pppllliiiyy2.16 证明：（a）如果 s 是类 X 上的距离相似侧度， ,0(,)xys，那么对于 0a， (,)sxy也是类 X 上的距离测度。（b）如果 d 是类 X 上的距离差异性测度，那么对于 a， d也是类 X 上的距离差异性测度 2.17 假设 :f

11、R是连续单调递增函数，满足()(),fxyfxyRd 是类 X 上的距离差异性测度且 0d。证明 (fd也是类 X 上的距离差异性测度。 2.18 假设 s 为类 X 上的距离相似侧度，有 ,0,)xys， :f是连续单调递增函数，满足1()(),xyfxfR证明 ()fx是 X 上的距离相似侧度。 2.19 证明：对于模式矢量集 X 上任意两个矢量 x和 y有21(,)(,)(,)xydd2.20 （a）证明公式/(,),qFlqiis中 (,)Fsxy的最大最小值分别是和 1/0.5ql。（b）证明当 q时，公式 1/(,)1(,)qqFlxyiis中 1(,)max(,)iliFysys

12、2.21 假设 d 是模式矢量集 X 上的差异性测度， maxd是相应相似测度。证明 max(,)(,),ps psavgvgCCX其中s和 s是分别根据 s 和 d 所定义的。 psavg的定义来自于下面公式，其中第一个集合只含有一个矢量。提示：平均亲近函数1(,)(,)ijijpsavgij xDyDxyn，其中 iDn和 j分别是集合 iD和 j的势。即使 是测度，显然 psavg不是测度。在公式中， i和 j中的所有矢量都参与计算。2.22 假设 ,0,1lxy。证明 2min(,)(,)Hagxyxyd。 2.23 考虑一维空间的两矢量，T1l和 T1l， 1majli ji j ，

13、定义距离 (,)nxy为1,(,)(2)/lni ii ijxyld这个距离曾被提议作为欧氏距离的近似值。（a）证明 n是距离。（b）比较 和 2的计算复杂度。 224 若定义下列准则函数 11()()icTTiiixXJmSx其中 i是 i中 iN个样本的均值向量， TS是总散布矩阵，（1）证明 TJ对数据的非奇异线形变换具有不变性。（2）证明把 iX中的样本 x转移到 jX中去，则使 TJ改变为* 1 1()()()()jTiTjj iiNNJmSxmSx （3）写出使 TJ最小化的迭代程序。 225 证明对于 C-均值算法，聚类准则函数满足使算法收敛的条件。（即若 (,)(,)JK，则有

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

15、3=(0,0) T，x4=(0,-1) T。试用 LMSE 算法判断其线性可分性。3.3 设等式方程组 bwX，其中：属于 1的样本作为 X的前 1N行，属于 2的样本作为 X的后 2N行。证明：当余量矢量 ),(21 NN时，MSE 解等价于 Fisher 解。 3.4 已知二维样本： 1x=(-1,0)T， 2x=(0,-1)T，=(0,0) T， 4x=(2,0)T和 5x=(0,2)T， 321,x， 54,。试用感知器算法求出分类决策函数，并判断 6=(1,1)T属于哪一类？ 3.4. 已知模式样本 x 1=(0,0)T,x2=(1,0)T,x3=(-1,1)T分别属于三个模式类别，

16、即， x11,x22,x33，（1）试用感知器算法求判别函数 gi(x)，使之满足，若 xii 则 gi(x)0，i=1,2,3；（2）求出相应的判决界面方程，并画出解区域的示意图。给定校正增量因子 C=1，初始值可以取：w1(1)=(4,-9,-4)T，w 2(1)=(4,1,-4,)T，w 3(1)=(-4,-1,-6)T。3.5 已知 1：(0,0) T,2：(1,1) T,3：(-1,1) T。用感知器算法求该三类问题的判别函数，并画出解区域。3.6 试证明：（1）从 x到超平面 0)(wxgT的距离 wxgr|)(|是在 0)(q的约束条件下，使 2q达到极小的解。（2） x在超平面

17、上的投影是 xgp2)(。 3.7 设有一维空间二次判别函数 2975)(xxg，试将其映射成广义齐次线性判别函数 yaxgT)(。 3.8 对二维线性判别函数 2)(1xg（1）将判别函数写成 0wxT的形式，并画出 0)(xg的几何图形；（2）将其映射成广义齐次线性判别函数 yaxgT)(；（3）指出上述 X 空间实际是 Y 空间的一个子空间，且 对 X 子空间的划分与原空间中 0wxT对原 X 空间的划分相同，并在图上表示出来。 3.9 指出在 Fisher 线性判别中， w的比例因子对 Fisher 判别结果无影响的原因。 3.10 证明两向量外积组成的矩阵一般是奇异的。3.11 证明

18、，在几何上，感知器准则函数值正比于被错分类样本到决策面的距离之和。3.12 解释为什么感知器函数是一个连续分段的线性分类器。3.13 如果在感知器算法中 k，那么在 *20wk步之后，这个算法收敛，其中 2， 。3.14 证明感知器算法的正确分类和错误分类在有限个反复的运算以后是收敛的3.15 考虑一种情况，在类 1中包含两个特征向量， 0,1T。类 2中包含 1,0T和 ,T两个向量。根据感知器算法，其中 ， ().5，设计一个线性分离器来区分这两类3.16 在上一章 2。12 问题中两分类问题中，取 1,T, 2,T, 21.对于每一类产生 50 个向量。为了确保对于这两类的线性分离，对于

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

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

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