模式识别考试.doc

简答题

1. 什么是模式与模式识别
模式识别: 模式识别是研究用计算机来实现人类模式识别能力的一门学科。
模式:模式是一些供模仿用的、完美无缺的标本。
2. 模式识别系统的组成
信息获取，预处理，特征提取和选取，分类器设计，分类决策
3. 什么是后验概率？
系统在某个具体的模式样本X条件下位于某种类型的概率。、
4. 确定线性分类器的主要步骤
采集训练样本，构成训练样本集。样本应该具有典型性
确定一个准则J=J(w,x)，能反映分类器性能，且存在权值w*使得分类器性能最优
设计求解w的最优算法，得到解向量w*
5. 样本集推断总体概率分布的方法？
参数估计
监督参数估计：样本所属类别及类条件总体概率密度函数的形式已知，某些参数未知
非监督参数估计：已知总体概率密度函数形式但未知样本类别，要推断某些参数
非参数估计：已知样本类别，未知总体概率密度函数形式，要求直接推断概率密度函数本身
6. 近邻法的主要思想
作为一种分段线性判别函数的极端情况，将各类中全部样本都作为代表点，这样的决策方法就是近邻法的基本思想。
7. 什么是K近邻法？
他是最近邻法的推广，取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。
8． 监督学习和非监督学习的区别
监督学习的用途明确，就是对样本进行分类。训练样本集给出不同类别的实例，从这些实例中找出区分不同类样本的方法，划定决策面
非监督学习的用途更广泛，用来分析数据的内在规律，如聚类分析，主分量分析，数据拟合等等
9. 什么是误差平法和准则
对于一个给定的聚类，均值向量是最能代表聚类中所有样本的一个向量，也称其为聚类中心。一个好的聚类方法应能使集合中的所有向量与这个均值向量的误差的长度平方和最小。
10. 分级聚类算法有两种基本思路
聚合法：把所有样本各自看为一类，逐级聚合成一类。基本思路是根据类间相似性大小逐级聚合，每级只把相似性最大的两类聚合成一类，最终把所有样本聚合为一类。
分解法：把所有样本看做一类，逐级分解为每个样本一类。
11. 特征抽取和选择的区别
在一定意义上特征抽取和特征选择都是要达到特征降维的目的，只是所实现的途径不同。特征抽取是通过变换的方法组合原始高维特征，获得一组低维的新特征，而特征选择是根据专家的经验知识或根据某种评价准则来挑选出那些对分类最有影响力的特征，并未形成新的特征。
12. 最优搜索算法
最优搜索算法：至今能得到最优解的唯一快速算法是“分支定界”算法。属于自上而下的算法，具有回溯功能。算法核心是通过合理组合搜索过程，避免一些重复计算。关键是利用了判据的单调性。
13. 统计学习理论的核心问题
经验风险最小化原则下统计学习一致性的条件
在这些条件下关于统计学习方法推广性的界的结论
在这些界的基础上建立的小样本归纳推理原则
实现这些新的原则的实际方法
14. 什么是支持向量机？
在统计学习理论基础上发展出的识别方法，在解决小样本、非线性及高维模式识别问题中表现出其优势。

问答题

1. 描述贝叶斯公式及其主要作用。

两个事物X与w联合出现的概率称为联合概率。利用该公式可以计算后验概率。

2. 利用最大似然估计方法对单变量正态分布函数来估计其均值μ和方差σ2。

3. 请详细写出感知器训练算法步骤。
设训练样本集X={x1,x2,…,xn}，其中xk属于wi或者wj，且xk的类别是已知的。为了确定加权向量w*，执行下面的训练算法
a) 给定初始值：置k=0，权向量w(k)为任意值，可选常数0＜c≤1
b) 输入样本xm∈ {x1,x2,…,xn}，计算判决函数值g(xm)=wT(k)xm
c) 按如下规则修改权向量
i. 若xm ∈wi，且g(xm) ≤0，则w(k+1)=w(k)+cxm
ii. 若xm ∈wj，且g(xm) ＞0，则w(k+1)=w(k)-cxm
d) 令k=k+1，返回第二步，直到w对所有样本稳定不变，结束

4. 请详细写出Fisher算法实现步骤。
• 在两类问题中，设分别属于wi与wj的样本数为n1与n2，n= n1+n2
• 令yk=wTxk(k=1,2,…,n)，由子集X1与X2映射后的两个子集为Y1与Y2。
• 使Y1与Y2最容易区分开的w方向正好是分类超平面的法线方向。
• 定义Fisher准则函数。使得JF最大的解w*就是最佳解向量
• 以上工作是将d维空间的样本映射到了一维样本集，这个一维空间的方向是相对于Fisher准则为最好的。
• 我们还需要解决分类问题。将d维分类问题转化为一维分类问题后，只需要确定一个阈值点，将投影点与阈值点比较，就可以做出决策。

5. 什么是两分剪辑近邻法与压缩近邻法。
将原始样本随机分为两个集合：预测集T和参考集R，来自预测集和参考集的样本分别完成考试和参考任务，相互独立。
对预测集T中的所有样本，利用参考集采用近邻法对其进行分类决策，如果决策结果与实际类别不同，则从预测集中删除该样本，最后得到经过剪辑的考试样本集TE。
利用考试样本集TE，采用最近邻法对测试样本进行分类决策。

剪辑近邻的结果只是去掉了两类边界附近的样本，而靠近两类中心的样本几乎没有被去掉。在剪辑的基础上，再去掉一部分这样的样本，有助于进一步缩短计算时间和降低存储要求。这类方法叫作压缩近邻法。

6. 请详细介绍初始聚类中心的选择方法。
任取前c个样本点作为初始聚类中心
凭经验选择
将全部数据随机分为c类，计算其重心，将重心作为聚类中心
密度法选择代表点（具有统计特性）
从c-1类划分中产生c类划分问题的初始聚类中心

7. 请描述K均值聚类算法。
a) 给定允许误差ℇ，令t=1
b) 初始化聚类中心wi(t)，i=1,2,…,c
c) 修正dij，
d) 修正聚类中心wi(t+1)
e) 计算误差E或者Je
f) 如果E< ℇ ，则算法结束；否则t=t+1，转步骤3

8. 什么是离散K-L变换以及离散有限K-L展开。
一个非周期性随机过程不能用具有互不相关的随机傅立叶系数的傅立叶级数表示，但是可以用具有互不相关系数的正交函数的级数展开。K-L展开式就是这样一种展开方法。
设X是一个n维的随机向量，它可以用下式展开

9. 必考：针对某个识别对象设计自己的模式识别系统，并叙述各步骤主要工作。
指纹识别技术举例
• 指纹图像的提取（获取数字图像）
• 图像的预处理（滤波、去噪、二值化、增强）
• 指纹特征分析（分析哪些特征可以表示指纹）
• 指纹特征提取（从图像中提取特征）
• 特征的识别（采用分类方法进行类别判断）

计算题
1、 在图像识别中，假定有灌木和坦克2种类型，它们的先验概率分别是0.7和0.3，损失函数如下表所示。其中，类型w1和w2分别表示灌木和坦克，判决a1=w1，a2=w2。现在做了2次实验，获得2个样本的类概率密度如下：
状态
损失
决策
W1
W2
a1
0.5
2
a2
4
1.0

（1）试用最小错误率贝叶斯准则判决2个样本各属于哪一类？坦克、灌木。
（2）试用最小风险决策规则判决2个样本各属于哪一类？灌木、灌木。
答：（1）最小错误率贝叶斯准则

（2）最小风险决策规则

2、 给出二维样本数据(-1,1),(2,2),(1,-1),(-2,-2)，试用K-L变换作一维数据压缩。
答：数据压缩结果：0，，0，

3、 已知两类的数据：ω1：(1,0),(2,0),(1,1)；ω2：(-1,0),(0,1),(-1,1)，试求该组数据的类内与类间散布矩阵。

4、已知欧氏二维空间中两类9个训练样本w1:(-1,0)T,(-2,0)T,(-2,1)T,(-2,-1)T
w2:(1,1)T,(2,0)T,(1,-1)T,(2,1)T,(2,2)T，试分别用最近邻法和K近邻法求测试样本(0,0)T的分类，取K=5，7。
答：
最近邻法：最近邻为(-1，0)T分类为w1
K近邻法：
K=5：5个近邻为1类的(-1,0)T,(-2,0)T，2类的(1,1)T,(2,0)T,(1,-1)T 分类为w2
K=7：1）若近邻为1类的(-1,0)T,(-2,0)T,(-2,1)T,(-2,-1)T，2类的(1,1)T,(2,0)T,(1,-1)T，则分类为w1
2）若近邻为1类的(-1,0)T,(-2,0)T,(-2,1)T或(-2,-1)T两个之一，2类的(1,1)T,(2,0)T,(1,-1)T,(2,1)T，则分类为w2
5.已知两类的训练样本：W1(0,0)T,(0,1)T,W2(1,0)T,(1,1)T,试用最小平方误差准则算法进行分类器训练，求解向量W*。