模式识别复习重点总结.doc

1.什么是模式及模式识别？模式识别的应用领域主要有哪些？
模式：存在于时间，空间中可观察的事物，具有时间或空间分布的信息；
模式识别：用计算机实现人对各种事物或现象的分析,描述,判断,识别。
模式识别的应用领域：（1）字符识别；（2） 医疗诊断；（3）遥感；
(4）指纹识别 脸形识别；（5）检测污染分析，大气，水源，环境监测；
（6）自动检测；（7 ）语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断；
（8）军事应用。

2.模式识别系统的基本组成是什么？
（1） 信息的获取：是通过传感器，将光或声音等信息转化为电信息；
（2） 预处理：包括A\D,二值化，图象的平滑，变换，增强，恢复，滤波等, 主要指图象处理；
（3） 特征抽取和选择：在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征；
（4） 分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库；
（5） 分类决策：在特征空间中对被识别对象进行分类。

3.模式识别的基本问题有哪些？
（1）模式(样本)表示方法：（a）向量表示；（b）矩阵表示；（c）几何表示；（4）基元(链码)表示；
（2）模式类的紧致性：模式识别的要求:满足紧致集，才能很好地分类；如果不满足紧致集，就要采取变换的方法,满足紧致集
（3）相似与分类；(a)两个样本xi ，xj之间的相似度量满足以下要求：
① 应为非负值
② 样本本身相似性度量应最大
③ 度量应满足对称性
④ 在满足紧致性的条件下，相似性应该是点间距离的
单调函数
(b) 用各种距离表示相似性
（4）特征的生成:特征包括：(a)低层特征;(b)中层特征;(c)高层特征
（5） 数据的标准化:(a)极差标准化；(b)方差标准化

4．线性判别方法
（1）两类：二维及多维判别函数，判别边界，判别规则
二维情况：（a）判别函数： ( )
（b）判别边界：g(x)=0;
（c）判别规则：

n维情况：（a）判别函数：
也可表示为：

（b）判别边界：g1(x) =WTX=0
（c）判别规则：

（2）多类：3种判别方法（函数、边界、规则）
(A)第一种情况：(a)判别函数：M类可有M个判别函数

(b) 判别边界：ωi （i=1,2,…,n）类与其它类之间的边界由 gi(x)=0确定
(c) 判别规则：

(B)第二种情况：(a)判别函数：有 M(M _ 1)/2个判别平面

(b) 判别边界：
(c) 判别规则：

(C)第三种情况：(a)判别函数：
(b) 判别边界：
gi(x) =gj(x) 或gi(x) -gj(x) =0
(c) 判别规则：

5．什么是模式空间及加权空间，解向量及解区？
（1）模式空间：由 构成的n维欧氏空间；
（2）加权空间：以 为变量构成的欧氏空间；
（3）解向量：分界面为H，W与H正交，W称为解向量；
（4）解区：解向量的变动范围称为解区。

6．超平面的四个基本性质是什么？
性质①：W与H正交；
性质 ②：

其中， 为x矢量到H的正交投影；
性质③：

性质④：

7．二分法能力如何表示？
N个样品线性可分数目(条件：样本分布良好）：

线性可分概率:

8．广义线性判别方法
（1）非线性→线性
一个非线性判别函数通过映射，变换成线性判别函数：

（2）线性判别

9．分段线性判别方法
1）基于距离:（1）子类，类判别函数
（2）判别规则
（1）子类：把ωi类可以分成li个子类:
∴ 分成l个子类。
子类判别函数：

在同类的子类中找最近的均值
（2）判别规则：

这是在M类中找最近均值。则把x归于ωj类完成分类

2）基于函数：（1）子类，类判别函数
（2）判别规则
（1）子类类判别函数：对每个子类定义一个线性判别函数为：

（2）判别规则：在各子类中找最大的判别函数作为此类的代表，则对于M类，可定义M个判别函数gi(x),i=1,2,…..M,因此，决策规则

3）基于凹函数的并：（1）析取范式，合取范式，凹函数
（2） 判别规则
（1） 析取范式：P=(L11∧L12∧…∧L1m)∨…∨(Lq1∧Lq2∧…∧Lqm)
合取范式：Q= (L11 ∨ L12 ∨ … ∨ L1m) ∧ … ∧(Lq1 ∨ Lq2 ∨ … ∨ Lqm)
凹函数：Pi=Li1∧Li2∧…∧Lim
（2） 判别规则：设第一类有q个峰，则有q个凹函数。
即P=P1∨P2∨……∨Pq

10．非线性判别方法
（1）集中，分散

（2）, 均集中

11．分类器的设计
（1）梯度下降法（迭代法）：准则函数，学习规则
（a）准则函数：J(W)≈J(Wk)+ ▽JT(W- Wk)+(W- Wk)TD(W- Wk)T/2
其中D为当W = Wk时 J(W)的二阶偏导数矩阵
（b）学习规则：从起始值W1开始，算出W1处目标函数的梯度矢量▽J(W1)，则下一步的w值为：W2 = W1-ρ1▽J(W1) 其中W1为起始权向量， ρ1为迭代步长，J(W1) 为目标函数，▽J(W1)为W1处的目标函数的梯度矢量
在第K步的时候
Wk+1 = Wk-ρk▽J(Wk) 最佳步长为ρk=||▽J||2/▽JTD▽J
这就是梯度下降法的迭代公式。

（2）感知器法：准则、学习规则（批量，样本）
（a）准则函数： 其中x0为错分样本

（b）学习规则：
1.错误分类修正wk
如wkTx≤0并且x∈ω1 wk+1= wk+ρkx
如wkTx≥0并且x∈ω2 wk+1= wk-ρkx
2.正确分类 ，wk不修正
如wkTx＞0并且x∈ω1
如wkTx＜0并且x∈ω2
wk+1= wk

（3）最小平方误差准则法（MSE法）（非迭代法）：准则、权向量解
(a)准则函数：

(b)权向量解：

（4）韦—霍氏法（LMS法）（迭代法）：准则，学习规则
(a)准则函数：

(b)学习规则： W1任意 ，Wk+1=Wk+ρk(bk-WkTXk) Xk
ρk随迭代次数k而减少，以保证算法收敛于满意的W值

（5）何—卡氏法（H-K法）（迭代法）：准则，，的学习规则
(a)准则：

它的解为：

（b）b，W的学习规则：

其中 c为矫正系数，ek为误差矢量，ek=XWk-bk

初始条件 W1=X+b1并且b1>0
迭代时检测
如果ek≥0时，XW >b，系统线性可分，迭代收敛
如果ek<0时，XW <b，系统线性不可分，迭代不收敛

（6）Fisher分类法：准则函数的建立，权值计算，的选择
(a)准则函数的建立：投影样本之间的类间分离性越大越好，投影样本的总离散度越小越好。
即可表示为：

其中Sw为类内散布矩阵, Sb为类间散布矩阵

(b)W权值计算：
(c)W0的选择 ：

Yki表示第i类中第k个样本的投影值
N1为ω1样本数 N2为ω2样本数 
（7）电位函数分类器：电位函数，累积电位的计算

(a)电位函数：电位分布函数有如下三种形式：

α为系数 xk为某一特定点

(b)累计电位的计算： Kk+1(x)= Kk(x)+rk+1K(x,xk)
其中： xk+1∈ω1并且Kk(xk+1)>0时 rk+1= 0
xk+1∈ω1并且Kk(xk+1) ≤ 0时 rk+1= 1
xk+1∈ω2并且Kk(xk+1)<0时 rk+1= 0
xk+1∈ω2并且Kk(xk+1) ≥ 0时 rk+1= -1

12．1）二类问题的贝叶斯判别
（1）判别函数的四种形式
（2）决策规则
（3）决策面方程
（4）决策系统的结构
（1）判别函数的四种形式：

（2）判别规则：

（3）决策面方程：g（x）=0
（4）决策系统的结构
（A）向量特征（B）判别计算（C）阈值单元（D）决策

2）多类问题的贝叶斯判别
（1）判别函数的四种形式
（2）决策规则
（3）决策面方程
（4）决策系统的结构
（1）判别函数的四种形式：M类有M个判别函数g1(x), g2(x),…, gm(x).

（2）决策规则：

另一种形式：

（3）决策面方程：

（4）决策系统的结构：
(a)特征向量；(b)判别计算；(c)最大选择器；(d)决策

13．三种最小错误率贝叶斯分类器（正态分布）：判别函数，判别规则，决策面方程
（1）第一种情况：各个特征统计独立，且同方差情况。(最简单情况)
(a)判别函数：

(b)判别规则：

(c)决策面方程：

（2）第二种情况：Σi＝ Σ相等，即各类协方差相等。
(a)判别函数：

(b)判别规则：

(c)决策面方程：

（3）第三种情况(一般情况)：Σί为任意，各类协方差矩阵不等，二次项xT Σί x与i有关。所以判别函数为二次型函数。
(a)判别函数：

(b)判别规则：

(c)决策面方程：

14．最小风险贝叶斯分类器：判别函数，判别规则
（1）判别函数：
条件风险：

αi：表示把模式x判决为ωi类的一次动作
期望风险：

（2）判别规则： ：

15．聂曼—皮尔逊判决：（二类）：准则，判别规则，阈值的确定
（1）准则：
（2）判别规则：

（3）阈值的确定：

16．最小最大损失准则判决（二类）：准则，判别规则，的确定
（1）准则：讨论在P(ωi)变化时如何使最大可能风险最小；
（2）判别规则：风险

通过最小风险与先验概率的关系曲线 ，确定最大风险，使最大风险最小。
（3）的确定：

17．什么是序贯分类？
序贯：随着时间的推移可以得到越来越多的信息。
序贯分类决策规则

18．什么是参数估计，非参数估计，监督学习，无监督学习？
参数估计：先假定研究的问题具有某种数学模型，如正态分布，二项分布，再用已知类别的学习样本估计里面的参数；
非参数估计：不假定数学模型，直接用已知类别的学习样本的先验知识直接估计数学模型；
监督学习：在已知类别样本指导下的学习和训练，参数估计和非参数估计都属于监督学习。
无监督学习：不知道样本类别，只知道样本的某些信息去估计，如：聚类分析。

19．（1）最大似然估计算法思想：准则，求解过程
（1）准则：第i类样本的类条件概率密度：
P(Xi/ωi)= P(Xi/ωi﹒θi) = P(Xi/θi)
原属于i类的学习样本为Xi=(X1 , X2 ,…XN,)T i=1,2,…M
求θi的最大似然估计就是把P(Xi/θi)看成θi的函数，求出使它最大时的θi值
（2）求解过程：
∵学习样本独立从总体样本集中抽取的
N个学习样本出现概率的乘积

取对数：

对θi求导,并令它为0：

（2）正态分布情况下：, 的计算
① ∑已知, μ未知,估计μ

② ∑， μ均未知
A一维情况：n=1对于每个学习样本只有一个特征的简单情况：

即学习样本的算术平均

样本方差

B多维情况：n个特征
估计值：

20．（1）贝叶斯估计算法思想：准则，求解过程
(A)准则：通过对第i类学习样本Xi的观察，使概率密度分布P(Xi/θ)转化为
后验概率P(θ/Xi) ，再求贝叶斯估计；
(B)求解过程： ① 确定θ的先验分布P(θ),待估参数为随机变量。
② 用第i类样本xi=(x1, x2,…. xN)T求出样本的联合概率密度分布P(xi|θ)，它是θ的函数。
③ 利用贝叶斯公式,求θ的后验概率

④

（2）正态分布情况下：的计算
对μ的估计为

若令P(μ)=N(μ0, σ02 )=N(0,1)

21．（1）贝叶斯学习概念
求出μ的后验概率之后，直接去推导总体分布即

当N↑,μN就反映了观察到N个样本后对μ的最好推测，而σN2反映了这种推测的不确定性, N↑, σN2↓,σN2 随观察样本增加而单调减小，且当N→∞, σN2 →0
当N↑，P(μ|xi)越来越尖峰突起；N→∞, P(μ|xi)→σ函数，这个过程成为贝叶斯学习。

（2）正态分布情况下的计算
(A)一维正态：已知σ2，μ未知

(B)多维正态（ 已知Σ，估计μ ）：

22．非参数估计的条件密度计算公式
（1）Parzen窗口估计的三种形式，条件密度的计算
（A）窗口的选择：（A）方窗函数；（B）正态窗函数；（C）指数窗函数

（B）条件密度的计算：

（2）K-近邻估计的基本思想及用K-近邻法作后验概率估计的方法
（A）基本思想：以x为中心建立空胞，使v↑，直到捕捉到KN个样本为止。
（B）用K-近邻法作后验概率估计的方法：由KN近邻估计知N个已知类别样
本落入VN内为KN个样本的概率密度估计为

N个样本落入VN内有KN个，KN个样本内有Ki个样本属于ωi类，则联合概率密度：

根据Bayes公式可求出后验概率：

23． 分类与聚类的区别是什么？
分类：用已知类别的样本训练集来设计分类器（监督学习）；
聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）。

24．（1）聚合聚类（系统聚类）的算法
思想：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。
若有n个样本：（A）设全部样本分为n类；
（B）作距离矩阵D(0)；
（C）求最小元素；
（D）将距离平方最小的元素归为一类；
（E）以新类从新分类，作距离矩阵D(1)；
（F）若合并的类数没有达到要求，转（C），否则停止。
（2）分解聚类的算法
思想：把全部样本作为一类，然后根据相似性、相邻性分解。
目标函数：两类均值方差
(

N：总样本数， ：ω1类样本数 ：ω2类样本数，

（3）动态聚类的算法（K-均值算法）
① 先选定某种距离作为样本间的相似性的度量;
② 确定评价聚类结果的准则函数;
③ 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。
25．（1）什么是模糊集，-水平截集？
（A）模糊集：假设论域E={x}（讨论的区间），模糊集A是由隶属函数μA(x)描述。其中，μA(x)是定义在E上在闭区间{0，1}中取值的一个函数，反映x对模糊集的隶属程度。
（B）-水平截集：设A为E=（x）中的模糊集，则A={x| μA(x)≥α}称为模糊集A的α水平集， α为阈值在（0，1）间取值。

（2）什么是模糊集的并，交，补运算？
设：A,B为E=（x）上的两个模糊集
并集:μA∪ B(x)＝max(μA(x) ,μB(x))
交集: μA∩ B(x)＝min(μA(x) ,μB(x))
补集: =1- μA(x) , μA(x) ,μB(x) 分别为A、B的隶属函数

（3）什么是模糊关系及其变换运算？
(A)模糊关系：设U,V为两个模糊集,则u,v的笛卡儿乘积集记为：U×V={(u,v)|u∈U,v∈V}, (u,v)是 U,V元素间的一种无约束搭配，若把这种搭配加某种限制， U,V间的这种特殊关系叫模糊关系R。
(B)变换运算：

（4）什么是相似关系，等价关系？
（A）相似关系：具有自反性对称性的模糊关系称为相似关系（或类似关系）；
（B）等价关系：具有自反性、对称性、传递性的模糊关系称为等价关系。

26．模糊识别方法
（1）隶属原则识别法的基本思想
设： A1, A2,…. ,An是E中的n个模糊子集， x0为E中的一个元素，若有隶属函数 μi(xo) =max(μ1(xo), μ2(xo),….. μn(xo)),则xo∈ μi。 则xo∈Ai
若有了隶属函数μ (x)，我们把隶属函数作为判别函数使用即可。

（2）择近原则识别法的基本思想
（a）贴近度的计算：

（b）设：E上有n个模糊子集 及另一模糊子集 。若贴近度

27．模糊聚类分析方法
1）基于等价关系
（1）-水平截阵
（2）等价划分
（1）α水平截阵： R α =[x| μA(x)≥α]
（2）等价划分：若 是E上的一个等价关系。则对任意阈值α(0≤ α ≤1)则模糊水平集R α也是E上的一个等价关系；由小到大选取阈值α(0≤ α ≤1)，将矩阵中相同的行的特征归为一类，得到分类；逐渐增大阈值，则分类增多，知道满足分类数目为止。

2）基于相似关系
（1）求传递闭包等价
（2）利用等价关系聚类
（1）把相似关系（相似矩阵） 变成等价关系方法为：
取 的乘幂为

（2）选择适当α值，取等价关系R的α水平集，根据水平集确定样本的类别

另：
1．所有作业涉及的计算问题！
2．分段线性判别方法中的基于凸函数的交方法？
3．结构模式识别中的形式语言、文法推断、句法分析、自动机理论等问题！