模式识别第1章

1、模式识别关于本课程的有关说明 相关学科相关学科 教学方法教学方法 教学目标教学目标 基本要求基本要求 教材教材/ /参考文献参考文献统计学统计学概率论概率论线性代数（矩阵计算）线性代数（矩阵计算）形式语言形式语言人工智能人工智能图像处理图像处理计算机视觉计算机视觉等等等等 相关学科 教学方法着重讲述模式识着重讲述模式识别的基本概念，基别的基本概念，基本方法和算法原理。本方法和算法原理。注重理论与实践注重理论与实践紧密结合紧密结合 实例教学：通过实例教学：通过实例讲述如何将所实例讲述如何将所学知识运用到实际学知识运用到实际应用之中应用之中避免引用过多的、避免引用过多的、繁琐的数学推导繁琐的数学推

2、导 教学目标掌握模式识别的掌握模式识别的基本概念和方法基本概念和方法有效地运用所学有效地运用所学知识和方法解决实知识和方法解决实际问题际问题为研究新的模式为研究新的模式识别的理论和方法识别的理论和方法打下基础打下基础 基本要求基本：完成课程习基本：完成课程习通过考试，获得学分。通过考试，获得学分。提高：能够将所知提高：能够将所知和内容用于课题究决和内容用于课题究决实际问题。实际问题。飞跃：通过模式的飞跃：通过模式的学习，改进思维式为学习，改进思维式为将来的工作打好础终将来的工作打好础终身受益。身受益。边肇祺边肇祺.模式识别模式识别.清华大学出版社清华大学出版社孙即祥孙即祥.现代模式识别现代模式

3、识别.国防科技出版社国防科技出版社 罗耀光罗耀光,盛立东盛立东.模式识别模式识别.人民邮电出版社人民邮电出版社付京荪付京荪.模式识别及应用模式识别及应用.科学出版社科学出版社Richard O. Duda et al ，Pattern Classification.(2nd version,中、英版），中、英版），机械工业出版社机械工业出版社 K.S.Fu .Syntactic Pattern Recognition and Application J.T.Tom R.C. Gouzales.Pattern Recognition Principles 教材教材/参考文献参考文献引引 言言模式

4、识别的发展模式识别的发展n1929年 G. Tauschek发明阅读机 ，能够阅读0-9的数字。n30年代 Fisher提出统计分类理论,奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。随着计算机运算速度的迅猛发展，这个问题得到一定克服。目前，统计模式识别仍是模式识别的主要理论。n50年代 Noam Chemsky 提出形式语言理论，在此基础上，美籍华人付京荪 提出句法结构模式识别。n60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。80年代 Hopfield提出神经元网络模型理

5、论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。90年代 小样本学习理论，支持向量机也受到了很大的重视。1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”，成立了国际模式识别协会-“IAPR”，每2年召开一次国际学术会议；1977年 IEEE的计算机学会成立了模式分析与机器智能（PAMI）委员会，每2年召开一次模式识别与图象处理学术会议；国内的组织有电子学会，通信学会，自动化协会，中文信息学会.。模式识别的应用领域更加广泛：模式识别的应用领域更加广泛： 生物、医学、军事、农业、工业、社会、教育、航天、航空、经济、金融、生物认证、数字水印基于语音： 重点人物通信监

6、控语音识别系统/规模音频资料检索基于图像： 光学字符识别(Optical Character Recognition OCR)/车牌识别(Vehicle License Plate Recognition VLPR)/人脸识别/指纹识别/签名认证/支票认证/表情和手势识别/农作物分类与害虫识别/生物信息学：DNA识别/航空与卫星遥测遥感数据资源调查/军用目标的图像识别/基于图形模式识别的机器人控制等基于工程数据： 振动模式分析与故障诊断/石油钻井数据分析与事故预报/基于状态模式的智能控制/数据挖掘与知识发现等n模式识别的计算手段更加先进：模式识别的计算手段更加先进： 海量存储技术、高速计算/并

7、行计算技术、 网格技术、网络技术、 新型前端器件(激光、红外、MEMS、传感器网络)n模式识别的新型算法层出不穷：模式识别的新型算法层出不穷： Computation with word(Zadeh) Soft Computation DNA Computationn国内外模式识别的学术活动从未间断国内外模式识别的学术活动从未间断: 小波/模式识别国际会议、机器学习/模式识别国际会议、图像处理/模式识别国际会议、数据挖掘/模式识别国际会议第1章 绪论例子例子1 1：医生诊病过程：医生诊病过程 1)测量病人的体温和血压，化验血沉，询问临床表现； 2)通过综合分析，抓住主要病症； 3)医生运用自己

8、的知识、经验，根据主要病症、测量化验结果，作出正确的诊断。n在模式识别技术中，常用的术语有：样本、模式、特征、类型等等，对照医生诊病过程，有：a.样本：医院里的众多患者，每个患者都是一个样本； 单一样本：医生诊断的某一患者，就是样本空间中的一个单一样本； 样本值：某一患者的化验、检查结果与表征现象。b.模式：各样本值按一定的数据准则综合的结果； 模式样本：具有某种模式的样本； 模式采集：获取某样本的测量数值的过程；医生诊病过程医生诊病过程c.特征：患者某些具有显著特征的化验数据及表征； 特征选择与提取：能表征(疾病)特异性的化验结果与表征；d.判决：医生运用知识、病例经验综合分析给出诊断； 判

9、决准则/规则：医生的知识 判决结果：将患者明确(或以概率)确定为某一种病症(或多种/并发病症)的患者(及病患严重程度)事实上，最后的结果也成为分类。因此有预先知道类别(已知病症)与未知类别(未知病症)的区别。模式识别：就是以计算机为工具、各种传感器为信息来源，数据计算与处理为方法，对各种现象、事物、状态等进行准确地分析、判断识别与归类。n人类在生产过程的长期发展中，辨别事物的能力逐渐增强，辨别事物的需求也逐渐扩大。尤其是近代，随着现代工业的飞速发展，辨别事物的能力逐渐发展为一项专门的技术，从20世纪初起，形成了专门的模式识别技术。n 从广义来说，模式识别是人类的基本活动。从狭义来说，模式识别是

10、专门对于机器识别而言的，或者说是基于数学的基本原理以及信息学的基本原理，利用计算机技术来完成的机器识别。n客观事物的主观(符号化)表征即为模式。n模式的概念源于分类学。作为一个抽象化的概念，它不是被识别对象的固有属性，而是人对被识别对象所加的主观标签。模式分类学的研究目的是基于特定的研究对象,寻找有效的描述方法,寻找对象固有的属性特征,寻找合理的数学方法,实现类别归属的确定。模式识别的几个主要关系：1.模式识别发展的动力是社会生产的需求2.分类类别的确定与确定类别的依据3.使用什么分类方法来完成分类目的以及所使用方法的评价n特征空间(描述空间,表示空间)n包含用以描述样本的特征向量的向量空间。

11、n决策空间(解释空间)n分类类别形成的集合.n寻找特征空间到决策空间的映射关系一、基本概念一、基本概念n模式识别模式识别(Pattern Recognition)(Pattern Recognition)：确定一个样本的类别属性确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类（模式类）的过程，即把某一样本归属于多个类型中的某个类型。型。n样本（样本（Sample)Sample)：一个具体的研究（客观）对象。如患者，某一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。人写的一个汉字，一幅图片等。n模式模式(Pattern)(Pattern)：对客体（研

12、究对象）特征的描述（定量的或对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。（或综合）。n特征特征(Features)(Features)：能描述模式特性的量（测量值）。在统计模能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量式识别方法中，通常用一个矢量 表示，称之为特征矢量，记表示，称之为特征矢量，记为为 n模式类模式类(Class)(Class)：具有某些共同特性的模式的集合。具有某些共同特性的模式的集合。x),(21nxxxx),(21nxxxx二、基本问题二、基本

13、问题模式模式(样本样本)表示方法表示方法模式类的紧致性描述模式类的相似性与度量模式类的特征描述空间映射的应用及其有效性准则函数的选择与其适用范围模式识别中的机器学习方法模式表示法模式表示法1.向量表示法向量表示法模式向量模式向量：以数量信息为特征的模式表示。即以模式的以数量信息为特征的模式表示。即以模式的n n个特征量测值组个特征量测值组成一个成一个n n维特征矢量维特征矢量 X=(xX=(x1 1,x,x2 2, ,x,xn n) )T T表示模式。表示模式。例：例：字符识别机，辨别每个输入，判断它是属于哪一种字符，字符识别机，辨别每个输入，判断它是属于哪一种字符，A AZ Z、0 09 9

14、、拒绝类，共、拒绝类，共26+10+1=3726+10+1=37个模式类。采用光电阵列把字符变成二值个模式类。采用光电阵列把字符变成二值的图象，如的图象，如6 66 6方阵，方阵，X=xX=x1 1x x2 2x x3 3x x3636 T T。 2. 2.矩阵表示矩阵表示N个样本，个样本，n个变量个变量(特征特征)3.几何表示几何表示一一维表示维表示 X1=0.5 X2=3 二维表示二维表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T三维表示三维表示 X1=(x1,x2,x3)T=(1,1,0)T X2=(x1,x2,x3)T=(1,0,1)T4. 4.符号串

15、表示法（符号串表示法（1 1）n定义了一定的模式基元，用模式基元的连接表示模式定义了一定的模式基元，用模式基元的连接表示模式。ba阶梯模式： ababab 即 (ab)n,n1符号串表示法（2）n定义算子定义算子, ,增加串的表示能力增加串的表示能力 baa+bbaabbaa*bbba模式基元：ba-bba5.树表示法n任何一个分层有序系统都导致树结构，引入任何一个分层有序系统都导致树结构，引入“在内部在内部”关系、关系、“由由组组成成”关系。关系。 abcdefghi$a$bcihgdfeR2R1R3T1T2墙（W）地板F立方体C锥体P锥体P$景物物体背景地板F墙W立方体CT1T2R1R2R

16、36.网表示法n网表示法：网是无向带标志的点图。在上图中，我们在引入网表示法：网是无向带标志的点图。在上图中，我们在引入“与与连接连接”，就可，就可以得到图所示的网。以得到图所示的网。 R2R1R3 T1 T2墙（W）地板F立方体C锥体P$景物物体背景地板F墙W锥体P立方体CT1T2R1R2R3模式类的紧致性描述为了保证分类的可行性,要求同类样本在描述空间中应尽可能地靠近,或者说同类样本是一个紧致集合.模式类的紧致性是就简单分类面还是复杂分类面而言的.1. 1. 紧致集：同一类模式类样本的分紧致集：同一类模式类样本的分布比较集中，没有临界样本或者布比较集中，没有临界样本或者临界样本很少，这样的

17、模式类称临界样本很少，这样的模式类称紧致集。紧致集。2. 2. 临界点临界点( (样本样本) )：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）临界样本（点）。3. 3. 紧致集的性质紧致集的性质 要求临界点很少要求临界点很少. . 集合内的任意两点的连线集合内的任意两点的连线, ,在线上的点属于同在线上的点属于同 一集合一集合. . 集合内的每一个点都有足够大的邻域集合内的每一个点都有足够大的邻域, ,在邻域内只包含同一集合的点在邻域内只包含同一集合的点. .4. 4. 模式识别的要求模式识别的要求: : 满

18、足紧致集，才能很好的分类；如果不满足紧致集，就要采取变满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法换的方法, ,满足紧致集满足紧致集. .模式类的相似性模式类的相似性用以确定不同样本是否同类.它是模式类上建立的一种相似关系.样本之间的相似程度可以通过计算样本距离而获得.常用的如欧氏距离,下降函数,向量夹角等,它们具有非负性,自反性,对称性,但不具有传递性.1. 1.两个样本两个样本 x xi i 和和 x xj j 之间的相似度量满足以下要求：之间的相似度量满足以下要求： 应为非负值。 样本本身相似性度量应最大。 度量应满足对称性。 在满足紧致性的条件下，相似性应该是点间距

19、离的单调函数。 2. 2. 用各种距离表示相似性：用各种距离表示相似性： 已知两个样本 xi=(xi1, xi2 , xi3,xin)T xj=(xj1, xj2 , xj3,xjn)T 常用的距离有欧氏距离、马氏距离等常用的距离有欧氏距离、马氏距离等3. 分类的主观性和客观性分类的主观性和客观性 分类的主观性：分类的主观性：目的不同，分类不同。例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。 分类的客观性：分类的客观性：科学性判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。模式类的特征模式类的特征是

20、从模式得到的对分类有用的度量,属性或者基元,在数学上特征的定义空间则称为特征空间.模式识别中的特征具有更加广泛的含义.在模式识别中,获取描述模式类的特征是关键的工作.所获特征是否有效,以及如何剔除与分类无关的特征均是特征研究中的重要问题(即特征提取与特征压缩).模式的特征空间表示模式的特征空间表示特征的分布特征的分布特征的生成特征的生成 1.低层特征：低层特征： 无序尺度：无序尺度：有明确的数量和数值. 有序尺度：有序尺度：有先后、好坏的次序关系，如酒分为上，中，下三个等级. 名义尺度：名义尺度：无数量、无次序关系，如有红，黄两种颜色. 2. 中层特征：中层特征：经过计算，变换得到的特征. 3

21、. 高层特征：高层特征：在中层特征的基础上有目的的经过运算形成. 例如：椅子的重量=体积*比重. 体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。模式识别的训练方法模式识别的训练方法v有监督学习有监督学习（有教师学习）：预先已知训练样本集合中每个样本的类别标号；v无监督学习监督学习（无教师学习）：预先不知道训练样本集合中每个样本的类别标号；统计识别方法的分类统计识别方法的分类v一、根据样本在空间中的几何分布进行分类 方法一：近邻法；方法二：判别函数法。v二、根据样本在空间中的概率分布进行分类贝叶斯分类器识别系统的设计步骤识别系统的设计步骤v收集样本 v确定识别特

22、征 v特征抽取 v特征分析v确定识别方法 v性能评价 v性能评价：v正确识别率 = 正确分类数/总数v错误识别率 = 错误分类数/总数v拒绝识别率 = 拒绝分类数/总数空间映射空间映射是解决特征空间与有效分类之间的桥梁.使用空间映射关系,可以将各种有效的数学方法应用于模式识别之中以解决分类问题.常用的空间映射方法:线性映射,傅立叶变换,DCT变换,沃尔什变换,K-L变换,非线性变换.数据的标准化数据的标准化ijijiXXRminmaxi jii jiXXXRi jii jiXXXS1.1.极差标准化极差标准化: :一批样本中，每个特征的最大值与最小值之差为极差。极差极差标准化2.2.方差标准化

23、：方差标准化： Si 为方差标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。准则函数的选择准则函数是用以解决分类问题的依据.对于具体的分类问题应选择合理的分类器设计方法与合理的准则函数,使得分类器的设计满足分类需要.各种准则函数都是在限定条件下被提出来,因此在实际使用中都有一定的局限性.机器学习方法即使用已知样本来训练分类器,使之达到希望的性能.各种分类器设计中,无一例外地使用了机器学习的方法.机器学习通过对样本信息的学习获得关于类别的知识,从而得到有效的分类器.三、各类空间（三、各类空间（Space)模模式式识识别别三三大大任任务务对象空间对象空间模式空

24、间模式空间特征空间特征空间类型空间类型空间模式采集：模式采集：从客观世界（对象从客观世界（对象空间）到模式空间的过程称为空间）到模式空间的过程称为模式采集。模式采集。特征提取和特征选择：特征提取和特征选择：由模式由模式空间到特征空间的变换和选择。空间到特征空间的变换和选择。类型判别：类型判别：特征空间到类型空特征空间到类型空间所作的操作。间所作的操作。四、模式识别系统数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识别结果数字化数字化比特流比特流预处理这个环节的内容预处理这个环节的内容很广泛，与要解决的具体很广泛，与要解决的具体问题有

25、关，例如，从图象问题有关，例如，从图象中将汽车车牌的号码识别中将汽车车牌的号码识别出来，就需要先将车牌从出来，就需要先将车牌从图像中找出来，再对车牌图像中找出来，再对车牌进行划分，将每个数字分进行划分，将每个数字分别划分开。做到这一步以别划分开。做到这一步以后，才能对每个数字进行后，才能对每个数字进行识别。以上工作都应该在识别。以上工作都应该在预处理阶段完成。预处理阶段完成。通常能描述对象的元素很多，通常能描述对象的元素很多，为节约资源和提高处理速度，有时为节约资源和提高处理速度，有时更为了可行性，在满足分类识别正更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽确率要求的条件下，按

26、某种准则尽量选用对正确分类识别作用较大的量选用对正确分类识别作用较大的特征。使得用较少的特征就能完成特征。使得用较少的特征就能完成分类识别任务。分类识别任务。分类识别是根据事先确定的分分类识别是根据事先确定的分类规则对前面选取的特征进行分类规则对前面选取的特征进行分类（即识别）。类（即识别）。40数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识别结果数据采集数据采集特征提取特征提取改进分类改进分类识别规则识别规则二次特征提二次特征提取与选择取与选择训练训练样本样本改进采集改进采集提取方法提取方法改进特征提改进特征提取与选择取与选择制

27、定改进分制定改进分类识别规则类识别规则人工人工干预干预正确率正确率测试测试模式识别系统的主要环节：模式识别系统的主要环节：特征提取：特征提取：符号表示，如长度、波形、。符号表示，如长度、波形、。特征选择：特征选择：选择有代表性的特征，能够正确分类选择有代表性的特征，能够正确分类学习和训练：学习和训练：利用已知样本建立分类和识别规则利用已知样本建立分类和识别规则分类识别：分类识别：对所获得样本按建立的分类规则进行对所获得样本按建立的分类规则进行分类识别分类识别五、模式识别的方法五、模式识别的方法n决策理论方法（统计识别法）：以判别函数为基础，利用判别函数对模式决策理论方法（统计识别法）：以判别函

28、数为基础，利用判别函数对模式进行分类。进行分类。n句法模式识别（结构模式识别）：将对象分解为若干个基本单元句法模式识别（结构模式识别）：将对象分解为若干个基本单元基元，基元，用基元和他们的结构关系描述对象，运用形式语言理论进行句法分析，根用基元和他们的结构关系描述对象，运用形式语言理论进行句法分析，根据其是否符合某一类的文法而决定其类别。据其是否符合某一类的文法而决定其类别。n模糊模式识别：运用模糊数学的理论和方法解决模式识别问题，适用于分模糊模式识别：运用模糊数学的理论和方法解决模式识别问题，适用于分类识别对象本身或要求的识别结果具有模糊性的场合。类识别对象本身或要求的识别结果具有模糊性的场

29、合。n人工神经网络法：是由大量简单的神经元相互连接而构成的非线性动态系人工神经网络法：是由大量简单的神经元相互连接而构成的非线性动态系统，具有学习、自组织、联想能力，在学习中具有自动提取特征，进行识统，具有学习、自组织、联想能力，在学习中具有自动提取特征，进行识别、决策。别、决策。n人工智能方法：人工智能研究如何使机器具有人工智能方法：人工智能研究如何使机器具有人脑功能的理论和方法。将人脑功能的理论和方法。将学习、知识表示、推理等用于模式识别。学习、知识表示、推理等用于模式识别。统计模式识别统计模式识别n统计模式识别：是以决策函数为基础，对模式向量进行分类。例w1,w2判别函数：d(X)=w1x1+w2 x 2+