模式识别试题及总结.doc

一、 填空与选择填空（本题答案写在此试卷上，30分）
1、模式识别系统的基本构成单元包括： 模式采集 、 特征提取与选择
和 模式分类 .
2、统计模式识别中描述模式的方法一般使用 特真矢量 ;句法模式识别中模式描述方法一般有 串 、 树 、 网 .
3、聚类分析算法属于 (1） ；判别域代数界面方程法属于 (3） .
（1）无监督分类 （2）有监督分类 （3)统计模式识别方法（4）句法模式识别方法
4、若描述模式的特征量为0—1二值特征量，则一般采用 （4） 进行相似性度量。
(1）距离测度 (2）模糊测度 （3）相似测度 (4）匹配测度
5、 下列函数可以作为聚类分析中的准则函数的有 （1）（3）（4） .
（1) （2） （3）
（4）
6、Fisher线性判别函数的求解过程是将N维特征矢量投影在 （2） 中进行 .
（1）二维空间 （2)一维空间 （3）N—1维空间
7、下列判别域界面方程法中只适用于线性可分情况的算法有 （1） ；线性可分、不可分都适用的有 （3） 。
（1)感知器算法 （2)H-K算法 (3）积累位势函数法
8、下列四元组中满足文法定义的有 （1）（2)(4) .
（1)（{A， B｝， {0, 1}， ｛A®01, A®0A1 ， A®1A0 ， B®BA , B® 0｝， A）
（2)（{A｝， {0， 1｝， ｛A®0， A®0A｝， A）
（3）（{S｝， ｛a， b｝, ｛S ® 00S, S ® 11S, S ® 00， S ® 11｝， S）
（4）（｛A}, {0， 1}， ｛A®01， A®0A1， A®1A0｝， A）
9、影响层次聚类算法结果的主要因素有（计算模式距离的测度、（聚类准则、类间距离门限、预定的类别数目））.
10、欧式距离具有（ 1、2 ）；马式距离具有(1、2、3、4 )。
(1）平移不变性(2）旋转不变性（3)尺度缩放不变性（4）不受量纲影响的特性
11、线性判别函数的正负和数值大小的几何意义是（正（负)表示样本点位于判别界面法向量指向的正(负)半空间中；绝对值正比于样本点到判别界面的距离.)。
12、感知器算法1.
（1）只适用于线性可分的情况;(2）线性可分、不可分都适用.
13、积累势函数法较之于H—K算法的优点是（该方法可用于非线性可分情况（也可用于线性可分情况) ）;位势函数K(x，xk）与积累位势函数K（x)的关系为（)。
14、在统计模式分类问题中，聂曼—皮尔逊判决准则主要用于( 某一种判决错误较另一种判决错误更为重要)情况；最小最大判决准则主要用于（ 先验概率未知的）情况.
15、“特征个数越多越有利于分类"这种说法正确吗？（错误）。特征选择的主要目的是(从n个特征中选出最有利于分类的的m个特征（m〈n）,以降低特征维数）。一般在(可分性判据对特征个数具有单调性）和（ Cnm〉〉n ）的条件下，可以使用分支定界法以减少计算量。
16、 散度Jij越大，说明wi类模式与wj类模式的分布(差别越大）；当wi类模式与wj类模式的分布相同时，Jij=（0）。
17、 已知有限状态自动机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:{a,d}；ω2:{b，c｝ ）。
18、影响聚类算法结果的主要因素有（②③④)。
①已知类别的样本质量;②分类准则；③特征选取；④模式相似性测度。
19、模式识别中，马式距离较之于欧式距离的优点是（③④）.
①平移不变性；②旋转不变性;③尺度不变性；④考虑了模式的分布.
20、基于二次准则函数的H-K算法较之于感知器算法的优点是（①③）。
①可以判别问题是否线性可分;②其解完全适用于非线性可分的情况；
③其解的适应性更好；④计算量小。
21、影响基本C均值算法的主要因素有(④①②)。
①样本输入顺序;②模式相似性测度；③聚类准则；④初始类心的选取.
22、位势函数法的积累势函数K（x)的作用相当于Bayes判决中的(②④）。
①先验概率；②后验概率；③类概率密度；④类概率密度与先验概率的乘积。
23、在统计模式分类问题中，当先验概率未知时,可以使用（②④).
①最小损失准则;②最小最大损失准则；③最小误判概率准则；④N—P判决。
24、在（①③）情况下，用分支定界法做特征选择计算量相对较少。
①Cnd>〉n，(n为原特征个数，d为要选出的特征个数）；②样本较多；③选用的可分性判据J对特征数目单调不减;④选用的可分性判据J具有可加性。
25、 散度JD是根据(③）构造的可分性判据。
①先验概率；②后验概率；③类概率密度；④信息熵；⑤几何距离。
26、似然函数的概型已知且为单峰,则可用(①②③④⑤）估计该似然函数。
①矩估计；②最大似然估计；③Bayes估计；④Bayes学习；⑤Parzen窗法。
27、Kn近邻元法较之Parzen窗法的优点是（②).
①所需样本数较少；②稳定性较好；③分辨率较高；④连续性较好.
28、从分类的角度讲,用DKLT做特征提取主要利用了DKLT的性质：(①③）。
①变换产生的新分量正交或不相关;②以部分新的分量表示原矢量均方误差最小；③使变换后的矢量能量更趋集中；
29、一般，剪辑k—NN最近邻方法在（①）的情况下效果较好。
①样本数较大；②样本数较小;③样本呈团状分布；④样本呈链状分布。
30、如果以特征向量的相关系数作为模式相似性测度，则影响聚类算法结果的主要因素有（②③）。
①已知类别样本质量；②分类准则；③特征选取；④量纲。
二、（15分）简答及证明题
(1）影响聚类结果的主要因素有那些?
(2）证明马氏距离是平移不变的、非奇异线性变换不变的.
答：（1)分类准则,模式相似性测度，特征量的选择，量纲。
（2）证明:
(2分）
（2分）
（1分）
设，有非奇异线性变换: (1分)
(4分)
三、(8分）说明线性判别函数的正负和数值大小在分类中的意义并证明之.
答：(1)(4分)的绝对值正比于到超平面的距离
平面的方程可以写成
式中。于是是平面的单位法矢量，上式可写成
设是平面中的任一点，是特征空间中任一点,点到平面的距离为差矢量在上的投影的绝对值，即
（1—1）
上式中利用了在平面中，故满足方程
式(1—1)的分子为判别函数绝对值，上式表明，的值正比于到超平面的距离,一个特征矢量代入判别函数后所得值的绝对值越大表明该特征点距判别界面越远。
(2）（4分)的正（负）反映在超平面的正(负）侧
两矢量和的数积为
（2分）
显然，当和夹角小于时，即在指向的那个半空间中，〉0；反之，当和夹角大于时,即在背向的那个半空间中,〈0。由于，故和同号。所以，当在指向的半空间中时，；当在背向的半空间中，。判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧.
五、(12分，每问4分) 在目标识别中，假定有农田和装甲车两种类型，类型w1和类型w2分别代表农田和装甲车，它们的先验概率分别为0.8和0.2，损失函数如表1所示。现在做了三次试验，获得三个样本的类概率密度如下：
:0.3，0.1,0。6
：0。7，0。8，0.3
(1） 试用贝叶斯最小误判概率准则判决三个样本各属于哪一个类型;
(2） 假定只考虑前两种判决，试用贝叶斯最小风险准则判决三个样本各属于哪一类；
(3） 把拒绝判决考虑在内，重新考核三次试验的结果。
表1
类型
损失
判决

1
4

5
1

1
1
解：由题可知：，，,
,
(1)（4分）根据贝叶斯最小误判概率准则知：
，则可以任判；，则判为;，则判为;
（2）（4分）由题可知:
则 ，判为；
，判为；
，判为；
（3）（4分）对于两类问题，对于样本，假设已知，有
则对于第一个样本，
，则拒判；
，则拒判；
，拒判。
1.监督学习与非监督学习的区别:
监督学习方法用来对数据实现分类,分类规则通过训练获得。该训练集由带分类号的数据集组成,因此监督学习方法的训练过程是离线的.
　　非监督学习方法不需要单独的离线训练过程，也没有带分类号（标号)的训练数据集，一般用来对数据集进行分析，如聚类，确定其分布的主分量等。
　　（实例:道路图）就道路图像的分割而言，监督学习方法则先在训练用图像中获取道路象素与非道路象素集，进行分类器设计，然后用所设计的分类器对道路图像进行分割.
使用非监督学习方法，则依据道路路面象素与非道路象素之间的聚类分析进行聚类运算，以实现道路图像的分割.
2。动态聚类是指对当前聚类通过迭代运算改善聚类；
　　分级聚类则是将样本个体，按相似度标准合并，随着相似度要求的降低实现合并。
3。线性分类器三种最优准则：
　　Fisher准则:根据两类样本一般类内密集， 类间分离的特点，寻找线性分类器最佳的法线向量方向，使两类样本在该方向上的投影满足类内尽可能密集，类间尽可能分开。
　　该种度量通过类内离散矩阵Sw和类间离散矩阵Sb实现。
　　感知准则函数：准则函数以使错分类样本到分界面距离之和最小为原则。
　　其优点是通过错分类样本提供的信息对分类器函数进行修正，这种准则是人工神经元网络多层感知器的基础.
　　支持向量机：基本思想是在两类线性可分条件下，所设计的分类器界面使两类之间的间隔为最大, 它的基本出发点是使期望泛化风险尽可能小.
一、 试问“模式”与“模式类”的含义。如果一位姓王的先生是位老年人，试问“王先生”和“老头”谁是模式，谁是模式类？
答:在模式识别学科中，就“模式"与“模式类”而言,模式类是一类事物的代表，概念或典型,而“模式”则是某一事物的具体体现，如“老头”是模式类，而王先生则是“模式”，是“老头”的具体化.
二、 试说明Mahalanobis距离平方的定义，到某点的Mahalanobis距离平方为常数的轨迹的几何意义，它与欧氏距离的区别与联系.
答：Mahalanobis距离的平方定义为：

　　其中x，u为两个数据，是一个正定对称矩阵（一般为协方差矩阵).根据定义,距某一点的Mahalanobis距离相等点的轨迹是超椭球，如果是单位矩阵Σ,则Mahalanobis距离就是通常的欧氏距离。
三、 试说明用监督学习与非监督学习两种方法对道路图像中道路区域的划分的基本做法，以说明这两种学习方法的定义与它们间的区别。
答:监督学习方法用来对数据实现分类,分类规则通过训练获得.该训练集由带分类号的数据集组成,因此监督学习方法的训练过程是离线的.
　　非监督学习方法不需要单独的离线训练过程,也没有带分类号(标号）的训练数据集，一般用来对数据集进行分析，如聚类,确定其分布的主分量等。
　　就道路图像的分割而言，监督学习方法则先在训练用图像中获取道路象素与非道路象素集，进行分类器设计，然后用所设计的分类器对道路图像进行分割.
　　使用非监督学习方法,则依据道路路面象素与非道路象素之间的聚类分析进行聚类运算，以实现道路图像的分割。
四、 试述动态聚类与分级聚类这两种方法的原理与不同。
　答：动态聚类是指对当前聚类通过迭代运算改善聚类；分级聚类则是将样本个体，按相似度标准合并，随着相似度要求的降低实现合并.
五、 如果观察一个时序信号时在离散时刻序列得到的观察量序列表示为，而该时序信号的内在状态序列表示成。如果计算在给定O条件下出现S的概率,试问此概率是何种概率。如果从观察序列来估计状态序列的最大似然估计，这与Bayes决策中基于最小错误率的决策有什么关系.
答:在给定观察序列条件下分析它由某个状态序列S产生的概率似后验概率，写成P（S｜O），而通过O求对状态序列的最大似然估计，与贝叶斯决策的最小错误率决策相当。
六、 已知一组数据的协方差矩阵为，试问
　　1． 协方差矩阵中各元素的含义.
　　2． 求该数组的两个主分量。
　　3． 主分量分析或称K—L变换,它的最佳准则是什么？
　　4． 为什么说经主分量分析后，消除了各分量之间的相关性。
答：协方差矩阵为，则
　　1） 对角元素是各分量的方差，非对角元素是各分量之间的协方差.
　　2) 主分量，通过求协方差矩阵的特征值,用得，则，相应的特征向量为：，对应特征向量为，对应。
这两个特征向量即为主分量。
　　3) K-L变换的最佳准则为：
　　对一组数据进行按一组正交基分解，在只取相同数量分量的条件下,以均方误差计算截尾误差最小。
　　4） 在经主分量分解后，协方差矩阵成为对角矩阵，因而各主分量间相关消除.
七、 试说明以下问题求解是基于监督学习或是非监督学习：
　　1. 求数据集的主分量
　　2。 汉字识别
　　3. 自组织特征映射
　　4。 CT图像的分割
答：1、求数据集的主分量是非监督学习方法;
　　2、汉字识别对待识别字符加上相应类别号—-有监督学习方法；
　　3、自组织特征映射—-将高维数组按保留近似度向低维映射——非监督学习；
　　4、CT图像分割--按数据自然分布聚类—-非监督学习方法;
八、 试列举线性分类器中最著名的三种最佳准则以及它们各自的原理.
答：线性分类器三种最优准则：
　　Fisher准则：根据两类样本一般类内密集, 类间分离的特点，寻找线性分类器最佳的法线向量方向，使两类样本在该方向上的投影满足类内尽可能密集,类间尽可能分开.
　　该种度量通过类内离散矩阵Sw和类间离散矩阵Sb实现。
　　感知准则函数：准则函数以使错分类样本到分界面距离之和最小为原则。
　　其优点是通过错分类样本提供的信息对分类器函数进行修正，这种准则是人工神经元网络多层感知器的基础。
　　支持向量机:基本思想是在两类线性可分条件下，所设计的分类器界面使两类之间的间隔为最大, 它的基本出发点是使期望泛化风险尽可能小.
九、 在一两维特征空间，两类决策域由两条直线H1和H2分界，
　　其中
　　而包含H1与H2的锐角部分为第一类，其余为第二类。
　　试求:
　　1．用一双层感知器构造该分类器
　　2．用凹函数的并构造该分类器
答：按题意要求　　1) H1与H2将空间划分成四个部分，按使H1与H2大于零与小于零表示成四个区域，而第一类属于(－＋）区域,为方便起见，令则第一类在（＋＋）区域.用双层感知器，神经元用域值，则在第一类样本输入时,两隐层结点的输出均为＋1,其余则分别为（＋－)，(――），(－＋）， 故可按图设置域值。　　2） 用凹函数的并表示：或表示成,如,则，否则
十、 设有两类正态分布的样本基于最小错误率的贝叶斯决策分界面，分别为X2=0，以及X1=3，其中两类的协方差矩阵，先验概率相等，并且有, .
　　试求：以及。
答：设待求，待求　　由于,先验概率相等。　　则基于最小错误率的Bayes决策规则，在两类决策面分界面上的样本X应满足（1)　　其中按题意，(注:为方便起见，在下面计算中先去掉系数4/3）。　　按题意分界面由x1=3及x2=0两条直线构成，则分界面方程为 (2）　　对（1)式进行分解有　　得 （3）　　由(3)式第一项得（4）　　将（4)式与（2)式对比可知　　a=1，c=1　　又由c=1与,得b2=1/4，b有两种可能，即b=1/2或b=—1/2,
　　如果b=1/2，则表明,此时分界面方程应为线性，与题意不符，只有b=—1/2
　　则（4）式为:2X1X2　　（5）
　　将相应结果带入（3）式第二项有
　　(6）
　　则结合(5)（2）应有
　　，则 （7)

　　解得,
　　由得
九、证明在Σ正定或半正定时，Mahalanobis距离r符合距离定义的三个条件，即
　　（1）r（a，b）=r（b，a）
　　（2）当且仅当a=b时，有r（a，b)=0
　　（3)r（a，c)≤r(a,b）+r(b,c)
证明：（1) 根据定义（2) 由于Σ为对称阵，故Σ可以分解为，其中，且所有特征值大于等于零。
　　可以认为
这就变为了传统意义上的欧氏距离,可以由欧氏距离满足的性质直接证明本命题。

十、对一副道路图像，希望把道路部分划分出来,可以采用以下两种方法：
1．在该图像中分别在道路部分与非道路部分画出一个窗口,把在这两个窗口中的象素数据作为训练集,用Fisher准则方法求得分类器参数,再用该分类器对整幅图进行分类。
2．将整幅图的每个象素的属性记录在一张数据表中，然后用某种方法将这些数据按它们的自然分布状况划分成两类。因此每个象素就分别得到相应的类别号，从而实现了道路图像的分割。试问以上两种方法哪一种是监督学习，哪个是非监督学习？
答：
第一种方法中标记了两类样本的标号，需要人手工干预训练过程，属于监督学习方法;
第二种方法只是依照数据的自然分布，把它们划分成两类，属于非监督学习方法。
十一、已知有两类数据，分别为

试求:该组数据的类内及类间离散矩阵及.
答：第一类的均值向量为

十二、设一个二维空间中的两类样本服从正态分布，其参数分别为:，,
先验概率，
试证明：其基于最小错误率的贝叶斯决策分界面方程为一圆，并求其方程。
证明:先验概率相等条件下，基于最小错误率贝叶斯决策的分界面上两类条件概率密度函数相等。
　　因此有：

　　化简为，是一个圆的方程.
十三、试分析五种常用决策规则思想方法的异同。
答、五种常用决策是：
1。 基于最小错误率的贝叶斯决策，利用概率论中的贝叶斯公式，得出使得错误率最小的分类规则.
2。 基于最小风险的贝叶斯决策，引入了损失函数，得出使决策风险最小的分类。当在0－1损失函数条件下,基于最小风险的贝叶斯决策变成基于最小错误率的贝叶斯决策.
3。 在限定一类错误率条件下使另一类错误率最小的两类别决策。
4。 最大最小决策：类先验概率未知,考察先验概率变化对错误率的影响，找出使最小贝叶斯奉献最大的先验概率,以这种最坏情况设计分类器。
5。 序贯分类方法，除了考虑分类造成的损失外，还考虑特征获取造成的代价，先用一部分特征分类，然后逐步加入性特征以减少分类损失,同时平衡总的损失，以求得最有效益。
十四、假设在某个地区细胞识别中正常（w1)和异常（w2）两类先验概率分别为 P（w1）=0。9，P(w2）=0。1，现有一待识别的细胞，其观察值为x,从类条件概率密度分布曲线上查得，，并且已知，，，
试对该细胞x用一下两种方法进行分类：
1. 基于最小错误率的贝叶斯决策；
2. 基于最小风险的贝叶斯决策；
请分析两种结果的异同及原因。
答:1。
2.
十五、既然有线性判别函数，为什么还要引进非线性判别函数？试分析由“线性判别函数"向“非线性判别函数"推广的思想和方法.
答:实际中有很多模式识别问题并不是线性可分的,这时就需要采用非线性分类器，比如当两类样本分不具有多峰性质并互相交错时,简单的线性判别函数往往会带来较大的分类错误。这时，树分类器作为一种分段线性分类器，常常能有效地应用于这种情况。
十六、1。 什么是特征选择？
2。 什么是Fisher线性判别?
答：1。 特征选择就是从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的.
2。 Fisher线性判别:可以考虑把d维空间的样本投影到一条直线上,形成一维空间,即把维数压缩到一维，这在数学上容易办到,然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，如果把它们投影到一条任意的直线上，也可能使得几类样本混在一起而变得无法识别。但是在一般情况下，总可以找到某个方向，使得在这个方向的直线上，样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、最易于分类的投影线,这就是Fisher算法所要解决的基本问题。
十七、写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程.
数据获取
预处理
特征提取与选择
分类决策
分类器设计
信号空间
特征空间
十八、请论述模式识别系统的主要组成部分及其设计流程,并简述各组成部分中常用方法的主要思想.
信息获取:通过测量、采样和量化，可以用矩阵或向量表示二维图像或以为波形。
预处理：去除噪声,加强有用的信息，并对输入测量仪器或其他因素造成的退化现象进行复原。
特征选择和提取：为了有效地实现分类识别,就要对原始数据进行变换，得到最能反映分类本质的特征.
分类决策：在特征空间中用统计方法把识别对象归为某一类。
十九、有两类样本集
，，，
，，，
1。 用K—L变换求其二维特征空间，并求出其特征空间的坐标轴；
2。 使用Fisher线性判别方法给出这两类样本的分类面。
二十、定性说明基于参数方法和非参数方法的概率密度估计有什么区别?
答： 基于参数方法：是由已知类别的样本集对总体分布的某些参数进行统计推断
非参数方法：已知样本所属类别,但未知总体概率密度函数形式
二十一、
答：
二十二、简述支持向量机的基本思想.
答：
SVM从线性可分情况下的最优分类面发展而来.
最优分类面就是要求分类线不但能将两类正确分开（训练错误率为0),且使分类间隔最大。
SVM考虑寻找一个满足分类要求的超平面，并且使训练集中的点距离分类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域(margin)最大。
过两类样本中离分类面最近的点,且平行于最优分类面的超平面上H1,H2的训练样本就叫支持向量。
二十三、对于两类问题，假定，,为d维特征向量
请给出以下三种情况下的贝叶斯判别函数，并说明各有什么特点:
1.
2。
3. ,为单位矩阵
答：
1.
2。

判别边界仍是一条直线，但不垂直于均值的连线。
3。

判决平面：

判别边界是一条直线，且垂直于均值的连线。
二十四、设两个家庭,每家3—5人,选每个人的一张照片,共8张,混放在一起,将照片两两对照，得出描述其“相似程度"的模糊关系矩阵。要求按相似程度聚类,希望把二个家庭分开。
第 12 页 共 12 页