模式识别复习重点总结21485.pdf

《模式识别复习重点总结21485.pdf》由会员分享，可在线阅读，更多相关《模式识别复习重点总结21485.pdf（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 模式识别复习重点总结 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】1.什么是模式及模式识别模式识别的应用领域主要有哪些 模式：存在于时间，空间中可观察的事物，具有时间或空间分布的信息；模式识别：用计算机实现人对各种事物或现象的分析,描述,判断,识别。模式识别的应用领域：（1）字符识别；（2）医疗诊断；（3）遥感；(4）指纹识别 脸形识别；（5）检测污染分析，大气，水源，环境监测；（6）自动检测；（7）语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断；（8）军事应用。2.模式识别系统的基本组成是什么（1）信息的获取：是通

2、过传感器，将光或声音等信息转化为电信息；（2）预处理：包括 AD,二值化，图象的平滑，变换，增强，恢复，滤波等,主要指图象处理；（3）特征抽取和选择：在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征；（4）分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库；（5）分类决策：在特征空间中对被识别对象进行分类。3.模式识别的基本问题有哪些（1）模式(样本)表示方法：（a）向量表示；（b）矩阵表示；（c）几何表示；（4）基元(链码)表示；（2）模式类的紧致性：模式识别的要求:满足紧致集，才能很好地分类；如果不满足紧致集

3、，就要采取变换的方法,满足紧致集（3）相似与分类；(a)两个样本 xi，xj之间的相似度量满足以下要求：应为非负值 样本本身相似性度量应最大 度量应满足对称性 在满足紧致性的条件下，相似性应该是点间距离的 单调函数 (b)用各种距离表示相似性（4）特征的生成:特征包括：(a)低层特征;(b)中层特征;(c)高层特征（5）数据的标准化:(a)极差标准化；(b)方差标准化 4线性判别方法（1）两类：二维及多维判别函数，判别边界，判别规则 二维情况：（a）判别函数：()（b）判别边界：g(x)=0;32211)(wxwxwxg为坐标向量为参数，21,xxw （c）判别规则：n 维情况：（a）判别函数

4、：也可表示为：（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)判别规则：21,0,0)(XXxgi12211.)(nnnwxwxwxwxgXWxgT)(为增值模式向量。，为增值权向量，TnnTnnxxxxXwwwwW)1,.,(),.,(21121。其它MiXXWxgiTii,.,2,1,0

5、,0)(XWxgTii)(XWxgTijij)(0)(xgijjixgijjix0 x0)(当当权向量。个判别函数的为第式中iwwwwWTininiii),.,(121。其它MiXXWxgiTii,.,2,1,0,0)(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

6、与H正交；性质：W)x(gr 其中，为 x 矢量到 H 的正交投影；性质：性质：7二分法能力如何表示 XWxgKk)(小，其它最大，当iTkixXWxg)(TnxxxxX),.,(321121,.,nwwwr成正比的距离与原点到11,nnWHWWq通过原点。，说明超平面则若在原点负侧。则在原点正侧，若则若HxWxgWHWHWTnnn)(,0,0,0111N 个样品线性可分数目(条件：样本分布良好）：线性可分概率:8广义线性判别方法（1）非线性线性 一个非线性判别函数通过映射，变换成线性判别函数：（2）线性判别 9分段线性判别方法 nkkNNnNCnNnND011,21,2),(若若为特征数为样

7、本数其中nNkNkNCkN,)!1(!)!1(11101,1(,)(,)2,12nNkNNkNnD N nP N nCNn若若强。说明样本少时二分能力范围，即在。时，线性可分概率为时，即值，对于任意。处出现明显的门限效应时，曲线急剧下降，在由当,1),(),1(22:)(21),()1(22:)(21:)(nNPnNcnNPnNnbna.2),1(2:)(,),1(22:)(0是最好情况即二分能力）的估计：个样本的线性可分性（对多线性可分能力越差。说明样品越线性可分概率急剧下降范围，即在nNNenNd)(,)(.)()()(,.)()()(212111增广模式向量。广义权向量其中：空间变换空间

8、xfxfxfYwwwWYgYWxfwxgkkTyxkiii0YWT判别平面：21,0,0)(xxYgYWT1）基于距离:（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）析

9、取范式，合取范式，凹函数（2）判别规则（1）析取范式：P=(L11L12L1m)(Lq1Lq2Lqm),.,(21liiiilillixxg,.,2,1min)(Mixgxgij,.,2,1),(min)(子类的权向量。为其中lilililiwxwxg,)(jiMijxxgxg则),(max)(,.,2,1合取范式：Q=(L11 L12 L1m)(Lq1 Lq2 Lqm)凹函数：Pi=Li1Li2Lim（2）判别规则：设第一类有q个峰，则有q个凹函数。即 P=P1P2Pq 10非线性判别方法（1）1集中，2分散 （2）1,2均集中 11分类器的设计。每个子类的判别函数数子类。mjxqixxwL

10、ijij,.,2,1,0,.,2,1,02121,0,0 xPxP则则判别规则：协方差为均值，为其中：大小。的大小，决定超平面的判别函数定义1111111121,)()()(:kxxkxgT协方差，为均值，为其中：，两个判别函数：都比较集中，那么定义，如果212112212,1)()()(iiiiTiiiixxkxg。可用来调整二类错误率判别规则：判别平面方程：21212221212211111221111211221,0,0)(0)()()(2)()()()(kkxxxgkkxxxxgxgxgTTTT（1）梯度下降法（迭代法）：准则函数，学习规则（a）准则函数：J(W)J(Wk)+JT(W-

11、Wk)+(W-Wk)TD(W-Wk)T/2 其中 D 为当 W=Wk时 J(W)的二阶偏导数矩阵（b）学习规则：从起始值 W1开始，算出 W1处目标函数的梯度矢量J(W1)，则下一步的 w 值为：W2=W1-1J(W1)其中 W1为起始权向量，1为迭代步长，J(W1)为目标函数，J(W1)为 W1处的目标函数的梯度矢量 在第 K 步的时候 Wk+1=Wk-kJ(Wk)最佳步长为 k=|J|2/JTDJ 这就是梯度下降法的迭代公式。（2）感知器法：准则、学习规则（批量，样本）（a）准则函数：其中 x0为错分样本 （b）学习规则：1.错误分类修正 wk 如 wkTx0 并且 x1 wk+1=wk+

12、kx 如 wkTx0 并且 x2 wk+1=wk-kx 2.正确分类，wk不修正 如 wkTx0 并且 x1 如 wkTx0 并且 x2 wk+1=wk （3）最小平方误差准则法（MSE 法）（非迭代法）：准则、权向量解 0)(XXXWWJT(a)准则函数：(b)权向量解：（4）韦霍氏法（LMS 法）（迭代法）：准则，学习规则(a)准则函数：(b)学习规则：W1任意，Wk+1=Wk+k(bk-WkTXk)Xk k随迭代次数 k 而减少，以保证算法收敛于满意的 W值 （5）何卡氏法（H-K 法）（迭代法）：准则，b，W的学习规则(a)准则：它的解为：（b）b，W 的学习规则：其中 c 为矫正系数

13、，ek为误差矢量，ek=XWk-bk 初始条件 W1=X+b1并且 b10 迭代时检测 如果 ek0 时，XW?b，系统线性可分，迭代收敛 如果 ek0 时，XW?0 时 rk+1=0 xk+11并且 Kk(xk+1)0 时 rk+1=1 xk+12并且 Kk(xk+1)0 时 rk+1=0 xk+12并且 Kk(xk+1)0 时 rk+1=-1 121）二类问题的贝叶斯判别（1）判别函数的四种形式（2）决策规则（3）决策面方程（4）决策系统的结构 （1）判别函数的四种形式：（2）判别规则：|sin|)K(3.22kkkxxxxXX)(,)()(ln)()(ln)()()(,)()()()()

14、()()(),()()()()()()(),()()()(12211221221121取对数方法似然比形式类条件概率密度后验概率PPxPxPxgDPPxPxPxgCPxPPxPxgBxPxPxgA2112212112212122112121)()(ln)()(ln)()()()()()()()()()()()()()()(xPPxPxPxgDxPPxPxPCxPxPPxPBxxPxPA（3）决策面方程：g（x）=0 （4）决策系统的结构 （A）向量特征（B）判别计算（C）阈值单元（D）决策 2）多类问题的贝叶斯判别（1）判别函数的四种形式（2）决策规则（3）决策面方程（4）决策系统的结构 （1

15、）判别函数的四种形式：M 类有 M 个判别函数 g1(x),g2(x),gm(x).（2）决策规则：另一种形式：)(,)()(ln)()(ln)()()(,)()()()()()()(),()()()()()()(),()()()(12211221221121取对数方法似然比形式类条件概率密度后验概率PPxPxPxgDPPxPxPxgCPxPPxPxgBxPxPxgA),.,2,1(,)()(max)()()(1MixPxPPxPxgijjMjiiiiijMjiiixPxPPxPxg)(ln)(lnmax)(ln)(ln)(1（3）决策面方程：（4）决策系统的结构：(a)特征向量；(b)判别计

16、算；(c)最大选择器；(d)决策 13三种最小错误率贝叶斯分类器（正态分布）：判别函数，判别规则，决策面方程（1）第一种情况：各个特征统计独立，且同方差情况。(最简单情况)(a)判别函数：(b)判别规则：(c)决策面方程：（2）第二种情况：i 相等，即各类协方差相等。(a)判别函数：0)()(),()(xgxgxgxgjiji即)(ln21,21)(,)(2020iiTiiiiiTiiPwwwxwxg其中：线性判别函数ijTjMwiTiixwxwwxwxg010max)()()(ln)(210)(0)()(200jijijijijijiPPxWxxWxgxg其中)(ln21,)(1010iiT

17、iiiiiTiiPwWwxWxg其中（线性函数）(b)判别规则：(c)决策面方程：（3）第三种情况(一般情况)：为任意，各类协方差矩阵不等，二次项xT x与i有关。所以判别函数为二次型函数。(a)判别函数：(b)判别规则：(c)决策面方程：14最小风险贝叶斯分类器：判别函数，判别规则（1）判别函数：条件风险：i：表示把模式x判决为 i类的一次动作 期望风险：ijTjMjiTiixwxWwxWxg010max)(0)()(xgxgjiji相邻与若)()()()()(ln)(21)(,0)(1010jiTjijijijijiTPPxWxxW。其中)(lnln2121)()(,21,)(10110i

18、iiiTiiiiiiiiTiiTiPwnWnnWwxWxWxxg，维列向量矩阵其中ijTjjTMjiTiiTixwxWxWxwxWxWxxg010max)().(,.,2,1,1MaaixPExRjMjjijii )(,平均风险dxxPxxRR（2）判别规则：15聂曼皮尔逊判决：（二类）：准则，判别规则，阈值的确定（1）准则：（2）判别规则：（3）阈值的确定：16最小最大损失准则判决（二类）：准则，判别规则，*1()P的确定（1）准则：讨论在 P(i)变化时如何使最大可能风险最小；（2）判别规则：风险 通过最小风险与先验概率的关系曲线，确定最大风险，使最大风险最小。（3）*1()P的确定：17

19、什么是序贯分类 序贯：随着时间的推移可以得到越来越多的信息。kiMikxxRxR则若,min,.,2,1最小，使为常数时在取1022,.)()(2121TxTxPxP值皮尔逊规则归结为找阈最小一定这时可确定，为常数时，的函数在取为的分界线作时当1222222121,)(.,)()(TTdxxPTTxPxPT 1222221211121221122212221dxxPdxxPbdxxPabPaR其中：2122221222222121112122111210.,0,dxxPaRdxxPdxxPPRb，这时候最大风险为最小即无关与使如果选择序贯分类决策规则 18什么是参数估计，非参数估计，监督学习，

20、无监督学习 参数估计：先假定研究的问题具有某种数学模型，如正态分布，二项分布，再用已知类别的学习样本估计里面的参数；非参数估计：不假定数学模型，直接用已知类别的学习样本的先验知识直接估计数学模型；监督学习：在已知类别样本指导下的学习和训练，参数估计和非参数估计都属于监督学习。无监督学习：不知道样本类别，只知道样本的某些信息去估计，如：聚类分析。19（1）最大似然估计算法思想：准则，求解过程（1）准则：第 i 类样本的类条件概率密度：P(Xi/i)=P(Xi/ii)=P(Xi/i)原属于 i 类的学习样本为 Xi=(X1,X2,XN,)T i=1,2,M 求 i的最大似然估计就是把 P(Xi/i

21、)看成 i的函数，求出使它最大时的 i值（2）求解过程：时，继续观察时时AXPXPBXePePBXPXPXePePAXPXPiiiiii)()()(1)()()()()(1)()(212212112121学习样本独立从总体样本集中抽取的 N 个学习样本出现概率的乘积 取对数：对 i求导,并令它为 0：（2）正态分布情况下：,的计算 已知,未知,估计 ，均未知 A 一维情况：n=1 对于每个学习样本只有一个特征的简单情况：即学习样本的算术平均 样本方差 NkiXkPiXPiiXPii1)|()|().|(NkikikNkXPXP11)|(log)|(log0)|(log.11NkikpXP0)|

22、(log.0)|(log111ikNkpikNkXPXP，即为的估值利用上式求出iiNkkXN11NkkXN1111NkXkN122121B 多维情况：n 个特征 估计值：20（1）贝叶斯估计算法思想：准则，求解过程(A)准则：通过对第 i 类学习样本 Xi的观察，使概率密度分布 P(Xi/)转化为 后验概率 P(/Xi)，再求贝叶斯估计；(B)求解过程：确定 的先验分布 P(),待估参数为随机变量。用第 i 类样本 xi=(x1,x2,.xN)T求出样本的联合概率密度分布 P(xi|)，它是 的函数。利用贝叶斯公式,求 的后验概率?（2）正态分布情况下：的计算 对的估计为 若令 P()=N(

23、0,02)=N(0,1)21（1）贝叶斯学习概念 求出的后验概率之后，直接去推导总体分布即 NkkXN111XTXNkNkk121dPXPPXPXPiii)()|()().|()|(dXPi)|(求贝叶斯估计02022120202NXNNkkNNNkkXNN111dXPXPdXPXPXXPiii)|()|()|()|()|(当 N,N就反映了观察到 N 个样本后对的最好推测，而 N2反映了这种推测的不确定性,N,N2,N2 随观察样本增加而单调减小，且当N,N2 0 当 N，P(|xi)越来越尖峰突起；N,P(|xi)函数，这个过程成为贝叶斯学习。（2）正态分布情况下()iP x X的计算(A

24、)一维正态：已知 2，未知 (B)多维正态（已知，估计）：22非参数估计的条件密度计算公式（1）Parzen 窗口估计的三种形式，条件密度的计算（A）窗口的选择：（A）方窗函数；（B）正态窗函数；（C）指数窗函数 dxPxPdxPxPxxPiii)|()|()|()|()|(dxNNN21exp2121exp2122dxxNNNNNNNN21exp21exp2122222222222221exp2122222NNNx为正态函数),(22NNN010101)1(1)1(01 NNxNNkkNN分类器就可以设计代入将BayesdxPxPxxPiiN)|()|()|(（B）条件密度的计算：（2）K-

25、近邻估计的基本思想及用 K-近邻法作后验概率估计的方法（A）基本思想：以 x 为中心建立空胞，使 v，直到捕捉到 KN个样本为止。（B）用 K-近邻法作后验概率估计的方法：由 KN近邻估计知 N 个已知类别样 本落入 VN内为 KN个样本的概率密度估计为 N 个样本落入 VN内有 KN个，KN个样本内有 Ki个样本属于 i类，则联合概率密度：根据 Bayes 公式可求出后验概率：23 分类与聚类的区别是什么 其他.021|,1)(uu21exp21)(2uu|exp)(uuNiNiNNNNhxxVNVNKxP1)|(11)(VNkxPNNN)()()|(),(iiNiiNPxPvNkxPMji

26、NiNNiiiiiiNxPxPPxPPxPxP11),(),()()|()()|()|(kkxPNiiN)|(后验概率的估计：分类：用已知类别的样本训练集来设计分类器（监督学习）；聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）。24（1）聚合聚类（系统聚类）的算法 思想：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。若有 n 个样本：（A）设全部样本分为 n 类；（B）作距离矩阵 D(0)；（C）求最小元素；（D）将距离平方最小的元素归为一类；（E）以新类从新分类，作距离矩阵 D(1)；（F）若合并的类数没有达到要求，转（C），否则停止。（2）分

27、解聚类的算法 思想：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数：两类均值方差 N：总样本数，：1 类样本数 ：2 类样本数，)()(212121xxxxTNNNE1N两类均值:,21xx2N （3）动态聚类的算法（K-均值算法）先选定某种距离作为样本间的相似性的度量;确定评价聚类结果的准则函数;给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。25（1）什么是模糊集，-水平截集（A）模糊集：假设论域 E=x（讨论的区间），模糊集 A 是由隶属函数A(x)描述。其中，A(x)是定义在 E 上在闭区间0，1中取值的一个函数，反映x对模糊集的隶属程度。（B）-水平截集：设

28、 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）什么是模糊关系及其变换运算)(xA(A)模糊关系：设 U,V 为两个模糊集,则u,v的笛卡儿乘积集记为：UV=(u,v)|uU,vV,(u,v)是 U,V 元素间的一种无约束搭配，若把这种搭配加某种限制，U,V 间的这种特殊关系叫模糊关系 R。(B)变换

29、运算：（4）什么是相似关系，等价关系（A）相似关系：具有自反性对称性的模糊关系称为相似关系（或类似关系）；（B）等价关系：具有自反性、对称性、传递性的模糊关系称为等价关系。26模糊识别方法（1）隶属原则识别法的基本思想 设：A1,A2,.,An是 E 中的n个模糊子集，x0为 E 中的一个元素，若有隶属函数 i(xo)=max(1(xo),2(xo),.n(xo),则xo i。则xoAi 若有了隶属函数 (x)，我们把隶属函数作为判别函数使用即可。（2）择近原则识别法的基本思想（a）贴近度的计算：维模糊矩阵是维模糊矩阵；是rmsSmnrRikij”表示求最小值”表示求最大值，“；式中“令),.

30、,2,1;,.,2,1(,1rknisrtjkijmiik。的最大最小合成关系与上式表示SR SRTSRtTik的复合矩阵，记作对为)121)(BABABA（b）设：E 上有 n 个模糊子集 及另一模糊子集 。若贴近度 27模糊聚类分析方法 1）基于等价关系（1）-水平截阵（2）等价划分（1）水平截阵：R =x|A(x)（2）等价划分：若 是 E 上的一个等价关系。则对任意阈值(0 1)则模糊水平集 R 也是 E 上的一个等价关系；由小到大选取阈值(0 1)，将矩阵中相同的行的特征归为一类，得到分类；逐渐增大阈值，则分类增多，知道满足分类数目为止。2）基于相似关系（1）求传递闭包等价（2）利用

31、等价关系聚类 （1）把相似关系（相似矩阵）变成等价关系方法为：取 的乘幂为 ”表示求最小。”表示求最大，“符号“的内积和外积。与分别称为式中)()(),()(,BAxBxABAxBxABAExEx21,.,nAAAB方法。，这就是择近原则识别类则最贴近与则称.)(max)(1iijnjiABABABABRRR.,842RRR44822422kk,.RRRRRRRRRRRRR就是模糊等价关系。且则若在某一步有 （2）选择适当 值，取等价关系 R 的 水平集，根据水平集确定样本的类别 另：1所有作业涉及的计算问题！2分段线性判别方法中的基于凸函数的交方法 3结构模式识别中的形式语言、文法推断、句法分析、自动机理论等问题！