模式识别剖析课件

模式识别基础参考书籍n模式识别模式识别 清华大学出版社清华大学出版社 边肇祺边肇祺n模式识别及应用模式识别及应用 科学出版社科学出版社 付京荪付京荪nPattern Classification Richard O.Duda,Peter E.Hart,David G.StorknSyntactic Pattern Recognition and Application K.S.Fu nPattern Recognition Principles J.T.Tom R.C.Gouzales主要期刊和会议nIEEE Trans.On PAMI,NNnPattern RecognitionnPattern Recognition LetternMachine LearningnNeural Computationn模式识别与人工智能nCVPR、ICPR、ICML、COLT、NIPS实验安排n第6，8，12，14，16周周四下午。n扬帆楼201。考试n期末考试（60分）n开卷；n平时成绩 （40分）n实验：20分；n作业：10分；n出勤：5分；n小测：5分。第一章 概述 1-1 模式识别的基本概念模式识别的基本概念模式模式(pattern)-存在于时间，空间中可观察的事物，具有时间或空间分布的信息。Watanabe defines a pattern“as opposite of a chaos;it is an entity,vaguely defined,that could be given a name.”第一章 概述 1-1 模式识别的基本概念模式识别的基本概念第一章 概述 1-1 模式识别的基本概念模式识别的基本概念第一章 概述 1-1 模式识别的基本概念模式识别的基本概念第一章 概述 1-1 模式识别的基本概念模式识别的基本概念第一章 概述 1-1 模式识别的基本概念模式识别的基本概念n听觉听觉 n嗅觉嗅觉n触觉触觉第一章 概述 1-1 模式识别的基本概念模式识别的基本概念n识别（识别（Recognition）n识别是时时刻刻发生的识别是时时刻刻发生的n识别（识别（Recognition)再认知（再认知（Re-Cognition)n主要研究相似和分类问题主要研究相似和分类问题n有监督分类有监督分类n有训练样本情况下的模式识别。有训练样本情况下的模式识别。n无监督分类无监督分类n没有训练样本情况下的模式识别。没有训练样本情况下的模式识别。第一章 概述 1-1 模式识别的基本概念模式识别的基本概念模式识别模式识别(Pattern Recognition)-用计算机实现人对各种事物或现象的分析、描述、判断、识别。Pattern recognition is the study of how machines can observe the environment,learn to distinguish patterns of interest from their background,and make sound and reasonable decisions about the categories of the patterns.(Anil K.Jain)第一章 概述 1-1 模式识别的基本概念模式识别的基本概念n与其他学科的关系n统计学n人工智能n机器学习n运筹学第一章 概述 1-1 模式识别的基本概念模式识别的基本概念n基本概念n识别（Recognition）n决策（Decision）n学习（Learning）nGeneralization第一章 概述 1-1 模式识别的基本概念模式识别的基本概念nGeneralizenTo reduce to a general form,class,or law.n使一般化赋予一普遍形式、种类或定制nTo render indefinite or unspecific.n使概括使不确定或不具体nTo infer from many particulars.n概括出，归纳从许多特殊事物中推论nTo draw inferences or a general conclusion from.n概括从中得出推论或一普遍结论nTo make generally or universally applicable.n使普遍适用，使全球适用nTo popularize.n推广第一章 概述 1-2 模式识别系统模式识别系统n信息的获取：是通过传感器，将光或声音等信息转化为计算机可以运算的符号来表示所研究的对象。n二维的图像，如文字、图片等；n一维的波形，如声波、心电图、脑电图；n物理量与逻辑值，如身高、体重、性别等。第一章 概述 1-2 模式识别系统模式识别系统n预处理：去除噪声，加强有用的信息，并对输入测量仪器或其他因素所造成的退化现象进行复原。n包括AD,二值化，图像的平滑，变换，增强，恢复，滤波等,主要指图像、信号处理第一章 概述 1-2 模式识别系统模式识别系统n特征提取和选择：例如，一幅64x64的图象可以得到4096个数据。在模式识别中，为了有效地实现分类识别，需要对原始数据进行变换，得到最能反映分类本质的特征。这就是特征提取和选择的过程。n测量空间：原始数据组成的空间n特征空间：分类识别赖以进行的空间第一章 概述 1-2 模式识别系统模式识别系统n分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。第一章 概述 1-2 模式识别系统模式识别系统n分类决策：在特征空间中对被识别对象进行分类，用统计方法把被识别对象归为某一类别。第一章 概述 1-2 模式识别系统模式识别系统n例子医生诊病过程 1)测量病人的体温和血压，化验血液，询问临床表现；2)通过综合分析，抓住主要病症；3)医生运用自己的知识、经验，根据主要病症、测量化验结果，作出正确的诊断。在模式识别技术中，常用的术语有：样本、模式、特征、类型等等，对照医生诊病过程，有：第一章 概述 1-2 模式识别系统模式识别系统n例子在模式识别技术中，常用的术语有：样本、模式、特征、类型等等，对照医生诊病过程：a.样本：医院里的众多患者，每个患者都是一个样本；单一样本：医生诊断的某一患者，就是样本空间中的一个单一样本；样本值：某一患者的化验、检查结果与表征现象。b.模式：各样本值按一定的数据准则综合的结果；模式样本：具有某种模式的样本；模式采集：获取某样本的测量数值的过程；c.特征：患者某些具有显著特征的化验数据及表征；特征选择与提取：能表征(疾病)特异性的化验结果与表征；第一章 概述 1-2 模式识别系统模式识别系统n例子在模式识别技术中，常用的术语有：样本、模式、特征、类型等等，对照医生诊病过程：d.判决：医生运用知识、病例经验综合分析给出诊断；判决准则/规则：医生的知识 判决结果：将患者明确(或以概率)确定为某一种病症(或多种/并发病症)的患者(及病患严重程度)事实上，最后的结果也成为分类。因此有预先知道类别(已知病症)与未知类别(未知病症)的区别。模式识别：就是以计算机为工具、各种传感器为信息来源，数据计算与处理为方法，对各种现象、事物、状态等进行准确地分析、判断识别与归类。第一章 概述 1-2 模式识别系统模式识别系统n例子n“利用光学感知手段将传送带上的鱼根据种类排列”鲈鱼种类鲑鱼第一章 概述 1-2 模式识别系统模式识别系统n例子n“利用光学感知手段将传送带上的鱼根据种类排列”鲈鱼种类鲑鱼鲑鱼上下嘴边无牙，只在口腔中部有少量小牙。体型细长如潜水艇状，鱼鳞细小，用肉眼极难看到，身上的斑点为白色、灰色、黄色、桔红色和鲜红色，腹部的鳍、翅及尾部下沿都有一条白色的条纹边，非常明显美观。体延长而侧扁，眼间隔微凹。其间有4条隆起线。口大，下颌长于上颌。吻尖，牙细小，在两颌、犁骨及腭骨上排列成绒毛状牙带。前鳃盖骨后缘有细锯齿，隅角及下缘有钝棘。第一背鳍发达并有12根硬棘。第二背鳍由13根鳍条组成；腹鳍位于胸鳍始点稍后方。第二背鳍基部浅黄色，胸鳍黄绿色，尾鳝叉形呈浅褐色。第一章 概述 1-2 模式识别系统模式识别系统n例子n问题分析n架设一台摄像机，拍摄若干样品的图像用来提取特征n长度n光泽n宽度n鳍的数量和形状n嘴的位置,etcn这是用于我们的分类器的所有可能的特征第一章 概述 1-2 模式识别系统模式识别系统n例子n预处理n使用分割技术将鱼彼此分开，并将鱼同背景分开n将每条鱼的信息送入一个特征提取器，其作用是通过测量特定的“特征”或“属性”来简化原始数据n将特征传送给一个分类器第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n例子n分类n选择鱼的长度作为一种可能的特征第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n例子长度本身不是一个好的特征!选择光泽度作为一种可能的特征第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n例子n预知判别边界和成本关联n将判别边界减小，使成本最小化(减少被错分为鲑鱼的鲈鱼的数目)决策理论的中心任务第一章 概述 1-2 模式识别系统模式识别系统n例子n采用鱼的光泽度和宽度鱼 xT=x1,x2光泽度光泽度宽度宽度第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n例子n我们可以加入其它的与现有特征无关的特征，需要注意的是：加入这些“噪声特征”绝不能降低性能n理想情况下,最好的判别边界应该能提供最佳性能第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n例子n但是,设计一个分类器的中心目的是正确区分新的样本 推广能力（泛化性 generalization）第一章 概述 1-2 模式识别系统模式识别系统n例子第一章 概述 1-2 模式识别系统模式识别系统n如何精确和定量的设计相对“简单”一些的分类器？n系统如何自动得出相对简单的分界曲线？n如何做到“推广能力”和“复杂度”的折中？n如何预测系统对新模式的推广能力？第一章 概述 1-2 模式识别系统模式识别系统n模式识别的方法n模板匹配n统计方法n句法方法n神经网络第一章 概述 1-2 模式识别系统模式识别系统n模板匹配n首先对每个类别建立一个或多个模板n输入样本和数据库中每个类别的模板进行比较，求相关或距离n根据相关性或距离大小进行决策n优点：直接、简单n缺点：适应性差n形变模板第一章 概述 1-2 模式识别系统模式识别系统n统计方法n根据训练样本，建立决策边界n统计决策理论根据每一类总体的概率分布决定决策边界n判别分析方法给出带参数的决策边界，根据某种准则，由训练样本决“最优”的参数n本课程的重点内容第一章 概述 1-2 模式识别系统模式识别系统n句法方法n许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元“n每个模式都可以由基元根据一定的关系来组成n基元可以认为是语言中的字母，每个模式都可以认为是一个句子，关系可以认为是语法n模式的相似性由句子的相似性来决定n优点：适合结构性强的模式n缺点：抗噪声能力差，计算复杂度高第一章 概述 1-2 模式识别系统模式识别系统n神经网络n大规模并行计算n学习、推广、自适应、容错、分布表达和计算n优点：可以有效的解决一些复杂的非线性问题n缺点：缺少有效的学习理论第一章 概述 1-2 模式识别系统模式识别系统n神经网络和统计模式识别的关系第一章 概述 1-2 模式识别系统模式识别系统n几种方法比较第一章 概述 1-2 模式识别系统模式识别系统n模式识别应用n文本分类n文本图像分析n工业自动化n数据挖掘n多媒体数据库检索n生物特征识别n语音识别n生物信息学n遥感n第一章 概述 1-3 模式识别发展史模式识别发展史n1929年 G.Tauschek发明阅读机，能够阅读0-9的数字。n30年代 Fisher提出统计分类理论,奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。第一章 概述 1-3 模式识别发展史模式识别发展史n50年代 Noam Chemsky 提出形式语言理论 美籍华人付京荪 提出句法结构模式识别。n60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。n80年代 Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。n90年代 小样本学习理论，支持向量机也受到了很大的重视。第一章 概述 1-3 模式识别发展史模式识别发展史n50年代 Noam Chemsky 提出形式语言理论 美籍华人付京荪 提出句法结构模式识别。n60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。n80年代 Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。n90年代 小样本学习理论，支持向量机也受到了很大的重视。第一章 概述 1-3 模式识别发展史模式识别发展史n模式识别的计算手段更加先进：n 海量存储技术、高速计算/并行计算技术、网格技术、网络技术、新型前端器件(激光、红外、MEMS、传感器网络)n模式识别的新型算法层出不穷：nComputation with word(Zadeh)Soft Computation DNA Computationn国内外模式识别的学术活动从未间断:n小波/模式识别国际会议、机器学习/模式识别国际会议、图像处理/模式识别国际会议、数据挖掘/模式识别国际会议第一章 概述 1-4 模式识别的基本问题模式识别的基本问题模式(样本)表示方法1.向量表示:假设一个样本有n个变量(特征)=(X1,X2,Xn)T2.矩阵表示:N个样本，n个变量(特征)第一章 概述 1-4 模式识别的基本问题模式识别的基本问题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第一章 概述 1-4 模式识别的基本问题模式识别的基本问题4.基元（链码）表示：在右侧的图中八个基元分别表示0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为 X1=006666这种方法将在句法模式识别中用到。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题4.基元（链码）表示：在右侧的图中八个基元分别表示0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为 X1=006666这种方法将在句法模式识别中用到。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n模式类的紧致性：临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n模式类的紧致性：n紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题紧致集的性质 要求临界点很少 集合内的任意两点的连线,在线上的点属于同 一集合 集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点模式识别的要求:满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法,满足紧致集.第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类1.两个样本xi，xj之间的相似度量满足以下要求：应为非负值 样本本身相似性度量应最大 度量应满足对称性 在满足紧致性的条件下，相似性应该是点间距离的单调函数 第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类2.用各种距离表示相似性：已知两个样本 xi=(xi1,xi2,xi3,xin)T xj=(xj1,xj2,xj3,xjn)T n 绝对值距离第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类 欧几里德距离明考夫斯基距离其中当q=1时为绝对值距离，当q=2时为欧氏距离第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类切比雪夫距离q趋向无穷大时明氏距离的极限情况 马哈拉诺比斯距离 其中xi，xj为特征向量，为协方差。使用的条件是 样 本符合正态分布第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类 夹角余弦样本间夹角小的为一类，具有相似性例：x1,x2,x3的夹角如图：x1x2x1x2x3因为x1,x2 的夹角小，所以x1,x2 最相似。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题n相似与分类相似与分类 相关系数 为xi xj的均值注意：在求相关系数之前，要将数据标准化第一章 概述 1-4 模式识别的基本问题模式识别的基本问题分类的主观性和客观性 分类带有主观性：目的不同，分类不同。例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。分类的客观性：科学性判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题特征的生成 1.低层特征：无序尺度：有明确的数量和数值。有序尺度：有先后、好坏的次序关系，如酒分为上，中，下三个等级。名义尺度：无数量、无次序关系，如有红，黄两种颜色 2.中层特征：经过计算，变换得到的特征 3.高层特征：在中层特征的基础上有目的的经过运算形成例如：椅子的重量=体积*比重 体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。第一章 概述 1-4 模式识别的基本问题模式识别的基本问题特征的生成 第一章 概述 1-4 模式识别的基本问题模式识别的基本问题数据的标准化 1.极差标准化，一批样本中，每个特征的最大值与最小值之差。极差 极差标准化 2.方差标准化 Si 为方差标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。