模式识别绪论

1、先修课程 概率论与数理统计概率论与数理统计, ,矩阵理论，矩阵理论， 线性代数线性代数, , 高级高级语言程序设计语言程序设计/ /MatlabMatlab课程简介 介绍模式识别的基本概念、基本理论、基本介绍模式识别的基本概念、基本理论、基本方法、基本应用。为今后学习人工智能、人机方法、基本应用。为今后学习人工智能、人机交互、系统分析等打下基础交互、系统分析等打下基础l基本：掌握模式识别的基本知识，按时上基本：掌握模式识别的基本知识，按时上课、完成作业，通过考试，获得学分。课、完成作业，通过考试，获得学分。l扩展：能够将所学知识和内容用于解决实扩展：能够将所学知识和内容用于解决实际问题，通过模

2、式识别的学习，改进思维际问题，通过模式识别的学习，改进思维方式，为将来的学习工作打好基础。方式，为将来的学习工作打好基础。l教材 模式识别模式识别清华大学出版社清华大学出版社 边肇祺边肇祺 、张学工、张学工。l参考文献：l1 模式识别模式识别，蔡元龙，西安电子科技大学出版社，蔡元龙，西安电子科技大学出版社。l2 模式识别模式识别，李晶皎、朱志良等，电子工业出版社，李晶皎、朱志良等，电子工业出版社l3 模式识别模式识别，杨光正、吴岷等，中国科技大学出版社，杨光正、吴岷等，中国科技大学出版社l4 Pattern Classification, 2nd Edition, Richard O. Dud

3、a, Peter E. Hart, and David G. Stork,l5 Pattern Recognition and Machine Learning，Christopher Bishopl6 The Elements of Statistical Learning, Trevor Hastie, Robert Tibshirani & Jerome Friedmanl课时安排： 每周每周2 2次课、共次课、共8 8周周l实验安排(课外自行安排）： 实验一：实验一：K K均值的系统聚类。均值的系统聚类。 实验二：均值向量和协方差矩阵的参数估计。实验二：均值向量和协方差矩阵的参

4、数估计。 实验三：计算总体散布矩阵、本征根和特征实验三：计算总体散布矩阵、本征根和特征向向l考试安排： 期末，开卷期末，开卷l第零章模式识别引论第零章模式识别引论(第第1章章) l第一章第一章 非监督学习方法非监督学习方法 (第三版第第三版第9章或第二版第章或第二版第10章章) l第二章第二章 线性判别函数线性判别函数 (第三版第第三版第4章第章第5章的章的5.15.3或第二版第或第二版第4,5章章) l第三章第三章 贝叶斯决策理论贝叶斯决策理论(第第2章章) l第四章第四章 概率密度函数估计概率密度函数估计 (第三版第第三版第3章第章第10章的章的10.1或第二版第或第二版第3章章) l第五

5、章第五章 特征选择与特征提取特征选择与特征提取 (第三版第第三版第7,8章或第二版第章或第二版第8,9章章) 1.1模式识别的基本概念一、模式识别基本定义 l模式(Pattern)：存在于时间，空间中可观察的事物，具有时间或空间分布的信息。l模式识别(Pattern Recognition)：用计算机实现人对各种事物或现象的分析,描述,判断,识别。NOTE：模式通常所指的不是事物本身，模式通常所指的不是事物本身，而是从事物获得的信息，因此，模式往而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。往表现为具有时间和空间分布的信息。l模式识别与图像识别,图像处理的关系: 模式识别

6、是模拟人的某些功能，达到划分对象的目的。 模拟人的视觉: 计算机+光学系统 模拟人的听觉: 计算机+声音传感器 模拟人的嗅觉和触觉: 计算机+传感器l图像识别：对二维图像信号的处理，识别感兴趣的部分。 比如，一副图像，里面有背景和人脸，要将人脸从图像重提取出来，甚至将人脸图像分成轮廓和五官等各个组件，这就完成了图像识别或者图像特征的提取。当需要从多幅这样的图像中分类出每个人的照片的时候，就需要完成模式识别了，每个五官都有自身的特点，即模式的特征，运用模式识别理论就可以达到分类。l主要动力：不同程度的模拟或者取代人脑的部分功能。l主要目标：利用机器（不仅仅是计算机），在错误概率最小的情况下，对对

7、象进行分类处理，使分类的结果与实际尽量相符合。l 1929年年 G. Tauschek发明阅读机发明阅读机 ，能够阅读，能够阅读0-9的数的数字。字。l20世纪世纪30年代年代 Fisher提出统计分类理论提出统计分类理论,奠定了统计奠定了统计模式识别的基础。因此，在模式识别的基础。因此，在6070年代，统计模式年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现特征也愈多，就出现“维数灾难维数灾难”。但由于计算机。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍

8、是模式识别的主要理论。计模式识别仍是模式识别的主要理论。l20世纪世纪50年代年代 Noam Chomsky提出形式语言理论提出形式语言理论 ，美籍华人付京荪美籍华人付京荪 提出句法结构模式识别。提出句法结构模式识别。l20世纪世纪60年代年代 L.A.Zadeh提出了模糊集理提出了模糊集理论，模糊模式识别理论得到了较广泛的应论，模糊模式识别理论得到了较广泛的应用。用。l20世纪世纪80年代年代 Hopfield提出神经元网络模提出神经元网络模型理论。近些年人工神经元网络在模式识型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。别和人工智能上得到较广泛的应用。l20世纪世纪9

9、0年代年代 小样本学习理论，支持向量小样本学习理论，支持向量机机(SVM)也受到了很大的重视。也受到了很大的重视。l近来近来 盲分析识别、独立分量分析等应用到盲分析识别、独立分量分析等应用到模式识别模式识别 。l1973年年 IEEE发起了第一次关于模式识别的国际会发起了第一次关于模式识别的国际会议议“ICPR” IEEE International Conference on Pattern Recognition，每每2年召开一次国际学术会议。年召开一次国际学术会议。lIEEE International Conference on Computer Vision and Pattern

10、Recognition (CVPR) lIEEE International Conference on Computer Vision (ICCV) lEuropean Conference on Computer Vision (ECCV)lIEEE International Conference on Image Processing (ICIP)l1977年年 IEEE的计算机学会成立了模式分析与机器的计算机学会成立了模式分析与机器智能（智能（PAMI）委员会，每委员会，每2年召开一次模式识别与年召开一次模式识别与图像处理学术会议。图像处理学术会议。lIEEE Transaction

11、s on Pattern Analysis and Machine Intelligence (PAMI)lInternational Journal of Computer VisionlIEEE Transactions on Image Processing (TIP)lPattern RecognitionlMachine Learning lIEEE Transactions on Multimedia (MM)lIEEE Transactions on Circuits and Systems for Video Technology (CSVT)l国内的组织有电子学会，通信学会，

12、自动化协会，国内的组织有电子学会，通信学会，自动化协会，中文信息学会。中文信息学会。l中科院自动化研究所模式识别重点实验室中科院自动化研究所模式识别重点实验室l中科院合肥智能机械研究所，主办模式识别与人中科院合肥智能机械研究所，主办模式识别与人工智能工智能信息获取预处理特征选取分类器设计模式分类错误率检测改进分类器(参数)识别结果输出信息的获取：通过传感器，将光或声音等信息转化为电信息。信息可以是二维的图像如文字，图像等；可以是一维的波形如声波，心电图，脑电图；也可以是物理量与逻辑值。预处理：包括A/D,二值化，图像的平滑，变换，增强，恢复，滤波等, 主要指图像处理。特征抽取和选择：在模式识别

13、中，需要进行特征的抽取和选择，例如，一幅64x64x8bits的图像可以得到4096个数据（字节），这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。错误率检测：计算分类器错误分类的概率，总结分类错误的主要特征。改进分类器(参数)： 依据错误率检测的结果适当修正分类器的参数或者构造新的分类器。模式分类：在特征空间中对被识别对象进行分类。1 1、字符识别：、字符识别： 包括印刷体字符的识别；手写体字符的识别，各种包括印刷体字符的识别

14、；手写体字符的识别，各种OCROCR（Optical character recognitionOptical character recognition）设备例如信函分拣、设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入、各种书写输入板。稿件输入、各种书写输入板。2 2、生物医学、生物医学 心电图，脑电图，染色体，癌细胞识别，心电图，脑电图，染色体，癌细胞识别，疾病诊断、疾病诊断、自动细胞学、染色体特性研自动细胞学、染色体特性研究、遗传研究究、遗传研究3 3、航空航天、航空航天 资源卫星照片，气象卫星照片处理，数字

15、资源卫星照片，气象卫星照片处理，数字化地球，图像分辨率可以达到化地球，图像分辨率可以达到1 1米。米。4 4、生物特征标识（、生物特征标识（安全检查）安全检查） 指纹识别指纹识别 、脸形识别，虹膜识别。、脸形识别，虹膜识别。5 5、环境保护、环境保护 检测污染分析、大气、水源、环境监测。检测污染分析、大气、水源、环境监测。6 6、工业生产、工业生产 自动检测：产品质量自动检测。自动检测：产品质量自动检测。7. 7. 人机智能人机智能 语声识别、机器翻译、电话号码自动查语声识别、机器翻译、电话号码自动查询、侦听、机器故障判断。询、侦听、机器故障判断。8. 8. 国防军事国防军事 军事设置的目标识

16、别。军事设置的目标识别。一一. .模式模式( (样本样本) )表示方法表示方法l向量表示向量表示 : 假设一个样本有假设一个样本有n个变量个变量(特征特征) = (X1,X2,Xn)T2. 矩阵表示矩阵表示: N个样本，个样本，n个变量个变量(特征特征) 变 量 样 本 x1 x2 xn X1 X11 X12 X1n X2 X21 X22 X2n XN XN1 XN2 XNn 3. 几何表示几何表示 一维表示一维表示 X1=1.5 X2=3 二维表示二维表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T 三维表示三维表示 X1=(x1,x2, x3)T=(1,1,

17、0)T X2=(x1,x2 , x3)T=(1,0,1)T4. 基元（链码）表示：基元（链码）表示：在右侧的图中八个基元在右侧的图中八个基元分别表示分别表示0，1，2，3，4，5，6，7，八个方向，八个方向和基元线段长度。和基元线段长度。则右侧样本可以表示为则右侧样本可以表示为 X1=006666这种方法将在句法模式识这种方法将在句法模式识别中用到。别中用到。1. 紧致集：同一类模式类样本的分布比较紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模集中，没有或临界样本很少，这样的模式类称紧致集。式类称紧致集。2. 临界点临界点(样本样本)：在多类样本中，某些样本的值：在多类样

18、本中，某些样本的值有微小变化时就变成另一类样本称为临界样本有微小变化时就变成另一类样本称为临界样本（点）。（点）。3. 紧致集的性质紧致集的性质 要求临界点很少要求临界点很少 集合内的任意两点的连线集合内的任意两点的连线,在线上的点属于在线上的点属于同同 一集合一集合 集合内的每一个点都有足够大的邻域集合内的每一个点都有足够大的邻域,在邻在邻域内只包含同一集合的点域内只包含同一集合的点4. 模式识别的要求模式识别的要求:满足紧致集，才能很好的分满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法类；如果不满足紧致集，就要采取变换的方法,满足紧致集满足紧致集.1.两个样本两个样本xi

19、 ，xj之间的相似度量满足以下要求：之间的相似度量满足以下要求： 应为非负值应为非负值 样本本身相似性度量应最大样本本身相似性度量应最大 度量应满足对称性度量应满足对称性 在满足紧致性的条件下，相似性应该是点间距离的在满足紧致性的条件下，相似性应该是点间距离的 单调函数单调函数 2. 用各种距离表示相似性：用各种距离表示相似性： 绝对值距离绝对值距离 已知两个样本已知两个样本 xi=(xi1, xi2 , xi3,xin)T xj=(xj1, xj2 , xj3,xjn)T 模式识别就是把具体事物归入某一类的过程。识别（Recognition）其实就是再认知（Re-Cognition）。相似和

20、分类是认知的基本问题。 欧几里德距离欧几里德距离明考夫斯基距离明考夫斯基距离 其中当其中当q=1q=1时为绝对值距离，当时为绝对值距离，当q=2q=2时为欧氏距离时为欧氏距离nkjkikijXXd1|nkjkikijXXd12nkjkikqijXXqqd1|1)( 切比雪夫距离切比雪夫距离 q q趋向无穷大时明氏距离的极限情况趋向无穷大时明氏距离的极限情况 马哈拉诺比斯距离马哈拉诺比斯距离 其中其中xi ，xj为特征向量，为特征向量， 为协方差。使用的条件是为协方差。使用的条件是 样样 本符合正态分布本符合正态分布|max)(1jkiknkijXXd1)(XjXiXXMdjiTij 夹角余弦夹

21、角余弦 为为xi xj的均值的均值 即样本间夹角小的为一类，具有相似性即样本间夹角小的为一类，具有相似性例：例： x1 , x2 , x3的夹角如图：的夹角如图：因为因为x1 , x2 的夹角小的夹角小，所以所以x1 , x2 最相似。最相似。nkjknkiknkjkikijXXXXC12121x1x2x1x2x3XXji, 相关系数相关系数 为为xi xj的均值的均值注意：在求相关系数之前，要将数据标准化注意：在求相关系数之前，要将数据标准化3. 分类的主观性和客观性分类的主观性和客观性 分类带有主观性：目的不同，分类不同。例如：鲸鱼，分类带有主观性：目的不同，分类不同。例如：鲸鱼，牛，马从

22、生物学的角度来讲都属于哺乳类，但是从产牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。 分类的客观性：科学性分类的客观性：科学性判断分类必须有客观标准，因此分类是追求客观性的，判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。但主观性也很难避免，这就是分类的复杂性。nknkjkjikinkjkjikiXXXXXXXXrij11221jiXX,四四.特征的生成特征的生成 (特征是决定相似性与分类的关键特征是决定相似性与分类的关键) 1.低层特征：低层特征： 无序尺度：有明确

23、的数量和数值。无序尺度：有明确的数量和数值。 有序尺度：有先后、好坏的次序关系，如酒有序尺度：有先后、好坏的次序关系，如酒 分为上，中，下三个等级。分为上，中，下三个等级。 名义尺度：无数量、无次序关系，如有红，名义尺度：无数量、无次序关系，如有红， 黄两种颜色黄两种颜色 2. 中层特征：经过计算，变换得到的特征中层特征：经过计算，变换得到的特征 3. 高层特征：在中层特征的基础上有目的的经过运高层特征：在中层特征的基础上有目的的经过运 算形成算形成例如：椅子的重量例如：椅子的重量=体积体积*比重比重 体积与长，宽，高有关；比重与材料，纹理，颜体积与长，宽，高有关；比重与材料，纹理，颜色有关。

24、这里低、中、高三层特征都有了。色有关。这里低、中、高三层特征都有了。五五.数据的标准化数据的标准化 1.极差标准化，一批样本中，每个特征的最大值极差标准化，一批样本中，每个特征的最大值与最小值之差。与最小值之差。 极差极差 极差标准化极差标准化 2. 方差标准化方差标准化 Si 为方差为方差标准化的方法很多，原始数据是否应该标准化，应采用标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。什么方法标准化，都要根据具体情况来定。ijijiXXRminmaxiiijRXXXijiiijSXXXij1 1、 对象具有显著的特征（对象具有显著的特征（可观察性）可观察性

25、） 对象在经过一定的处理之后能提取出部分显著对象在经过一定的处理之后能提取出部分显著的特征，这些特征可以描述该对象，或者以此的特征，这些特征可以描述该对象，或者以此将该对象区别与其他的对象将该对象区别与其他的对象, ,用特征向量来表用特征向量来表示特征示特征。2 2、 对象具有逻辑可分性（对象具有逻辑可分性（可区分性）可区分性） 从逻辑上可以依据一定的标准将对象划分成不从逻辑上可以依据一定的标准将对象划分成不同的类别，依据的标准可能与对象特征密切联同的类别，依据的标准可能与对象特征密切联系，划分的方法又直接关系到分类方法的正确系，划分的方法又直接关系到分类方法的正确程度，划分方法又可能从已有的

26、一部分样本来程度，划分方法又可能从已有的一部分样本来进行归纳得到。进行归纳得到。3 3、 统计意义上的最优性（源于统计意义上的最优性（源于相似性）相似性） 对象或者说是待分类的样本总体数目可对象或者说是待分类的样本总体数目可能无限大，有时候无法求得对所有的样能无限大，有时候无法求得对所有的样本进行精确分类，这个时候只是需要统本进行精确分类，这个时候只是需要统计意义上的最优，或者错误率最低则可。计意义上的最优，或者错误率最低则可。 模式识别系统的目标：在模式识别系统的目标：在特征空间特征空间和和分分类空间类空间之间找到一种之间找到一种归属关系映射映射，这这种映射也称之为种映射也称之为分类。特征空

27、间：从模式得到的对分类有用的度量、特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。属性或基元构成的空间。分类空间：将分类空间：将c个类别表示为个类别表示为其中其中 为所属类别的集合，称为分类空间。为所属类别的集合，称为分类空间。 X1、 X2 、 X3 、Xn 1、 2、 、 c1 判别函数 作为模式识别，模式分类的依据，从作为模式识别，模式分类的依据，从数值上划分模式。判别函数，有线性函数值上划分模式。判别函数，有线性函数和非线性函数，模式空间（或者模式数和非线性函数，模式空间（或者模式特征空间）特点决定了判别函数的得来特征空间）特点决定了判别函数的得来和特征以及表达形式。这也

28、是我们这门和特征以及表达形式。这也是我们这门课程研究的一个重点。将在不同的情形课程研究的一个重点。将在不同的情形确定判别函数，并且深入讨论它的特性。确定判别函数，并且深入讨论它的特性。 2 监督分类和非监督分类监督分类和非监督分类 监督类监督类( (Supervised)Supervised)分类方法分类方法：依靠已知所：依靠已知所属类别的训练样本集合，按照他们特征向属类别的训练样本集合，按照他们特征向量的分布来确定判别函数，只有判别函数量的分布来确定判别函数，只有判别函数确定之后才能用它来对未知的模式进行分确定之后才能用它来对未知的模式进行分类判别。类判别。 要求：进行大量的测试、实验、提炼

29、、要求：进行大量的测试、实验、提炼、统计得到足够的先验知识。作为确定判别统计得到足够的先验知识。作为确定判别函数的基础。并且要有足够的样本。函数的基础。并且要有足够的样本。3 监督分类和非监督分类监督分类和非监督分类 非监督（非监督（Unsupervised）分类方法分类方法：没有：没有(足够的足够的)先验知识，而是基于先验知识，而是基于“物以类聚物以类聚”的出发点，通过聚类分析，将模式特征的出发点，通过聚类分析，将模式特征相近的划分成一类，在特征空间相距比相近的划分成一类，在特征空间相距比较近的一些模式归为一类。较近的一些模式归为一类。 目标：用某种相似性度量的方法将原始数目标：用某种相似性

30、度量的方法将原始数据组织成有意义的和有用的各种数据集。据组织成有意义的和有用的各种数据集。4 统计模式识别统计模式识别 以模式集合的样本在特征空间中表现出随机性，以模式集合的样本在特征空间中表现出随机性，我们只能根据类的分布概率密度函数为基础，我们只能根据类的分布概率密度函数为基础，来确定判别函数，以某一个置信度来分类模式。来确定判别函数，以某一个置信度来分类模式。（1 1） 参数方法参数方法 已知概率密度函数的参数和表达形式，或已知概率密度函数的参数和表达形式，或者通过样本训练学习能估计出类的概率密度函者通过样本训练学习能估计出类的概率密度函数的近似表达式。数的近似表达式。（2 2） 非参数

31、方法非参数方法 在没有概率密度函数或者也估计不出概率密度在没有概率密度函数或者也估计不出概率密度函数的情况下，就无法利用概率密度函数来计算判函数的情况下，就无法利用概率密度函数来计算判别函数。按我们教材上的说法：凡是不采用某种概别函数。按我们教材上的说法：凡是不采用某种概率密度函数的估计参数来确定判别函数的，都可以率密度函数的估计参数来确定判别函数的，都可以归之为非参数方法。那么，归之为非参数方法。那么， (i) 绕过概率密度函数直接确定判别函数（或绕过概率密度函数直接确定判别函数（或者判函数的形式，再通过训练样本来确定参数）者判函数的形式，再通过训练样本来确定参数） (ii) 最邻近的原则分

32、类。最邻近的原则分类。 l19名男女同学进行体检，测量了身高和名男女同学进行体检，测量了身高和体重，但事后发现其中有体重，但事后发现其中有4人忘记填写人忘记填写性别，试问（在最小错误的条件下）这性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：人是男是女？体检数值如下：待识别的模式：性别（男或女）待识别的模式：性别（男或女）测量的特征：身高和体重测量的特征：身高和体重训练样本：训练样本：15名已知性别的样本特征名已知性别的样本特征目标：希望借助于训练样本的特征建立判目标：希望借助于训练样本的特征建立判别函数（即数学模型）别函数（即数学模型）l由训练样本得到的特征空间分布图由训练样本

33、得到的特征空间分布图l从图中训练样本的分布情况，找出男、从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。一个判别函数（直线或曲线）。l只要给出待分类的模式特征的数值，看只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。就可以判别是男还是女了。5 句法模式识别 对象从结构上由多个部分组成，依据对象从结构上由多个部分组成，依据文法理论和句式结构，判断组成部分之文法理论和句式结构，判断组成部分之间的结构关系，通过该关系达到分类对间的结构关系

34、，通过该关系达到分类对象集合。象集合。 l问题：如何利用对图像的结构信息描述，问题：如何利用对图像的结构信息描述，识别如下所示图片：识别如下所示图片：l将整个场景图像结构分解成一些比较简单的将整个场景图像结构分解成一些比较简单的子图像子图像(subimage)的组合；的组合；l子图像又用一些更为简单的基本图像单元子图像又用一些更为简单的基本图像单元(item ,element)来表示，直至子图像达到了我来表示，直至子图像达到了我们认为的最简单的图像单元（基元）；们认为的最简单的图像单元（基元）；l所有这些基元按一定的结构关系来表示，利所有这些基元按一定的结构关系来表示，利用多级树结构对其进行描

35、述（这种描述可以用多级树结构对其进行描述（这种描述可以采用形式语言理论）。采用形式语言理论）。l多级树描述结构多级树描述结构l训练过程：用已知结构信息的图像作为训练样本，先识别出基元（比如场景图中的X、Y、Z等简单平面）和它们之间的连接关系（例如长方体E是由X、Y和Z三个面拼接而成），并用字母符号代表之；然后用构造句子的文法来描述生成这幅场景的过程，由此推断出生成该场景的一种文法。l识别过程：先对未知结构信息的图像进行基元提取及其相互结构关系的识别；然后用训练过程获得的文法做句法分析；如果能被已知结构信息的文法分析出来，则该幅未知图像与训练样本具有相同的结构（识别成功），否则就不是这种结构（识

36、别失败）。形式语言和文法理论形式语言和文法理论 自然语言：人们平时说话时所使用的一种语言，：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。不同的国家和民族有着不同的语言。 形式语言：形式化描述的字母表上的字符串的：形式化描述的字母表上的字符串的集合。通过人们公认的符号，表达方式所描述集合。通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之分。的一种语言，是一种通用语言，没有国籍之分。形式语言是某个字母表上的字符串的集合，有形式语言是某个字母表上的字符串的集合，有一定的描述范围一定的描述范围. .字母表：字符的有限集合。：字符的有限集合。e.g.e.g.：

37、2626个英个英文字母构成的字母表。文字母构成的字母表。字符串：字母表中的字符构成的有限序列。：字母表中的字符构成的有限序列。e.g. hello, afjhkfyue.g. hello, afjhkfyu形 式 语 言 的 最 初 起 因 ： 语 言 学 家语 言 学 家（ChomskyChomsky）想用一套形式化方法来描述想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。在计算机科学中得到广泛应用。最初的应用：编译，：编译， 让计算机按照语法规则将让计算机按照语法规则将高级语言方便地翻译成机器语言。高级语言方便地翻

38、译成机器语言。现在： 已广泛应用在人工智能、图像处理、通已广泛应用在人工智能、图像处理、通信协议、通信软件等多个领域信协议、通信软件等多个领域在计算机理论科学方面：是可计算理论（算法：是可计算理论（算法在有限步骤内求得解、算法复杂性、停机问在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。生成）、模式识别等的基础。 补充：有的文献上对模式识别的分类方补充：有的文献上对模式识别的分类方法不太一样。如可以分成这样几个大类法不太一样。如可以分成这样几个大类: : （1 1）统计决策：）统计决策：依据概率论数

39、理统计的依据概率论数理统计的知识，研究对象的特征向量，并以此来知识，研究对象的特征向量，并以此来分类，常用的方法有几何分类（线性分分类，常用的方法有几何分类（线性分类、非线性分类）、统计分类（类、非线性分类）、统计分类（BayesBayes）决策、无教师分类（聚类分析）。决策、无教师分类（聚类分析）。（2 2）句法结构：）句法结构：依据形式语言和自动机技术等依据形式语言和自动机技术等理论研究符号串、树、图的关系，并以此来分理论研究符号串、树、图的关系，并以此来分类，常用的分类方法有自动机技术、类，常用的分类方法有自动机技术、CYKCYK剖析剖析算法、算法、EarlyEarly算法、转移图法。算

40、法、转移图法。（3 3）模糊判决）模糊判决 ：依据模糊数学的理论，建立模依据模糊数学的理论，建立模糊集合和模糊关系，用隶属度将模糊集合划分糊集合和模糊关系，用隶属度将模糊集合划分为若干子集，再根据择近原则分类。关键的就为若干子集，再根据择近原则分类。关键的就是隶属度函数的设计，通常有这样几种方法：是隶属度函数的设计，通常有这样几种方法：模糊统计法、二元对比排序法、推理法等模糊统计法、二元对比排序法、推理法等（4 4）逻辑推理：）逻辑推理：依据演绎逻辑和布尔代数的相依据演绎逻辑和布尔代数的相关理论，从事实出发运用一系列规则，推理得关理论，从事实出发运用一系列规则，推理得到不同的结果，以此达到分类

41、的目的。产生式到不同的结果，以此达到分类的目的。产生式推理、语义网推理、框架推理。推理、语义网推理、框架推理。（5 5）神经网络：）神经网络：依据神经生理学、心理学中的依据神经生理学、心理学中的一些原理来进行分类。这些原理就是阐述人类一些原理来进行分类。这些原理就是阐述人类在学习、记忆、推理等活动中的关系和规则。在学习、记忆、推理等活动中的关系和规则。通过对样本的学习建立起记忆，然后将为止模通过对样本的学习建立起记忆，然后将为止模式判决为其最接近的记忆。式判决为其最接近的记忆。总结：总结： 这种分类方法很明了，利用某一方面的概念、这种分类方法很明了，利用某一方面的概念、理论来描述对象、以此达到

42、分类识别的目的，理论来描述对象、以此达到分类识别的目的，有一种为了理论而模式识别的感觉。有一种为了理论而模式识别的感觉。 NOTE:NOTE:我们是面向问题的而不是面向知识和理我们是面向问题的而不是面向知识和理论的，我们要发现问题，为寻求解决问题而建论的，我们要发现问题，为寻求解决问题而建立相关的理论，寻求解决问题的方法。立相关的理论，寻求解决问题的方法。（1） 随机向量随机向量l如果一个对象的特征观察值为如果一个对象的特征观察值为x1, x2, , xn，它它可构成一个可构成一个n维的特征向量值维的特征向量值x，即即X= (x1, x2, , xn)T 式中，式中， x1, x2, , xn

43、为特征向量为特征向量X的各个分量。的各个分量。l一个特征可以看作一个特征可以看作n维空间中的向量或点，此空维空间中的向量或点，此空间称为模式的特征空间间称为模式的特征空间Rn。随机向量随机向量l在模式识别过程中，要对许多具体对象进行测量，在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。以获得许多次观测值。l每次观测值不一定相同，所以对许多对象而言，每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，即许多对象的特征各个特征分量都是随机变量，即许多对象的特征向量在向量在n维空间中呈随机性分布，称为随机向量。维空间中呈随机性分布，称为随机向量。分布函数分布函数密度函数密度函数随机向量的参数随机向量的参数l数学期望数学期望l协方差矩阵协方差矩阵l自相关矩阵自相关矩阵l协方差正定性协方差正定性l正态分布正态分布一维正态密度函数一维正态密度函数222)(exp21)(mxxpP(x)N(0,1.5)l正态分布多维正态密度函数不相关与独立性边界密度函数、条件概率密度函数。马氏平方 )()(),(12mxCmxCmxdt定义 称为X到m的马氏距离平方 l密度函数的变换和雅克比行列式)(XgY ),(),(11121nnnxxgxxgYYYJxpyp)()(nnnn