模式识别jnca01

1、1模式识别2 相关学科相关学科 教学目标教学目标 基本要求基本要求 教材教材/ /参考文献参考文献关于本课程的有关说明3 相关学科统计学统计学概率论概率论线性代数（矩阵计算）线性代数（矩阵计算）形式语言形式语言人工智能人工智能图像处理图像处理计算机视觉计算机视觉 等等等等4 教学目标掌握模式识别的基本概念和方法掌握模式识别的基本概念和方法有效地运用所学知识和方法解决实际问题有效地运用所学知识和方法解决实际问题为研究新的模式识别的理论和方法打下基础为研究新的模式识别的理论和方法打下基础 5 基本要求基本基本：完成课程学习，通过考试，获得学分。：完成课程学习，通过考试，获得学分。提高提高：能够将所

2、学知识和内容用于课题研究，：能够将所学知识和内容用于课题研究，解决实际问题。解决实际问题。飞跃：飞跃：通过模式识别的学习，改进思维方式，通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。为将来的工作打好基础，终身受益。6教材教材/ /参考文献参考文献R. Duda, P. Hart, D. Stork, Pattern Classification, second edition, 2000（有中译本）.Sergios Theodoridis, Konstantinos Koutroumbas, Pattern Recognition, Fourth Edition 李晶皎等译

3、，模式识别，电子工业出版社。李晶皎等译，模式识别，电子工业出版社。孙即祥，现代模式识别，国防科技大学出版社，孙即祥，现代模式识别，国防科技大学出版社，2003年。年。边肇祺，张学工，边肇祺，张学工，模式识别模式识别，清华大学出版社。，清华大学出版社。7讲授课程内容及安排第一章第一章 引论引论 第二章第二章 聚类分析聚类分析第三章第三章 判别域代数界面方程法判别域代数界面方程法 第四章第四章 统计判决统计判决 第五章第五章 学习、训练与错误率估计学习、训练与错误率估计 第六章第六章 最近邻方法最近邻方法第七章第七章 特征提取和选择特征提取和选择 8第一章 引论1.1 1.1 一个模式识别案例及基

4、本概念一个模式识别案例及基本概念1.2 1.2 特征矢量和特征空间特征矢量和特征空间1.3 1.3 随机矢量的描述随机矢量的描述1.4 1.4 正态分布正态分布91.1.1 一个模式识别案例一个模式识别案例n识别是人类的基本行为n模式识别（Pattern Recognition）使用计算机来辨别事物。机器识别，计算机识别，机器自动识别。10人类：人类： 学习、总结规律，抽象出概念学习、总结规律，抽象出概念机器：缺乏抽象能力机器：缺乏抽象能力基本方法是计算基本方法是计算11一个模式识别案例一个模式识别案例n鱼类加工厂需要将传送带上的鱼自动进行分类 鲈鱼(Seabass)品种 鲑鱼(Salmon)

5、12n问题分析采用摄像机获取图像，根据图像对鱼进行分类。可能遇到的问题：n目标的提取预处理n分类的依据特征提取n判别的规则分类器设计13n预处理 方便后续操作，同时又不损失关键信息。n去除噪声n光照调整n目标提取n方向、位置调整n大小规一化 在本例中需要采用分割技术将鱼和鱼、鱼和背景分开14n特征提取 原始数据量巨大，往往含有很多冗余信息，为了有效实现分类识别，需要对原始数据进行变换，以便得到最能反映分类本质的特征。 可以考虑的特征：n长度n光泽n宽度n鳍的数目和形状n嘴的位置, 等等15n分类 根据某种判决规则将被识别对象归为某一类别。 基本方法： 在训练样本集上确定某个判决规则，使按这种判

6、决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。16n预处理：去噪，用分割操作把鱼和鱼之间以及鱼和背景之间分开n特征提取和选择：对单个鱼的信息进行特征选择，从而通过测量某些特征来减少信息量n长度n亮度n宽度n鱼翅的数量和形状n嘴的位置，等等 n分类决策：把特征送入决策分类器1718n采用长度作为特征19n结论 单独使用长度错误率太高 必须考虑其它特征n改进措施 采用光泽度进行新的尝试20n采用光泽度作为特征21n改进： 运用两种特征组和：光泽度和宽度鱼 xT = x1, x2光泽度光泽度宽度宽度设 计 实 例22n 采用光泽度和宽度作为特征23n我们可以尝试增加其他特征，但必

7、须注意两点： 新增特征与已有特征不相关 不会引起性能的下降n我们还可以改进分类器模型，达到如下图所示的效果：2425n讨论：这样的效果好吗？设 计 实 例26n讨论 我们的目标是使所设计的分类器能够正确识别未知样本-泛化能力 过分复杂的判决边界，过分关注某些特定的训练样本，而忽略了类别的共同特征，导致泛化能力弱！ 27n决策边界过于复杂导致的问题n运算量大n数学表达困难n泛化能力差：对未知样本的分类错误率高28n理想状况：对训练样本的分类性能和分界面复杂度的折中29n面向特定任务的分类系统及错误分类（误判）的代价（损失） n如果两种错误代价相同，则以最小错误率为准则；n如果两种错误代价不等，则

8、以最小风险为准则。 可以调整阈值边界，确定最优的分界点。n确定某种决策规则，使得决策所引起的损失最小，这是决策理论的核心任务。30n采用光泽度作为特征，考虑误判代价1.1.2 模式识别的基本概念模式识别的基本概念n模式识别模式识别(Pattern Recognition)(Pattern Recognition)：确定一个确定一个样本的类别属性（模式类）的过程，即把某一样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。样本归属于多个类型中的某个类型。n样本（样本（Sample)Sample)：一个具体的研究（客观）对象。一个具体的研究（客观）对象。如一条鱼、患者，某人写的

9、一个汉字，一幅图片如一条鱼、患者，某人写的一个汉字，一幅图片等。等。x),(21nxxxxn特征特征(Features)(Features)：能描述模式特性的量（测能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一量值）。在统计模式识别方法中，通常用一个矢量个矢量 表示，称之为特征矢量，记为表示，称之为特征矢量，记为 n模式模式(Pattern)(Pattern)：对客体（研究对象）特征的对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。界的某一样本的测量值的集合（或综合）。n模式类模式类(C

10、lass)(Class)：具有某些共同特性的模式具有某些共同特性的模式的集合。的集合。33模式识别系统的主要环节：模式识别系统的主要环节：特征提取：特征提取：对重要特征量测，形成特征矢量对重要特征量测，形成特征矢量或将对象分解为基元，或将对象分解为基元，符号化，形成符号串或关系图符号化，形成符号串或关系图特征选择：特征选择： 选择有代表性的特征，能够正确分类选择有代表性的特征，能够正确分类学习和训练：学习和训练：利用已知样本建立分类和识别规则利用已知样本建立分类和识别规则分类识别：分类识别： 对所获得样本按建立的分类规则进行分对所获得样本按建立的分类规则进行分类识别类识别34模式识别的学习、训

11、练方法n有监督学习有监督学习（有教师学习）： 有一个已知样本集（有一个已知样本集（集合中每个样本的类别已知），作为作为训练样本集，并通过挖掘先验已知信息来指导设计分类器。n无监督学习无监督学习（无教师学习）： 没有已知类别标签的训练数据可用， 通过挖掘样本中潜在的相似性分类；35模式识别系统数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识别结果通常在采集信息过程中，还要去除所获取信息通常在采集信息过程中，还要去除所获取信息中的噪声，增强有用的信息等工作。这种使信息中的噪声，增强有用的信息等工作。这种使信息纯化的处理过程叫做信息的纯化

12、的处理过程叫做信息的预处理预处理。分类识别是根据事先确定的分类识别是根据事先确定的分类规则分类规则对前面选对前面选取的特征进行取的特征进行分类分类（即识别）。（即识别）。通常能描述对象的元素很多，为节约资源和提通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对别正确率要求的条件下，按某种准则尽量选用对正确分类识别作用较大的特征。使得用较少的特正确分类识别作用较大的特征。使得用较少的特征就能完成分类识别任务。征就能完成分类识别任务。预处理预处理这个环节的内容很广泛，与要解决的具这个

13、环节的内容很广泛，与要解决的具体问题有关，例如，从体问题有关，例如，从图象图象中将中将汽车车牌汽车车牌的号码的号码识别识别出来，就需要先将出来，就需要先将车牌车牌从从图像图像中找出来，再中找出来，再对对车牌车牌进行进行划分划分，将每个，将每个数字数字分别分别划分划分开。做到开。做到这一步以后，才能对每个这一步以后，才能对每个数字数字进行进行识别识别。以上工。以上工作都应该在预处理阶段完成。作都应该在预处理阶段完成。数字化数字化比特流比特流36模式识别系统数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识别结果数据采集数据采集特征提取特

14、征提取可改进规则可改进规则的分类识别的分类识别二次特征提二次特征提取与选择取与选择训练训练样本样本改进采集改进采集提取方法提取方法改进特征提改进特征提取与选择取与选择制定改进分制定改进分类识别规则类识别规则人工人工干预干预正确率正确率测试测试37对象空间对象空间模式空间模式空间特征空间特征空间类型空间类型空间各类空间（各类空间（Space)Space)的概念的概念模式采集：模式采集：从客观世界（对象从客观世界（对象空间）到模式空间的过程称为空间）到模式空间的过程称为模式采集。模式采集。特征提取和特征选择：特征提取和特征选择：由模式由模式空间到特征空间的变换和选择。空间到特征空间的变换和选择。类

15、型判别：类型判别：特征空间到类型空特征空间到类型空间所作的操作。间所作的操作。模模式式识识别别三三大大任任务务38纸币识别器对纸币按面额进行分类纸币识别器对纸币按面额进行分类 面额面额系统实例5元10元20元50元100元39系统实例 长度长度(mm) (mm) 宽度宽度(mm)(mm)5 5元元13613663631010元元14114170702020元元14614670705050元元1511517070100100元元156156777740系统实例磁性磁性金属条位置金属条位置( (大约大约) )5 5元元有有 54/8254/821010元元有有 54/8754/872020元元有有

16、 57/8957/895050元元有有 60/9160/91100100元元有有 63/9363/935元 10元 20元 50元 100元12345678反反射射光光波波形形42系统实例数据采集、特征提取：数据采集、特征提取： 长度、宽度、磁性、磁性的位置，光反射亮度、光长度、宽度、磁性、磁性的位置，光反射亮度、光透射亮度等等透射亮度等等 特征选择：特征选择： 长度、磁性及位置、反射亮度长度、磁性及位置、反射亮度分类识别：分类识别： 确定纸币的面额及真伪确定纸币的面额及真伪43模式识别的其他例子模式识别的其他例子计算机自动诊断疾病计算机自动诊断疾病:获取情况获取情况( (信息采集信息采集)

17、) 测量体温、血压、心率、血液化验、测量体温、血压、心率、血液化验、X X光透光透射、射、B B超、心电图、超、心电图、CTCT等尽可能多的信息，并将等尽可能多的信息，并将这些信息数字化后输入电脑。这些信息数字化后输入电脑。特征要进行选择特征要进行选择。2 2 运行在电脑中的运行在电脑中的专家系统专家系统或专用程序可以分或专用程序可以分析这些数据并进行析这些数据并进行分类分类，得出正常或不正常的，得出正常或不正常的判断，不正常情况还要指出是什么问题。判断，不正常情况还要指出是什么问题。441.1.3模式识别的基本方法一、统计模式识别一、统计模式识别二、句法模式识别二、句法模式识别三、模糊模式识

18、别三、模糊模式识别四、人工神经网络法四、人工神经网络法五、人工智能方法五、人工智能方法451.1.3 模式识别的基本方法一、统计模式识别一、统计模式识别模式描述方法：模式描述方法： 特征向量特征向量 模式判定：模式判定： 模式类用条件概率分布模式类用条件概率分布P(X/P(X/ i i) )表示表示,m,m类就有类就有m m个分布，然后判定未知模式属于哪一个分布。个分布，然后判定未知模式属于哪一个分布。),(21nxxxx461.1.3 模式识别的基本方法一、统计模式识别一、统计模式识别理论基础：理论基础：概率论，数理统计概率论，数理统计主要方法：主要方法：线性、非线性分类、线性、非线性分类、

19、BayesBayes决策、聚类分析决策、聚类分析主要优点：主要优点： 1 1）比较成熟）比较成熟 2 2）能考虑干扰噪声等影响）能考虑干扰噪声等影响 3 3）识别模式基元能力强）识别模式基元能力强主要缺点：主要缺点： 1 1）对结构复杂的模式抽取特征困难）对结构复杂的模式抽取特征困难2 2）不能反映模式的结构特征，难以描述模式的性质）不能反映模式的结构特征，难以描述模式的性质3 3）难以从整体角度考虑识别问题）难以从整体角度考虑识别问题471.1.3模式识别的基本方法二、句法模式识别二、句法模式识别模式描述方法：模式描述方法： 符号串，树，图符号串，树，图模式判定：模式判定： 是一种语言，用一

20、个文法表示一个类，是一种语言，用一个文法表示一个类，m m类就类就有有m m个文法，然后判定未知模式遵循哪一个文法。个文法，然后判定未知模式遵循哪一个文法。48例例2 2：如下图中一幅图形，要识别图中的物体，：如下图中一幅图形，要识别图中的物体，选用句法模式识别方法选用句法模式识别方法. .1.1.3模式识别的基本方法49解：解：图形结构复杂，首先应分解为简单的子图图形结构复杂，首先应分解为简单的子图（背景、物体）。（背景、物体）。构成一个多级树结构：构成一个多级树结构：1.1.3模式识别的基本方法50n在学习过程中，确定基元与基元之间的在学习过程中，确定基元与基元之间的关系，推断出生成景物的

21、方法。关系，推断出生成景物的方法。n判决过程中，首先提取基元，识别基元判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入做句法分析。若分析成立，则判断输入的景物属于相应的类型。的景物属于相应的类型。1.1.3模式识别的基本方法51理论基础：理论基础：形式语言，自动机技术形式语言，自动机技术主要方法：主要方法：自动机技术、自动机技术、CYKCYK剖析算法、剖析算法、EarlyEarly算法、算法、转移图法转移图法主要优点主要优点：1 1）识别方便，可以从简单的基元开始，由简至繁。）识别方便，可以从简单的基元开始

22、，由简至繁。2 2）能反映模式的结构特征，能描述模式的性质。）能反映模式的结构特征，能描述模式的性质。3 3）对图象畸变的抗干扰能力较强。）对图象畸变的抗干扰能力较强。主要缺点：主要缺点：当存在干扰及噪声时，抽取特征基元困难，且易失误。当存在干扰及噪声时，抽取特征基元困难，且易失误。1.1.3模式识别的基本方法521.1.3模式识别的基本方法三、模糊模式识别三、模糊模式识别模式描述方法：模式描述方法： 模糊集合模糊集合 A=(A=( a a,a), (,a), ( b b,b),. (,b),. ( n n,n),n)模式判定：模式判定： 是一种集合运算。用隶属度将模糊集合划分是一种集合运算。

23、用隶属度将模糊集合划分为若干子集，为若干子集， m m类就有类就有m m个子集，然后根据择近原个子集，然后根据择近原则分类。则分类。53理论基础：理论基础：模糊数学模糊数学主要方法：主要方法：模糊统计法、二元对比排序法、推理法、模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵模糊集运算规则、模糊矩阵主要优点主要优点：由于隶属度函数作为样本与模板间相似程度的度量，由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。相当程度的干扰与畸变。主要缺点：主要缺点：准确合理的隶属度函数往

24、往难以建立，故限制了它的准确合理的隶属度函数往往难以建立，故限制了它的应用。应用。1.1.3模式识别的基本方法541.1.3模式识别的基本方法四、人工神经网络法四、人工神经网络法模式描述方法：模式描述方法： 以不同活跃度表示的输入节点集（神经元）以不同活跃度表示的输入节点集（神经元）模式判定：模式判定： 是一个非线性动态系统。通过对样本的学习是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的建立起记忆，然后将未知模式判决为其最接近的记忆。记忆。55理论基础：理论基础：神经生理学，心理学神经生理学，心理学主要方法：主要方法：BPBP模型、模型、HOPHOP模型、高阶

25、网模型、高阶网主要优点主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。理规则不明确的问题。允许样本有较大的缺损、畸变。主要缺点：主要缺点：模型在不断丰富与完善中，目前能识别的模式类还不模型在不断丰富与完善中，目前能识别的模式类还不够多。够多。1.1.3模式识别的基本方法561.1.3模式识别的基本方法五、逻辑推理法（人工智能法）五、逻辑推理法（人工智能法）模式描述方法：模式描述方法： 字符串表示的事实字符串表示的事实模式判定：模式判定： 是一种布尔运算。从事实出发运用一系列规是一种布尔运算。从

26、事实出发运用一系列规则，推理得到不同结果，则，推理得到不同结果，m m个类就有个类就有m m个结果。个结果。57理论基础：理论基础：演绎逻辑，布尔代数演绎逻辑，布尔代数主要方法：主要方法：产生式推理、语义网推理、框架推理产生式推理、语义网推理、框架推理主要优点主要优点：已建立了关于知识表示及组织，目标搜索及匹配的完已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。问题，有很好的效果。主要缺点：主要缺点：当样本有缺损，背景不清晰，规则不明确甚至有歧义当样本有缺损，背景不清晰，规则不明确甚至

27、有歧义时，效果不好。时，效果不好。1.1.3模式识别的基本方法581.1.4模式识别的发展简史19291929年年 G. TauschekG. Tauschek发明阅读机发明阅读机 ，能够阅，能够阅读读0-90-9的数字。的数字。3030年代年代 FisherFisher提出统计分类理论，奠定了提出统计分类理论，奠定了统计模式识别的基础。统计模式识别的基础。5050年代年代 Noam Chemsky Noam Chemsky 提出形式语言理论提出形式语言理论傅京荪提出句法傅京荪提出句法/ /结构模式识别。结构模式识别。6060年代年代 L.A.ZadehL.A.Zadeh提出了模糊集理论，模糊

28、提出了模糊集理论，模糊模式识别方法得以发展和应用。模式识别方法得以发展和应用。591.1.4模式识别的发展简史8080年代年代 以以HopfieldHopfield网、网、BPBP网为代表的神经网网为代表的神经网络模型导致人工神经元网络复活，并络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。在模式识别得到较广泛的应用。9090年代年代 小样本学习理论，支持向量机也受到小样本学习理论，支持向量机也受到了很大的重视。了很大的重视。601.1.4模式识别的应用n生物学生物学自动细胞学、染色体特性研究、遗传研究自动细胞学、染色体特性研究、遗传研究n天文学天文学天文望远镜图像分析、自动光谱学

29、天文望远镜图像分析、自动光谱学n经济学经济学股票交易预测、企业行为分析股票交易预测、企业行为分析n医学医学心电图分析、脑电图分析、医学图像分析心电图分析、脑电图分析、医学图像分析611.1.4主要实用系统举例n文字识别（文字识别（Character Recognition）OCR（Optical Character Recognition）n智能交通（智能交通（Intelligent Traffic）车牌、车型。车牌、车型。n语音识别（语音识别（Speech recognition）翻译机，身份识别等翻译机，身份识别等n目标识别目标识别ATR（Automaic Target Recogniti

30、on）62nIEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)nNeural NetworksnPattern RecognitionnPattern Recognition LetternMachine LearningnNeural Computationn模式识别与人工智能nIEEE International Conference on Computer Vision and Pattern Recognition (CVPR) nIEEE International Conference on M

31、achine Learning (ICML) 国内外相关重要期刊和会议国内外相关重要期刊和会议63641.2 特征矢量和特征空间651.3 随机矢量的描述随机矢量：随机矢量：在模式识别过程中，要对许多具体对象进行不同特征在模式识别过程中，要对许多具体对象进行不同特征的测量。的测量。对同一对象的同一特征，多次测量值不一定相同；对同一对象的同一特征，多次测量值不一定相同；对不同对象的同一特征测量值，是按照某种统计规律对不同对象的同一特征测量值，是按照某种统计规律分布的；分布的；每个特征分量都是随机变量，同一对象的多个特征分每个特征分量都是随机变量，同一对象的多个特征分量组成一个随机矢量，即许多对象

32、的特征向量在量组成一个随机矢量，即许多对象的特征向量在n n维维空间中呈随机性分布。空间中呈随机性分布。661.3 随机矢量的描述P),(21nXXXX),(21nxxxx),(),(221121nnnxXxXxXPxxxF)()(xXPxF(一一)随机矢量的分布函数：随机矢量的分布函数：设设 为随机矢量，为随机矢量， 为确定性矢量。为确定性矢量。 随机矢量的联合概率分布函数定义为：随机矢量的联合概率分布函数定义为： 式中式中 表示括号中事件同时发生的概率。表示括号中事件同时发生的概率。 671.3 随机矢量的描述)(),(21xpxxxpnnnnxxxxxxF2121),(X随机矢量随机矢量 的联合概率密度函数定义为：的联合概率密度函数定义为： 681.3 随机矢量的描述6912X1X121.3 随机矢量的描述x xp(x)p(x)(1xp)(2xp2701.3 随机矢量的描述711.3 随机矢量的描述其中，其中， 的分量：的分量： 1212E()d.(,.,)d d.diiiiiinniXx p xxx p x xxx xxX)(ixpXiX式中，式中， 是是 的第的第 个分量的边缘个分量的边缘