《模式识别》试题库.doc
《《模式识别》试题库.doc》由会员分享，可在线阅读，更多相关《《模式识别》试题库.doc（23页珍藏版）》请在冰点文库上搜索。
《模式识别》试题库
一、基本概念题
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）
（2）（3）
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越大，说明wi类模式与wj类模式的分布（）。
当wi类模式与wj类模式的分布相同时，Jij=（）。
1.14若用Parzen窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是（），h1过大可能产生的问题是（）。
1.15信息熵可以作为一种可分性判据的原因是：
。
1.16作为统计判别问题的模式分类，在（）条件下，最小损失判决规则与最小错误判决规则是等价的。
1.17随机变量l（）=p（|w1）/p（|w2），l（）又称似然比，则E{l（）|w2}=（）。
在最小误判概率准则下，对数似然比Bayes判决规则为（ ）。
1.18影响类概率密度估计质量的最重要因素是（）。
1.19基于熵的可分性判据定义为，JH越（），说明模式的可分性越强。
当P（wi|）=（）（i=1,2,…,c）时，JH取极大值。
1.20Kn近邻元法较之于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）=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等价类分别为（[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试证明，多元正态随机矢量的分量的线性组合是一正态随机变量。
第二部分分析、证明、计算题
第二章聚类分析
2.1影响聚类结果的主要因素有那些？
2.2马氏距离有那些优点？
2.3如果各模式类呈现链状分布，衡量其类间距离用最小距离还是用最大距离？
为什么？
2.4动态聚类算法较之于简单聚类算法的改进之处何在？
层次聚类算法是动态聚类算法吗？
比较层次聚类算法与c-均值算法的优劣。
2.5ISODATA算法较之于c-均值算法的优势何在？
2.6简述最小张树算法的优点。
2.7证明马氏距离是平移不变的、非奇异线性变换不变的。
2.8设，类、的重心分别为、，它们分别有样本、个。
将和合并为，则有个样本。
另一类的重心为。
试证明与的距离平方是
2.9
（1）设有M类模式wi，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-均值算法可使误差平方和准则最小。
其中，k是迭代次数；是的样本均值。
2.11现有2k+1个一维样本，其中k个样本在x=-2处重合，另k个样本在x=0处重合，只有1个在x=a>0处。
若a=2（k+1），证明，使误差平方和准则Jc最小的两类划分是x=0处的k个样本与x=a处的1个样本为一类，其余为另一类。
这里，
cNj
Jc=åå（xi-mj）2
j=1i=1
其中，c为类别数，Nj是第j类的样本个数，xiÎwj，i=1,2,...,Nj，mj是第j类的样本均值。
2.12有样本集，试用谱系聚类算法对其分类。
2.13设有样本集S=，证明类心到S中各样本点距离平方和为最小时，有。
2.14假设s为模式矢量集X上的距离相似侧度，有且当时，。
证明d是距离差异性测度。
2.15证明欧氏距离满足旋转不变性。
提示：
运用Minkowski不等式，对于两矢量和，满足
2.16证明：
（a）如果s是类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所定义的。
的定义来自于下面公式，其中第一个集合只含有一个矢量。
提示：
平均亲近函数
，其中和分别是集合和的势。
即使是测度，显然不是测度。
在公式中，和中的所有矢量都参与计算。
2.22假设。
证明。
2.23考虑一维空间的两矢量，和，，定义距离为
这个距离曾被提议作为欧氏距离的近似值。
（a）证明是距离。
（b）比较和的计算复杂度。
2．24若定义下列准则函数
其中是中个样本的均值向量，是总散布矩阵，
（1）证明对数据的非奇异线形变换具有不变性。
（2）证明把中的样本转移到中去，则使改变为
（3）写出使最小化的迭代程序。
2．25证明对于C-均值算法，聚类准则函数满足使算法收敛的条件。
（即若，则有）
2．26令是点到聚类的相似性度量，式中和是聚类的均值和协方差矩阵，若把一点从转移到中去，计算由公式
所示的变化值。
第三章判别域代数界面方程法
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设等式方程组，其中：
属于的样本作为的前行，属于的样本作为的后行。
证明：
当余量矢量时，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分别属于三个模式类别，即，x1Îw1,x2Îw2,x3Îw3，
（1）试用感知器算法求判别函数gi（x），使之满足，若xiÎwi则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已知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子空间的划分与原空间中对原X空间的划分相同，并在图上表示出来。
3.9指出在Fisher线性判别中，的比例因子对Fisher判别结果无影响的原因。
3.10证明两向量外积组成的矩阵一般是奇异的。
3.11证明，在几何上，感知器准则函数值正比于被错分类样本到决策面的距离之和。
3.12解释为什么感知器函数是一个连续分段的线性分类器。
3.13如果在感知器算法中，那么在步之后，这个算法收敛，其中，。
3.14证明感知器算法的正确分类和错误分类在有限个反复的运算以后是收敛的
3.15考虑一种情况，在类中包含两个特征向量，。
类中包含和两个向量。
根据感知器算法，其中，，设计一个线性分离器来区分这两类
3.16在上一章2。
12问题中两分类问题中，取,,.对于每一类产生50个向量。
为了确保对于这两类的线性分离，对于向量[1，1]类确保，
对于[0，0]向量类。
下面的步骤就是使用这些向量去设计一个线性分类器使用（3.21）中的感知器算法。
在收敛以后，画出相关的判定线
3.17假如2.12问题中是多类分类问题，每一类有100个样本点。
根据LMS算法使用这些数据去设计一个线性分类器。
当所有的点被带入这个算法中进行计算的时候，画出这个算法收敛的相关超平面。
其中，然后使用。
观察这个结果
3.18证明，使用KESLER构造器，经过前面3。
21感知器算法的有限步正确与错误分类计算后，对于一个，变为
3.19证明理想权重向量的误差平方和趋渐进于MSE的解。
3.20使用均方误差和的原则解问题3.6并设计一个线性分类器。
3.21证明设计一个M类的线性分类器，有最佳误差平方和。
分类器减少到M等价个有相应的效果。
3.22证明，假如x,y服从联合高斯分布，对于x条件下y的分布是
，
3.23取M类分类器按照参数函数的形式存在，目的是估计参数，使得分类器根据输入向量x能够产生期望的响应输出值。
假设在每一类中x是随机分布，分类器的输出根据相关期望响应值的不同而不同。
按照高斯已知变量的一个高斯分布，假设所有的输出都是相同的。
证明按照误差平方和的原则，ML估计是产生一个等价的估计值。
提示：
在已知的类别当中取出N个训练样本值。
对于他们中的每一个形成。
是第k类中第i个样本点的期望响应值。
服从正态0均值，方差为的分布。
这个似然函数使用
3.24在二类分类问题中，贝叶斯最佳判定截面是通过给出，证明MSE中训练一个判定界面，目的是对两类进行有效判别，相关的，它等价于在MSE最优感知中，它等价于的渐进函数形式g（.）.
3.25假设在两类分类问题中有服从联合分布的特征向量，他们在有共同的方差。
设计一个线性MSE分类器，证明在2.11问题中的贝叶斯分类器和这个结果的MSE分类器仅仅通过一个阈值就可以区分。
简化起见，仅仅考虑等概率的类的情况。
提示：
计算MSE超平面，增加x的维数，它的解按照下列方式提供，
相关的R和在MSE分类器中按照下列的形式给出
第四章统计判决
4.1使用最小最大损失判决规则的错分概率是最小吗？
为什么？
4.2当Si=s2I时，先验概率对决策超平面的位置影响如何？
4.3假设在某个地区的细胞识别中正常和异常两类的先验概率分别为
正常状态：
异常状态：
现有一待识的细胞，其观测值为，从类条件概率密度分布曲线上查得
并且已知损失系数为l11=0，l12=1，l21=6，l22=0。
试对该细胞以以下两种方法进行分类：
①基于最小错误概率准则的贝叶斯判决；②基于最小损失准则的贝叶斯判决。
请分析两种分类结果的异同及原因。
4.4试用最大似然估计的方法估计单变量正态分布的均值和方差。
4.5已知两个一维模式类别的类概率密度函数为
ìx0≤x<1
p（x|w1）=í2-x 1≤x≤2
î0其它
ìx-11≤x<2
p（x|w2）=í3-x2≤x≤3
î0其它
先验概率P（w1）=0.6，P（w2）=0.4，
（1）求0-1代价Bayes判决函数；
（2）求总错误概率P（e）；
（3）判断样本{x1=1.35,x2=1.45,x3=1.55,x4=1.65}各属于哪一类别。
4.6在目标识别中，假定有农田和装甲车两种类型，类型和类型分别代表农田和装甲车，它们的先验概率分别为0.8和0.2，损失函数如表1所示。
现在做了三次试验，获得三个样本的类概率密度如下：
：
0.3，0.1，0.6
：
0.7，0.8，0.3
（1） 试用贝叶斯最小误判概率准则判决三个样本各属于哪一个类型；
（2） 假定只考虑前两种判决，试用贝叶斯最小风险准则判决三个样本各属于哪一个类型；
（3） 把拒绝判决考虑在内，重新考核三次试验的结果。
表1
类型
损失
判决
0.5
3
5
1
2
2
4.7已知两个一维模式类别的类概率密度函数为
先验概率P（w1）=P（w2），损失函数，l11=l22=0，l12=0.6，l21=0.4。
（1）求最小平均损失Bayes判决函数；
（2）求总的误判概率P（e）；
（3）对于一个两类一维问题，若这两类的类概率密度分别服从正态分布N（0,s2）和N（1,s2），证明使平均决策风险最小的决策门限为
这里，假设风险函数l11=l22=0。
一维正态分布：
4.8设是基于样本集{}对总体¾的协方差矩阵的最大似然估计。
试推导由求增加一个样本后协方差矩阵的估计的递推公式。
其中，是基于样本集{}对总体的均值向量的最大似然估计。
4.9设以下两类模式均为正态分布
w1：
{（0,0）T，（2,0）T，（2,2）T，（0,2）T}
w2：
{（4,4）T，（6,4）T，（6,6）T，（4,6）T}
（1）设P（w1）=P（w2）=1/2，求该两类模式之间的Bayes判别界面的方程。
（2）绘出判别界面。
4.10设以下两类模式均为正态分布
w1：
{（-5,-5）T，（-5,-4）T，（-4,-5）T，（-6,-5）T，（-5,-6）T}
w2：
{（5,5）T，（5,6）T，（6,5）T，（5,4）T，（4,5）T}
（1）试用正交函数逼近法求类概率密度的估计和，可选用Hermite正交多项式前四项低阶基函数：
H0（x）=1,H1（x）=2x,H2（x）=4x2-2,H3（x）=8x3-12x；
（2）设P（w1）=P（w2）=1/2，求Bayes判决函数；
（3）给出判别界面方程和图示。
4.11证明在多类问题中，贝叶斯决策准则使错误分类概率最小。
提示：
使用正确分类概率来证明要方便一些。
4.12在一个两类一维问题中，两类的概率分布密度函数分别为高斯分布和，证明使平均风险最小的门限为：
其中。
4.13假设两类类问题中损失矩阵为L=，e1是将本来属于w1类的样本错分为w2的概率，e2是将本来属于w2类的样本错分为w1的概率。
试证明平均风险为
4.14证明在多类分类问题中，M类的分类错误概率上限为Pe=（M-1）/M。
提示，对于每一个向量x最大后验概率密度函数，i=1,2，…，M，大于或等于1/M。
这等价于每一个都是相等的。
4.15假设在一维两类分类当中样本点符合Rayleigh概率密度函数分布：
试求判决边界。
4.16在两类分类问题中，限定其中一类的错分误概率为e1=e，证明，使另一类的错分概率e2最小等价于似然比判决：
如果P（w1）/P（w2）>q，则判xÎw1，这里，q是使e1=e成立的似然比判决门限。
注：
这就是Neyman-Pearson判决准则，它类似于贝叶斯最小风险准则。
提示：
该问题等价于用Langrange乘子法，使q=q（e1-e）+e2最小化。
4.17．二维三类问题，假设每一类都服从同一正态分布，且特征向量的的协方差矩阵为
各类的均值向量分别是，，。
（1）用贝叶斯最小错误概率分类器将向量分类。
（2）画出距离向量的等马氏距离曲线图（略图）。
4.18.在两类三维空间分类问题中，每一类中的特征向量都服从正态分布，协方差矩阵为
这两类的各自的均值向量分别为和。
试推导相应的线性决策函数和决策界面方程。
4.19．在两类等概率分类问题中，每一类中的特征向量的协方差矩阵均为S，相关的均值向量为，，证明对于贝叶斯最小错误概率分类器，错误概率分布是
其中，是这两个均值向量之间的马氏距离。
该函数是的增函数。
提示：
对数似然比是一个随机变量，且服从高斯分布：
，"；和，"。
据此计算错误概率。
4.20．证明假设每个向量都遵循高斯概率密度函数分布，在（2。
19）的最大似然概率检测
等价于
这里是和x之间关于矩阵的的马氏距离。
4.21．如果，证明上个问题成为，这里。
4.22．在二维两类问题中，每一类都服从以下分布：
其中，，假设，设计一个贝叶斯分类器，满足
（a）错误分类概率最小
（b）具有损失矩阵L的平均风险最小
使用一个伪随机的数值产生器，从每一个类中得到100个特征向量。
按照上面的概率密度函数。
使用这个分类器去分类已经产生的向量。
对于每个事例中的错误概率是多少？
用重复这个实验。
4.23．重复上面的实验，特征向量服从以下分布：
而且
并且，
提示：
升级会员 