模式识别期末练习题.pdf

2013 模式识别练习题 一 . 填空题 1、模式识别系统的基本构成单元包括： 模式采集 、 特征选择与提取 和 模式分类 。 2、统计模式识别中描述模式的方法一般使用 特征矢量 ；句法模式识别中模式描述方法一般有 串 、 树 、 网 。 3、 影响层次聚类算法结果的主要因素有 计算模式距离的测度、聚类准则、类间距离 阈值 、预定的类别 数目 。 4、线性判别函数的正负和数值大小的几何意义是 正（负）表示样本点位于判别界面法向量指向的正 （负） 半空间中；绝对值正比于样本点到判别界面的距离 。 5、 感知器算法 1 ， H-K 算法 （ 2） 。 （ 1）只适用于线性可分的情况；（ 2）线性可分、不可分都适用。 6、在统计模式分类问题中，聂曼 -皮尔逊判决准则主要用于 某一种判决错误较另一种判决错误更为重 要 情况；最小最大判 别 准则主要用于 先验概率未知的 情况。 7、 “特征个数越多越有利于分类 ”这种说法正确吗？ 错误 。 特征选择的主要目的是 从 n 个特征中选出最有利于分类的的 m 个特征（ mn ）的条件下，可以使用分支定界法以减少 计算量。 8、 散度 Jij越大，说明 i类模式与 j类模式的分布 差别越大 ； 当 i类模式与 j类模式的分布相同时， Jij= 0 。 二、 选择题 1、影响聚类算法结果的主要因素有（ B C D ）。 A.已知类别的样本质量； B.分类准则； C.特征选取； D.模式相似性测度 2、模式识别中，马式距离较之于欧式距离的优点是（ C D ）。 A.平移不变性； B.旋转不变性； C 尺度不变性； D.考虑了模式的分布 3、 影响基本 K-均 值算法的主要因素有（ D A B ）。 A.样本输入顺序； B.模式相似性测度； C.聚类准则； D.初始类中 心的选取 4、位势函数法的积累势函数 K(x)的作用相当于 Bayes 判决中的（ B D ）。 A. 先验概率； B. 后验概率； C. 类概率密度； D. 类概率密度与先验概率的乘积 5、在统计模式分类问题中，当先验概率未知时，可以使用（ B D ）。 A. 最小损失准则； B. 最小最大损失准则； C. 最小误判概率准则； D. N-P 判决 6、散度 JD是根据（ C ）构造的可分性判据。 A. 先验概率； B. 后验概率； C. 类概率密度； D. 信息熵； E. 几何距离 7、似然函数的概型已知且为单峰，则可用（ A B C D E）估计该似然函数。 A. 矩估计； B. 最大似然估计； C. Bayes 估计； D. Bayes 学习； E. Parzen 窗法 8、 KN 近邻元法较之 Parzen 窗法的优点是（ B ）。 A. 所需样本数较少； B. 稳定性较好； C. 分辨率较高； D. 连续性较好 9、从分类的角度讲，用 DKLT 做特征提取主要利用了 DKLT 的性质：（ A C ）。 A.变换产生的新分 量正交或不相关； B.以部分新的分量表示原矢量均方误差最小； C.使变换后的矢 量能量更集中 10、如果以特征向量的相关系数作为模式相似性测度，则影响聚类算法结果的主要因素有（ B C ）。 A. 已知类别样本质量； B. 分类准则； C. 特征选取； D. 量纲 11、欧式距离具有（ A B ）；马式距离具有（ A B C D ）。 A. 平移不变性； B. 旋转不变性； C. 尺度缩放不变性； D. 不受量纲影响的特性 12、聚类分析算法属于（ A ）；判别域代数界面方程法属于（ C ） 。 A.无监督分类； B.有监督分类； C.统计模式识别方法； D.句法模式识别方法 13、若描述模式的特征量为 0-1 二值特征量，则一般采用（ D ）进行相似性度量。 A. 距离测度； B. 模糊测度； C. 相似测度； D. 匹配测度 14、 下列函数可以作为聚类分析中的准则函数的有（ A C D ） 。 A. 1 BW SSTrJ ； B. 1 BWSSJ ； C. c j n i j jij mxJ 1 1 2)( ； D. )()( 1 mmmmJ j c j j 15、 Fisher 线性判别函数的求解过程是将 N 维特征矢量投影在（ B ）中进行 。 A.二维空间； B.一维空间； C. N-1 维空间 16、 用 parzen 窗法估计类概率密度函数时，窗宽过窄导致波动过大的原因是（ B、 C ）。 A.窗函数幅度过小； B.窗函数幅度过大； C. 窗口中落入的样本数过少； D.窗口中落入的样本数过多。 17、如下聚类算法中，属于静态聚类算法的是 ( A、 B )。 A. 最大最小距离聚类 ； B. 层次聚类； C. c-均值聚类。 18、 一般， k-NN 最近邻方法在（ B ）的情况下效果较好。 A.样本较多但典型性不好； B.样本较少但典型性好； C.样本呈团状分布； D.样本呈链状分布 19、影响 c 均值聚类算法效果的主要因素之一是初始类心的选取，相比较而言，（ C ） c 个样本作为初 始类心较好。 A. 按输入顺序选前； B. 选相距最远的； C. 选分布密度最高处的； D. 随机挑选。 20、类域界面方程法中，能求线性不可分情况下分类问题近似或精确解的方法是（ B、 C、 D ）。 A. 感知器算法； B. 伪逆法； C. 基于二次准则的 H-K 算法； D. 势函数法。 三、 简 答 题 1、 试说明 Mahalanobis 距离平方的定义，到某点的 Mahalanobis 距离平方为常数的轨迹的 几何意义，它与欧氏距离的区别与联系。 答： Mahalanobis 距离的平方定义为： 12 )()(),( uxuxuxr T 其中 x， u 为两个数据， 1 是一个正定对称矩阵（一般为协方差矩阵）。根据定义，距 某一点的 Mahalanobis 距离相等点的轨迹是超椭球， 如果是单位矩阵 ， 则 Mahalanobis 距离就是通常的欧氏距离。 2、 试说明用监督学习与非监督学习两种方法对道路图像中道路区域的划分的基本做法，以 说明这两种学习方法的定义与它们间的区别。 答： 监督学习方法用来对数据实现分类，分类规则通过训练获得。该训练集由带分类 号的数据集组成，因此监督学习方法的训练过程是离线的。 非监督学习方法不需要单独的离线训练过程，也没有带分类号（标号）的训练数据集， 一般用来对数据集进行分析，如聚类，确定其分布的主分量等。 就道路图像的分割而言，监督学习方法则先在训 练用图像中获取道路象素与非道路象 素集，进行分类器设计，然后用所设计的分类器对道路图像进行分割。 使用非监督学习方法，则依据道路路面象素与非道路象素之间的聚类分析进行聚类运 算，以实现道路图像的分割。 3、 已知一组数据的协方差矩阵为 12/1 2/11 ，试问 (1) 协方差矩阵中各元素的含义。 (2) 求该数组的两个主分量。 (3) 主分量分析或称 K-L 变换，它的最佳准则是什么？ (4) 为什么说经主分量分析后，消除了各分量之间的相关性。 答： 协方差矩阵为 12/1 2/11 ，则 (1) 对角元素是各分量的方差，非对角元素是各分量之间的协方差。 (2) 主分量，通过求协方差矩阵的特征值，用 121 2 11 0 得 4/1)1( 2 ，则 2/3 2/1 ，相应 地 ： 2/3 ，对应特征向量为 11 ， 21 ，对应 11 。 这两个特征向量 ， 即为主分量。 (3) K-L 变换的最佳准则为： 对一组数据进行按一组正交基分解，在只取相同数量分量的条件下，以均方误差计算 截尾误差最小。 (4) 在经主分量分解后，协方差矩阵成为对角矩阵，因而各主分量间相关 性 消除。 4、 试说明以下问题求解是基于监督学习或是非监督学习： (1) 求数据集的主分量 (2) 汉字识别 (3) 自组织特征映射 (4) CT 图像的分割 答： (1) 求数据集的主分量是非监督学习方法； (2) 汉字识别 ： 对待识别字符加上相应类别号 有监督学习方法； (3) 自组织特征映射 将高维数组按保留近似度向低维映射 非监督学习； (4) CT 图像分割 按数据自然分布聚类 非监督学习方法； 5、 试列举线性分类器中最著名的三种最佳准则以及它们各自的原理。 答： 线性分类器三种最优准则： Fisher 准则 ：根据两类样本一般类内密集 ， 类间分离的特点，寻找线性分类器最佳的法线 向量方向，使两类样本在该方向上的投影满足类内尽可能密集，类间尽可能分开。 这 种度量通过类内离散矩阵 Sw 和类间离散矩阵 Sb 实现。 感知准则函数 ：准则函数以使错分类样本到分界面距离之和最小为原则。 其优点是通过错分 类样本提供的信息对分类器函数进行修正 ， 这种准则是人工神经元 网络多层感知器的基础。 支持向量机 ：基本思想是在两类线性可分条件下 ， 所设计的分类器界面使两类之间的 间隔为最大 ， 它的基本出发点是使期望泛化风险尽可能小。 6、 试分析五种常用决策规则思想方法的异同。 答、五种常用决策是： 1. 基于最小错误率的贝叶斯决策 ，利用概率论中的贝叶斯公式，得出使得错误率最小 的分类规则。 2. 基于最小风险的贝叶斯决策 ，引入了损失函数，得出使决策风险最小的分类。当在 0-1 损失函数条件下，基于最小风险的贝叶斯决策变成 基于最小错误率的贝叶斯决 策。 3. 在限定一类错误率条件下使另一类错误率最小的两类别决策。 4. 最大最小决策： 类先验概率未知，考察先验概率变化对错误率的影响，找出使最小 贝叶斯奉献最大的先验概率，以这种最坏情况设计分类器。 5. 序贯分类方法 ，除了考虑分类造成的损失外，还考虑特征获取造成的代价，先用一 部分特征分类，然后逐步加入性特征以减少分类损失，同时平衡总的损失，以求得 最有效益。 7、 1. 什么是特征选择？ 2. 什么是 Fisher 线性判别？ 答： 1. 特征选择就是从一组特征中 挑选出一些最有效的特征以达到降低特征空间维数的目 的。 2. Fisher 线性判别：可以考虑把 d 维空间的样本投影到一条直线上，形成一维空间， 即把维数压缩到一维，这在数学上容易办到，然而，即使样本在 d 维空间里形成若干紧凑 的互相分得开的集群，如果把它们投影到一条任意的直线上，也可能使得几类样本混在一 起而变得无法识别。但是在一般情况下，总可以找到某个方向，使得在这个方向的直线上， 样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、最易于分类的投影 线，这就是 Fisher 算法所要解决的基本问题。 8、 写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。 两类问题：判别函数 )()()( 2121111 xwpxwpxg )()()( 2221212 xwpxwpxg 决策面方程： )()( 21 xgxg C 类问题：判别函数 )()( 1 xwpxg jij c ji ， ci ,.2,1 决策面方程： )()( xgxg ji ， ji ， ci ,.2,1 ， cj ,.2,1 9、 请论述模式识别系统的主要组成部分及其设计流程，并简述各组成部分中常用方法的主 要思想。 信息获取 ：通过测量、采样和量化，可以用矩阵或向量表示二维图像或波形。 预处理： 去除噪声，加强有用的信息，并对输入测量仪器或其他因素造成的退化现象进 行复原。 特征选择和提取： 为了有效地实现分类识别，就要对原始数据进行变换，得到最能反映 分类本质的特征。 分类决策： 在特征空间中用统计方法把识别对象归为某一类。 10、 简述支持向量机的基本思想。 答： SVM 从线性可分情况下的最 优分类面发展而来。 最优分类面就是要求分类线不但能将两类正确分开 (训练错误率为 0)，且使分类间隔 最大。 SVM 考虑寻找一个满足分类要求的超平面，并且使训练集中的点距离分类面尽可能 的远，也就是寻找一个分类面使它两侧的空白区域 (margin)最大。 过两类样本中离分类面最近的点，且平行于最优分类面的超平面上 H1， H2的训练样 本就叫支持向量。 四、计算题 1、 设两类样本的类内 散布 矩阵分别为 11,11 21 2 1 221 2 1 1 SS ， 两类的类心分别为 m1=(2,0)T, m2=(2,2)T, 试用 fisher 准则求其决策面方程。 数数 据据 获获 取取 预预 处处 理理 特特 征征 提提 取取 与与 选选 择择 分分 类类 决决 策策 分分 类类 器器 设设 计计 信号空间 特征空间 解： 10 01)( 2121 SSS w ， 10 011wS 22)1,2(10 01)2,0()()()( 2212121 21 xxxxSmmxd TmmwT 2 10)( xxd 或 写出决策面方程 01)( 2 xxd 2、 已知两个一维模式类别的类概率密度函数为 : 其它 21 10 0 2)/( 1 xxxxxp 其它 32 21 0 3 1 )/( 2 xxxxxp 先验概率 P(1)=0.6， P(2)=0.4， （ 1）求 0-1 代价 Bayes 判决函数； （ 2）求总错误概率 P(e)； （ 3）判断样本 x1=1.35, x2=1.45, x3=1.55, x4=1.65 各属于哪一类别。 答： (1) 基于 0-1 代价 Bayes 判决函数为： 当 67.0 326.0 4.0)( )()|( )|( 1221 PPxp xp 时， 1wx ，否则 2wx ， (2) 总的误判概率 P(e)为： 由 3212 x x ， 得： 6.158x 1 2 3 x 概率密度 )|()( 11 xpP )|()( 22 xpP |x3-Z20|=2，所以 x32 因为 |x4-Z10|=81/2|x4-Z20|=51/2，所以 x42 x52, x61 由此得到新的类： 1=x1, x6 N1=2, 2=x2, x3, x4, x5 N2=4 第三步：根据新分成的两类计算新的聚类中心 Z11=(x1+x6)/2=(0.5, 0)T Z21=(x2+x3+x4+x5)/4=(1.75, 2.25)T 第四步：因为新旧聚类中心不等，转第二步 第二步：重新计算 x1, x2, x3, x4, x5, x6到 Z11、 Z12的距离，把它们归为最近聚类中心 ，重 新分为两类 1=x1, x2, x6 N1=3, 2=x3, x4, x5 N2=3 第三步：根据新分成的两类计算新的聚类中心 Z12=(x1+x2+x6)/3=(1/3, 1/3)T Z22=(x3+x4+x5)/3=(7/3, 8/3)T 第四步：因为新旧聚类中心不等，转第二步 重新计算 x1, x2, x3, x4, x5, x6到 Z12、 Z22的距离，把它们归为最近聚类中心，重新分 为两类 1=x1, x2, x6， N1=3, 1=x3, x4, x5 ， N2=3 和上次 聚类结果一样，计算结束。 7、 已知二维样本： 1x =(-1,0)T， 2x =(0,-1)T， 3x =(0,0)T， 4x =(2,0)T和 5x =(0,2)T， 121 , xx ， 2543 , xxx 。试用感知器算法求出分类决策函数，并判断 6x =(2,1) T属于哪一类？ 答： 将样本符号规范化得： 1x =(-1,0,1) T， 2x =(0,-1,1) T， 3x =(0,0,-1) T， 4x =(-2,0,-1) T和 5x =(0,-2,-1) T， 赋初值 Tw )1 ,1 ,1()1( ，取增量 1 , 置迭代步数 k=1, 则有： k=1, 1xxk , 0)()( kTk xkwxd , Txww )2 ,1 ,0()1()2( 1 k=2, 2xxk , 01)()( kTk xkwxd , )2()3( ww k=3, 3xxk , 02)()( kTk xkwxd , Txww )1 ,1 ,0()3()4( 3 k=4, 4xxk , 01)()( kTk xkwxd , Txww )0 ,1 ,2()4()5( 4 k=5, 5xxk , 02)()( kTk xkwxd , Txww )1 ,1 ,2()5()6( 5 k=6, 1xxk , 01)()( kTk xkwxd , )6()7( ww k=7, 2xxk , 0)()( kTk xkwxd , Txww )0 ,2 ,2()7()8( 2 k=8, 3xxk , 0)()( kTk xkwxd , Txww )1 ,2 ,2()8()9( 3 k=9, 4xxk , 05)()( kTk xkwxd , )9()10( ww k=10, 5xxk , 05)()( kTk xkwxd , )10()11( ww k=11, 1xxk , 01)()( kTk xkwxd , )11()12( ww k=12, 2xxk , 05)()( kTk xkwxd , )12()13( ww k=13, 3xxk , 05)()( kTk xkwxd , )13()14( ww 所以， 最后收敛于 Tw )1 ,2 ,2( , 分类决策函数为 122)( 21 xxxd 将 Tx )1 ,2(6 代入决策函数， 07)( xd , 所以 26 x 8、 两 类样本的均值矢量分别为 m1=(4, 2)T 和 m2=(- 4,-2)T， 协方差矩阵分别为： 31 131C , 42 242C , 两类的先验概率相等， 试求一维特征提取矩阵。 特征的选择与提取 84 页 ppt 9、设语言 L(G)的正样本集 111 ,101R ，试推断出余码文法 Gc。 句法模式识别 ppt 32 页