模式识别试题库

《模式识别》试题库一、基本概念题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积累位势函数法的判别界面一般为。（1）线性界面；（2）非线性界面。1.9基于距离的类别可分性判据有：。（1）1[]wBTrSS（2）BWSS（3）BWBSSS1.10作为统计判别问题的模式分类，在（）情况下，可使用聂曼-皮尔逊判决准则。1.11确定性模式非线形分类的势函数法中，位势函数K(x,xk)与积累位势函数K(x)的关系为（）。1.12用作确定性模式非线形分类的势函数法，通常，两个n维向量x和xk的函数K(x,xk)若同时满足下列三个条件，都可作为势函数。①（）；②（）；③K(x,xk)是光滑函数，且是x和xk之间距离的单调下降函数。1.13散度Jij越大，说明i类模式与j类模式的分布（）。当i类模式与j类模式的分布相同时，Jij=（）。1.14若用Parzen窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是（），h1过大可能产生的问题是（）。1.15信息熵可以作为一种可分性判据的原因是：。1.16作为统计判别问题的模式分类，在（）条件下，最小损失判决规则与最小错误判决规则是等价的。1.17随机变量l(x)=p(x1)/p(x2)，l(x)又称似然比，则El(x)2=（）。在最小误判概率准则下，对数似然比Bayes判决规则为（）。1.18影响类概率密度估计质量的最重要因素是（）。1.19基于熵的可分性判据定义为)]|(log)|([1xPxPEJiciixH，JH越（），说明模式的可分性越强。当P(i|x)=（）(i=1,2,…,c)时，JH取极大值。1.20Kn近邻元法较之于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)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等价类分别为（[a]R=，[b]R=，[c]R=，[d]R=）。1.24如果集合X上的关系R是传递的、（）和（）的，则称R是一个等价关系。1.25一个模式识别系统由那几部分组成？画出其原理框图。1.26统计模式识别中，模式是如何描述的。1.27简述随机矢量之间的统计关系：不相关，正交，独立的定义及它们之间的关系。1.28试证明，对于正态分布，不相关与独立是等价的。1.29试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。1.30试证明，多元正态随机矢量X的分量的线性组合是一正态随机变量。第二部分分析、证明、计算题第二章聚类分析2.1影响聚类结果的主要因素有那些？2.2马氏距离有那些优点？2.3如果各模式类呈现链状分布，衡量其类间距离用最小距离还是用最大距离？为什么？2.4动态聚类算法较之于简单聚类算法的改进之处何在？层次聚类算法是动态聚类算法吗？比较层次聚类算法与c-均值算法的优劣。2.5ISODATA算法较之于c-均值算法的优势何在？2.6简述最小张树算法的优点。2.7证明马氏距离是平移不变的、非奇异线性变换不变的。2.8设，类p、q的重心分别为px、qx，它们分别有样本pn、qn个。将和q合并为l，则l有qplnnn个样本。另一类k的重心为kx。试证明k与l的距离平方是2222pqlkqpkqlkqkplkpklDnnnnDnnnDnnnD2.9（1）设有M类模式i，i=1,2,...,M，试证明总体散布矩阵ST是总类内散布矩阵SW与类间散布矩阵SB之和，即ST＝SW＋SB。（2）设有二维样本：x1=(-1,0)T，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-均值算法可使误差平方和准则)()()()()(1)(kjixkjiTkjicjkzxzxJ最小。其中，k是迭代次数；)(kjz是)(kj的样本均值。2.11现有2k+1个一维样本，其中k个样本在x=-2处重合，另k个样本在x=0处重合，只有1个在x=a0处。若a=2(k+1)，证明，使误差平方和准则Jc最小的两类划分是x=0处的k个样本与x=a处的1个样本为一类，其余为另一类。这里，cNjJc=(ximj)2j=1i=1其中，c为类别数，Nj是第j类的样本个数，xij，i=1,2,...,Nj，mj是第j类的样本均值。2.12有样本集}01,55,45,54,44,10,00{，试用谱系聚类算法对其分类。2.13设有样本集S=},...,,{21nxxx，证明类心z到S中各样本点距离平方和niiTizxzx1)()(为最小时，有niixnz11。2.14假设s为模式矢量集X上的距离相似侧度，有,0,(,)0xysxy且当0a时，(,)/(,)dxyasxy。证明d是距离差异性测度。2.15证明欧氏距离满足旋转不变性。提示：运用Minkowski不等式，对于两矢量T1[,,]lxxx和minminmaxmaxmm(),(),(),()()ssssssssssssssssavgavgeaneandsdsdsdsds，满足1/1/1/111()()()ppplllpppiiiiiiiyyxx2.16证明：（a）如果s是类X上的距离相似侧度，,0,(,)0xysxy，那么对于0a，(,)sxya也是类X上的距离测度。（b）如果d是类X上的距离差异性测度，那么对于0a，da也是类X上的距离差异性测度2.17假设:fRR是连续单调递增函数，满足()()(),,fxfyfxyxyRd是类X上的距离差异性测度且00d。证明()fd也是类X上的距离差异性测度。2.18假设s为类X上的距离相似侧度，有,0,(,)0xysxy，:fRR是连续单调递增函数，满足111()()(),,xyfxfyfxyR证明()fx是X上的距离相似侧度。2.19证明：对于模式矢量集X上任意两个矢量x和y有21(,)(,)(,)xyxyxyddd2.20（a）证明公式1/(,)1(,)()qFlqqxyiiisxys中(,)Fsxy的最大最小值分别是和1/0.5ql。（b）证明当q时，公式1/(,)1(,)()qqFlqxyiiisxys中1(,)max(,)iliiFxysxys2.21假设d是模式矢量集X上的差异性测度，maxsdd是相应相似测度。证明max(,)(,),,pspsavgavgxCxCxXCXsdd其中psavgs和psavgd是分别根据s和d所定义的。psavg的定义来自于下面公式，其中第一个集合只含有一个矢量。提示：平均亲近函数1(,)(,)ijijpsavgijxDyDDDDDxynn，其中iDn和jDn分别是集合iD和jD的势。即使是测度，显然psavg不是测度。在公式中，iD和jD中的所有矢量都参与计算。2.22假设,{0,1}lxy。证明2min(,)(,)Hamgxyxydd。2.23考虑一维空间的两矢量，T1[,,]lxxx和T1[,,]lyyy，1max{}jlijijyyxx，定义距离(,)nxyd为1,1(,)[(2)/2]lniiiijjixyllyydxx这个距离曾被提议作为欧氏距离的近似值。（a）证明nd是距离。（b）比较nd和2d的计算复杂度。2．24若定义下列准则函数11()()icTTiTiixXJxmSxm其中im是iX中iN个样本的均值向量，TS是总散布矩阵，（1）证明TJ对数据的非奇异线形变换具有不变性。（2）证明把iX中的样本ˆx转移到jX中去，则使TJ改变为*11ˆˆˆˆ[()()()()]11jTTiTTjTjiTijiNNJJxmSxmxmSxmNN（3）写出使TJ最小化的迭代程序。2．25证明对于C-均值算法，聚类准则函数满足使算法收敛的条件。（即若(,)(,)JKJK，则有(,)(,)JKJK）2．26令111(,)()()log||22TjjjjjyKymym是点到聚类的相似性度量，式中jm和j是聚类j的均值和协方差矩阵，若把一点从i转移到j中去，计算由公式1(,)jcKjiyJyK所示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：x3=(0,0)T，x4=(0,-1)T。试用LMSE算法判断其线性可分性。3.3设等式方程组bwX，其中：属于1的样本作为X的前1N行，属于2的样本作为X的后2N行。证明：当余量矢量),,,,,(212211NNNNNNNNNNb时，MSE解等价于Fisher解。3.4已知二维样本：1x=(-1,0)T，2x=(0,-1)T，=(0,0)T，4x=(2,0)T和5x=(0,2)T，1321},,{xxx，254},{xx。试用感知器算法求出分类决策函数，并判断6x=(1,1)T属于哪一类？3.4.已知模式样本x1=(0,0)T,x2=(1,0)T,x3=(-1,1)T分别属于三个模式类别，即，x11,x22,x33，（1）试用感知器算法求判别函数gi(x)，使之满足，若xii则gi(x)0，i=1,2,3；（2）求出相应的判决界面方程，并画出解区域的示意图。给定校正增量因子C=1，初始值可以取：w1(1)=(4,-9,-4)T，w2(1)=(4,1,-4,)T，w3(1)=(-4,-1,-6)T。3.5已知1：{(0,0)T},2：{(1,1)T},3：{(-1,1)T}。用感知器算法求该三类问题的判别函数，并画出解区域。3.6试证明：（1）从x到超平面0)(