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

《模式识别复习重点总结.docx》由会员分享，可在线阅读，更多相关《模式识别复习重点总结.docx（36页珍藏版）》请在三一办公上搜索。

1、模式识别复习重点总结1.什么是模式及模式识别？模式识别的应用领域主要有哪些？ 模式：存在于时间，空间中可观察的事物，具有时间或空间分布的信息； 模式识别：用计算机实现人对各种事物或现象的分析,描述,判断,识别。 模式识别的应用领域：字符识别； 医疗诊断；遥感； (4）指纹识别 脸形识别；检测污染分析，大气，水源，环境监测； 自动检测；语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断； 军事应用。 2.模式识别系统的基本组成是什么？ 信息的获取：是通过传感器，将光或声音等信息转化为电信息； 预处理：包括AD,二值化，图象的平滑，变换，增强，恢复，滤波等, 主要指图象处理； 特征抽取和选择

2、：在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征； 分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库； 分类决策：在特征空间中对被识别对象进行分类。 3.模式识别的基本问题有哪些？ 模式(样本)表示方法：向量表示；矩阵表示；几何表示；基元(链码)表示； 模式类的紧致性：模式识别的要求:满足紧致集，才能很好地分类；如果不满足紧致集，就要采取变换的方法,满足紧致集 相似与分类；(a)两个样本xi ，xj之间的相似度量满足以下要求： 应为非负值 样本本身相似性度量应最大 度量应满足对称性 在满足紧致性的条件下，相似

3、性应该是点间距离的 单调函数 (b)用各种距离表示相似性 特征的生成:特征包括：(a)低层特征;(b)中层特征;(c)高层特征 数据的标准化:(a)极差标准化；(b)方差标准化 4线性判别方法 两类：二维及多维判别函数，判别边界，判别规则 二维情况：判别函数： g ( x ) = w 1 + w 2x 3 ( w 为参数， x ) w1x2 +1,x2为坐标向量 判别边界：g(x)=0; 判别规则： 0,Xw1g(x)= i0,XwiTgi(x)=WiX0,Xwigi(x)=WiX0当xwigij(x)ij0,则H在原点正侧，若Wn+10,则H在原点负侧。 若Wn+1=0,则g(x)=WTx，

4、说明超平面H通过原点。 7二分法能力如何表示？ N个样品线性可分数目(条件：样本分布良好）： 2N,若Nn+1k=0 (N-1)!k其中CN,N为样本数,n为特征数-1= k!(N-k-1)!线性可分概率: 1,若Nn+12 2k=0 (a):当n由1时，曲线急剧下降，在l=2处出现明显的门限效应。 1P(N,n)=。 (b):对于任意n值，l=2时，即N=2(n+1)时，线性可分概率为2(c):在l2范围，即N2范围，即N2(n+1),线性可分概率急剧下降,说明样品越 多线性可分能力越差。 (e):对N个样本的线性可分性的估计：N0=2(n+1),即 . l=2是最好情况8广义线性判别方法

5、非线性线性 一个非线性判别函数通过映射，变换成线性判别函数： k+1 x空间变换y空间g(x)=wifi(x)WTY=g(Y) i=1w1f1(x) wf(x)其中：W=2,(广义权向量)。Y=2,(增广模式向量) . wf(x)kk 线性判别 判别平面：WTY=0 0,xw1TWY=g(Y) 0,xw1,i=1,2,.,q子类。Lij=wijx 。0,则xw1 判别规则：P0,则xw2 10非线性判别方法 w1集中，w2分散 w1, 定义w1判别函数:-1g(x)=k2-(x-m1)T1(x-m1),k的大小，决定超平面的大小。其中：m1为w1均值，1为w1协方差g(x)0,xw1判别规则：

6、g(x)0,xw1判别规则：g(x) 0 迭代时检测 如果ek0时，XW b，系统线性可分，迭代收敛 如果ek0时，XW 0时 rk+1= 0 xk+11并且Kk(xk+1) 0时 rk+1= 1 xk+12并且Kk(xk+1)(A)P(w1x)P(w2x)x1w2(B)P(xw1)P(w1)P(xw2)P(w2)x1w2P(w2)x1P(xw2)P(w2)lnx1w2P(xw2)P(w1)(D)g(x)=ln 决策面方程：g=0 决策系统的结构 向量特征判别计算阈值单元决策 2）多类问题的贝叶斯判别 判别函数的四种形式 决策规则 决策面方程 决策系统的结构 判别函数的四种形式：M类有M个判别

7、函数g1(x), g2(x), gm(x). (A)g(x)=P(w1x)-P(w2x),(后验概率) (B)g(x)=P(xw1)P(w1)-P(xw2)P(w2),(类条件概率密度) P(xw1)P(w2)(C)g(x)=-,(似然比形式) P(xw2)P(w1)P(xw1)P(w2) (D)g(x)=ln-ln,(取对数方法)P(xw2)P(w1)决策规则： gi(x)=P(xwi)P(wi) =maxP(xwj)P(wj)xwi,(i=1,2,.,M)1jM 另一种形式： gi(x)=lnP(xwi)+lnP(wi) =maxlnP(xwj)+lnP(wi)xwi1jM决策面方程： g

8、i(x)=gj(x),即gi(x)-gj(x)=0 决策系统的结构： (a)特征向量；(b)判别计算；(c)最大选择器；(d)决策 13三种最小错误率贝叶斯分类器：判别函数，判别规则，决策面方程 第一种情况：各个特征统计独立，且同方差情况。(最简单情况) (a)判别函数： ) = w T x + w , (线性判别函数 ) g (xiii0其中：wi= (b)判别规则： 12d2mi,wi0=-12d2miTmi+lnP(wi)gi(x)=wiTx+wi0=maxwTjx+wj0xwi1wM (c)决策面方程： gi(x)-gj(x)=0W(x-x0)=0 其中W=mi-mj 第二种情况：i

9、相等，即各类协方差相等。 (a)判别函数： gi(x)=WiTx+wi0, -1其中Wi=mi1-1 wi0=-miTmi+lnP(wi)2 d2(mi-mj)P(wi)1x0=(mi+mj)-ln2P(wj)mi-mj (b)判别规则： gi(x)=WiTx+wi0=maxWjTx+wj0xwi1jM (c)决策面方程： 若w与w相邻g(x)-g(x)=0ijijWT(x-x0)=0,其中W=-1(mi-mj)。P(wi) ln(mi-mj)P(wj)1 x0=(mi-mj)-2(mi-mj)T-1(mi-mj)第三种情况(一般情况)：为任意，各类协方差矩阵不等，二次项xT x与i有关。所以

10、判别函数为二次型函数。 (a)判别函数： 1-1TTg(x)=xWx+Wx+w,其中W=-iiiii0i,(nn矩阵) 21T-11Wi=i-1mi(n维列向量)，wi0=-miimi-lni+lnP(wi)22(b)判别规则： gi(x)=xWix+Wix+wi0 =maxxTWjx+WjTx+wj0xwi1jMgi(x)-gj(x)=0 (c)决策面方程： 14最小风险贝叶斯分类器：判别函数，判别规则 判别函数： 条件风险： M R(aix)=Elaiwj=laiwjPwjx,i=1,2,.,a.(aTx皮尔逊规则归结为找阈值T. w2P(xw2)阈值的确定： P(xw1)当=T时,T作W

11、1W2的分界线. P(xw2) Te2=P(xw2)dx,T为e2的函数在取e2为常数时，T可确定， - 这时e2一定e1最小 16最小最大损失准则判决：准则，判别规则，P*(w1)的确定 准则：讨论在P(i)变化时如何使最大可能风险最小； 判别规则：风险 R = a + bP ( w 1 ) 其中：a=l22+(l12-l22)P(xw2)dxW2b=(l11-l22)+(l21-l11)P(xw1)dx-(l12-l22)P(xw2)dx W2W1 通过最小风险与先验概率的关系曲线 ，确定最大风险，使最大风险最小。 P(w1)的确定： *如果选择W1,W2使b=0,R与P(w1)无关. 即

12、(l11-l22)+(l21-l11)WP(xw1)dx-(l12-l22)WP(xw2)dx=021这时候最大风险为最小，R=a=l22+(l12-l22)P(xw2)dx W217什么是序贯分类？ 序贯：随着时间的推移可以得到越来越多的信息。 序贯分类决策规则 Pi(Xw1)1-P1(e)A=时Xw1 P2(e)Pi(Xw2) Pi(Xw1)P 1(e)B=时Xw2 P(Xw)1-P(e)22i Pi(Xw1)BA时，继续观察 P(Xw)i2 18什么是参数估计，非参数估计，监督学习，无监督学习？ 参数估计：先假定研究的问题具有某种数学模型，如正态分布，二项分布，再用已知类别的学习样本估计

13、里面的参数； 非参数估计：不假定数学模型，直接用已知类别的学习样本的先验知识直接估计数学模型； 监督学习：在已知类别样本指导下的学习和训练，参数估计和非参数估计都属于监督学习。 无监督学习：不知道样本类别，只知道样本的某些信息去估计，如：聚类分析。 19最大似然估计算法思想：准则，求解过程 准则：第i类样本的类条件概率密度： P(Xi/i)= P(Xi/ii) = P(Xi/i) 原属于i类的学习样本为Xi=(X1 , X2 ,XN,)T i=1,2,M 求i的最大似然估计就是把P(Xi/i)看成i的函数，求出使它最大时的i值 求解过程： 学习样本独立从总体样本集中抽取的 N N个学习样本出现

14、概率的乘积 iiiiP(X|wi.q)=P(X|q)=P(Xk|qi) k=1NNi取对数： logP(Xk|q)=logP(Xk|qi)k=1k=1对i求导,并令它为0： Nq1i.logP(Xk|q)=0k=1qpNi logP(|)=0qXk k=1q1. . NilogP(|)=0qXk k=1qp ii利用上式求出q的估值q，即为qq 正态分布情况下：m, S的计算 已知, 未知,估计 1Nm=m=Xk Nk=1 ， 均未知 A一维情况：n=1对于每个学习样本只有一个特征的简单情况： N 1即学习样本的算术平均 q1=m1=XkNk=1 21N2=1= q 2 s N k =1 X

15、k - m 样本方差 B多维情况：n个特征 1N估计值： q 1 = m = X k Nk=1 T1N=S=q2-mXk-m Nk=1Xk 20贝叶斯估计算法思想：准则，求解过程 (A)准则：通过对第i类学习样本Xi的观察，使概率密度分布P(Xi/)转化为 后验概率P(/Xi) ，再求贝叶斯估计； (B)求解过程： 确定的先验分布P(),待估参数为随机变量。 用第i类样本xi=(x1, x2,. xN)T求出样本的联合概率密度分布P(xi|)，它是的函数。 i 利用贝叶斯公式,求的后验概率 P(q|Xi)=P(X|q).P(q)iP(|q)P(q)dqX q求贝叶斯估计q=qP(q|Xi)dq

16、 q正态分布情况下：m的计算 ()()()对的估计为 s0 mN=mN=Ns02+s2 若令P()=N(0, 02 )=N(0,1) 2Xk=1Nk+s2Ns02+s2m01N XkmN=N+1k=1 21贝叶斯学习概念 求出的后验概率之后，直接去推导总体分布即 iiiP(X|)=P(X|q)P(q|)dq=P(X|m)P(m|)dmXXX 当N,N就反映了观察到N个样本后对的最好推测，而N2反映了这种推测的不确定性, N, N2,N2 随观察样本增加而单调减小，且当N, N2 0 当N，P(|xi)越来越尖峰突起；N, P(|xi)函数，这个过程成为贝叶斯学习。 i正态分布情况下P(xX)的

17、计算 (A)一维正态：已知2，未知 P(x|xi)=P(x|q)P(q|xi)dq=P(x|m)P(m|xi)dm 2211x-m11m-mN =exp-exp-dm2s2sN2ps2psN 2222 11x-m1s2s2Nx+smNN+s=exp-exp-dmm-2222pssN2s22s2 s2N+sNsN+s()N)()=122ps2N+sexp-122s2N+sx-mN22=N(mN,s2N+s)为正态函数(B)多维正态： -1 11N11-1 mN=00+(xk)+(0+)m0NNNNk=1 ii 将mN代入P(x|x)=P(x|m)P(m|x)dm就可以设计Bayes分类器 22非

18、参数估计的条件密度计算公式 Parzen窗口估计的三种形式，条件密度的计算 窗口的选择：方窗函数；正态窗函数；指数窗函数 1 1,|u|112j(u)=j(u)=exp-2-|u|uj(u)=exp 22p0.其他 条件密度的计算： 1N1|x-xi|KNNPN(x)=jNVNhNi=1VNK-近邻估计的基本思想及用K-近邻法作后验概率估计的方法 基本思想：以x为中心建立空胞，使v，直到捕捉到KN个样本为止。 用K-近邻法作后验概率估计的方法：由KN近邻估计知N个已知类别样 本落入VN内为KN个样本的概率密度估计为 kN NPN(x)= VNN个样本落入VN内有KN个，KN个样本内有Ki个样本

19、属于i类，则联合概率密度： kiN=P(x|)P wiwiPN(x,wi)=vN 根据Bayes公式可求出后验概率： P(x|wi)P(wi)PN(x,wi)(|x)=wPNiNM P(x|wi)P(wi)PN(x,wi) i=1j=1ki后验概率的估计：PN(wi|x)= kN 23 分类与聚类的区别是什么？ 分类：用已知类别的样本训练集来设计分类器； 聚类：用事先不知样本的类别，而利用样本的先验知识来构造分类器。 24聚合聚类的算法 思想：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。 若有n个样本：设全部样本分为n类； 作距离矩阵D(0)； 求最小元素； 将距离平方最小的元素

20、归为一类； 以新类从新分类，作距离矩阵D(1)； 若合并的类数没有达到要求，转，否则停止。 分解聚类的算法 思想：把全部样本作为一类，然后根据相似性、相邻性分解。 目标函数：两类均值方差 TN1N2 E=1212N N：总样本数， N 1 ：1类样本数 N 2 ：2类样本数， x 1 , x 2 : 两类均值 (x-x)(x-x)动态聚类的算法 先选定某种距离作为样本间的相似性的度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。 25什么是模糊集，a-水平截集？ 模糊集：假设论域E=x，模糊集A是由隶属函数A(x)描述。其中，A(x)是定义在

21、E上在闭区间0，1中取值的一个函数，反映x对模糊集的隶属程度。 a-水平截集：设A为E=中的模糊集，则A=x| A(x)称为模糊集A的水平集，为阈值在间取值。 什么是模糊集的并，交，补运算？ 设：A,B为E=上的两个模糊集 并集:A B(x)max(A(x) ,B(x) 交集: A B(x)min(A(x) ,B(x) 补集: m A ( x ) =1- A(x) , A(x) ,B(x) 分别为A、B的隶属函数 什么是模糊关系及其变换运算？ (A)模糊关系：设U,V为两个模糊集,则u,v的笛卡儿乘积集记为：UV=(u,v)|uU,vV, (u,v)是 U,V元素间的一种无约束搭配，若把这种搭

22、配加某种限制， U,V间的这种特殊关系叫模糊关系R。 (B)变换运算：R (r )是 n m 维模糊矩阵； S ( s ) 是 m ijikr维模糊矩阵 令timik=1rijsjk,(i=1,2,.,n;k=1,2,.,r)；式中“”表示求最大值，“ 上式表示R与S的最大最小合成关系。T(tik)为R对S的复合矩阵，记作T=RoS 什么是相似关系，等价关系？ 相似关系：具有自反性对称性的模糊关系称为相似关系； 等价关系：具有自反性、对称性、传递性的模糊关系称为等价关系。 26模糊识别方法 ”表示求最小 隶属原则识别法的基本思想 设： A1, A2,. ,An是E中的n个模糊子集， x0为E中

23、的一个元素，若有隶属函数 i(xo) =max(1(xo), 2(xo),. n(xo),则xo i。 则xoAi 若有了隶属函数 (x)，我们把隶属函数作为判别函数使用即可。 择近原则识别法的基本思想 贴近度的计算： 1 (AB)=AoB+设：E上有n个模糊子集 A 1 , A 2 ,., A n 及另一模糊子集 B 。若贴近度 (BAi)max(BAj)1jn 则称B与A最贴近.则BA类.，这就是择近原则识别方法。ii 27模糊聚类分析方法 1）基于等价关系 a-水平截阵 等价划分 水平截阵： R =x| A(x) 等价划分：若 R 是E上的一个等价关系。则对任意阈值(0 1)则模糊水平集R 也是E上的一个等价关系；由小到大选取阈值(0 1)，将矩阵中相同的行的特征归为一类，得到分类；逐渐增大阈值，则分类增多，知道满足分类数目为止。 2）基于相似关系 求传递闭包等价 利用等价关系聚类 R 变成等价关系方法为： 把相似关系248取 R 的乘幂为 R , R , R . k2k 若在某一步有RRR. 2则R就是模糊等价关系。且RRoR 422844RRoR,RRoR 选择适当值，取等价关系R的水平集，根据水平集确定样本的类别 另： 1所有作业涉及的计算问题！ 2分段线性判别方法中的基于凸函数的交方法？ 3结构模式识别中的形式语言、文法推断、句法分析、自动机理论等问题！