张鸿宾模式识别-第一讲.ppt

模 式 识 别 Pattern Recognition,张鸿宾,第一章 绪论,模式识别的研究内容、方法和应用,模式识别学科已经有近五十年的历史了。,广义上讲如何使机器具有智能。和人工智能学科一样。 狭义上讲研究模式的分类、聚类、决策和估计问题。 使机器具有智能是人类的愿望。（机器是人手的延长， 智能机是人脑的延长） 但使机器具有智能这个工作很不容易，仍然有许多谜，人脑的机制不明。,尽管已有近五十年的历史，但仍有许多的问题待解决，也可以说刚起步。,Ross在1998年的书中说，“一个好的计算机程序可以帮助银行对人的信用评估，帮助医生诊断疾病，帮助飞机驾驶员着陆，所以应该更加重视模式识别的教学。 这一节介绍什么是模式识别、模式识别的方法、模式识别的应用，然后结合一些例子说明模式识别的一些基本概念。,一. 什么是模式识别,使机器具有能够自动地对物体描述、分类、分组是科技、工程中的重要问题 。 在社会科学、生物学、心理学、医学、市场分析预测、自动化、计算机视觉、人工智能、遥感、军事、生物特征识别等问题中有重要应用。,什么是模式呢？,Watanabe定义模式 “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name. 模式，（匈牙利，波兰，新加波) 相似但又不完全相同的一些物体、现象，不混沌（chaos）。 模式可以是一个手写的字符、一幅指纹图像、一幅人脸的图像、一段语音信号等。,模式(pattern)这个单词的 两种用法 ：单个，模式类,模式的识别/分类可能有两种方式： 有监督的分类/识别（Supervised Classification）：把模式分到预先定义好的类里去。 无监督的分类/识别（Unsupervised Classification, clustering）：基于相似性，把模式聚合成一定的类。,二. 模式识别的应用,随着计算机性能的提高、Internet的迅速发展，模式识别的应用不仅在它的传统领域，如文字识别、语音识别、指纹识别、遥感图像、医学等越做越好，而且涌现了很多新的应用。例如数据挖掘（data mining）、文档的分类（document classification）、财政金融、股票的预测、预报，多媒体数据库的检索，基于biometrics（生物统计学）的人的身份鉴别，甚至有的人研究识别人的感情。 特征是数据驱动提取的，不是专家建议的。,模式识别应用的一些例子,模式识别应用的一些例子（续）,模式识别应用的一些例子（续）,模式识别应用的一些例子（续）,三. 模式识别的方法,随着供模式识别系统使用的计算机的性能（速度和存储能力）的提高，使得使用更复杂的算法、使用多信息源、多种算法的融合与集成来处理更多的数据成为可能。另一方面，现实中的问题要求更高（速度、精度、代价）。,在要解决的问题更复杂的情况下，单一的模式识别方法、单一的数据源已经达不到要求,要组合不同的方法（算法）、不同传感器的信息。（Fusion，Several sensing modality),一个模式识别系统，基本上都包括以下三个方面,数据的获得和预处理 数据的表示 分类、决策（decision making） 在解决不同的具体问题时，要根据该问题的性质，确定传感器、预处理、数据的表示和分类算法,常用的模式识别方法,模板匹配（template matching） 统计的方法（statistical P.R.） 句法或结构的方法（syntactic or structural P.R.） 人工神经网络的方法（artificial neural network, ANN） 这些方法不是绝对独立的，同一种方法有不同的解释，有时要混合使用。,1.模板匹配,模式识别中使用最早、最简单、直观的方法 所谓匹配是一类运算，用来确定两个对象间（点集、曲线、面、形状）间的相似性。 在模板匹配中，要有一个模板（一般是一个二维形状）或一个模式原型（prototype），待匹配的模式和这个预先存储好的模板相匹配 模板本身也是从训练样本中学习得来的 模板匹配一般要花费较大的计算量，随着计算机速度的加快，这种方法变得更可行了,1. 模板匹配(续）,刚性模板匹配的缺点：处理畸变模式难 传感器问题、视点改变、类内偏差大 使用变形模板,2. 统计模式识别,在统计模式识别中，每一模式是用一个d维的测量值、特征向量来表示的，它是d维特征空间的一个点。目标是选择这样的一些特征，使同一类的模式在空间中尽量紧凑，而不同类的模式间尽量分开、不相交 给定一组样本，模式识别的任务是要确定决策（分割）面、边界，以把不同的类分开。,在统计决策理论的方法下，决策边界是根据模式的概率分布确定的。这些概率分布是事先知道，或通过学习估计得到。,另外一种统计模式识别的工具是判别分析（discriminant analysis）。这种方法是先假定决策边界的数学形式（一次、或二次），然后利用训练样本确定最好的边界（方程中的一些参数）。构造边界时一般利用均方差准则（mean squared error）。,再一种方法是从样本中直接构造决策边界。如Vapnik的支撑向量机（support vector machine）,Vapnik方法的思想（哲学，philosophy）是：“当只有有限的信息来求解某一问题时，那你就直接去解这一问题，不要试着去解一个更一般的问题，然后再解决你的特殊问题。因为你手中的信息也许对解决你的具体问题是够（充分）的，但对解决更一般的问题也许就不够了。”,3. 句法或结构的方法,句法模式识别的方法来源于这样的思想：复杂的模式是由简单的子模式组成的，而子模式又是由更简单的子模式组成。最简单的子模式称为基元（primitives），复杂模式就是由这些基元以及它们间的相互关系确定。如同物体组成的原子、分子论。,句法模式识别的方法来源于形式语言和自动机：模式句子，基元字母表，模式结构语法规则，模式分类语法分析。规则的产生要靠语法推断,结构模式识别的优点是它的层次结构，用少量的基元和规则来描述物体。这种方法常用在有一定结构的模式上，例如心电图（ECG）、纹理图像（texture）、物体轮廓的分析上,句法模式识别的难点在于如何从噪声干扰下分割出模式基元，如何从训练样本中推断出语法规则来,存在组合“爆炸”的问题，要求大的训练样本集、高计算复杂度。 “Conundrum of combinatorial complexity”,4. 人工神经网络的方法,人工神经网络是一个超大规模的并行计算系统。它由大量很简单的计算单元相互连接组成。模拟人脑的计算，它试图把学习、泛化（generalization）、自适应（adaptivity）、容错（fault tolerance）、分布式表示和计算、联想等功能实现在一个加权的有向图式的结构上：图的节点神经元，有向边（加权的）神经元输入、输出连接,人工神经网络的突出优点是它可以学习复杂的非线性输入输出关系（从样本序列中）,常用的神经网络有两种 : 前馈性网络：分层 多层感知器（Multilayer Perceptron) 径向基函数网（Radial Basis Function) 互连型网络：互连 Kohonen的 Self-Oeganization Map Hopfield型的互连网,网络学习的过程是利用提供的样本修改连接权（connection weights）或网络的结构（增减神经元 ),人工神经网络的应用（分类、特征提取）获得了很大的普及，其原因是： 1. 对特定问题域的知识较少依赖（和基于规则或模型的方法相比） 2.对实际工作者来讲，有有效的学习算法可供使用 人工神经网络为解决非线性的特征提取和分类提供了一套工具。此外，已经存在的统计模式识别方法也可以用神经网络实施,Anderson(MIT, 1990)指出：“神经网络是外行人（amateurs）的统计学”。,尽管统计的方法和人工神经网络在基本原理上有很多不同，但它们在方法上是等价或相似的 人工神经网络为外行提供了求解非线性问题的工具,四种方法的比较,四种方法的比较（续）,四. 模式识别系统,模式识别系统,六. 几个例子,1. 字符识别 印刷的、手写的 通过OCR等设备（Optical Character Reader）得到观测向量,G,字符识别,观察向量：物理的，几何的，数学的，主观的,特征空间：Rd，0，1d,符号或逻辑值的,2. 医疗诊断问题-心电图正常/异常,小结：,模式可以用多维向量空间中的一个矢量来表示，一个点 模式不是确定性的，带有概率性质，要用统计的方法，要用到数理统计、线性代数（矩阵）等工具。 分类就是要把特征空间划分为一些区域，不相交，类间不重迭。,分类区域、形式,线性（或分段线性）,二次的,一般的,R1,R2,R3,R3,R2,R2,R1,R1,R3,R4,3. 两类字符识别,测量矢量:,0,如何确定决策的阈值：作直方图，可以得到“0”和“1”的分布,R1,R2,P1,P0,5.5,5.5,面积,N,小结：,设计分类器时不是要求没有错分类的，而是在一定意义下使错误率最小 下面我们再看一个稍微复杂的问题,4. 三类字符识别-除了“0”、“1”之外，还要识别“x”,一个特征（占的面积）就不够了。“0”、“x”的覆盖面积近似相等。加上另一特征（对角线上1、7、13、19、25面积之和）,分类规则：,if else,上面的分类规则还可以写成更方便的形式：,定义函数： 这样，决策规则可以表示为：若,分到 类,则,上面的g(y)称为判别函数。这种形式特别方便计算机实施,计算各个判别函数 选择最大的判别函数值，归到该类 所形成的决策区域为：,各个分类（决策）边界可以表示为： gi(y)=gj(y), ij,小结：增加维数可以增加模式识别的能力，但计算量要增加，并且需要的样本数大大增加。维数和计算量的折衷。 例3：从25维测量矢量 1维的特征矢量 例4：从25维测量矢量 2维的特征矢量,5.聚类问题,聚类问题，是另一类模式识别问题。如遥感图像分类。这类问题，样本类别不知，甚至类别数目也不知。这类问题经常用在化学、生物、医学、心理学、社会、经济预测、预报等领域 人材预测问题： 有200个问题的答卷，每一个作了0-10的量化 200维的特征空间,七. 模式识别方法中的一些问题,1. 机器学习 人的学习能力，(如小孩认字，能分类),机器能否做到？ 什么是机器学习？ 人脑的不透明过程 机器的透明过程 学习目的的一种：使模式识别系统的某个规定的性能指标达到最优。,所谓学习就是调整系统的参数和结构使性能指标达到最优。,在P.R.中，一般采用错分率的平均值或期望作准则函数： J(c)=E R( F(y,c) 找c* F：决策规则，R()：损失函数，E：数学期望 c：要学习的参数，例如“0”、“1”判别中的阈值,模式的紧致性和可分性,为了能够进行分类，要求同一类的模式组成一个紧致集。 1. 从一点可以均匀过渡到另一点，且途中所有点属于同一类； 2. 小邻域内仍属同一类。,如果模式满足紧致性要求，原则上P.R.没有什么困难。如果在某个特征空间不满足紧致性要求，能否找到一个线性或非线性变换，把它变到另一个空间中的紧致集？神经网络。,距离和相似性度量,紧致性要求定义距离度量（在相应的空间），及模式间的相似性度量 相似不相似。定性、定量描述,本节小结,上面介绍了模式信息处理、模式识别的一些基本概念。,参考书：,模式识别，边肇祺，张学工等著，清华大学出版社。 R.O.Duda, P.E.Hart, and D.G.Stocrk, Pattern Recognition and Scene Analysis, Second ed. K.Fukunaka, Introduction to Ststiscal Pattern Recognition,Second ed.,参考书：,4. S.Theodoridis, and K. koutroumbas, Pattern Recognition, Second ed.,2003. 神经网络和模式识别： 5. Simon Haykin, Neural Networks: a comprehensive F