中科院-模式识别考题总结(详细答案)

1. 简述模式的概念及其直观特性，模式识别的分类，有哪几种方法。（6’）

答（1）：什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。

模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。

模式的直观特性：可观察性；可区分性；相似性。 答（2）：模式识别的分类：

假说的两种获得方法（模式识别进行学习的两种方法）：  监督学习、概念驱动或归纳假说；  非监督学习、数据驱动或演绎假说。 模式分类的主要方法：  数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据

集。是一种非监督学习的方法，解决方案是数据驱动的。

 统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。

特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法，分类器是概念驱动的。  结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目

的。（句法模式识别）

 神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以

在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。

2. 什么是神经网络？有什么主要特点？选择神经网络模式应该考虑什么因素？（8’）

答（1）：所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。

人工神经网络的两种操作过程：训练学习、正常操作（回忆操作）。 答（2）：人工神经网络的特点：  固有的并行结构和并行处理；  知识的分布存储；  有较强的容错性；  有一定的自适应性； 人工神经网络的局限性：

 人工神经网络不适于高精度的计算；

 人工神经网络不适于做类似顺序计数的工作；

 人工神经网络的学习和训练往往是一个艰难的过程；  人工神经网络必须克服时间域顺序处理方面的困难；  硬件；

 正确的训练数据的收集。 答（3）：选取人工神经网络模型，要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：

.................

    

网络大小；

所需输出类型； 联想记忆类型； 训练方法； 时间的限定。 3. 画出句法模式识别的框图，并解释其工作原理。（8’）

答（1）：句法模式识别框图如下：

答（2）：句法模式识别系统的组成：图像预处理，图像分割，基元及其关系识别，句法分析。

基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。

因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。

句法模式识别系统处理过程：基元本身包含的结构信息已不多，仅需少量特征即可识别。如果用有限个字符代表不同的基元，则由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表。假如事先用形式语言的规则从字符串中推断出能生成它的文法，则可以通过句法分析，按给定的句法（文法）来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所能描述的模式类，达到分类的目的。

4. （1）解释线性判别函数进行模式分类的概念；（2）既然有了线性判别函数，为什么还要用非线性判别函数进行模式分类？（3）两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）（8’）

答（1）：模式识别系统的主要作用是判别各个模式所属的类别。线性判别函数分类就是使用线性判别函数将多类样本模式分开。

一个n维线性判别函数的一般形式：

d(x)w1x1w2x2wnxnwn1w0xwn1

TTT其中w0(w1,w2,...,wn)称为权向量（或参数向量），x(x1,x2,...,xn)。

d(x)也可表示为：d(x)wTx

TT其中，x(x1,x2,...,xn,1)称为增广模式向量，w0(w1,w2,...,wn,wn1)称为增广权

.................

向量。

两类情况：判别函数d(x)：

0ifx1d(x)wx

0ifx2T多类情况：设模式可分成1,2,...,M共M类，则有三种划分方法：  多类情况1

用线性判别函数将属于i类的模式与不属于i类的模式分开，其判别函数为：

0ifxidi(x)wx

0ifxiTi这种情况称为i/i两分法，即把M类多类问题分成M个两类问题，因此共有M个判别函数，对应的判别函数的权向量为wi,i1,2,...,n1。

 多类情况2

采用每对划分，即i|j两分法，此时一个判别界面只能分开两种类别，但不能把它与其余所有的界面分开。

其判别函数为：dij(x)wijx若dij(x)0，ji，则xi 重要性质：dijdji

要分开M类模式，共需M(M-1)/2个判别函数。

不确定区域：若所有dij(x)，找不到ji，dij(x)0的情况。  多类情况3（多类情况2的特例）

这是没有不确定区域的i|j两分法。假若多类情况2中的dij可分解成：

Tdij(x)di(x)dj(x)(wiwj)Tx，则dij0相当于di(x)dj(x)，ji。这时

不存在不确定区域。此时，对M类情况应有M个判别函数：

dk(x)wkx,k1,2,T,M

即di(x)dj(x)，ji，i,j1,2,...M，则

xi，也可写成，若

di(x)max{dk(x),k1,2,...,M}，则xi。

该分类的特点是把M类情况分成M-1个两类问题。 模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。一旦线性函数的系数wk被确定，这些函数就可用作模式分类的基础。

.................

对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。

采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。

由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。

答（2）广义线性判别函数出发点：  线性判别函数简单，容易实现；  非线性判别函数复杂，不容易实现；

 若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。

采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。所以某些情况下使用非线性判别函数或分段线性判别函数效果更好。

解（3）假设该两类模式是线性可分的，则在三维空间中一个线性平面可以将这两类模式分开，所以判别函数可以写成：

d(x)w1xw2xw3xw4

所以权向量需要4个系数。

对于n维x向量，采用r次多项式，d(x)的权系数w的项数为：

当r=2，n=3时，

rNwCnr(nr)! r!n!NW(n2)!(n2)(n1)10 2!n!2所以，此时权向量需要10个系数分量。

5. 设一有限态自动机A({0,1},{q0,q1,q2},,q0,q2}，定义如下：

(q0,0)q2,(q1,0)q2,(q2,0)q2

(q0,1)q1,(q1,1)q0,(q2,1)q1试求等价的正则文法，使得L(G)=T(A)。（10’）

.................

VT{0,1}，Sq0 解：设由A得一正则文法G(VN,VT,P，S)，则VN{S,x1,x2}，

1x1 由(q0,1)q1，得生成式S0,S0x2 由(q0,0)q2，得生成式S1S 由(q1,1)q0，得生成式x10,x10x2 由(q1,0)q2，得生成式x11x1 由(q2,1)q1，得生成式x20,x20x2 由(q2,0)q2，得生成式x2对比实例：当扫描字符串1110时，A按以下状态序列接受该字符串

1110q0q1q0q1q2

用对应的正则文法G推导，得：

S1x111S111x11110

 按有限态自动机确定正则文法

给定一个有限态自动机A(,Q,,q0,F)，可确定一个正则文法G(VN,VT,P,S)，使得L(G) = T(A)。

由Q{q0,q1,...,qn,qn1},qn1F ，可确定：VN{S,x1,x2,...,xn,xn1}，Sq0，

xiqi，VT。

从求G中的生成式P可按如下原则： (1) 若(qi,a)qj，则xiaxj

(2) 若(qi,a)qn1，则xia,xiaxn1

6. K-均值算法聚类：K=2，初始聚类中心为x1,x2，数据为：（10’）

{x1(0,0),x2(1,0),x3(0,1),x4(1,1),x5(8,7)x6(9,7),x7(8,8),x8(9,8),x9(8,9),x10(9,9)}算法：

第一步：选K个初始聚类中心，z1(1),z2(1),...,zk(1)，其中括号内的序号为寻找聚类中

心的迭代运算的次序号。可选开始的K 个模式样本的向量值作为初始聚类中

心。

.................

第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个

zj(1)。即Dj(k)min{xzi(k),i1,2,K}，则xSj(k)，其中k 为

迭代运算的次序号，第一次迭代k1，Sj表示第j个聚类，其聚类中心为zj。

第三步：计算各个聚类中心的新的向量值，zj(k1),j1,2,...,K

求各聚类域中所包含样本的均值向量：

zj(k1)1NjxSj(k)x,j1,2,,K

其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：

JjxSj(k)xzj(k1),2j1,2,,K

在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算

法。

第四步：若zj(k1)zj(k)，则返回第二步，将模式样本逐个重新分类，重复迭代

运算；

若zj(k1)zj(k)，则算法收敛，计算结束。

7. 给出两类模式分布，每一列代表一个样本：

554561 ：x1

545655562 ：x2

565试用K-L变换来做一维特征的提取（12’）。

解：首先将所有样本看作一个整体，求出样本均值向量：

1515mx1jx2j0

5j15j1由于均值为0，符合K-L变换的最佳条件。如果均值不为0，则所有样本要减去均值向量。由于1和2的样本数相同，所以认为他们的先验概率相同，即：

P(1)P(2)0.5

求出总体的自相关矩阵R或协方差矩阵C：

.................

25.425RP(i)E{xixiT}

i12525.42解特征方程RI0，求出R的特征值：

150.4,20.4

求出对应于特征值的特征向量Riii：

11111,2 2121T选取1对应的特征向量作为变换矩阵，由yx得出变换后的一维模式：

101 ：x1'2102 ：x2'21129211292921111 229 2

8. 用第二类势函数的算法进行分类（10’）

选择指数型势函数，取α=1，在二维情况下势函数为：

K(x,xk)exxk2e[(x1xk1)2(x2xk2)2]

这里：ω1类为x①=(0 0)T, x②=(2 0)T；ω2类为x③=(1 1)T, x④=(1 -1)T

解：可以看出，这两类模式是线性不可分的。算法步骤如下： 第一步：取x(1)(0,0)1 ，则

TK1(x)K(x,x(1))exp{[(x10)2(x20)2]}exp[(x12x22)]

第二步：取x(2)(2,0)1

因exp[(40)]exp(4)0，

22故K2(x)K1(x)exp[(x1x2)]

T第三步：取x(3)(1,1)2

因exp[(11)]exp(2)0， 故

TK3(x)K2(x)K(x,x(3))exp[(x12x22)]exp{[(x11)2(x21)2]}

.................

……

后面同理，就是不断将样本带入，如果分类正确，则势函数保持不变，即：

Kk1(x)Kk(x)

如果分类错误，则有两种情况：  

x(k1)1,Kk(x(k1))0，则Kk1(x)Kk(x)K(x,x(k1))

x(k1)2,Kk(x(k1))0，则Kk1(x)Kk(x)K(x,x(k1))

经过迭代，全部模式都已正确分类，因此算法收敛于判别函数。 得出：d(x)e22(x1x2)e[(x11)2(x21)2]e[(x11)2(x21)2]e2[(x12)2x2]

9. 有一种病，正常为1 ，不正常为2 ，已知：

P(1)0.9,P(2)0.1

现对某人进行检查，结果为x，由概率曲线查出：

P(x|1)0.2,P(x|2)0.4

风险代价矩阵为：

LL11L21L1206 L2210对该检查者进行判决：

（1） 用贝叶斯最小错误概率判别，求出判决函数和决策分界面。 （2） 用贝叶斯最小风险判别，求出判别函数和决策分界面。

解（1）： 由于

P(1|x)P(1)P(x|1)P(2|x)P(2)P(x|2)

lP(x|1)1P(2)1

P(x|2)2P(1)9所以x1。 解（2）： 由于

rj(x)LijP(x|i)P(i),j1,2

i12l'P(x|1)1P(2)L21L221

P(x|2)2P(1)L12L11.................

所以x1。

10. 阐述误差反传算法（BP算法）的原理，并写出其训练步骤。

答（1）：

 BP算法推算过程：

当加入第k个输入时，隐蔽层h结点的输入加权和为：

kshwihxik

i如果令第一层的加权矩阵为W1 ，则还可以表示为：

相应节点的输出为：

kkyhF(sh)F(wihxik)

ikshW1Txk

写成矩阵形式为：

kkyhF(sh)F(W1Txk)

同样，输出层j结点的输入加权和为：

kkskwywF(wxhjhhjihi) jhhi令第二次的加权矩阵为W2，则可以写成：

相应点的输出：

kkkykjF(sj)F(whjyh)F[whjF(wihxi)]

hhiTkTTkskjW2yhW2F(W1x)

写成矩阵形式为：

.................

TTkykjF(W2F(W1x))

这里，各结点的阈值等效为一个连接的加权w0h或w0j，这些连接由各结点连到具有固定值-1的偏置结点，其连接加权也是可调的，同其它加权一样参与调节过程。

误差函数为：

E(W)11kk2kk2(Ty){TF[wF(wx)]} jjjhjihi2k,j2k,jhi为了使误差函数最小，用梯度下降法求得最优的加权，权值先从输出层开始修正，然

后依次修正前层权值，因此含有反传的含义。根据梯度下降法，由隐蔽层到输出层的连接的加权调节量为：

whjEkkkk(Tjkyk)F(s)yjjhjyh

whjkk其中jk为输出结点的误差信号：

kkkkjkF(sk)(Ty)F(s)jjjjj

kjTjkykj

在BP算法中常采用Sigmoid函数：yF(s)其导数为：F'(s)F(s)(1F(s))y(1y) 对应的误差为：jkkkkykj(1yj)(Tjyj)

11es

对于输入层到隐蔽层结点连接的加权修正量wih，必须考虑将E(W)对wih求导，因此利用分层链路法，有：

kEEyhkkkwihk{(Tjkykj)F(sj)whjF(sh)xi}wihkyhwihk,jwhjF(s)xxkjkhkik,jkkkhi

其中：

kkkhkF(sh)whjjkF(sh)h

jkkwhjj hj这样就可以根据whj和wih分别调整输出层和隐层的权值了。  BP训练算法实现步骤

.................

准备：设网络具有m层，yj表示第m层中第j个结点的输出，yj（零层输出）等于xj，即第j个输入。wij表示从yimm1m0到

ym这里，m代表层号，而不是向量的类号。 j的连接加权。

1.（初始化加权矩阵）将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。

2.（输入数据）从训练数据组中选一数据对(x,T)，将输入向量加到输入层（m=0），

0k使得对所有端点i：yixi，k表示向量类号。

kk3.（输出预测数据）信号通过网络向前传播，即利用关系式：

mmm1ymF(s)F(w) jjijyii计算从第一层开始的各层内每个结点i的输出yj，直到输出层的每个结点的输出计算完为止。

4.（计算输出层误差）计算输出层每个结点的误差值，对Sigmod函数：

kmmmkmjmF(smj)(Tjyj)yj(1yj)(Tjyj)

m它是由实际输出和要求目标值之差获得。

5.（误差反传）计算前面各层各结点的误差值

1jm1F(sm)wjiim ji这里逐层计算反传误差，直到将每层内每个结点的误差值算出为止。

6.（修改权值）利用加权修正公式：

mwijjmyim1 newoldwijwijwij

修正所有连接权。一般0.01~1，称为训练速率系数。

7.（运算至权值收敛）返回第2步，为下一个输入向量重复上述步骤，直至网络收敛。

.................