《模式识别概论》PPT课件.ppt

教材和参考书:,边肇祺.模式识别.清华大学出版社孙即祥.现代模式识别.国防科技出版社 罗耀光,盛立东.模式识别.人民邮电出版社付京荪.模式识别及应用.科学出版社Richard O.Duda et al，Pattern Classification.(2nd version,中、英版），机械工业出版社.Syntactic Pattern Recognition and Application R.C.Gouzales.Pattern Recognition Principles,模式识别导论,编程试验：matlab作业：课后作业题考试/考査：书面考试/写小论文，结合平时成绩,第一章 概论1-1 模式识别的基本概念,一、模式识别的基本定义 样本指待处理的个体。（有时称为模式）模式指一类样本所构成的集合中所有样本的共同特性。（有时又称模式类）模式(pattern)存在于时间，空间中可观察的事物。具有时间或空间分布的信息。模式识别(Pattern Recognition)-用计算机实现人对各种事物或现象的分析,描述,判断,识别。,模式识别系统：模拟人的视觉:计算机+光学系统 模拟人的听觉:计算机+声音传感器 模拟人的嗅觉和触觉:计算机+传感器 模式识别与图象识别、图象处理的关系 模式识别是模拟人的某些功能模式识别系统的组成在后面再做详细的介绍。,二、模式识别的发展史,1929年 G.Tauschek发明阅读机，能够阅读0-9的数字。30年代 Fisher提出统计分类理论,奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。,50年代 Noam Chemsky 提出形式语言理论 美籍华人付京荪 提出句法结构模式识别。60年代 提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。80年代 Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。90年代 小样本学习理论，支持向量机也受到了很大的重视。,三、关于模式识别的国内、国际学术组织,1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”，成立了国际模式识别协会-“IAPR”，每2年召开一次国际学术会议。1977年 IEEE的计算机学会成立了模式分析与机器智能（PAMI）委员会，每2年召开一次模式识别与图象处理学术会议。国内的组织有电子学会，通信学会，自动化协会，中文信息学会.。,1-2 模式识别系统,信息的获取：是通过传感器，将光或声音等信息转化为电信息。信息可以是二维的图象如文字，图象等；可以是一维的波形如声波，心电图，脑电图；也可以是物理量与逻辑值。预处理：包括A/D,二值化，图象的平滑，变换，增强，恢复，滤波等,主要指图象处理。,特征抽取和选择：在模式识别中，需要进行特征的抽取和选择，例如，一幅6464的图象可以得到4096个数据，这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。分类决策：在特征空间中对被识别对象进行分类。,1-3 模式识别的应用,1.字符识别：包括印刷体字符的识别；手写体字符的识别（脱机），各种OCR设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入；在线手写字符的识别（联机），各种书写输入板。2.医疗诊断：心电图，脑电图，染色体，癌细胞识别，疾病诊断，例如关幼波肝炎专家系统。3.遥感：资源卫星照片，气象卫星照片处理，数字化地球，图象分辨率可以达到1米。,4.指纹识别、脸形识别5.检测污染分析：大气，水源，环境监测。6.自动检测：产品质量自动检测7.语声识别、机器翻译：电话号码自动查询，侦听，机器故障判断。8.军事应用,1-4 模式识别的基本问题,一、模式(样本)表示方法向量表示:假设一个样本有n个变量(特征)x=(x1,x2,xn)T2.矩阵表示:N个样本，n个变量(特征),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,0)T X2=(x1,x2,x3)T=(1,0,1)T,x1,x2,x3,x1,x2,4.基元（链码）表示：在右侧的图中八个基元分别表示:0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为 X1=006666这种方法将在句法模式识别中用到。,二、模式类的紧致性,1.紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。,2.临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。3.紧致集的性质 要求临界点很少 集合内的任意两点的连线,在线上的点属于同一集合 集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点4.模式识别的要求:满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法,满足紧致集.,三、相似与分类,1.两个样本Xi，Xj之间的相似度量满足以下要求：应为非负值 样本本身相似性度量应最大 度量应满足对称性 在满足紧致性的条件下，相似性应该是点间距离的单调函数,距离值越小，相似性越高,如果用dij表示第i个样本和第j个样本之间的距离，那么对一切i，j和k，dij应该满足如下四个条件：当且仅当i=j时，dij=0dij0dijdji（对称性）dijdikdkj（三角不等式）,距离度量,2.用各种距离度量相似性：已知两个样本：Xi=(xi1,xi2,xi3,xin)T Xj=(xj1,xj2,xj3,xjn)T,绝对值距离(街坊距离或Manhattan距离）：,欧几里德(Euclidean)距离明考夫斯基(Minkowski)距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离,其中Xi，Xj为特征向量，为协方差矩阵。使用于N个样本的集合中两个样本之间求M氏距离：,切比雪夫(Chebyshev)距离：,是q趋向无穷大时明氏距离的极限情况,马哈拉诺比斯（Mahalanobis)距离,N样本个数,例：马哈拉诺比斯（Mahalanobis)距离：,设X1=（0,0)T,X2=（0,1)T,X3=（1,0)T,X4=（1,1)T.则N=4，,两点之间的马氏距离,两点之间的欧氏距离,都具对称性。但数值不同。欧氏距离的计算步骤：1.求样本均值；2.求协方差矩阵；3.求协方差矩阵的逆矩阵；4。按公式求两点间马氏距离。,即样本间夹角小的具有相似性强。例：X1,X2,X3的夹角如图：因为X1,X2 的夹角小，所以X1,X2 最相似。,夹角余弦,如：1，3，5，7，9与2，4，6，8，10的相关系数为1；1，3，5，7，9与10，8，6，4，2的相关系数为-1；注意：在求相关系数之前，要将数标准化,*相关系数,分别为Xi,Xj的均值:,其中，Xi=(xi1,xi2,xin),Xj=(xj1,xj2,xjn).,3.分类的主观性和客观性 分类带有主观性：目的不同，分类不同。例如：鲸鱼、牛、马从生物学的角度来讲都属于哺乳类;但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。分类的客观性：科学性 判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。,四、特征的生成 1.底层特征：（1）数值尺度（numerical size）：有明确的数量和数值。（2）非数值尺度（non-numerical size)有序尺度：有先后、好坏的次序关系，如酒 分为上，中，下三个等级。名义尺度(nominal)：无数量、无次序关系，如颜色：红、黄、蓝、黑 2.中层特征：经过计算，变换得到的特征 3.高层特征：在中层特征的基础上有目的的经过运 算形成 例：椅子的重量=体积*比重；（比重与材料有关）体积与长，宽，高有关；这里低、中、高三层特征都有了。,五、数据的标准化 标准化的方法很多，这里介绍几个基本的：1.极差:一批样本中，每个特征的最大值与最小值之差。极差 2.极差标准化 3.方差标准化 Si 为标准方差(统计量）原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。,Xi=(xi1,xi2,xin),例1：19人进行体检，结果如下表。但事后发现4人忘了写性别，试问，这4人是男是女？,M,M,F,F,解：试验样本是人，分为男、女两个类别。主要特征身高、体重构成二维特征空间。已知15人的性别，可以作为训练样本，其值确定他们在特征空间的位置。,男,女,图中，男性集中于右上方，女性集中于左下方，这就是聚类性质。采用数理统计方法，可在两个性别之间描绘一条曲线，它是特征x1（身高）、x2（体重）的函数。可以确定：，则；若，则 其中，x=(x1,x2)T是向量，称为模式向量。g(x1,x2)=0描绘的曲线称为分界线。现考察1619号体检者，由身高、体重确定在上图中的位置。显然，16、19在负线一侧，判定他们为女性。17、18位于正线一侧，判为男性。上述判决方法使分类错误率最小。,例2：如下图中一幅图形，要识别图中的物体，选用句法模式识别方法,景物,解：图形结构复杂，首先应分解为简单的子图（背景、物体）。背景由地板和墙组成，物体为长方体和三角体。三角体又分为1个长方形面和1个三角形面。长方体又分为3个长方形面。上述分析构成一个多级树结构：,其中，面、三角形、地板和墙壁，即L、T、X、Y、Z、M和N均为基本图形单元，简称基元。在句法模式识别中，基元就是特征。,句法模式识别的方法：在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入的景物属于相应的类型。,1.5 模式识别的方法,模版匹配法(template matching)统计方法(statistical pattern recognition)神经网络方法(neural network)结构方法(句法方法)(structural pattern recognition),模版匹配,首先对每个类别建立一个或多个模版输入样本和数据库中每个类别的模版进行比较，例如求相关或距离根据相似性（相关性或距离）大小进行决策优点：直接、简单缺点：适应性差扩展：弹性模版法,方法,统计方法,根据训练样本，建立决策边界(decision boundary)统计决策理论根据每一类总体的概率分布决定决策边界判别式分析方法给出带参数的决策边界，根据某种准则，由训练样本决定“最优”的参数本课程的重点内容,方法,句法方法,许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元”每个模式都可由基元根据一定的关系来组成基元可以认为是语言中的词语，每个模式都可以认为是一个句子，关系可以认为是语法模式的相似性由句子的相似性来决定优点：适合结构性强的模式缺点：抗噪声能力差，计算复杂度高,方法,神经网络,进行大规模并行计算的数学模型具有学习、推广、自适应、容错、分布表达和计算的能力优点：可以有效解决一些复杂的非线性问题缺点：缺少有效的学习理论,方法,几种方法比较,方法,神经网络和统计模式识别的关系,方法,本章小结,模式识别的基本概念：样本、模式、模式识别系统、特征抽取和选择距离：绝对值、欧式、闵氏、马氏等相似性和相关性数据规范或标准化,习题,试简述样本，模式和模式类等概念间的关系。试简述模式识别系统的主要组成部分。试简述先验概率，类条件概率密度函数和后验概率等概念间的关系。,