模式识别绪论

1、模 式 识 别 Pattern Recognition第一章 绪论 模式识别的研究内容、方法和应用 模式识别学科已经有近五十年的历史了模式识别是五十年代末迅速发展的一门学科，当时的兴趣主要在“学习机械”上。在六、七十年代得到了迅速的发展。P.R.的研究推动了“机器智能”的发展，扩大了计算机应用的领域。P.R.所研究的理论和方法在许多领域得到了应用。P.R.已经成为当今机器智能的重要支撑学科。已广泛应用于工业自动化、空间和军事技术、地质、气象、天文、医疗、材料分析、化工、产品检验和控制、经济上的预测和预报等领域。广义上讲如何使机器具有智能。和人工智能学科一样。机器学习的一种方法，参数、分布、决策

2、的学习。狭义上讲研究模式的分类、聚类、决策和估计等问题。使机器具有智能是人类的愿望。（机器是人手的延长，智能机是人脑的延长）但使机器具有智能这个工作很不容易，仍然有许多谜，人脑的机制不明。尽管已有五十年的历史，但仍有许多问题有待解决，目前仍然是一个活跃的学科Ross在1998年的书中说，“一个好的计算机程序可以帮助银行对人的信用进行评估，帮助医生诊断疾病，帮助飞机驾驶员着陆，所以应该更加重视模式识别的教学。”这一节介绍什么是模式识别、模式识别的方法、模式识别的应用，然后结合一些例子说明模式识别的一些基本概念。一. 什么是模式识别 使机器具有能够感知环境，自动地对物体进行描述、分类、分组的能力是

3、科技、工程中的重要问题 。在社会科学、生物学、心理学、医学、市场分析和预测、自动化、计算机视觉、人工智能、遥感、军事、生物特征识别等问题中有重要应用。什么是模式呢？ Watanabe定义模式 “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name.模式，（匈牙利，波兰，新加波)相似但又不完全相同的一些物体、现象，对象。不混沌（chaos）。 模式可以是一个手写的字符、一幅指纹图像、一幅人脸的图像、一段语音信号等。 模式(pattern)这个单词的 两种用法 ：单个，模式类模式的识

4、别/分类可能有两种方式： 有监督的分类/识别（Supervised Classification）：把模式分到预先定义好的类里去。 无监督的分类/识别（Unsupervised Classification, clustering）：基于相似性，把模式聚合成一定的类。二. 模式识别的应用 随着计算机性能的提高、Internet的迅速发展，理论研究的深入，和其他研究领域的融合、促进（如机器学习、神经网络、数学、统计学、计算机科学、生物学等），模式识别的应用不仅在它的传统领域，如文字识别、语音识别、指纹识别、遥感图像、医学等领域越做越好，而且涌现了很多新的应用。模式识别的应用（续）例如数据挖掘（d

5、ata mining）、文档的分类（document classification）、财政金融、股票的预测、预报，多媒体数据库的检索，基于biometrics（生物特征）的人的身份鉴别，人的情感识别等等。特征是数据驱动，自动提取挖掘的，不是专家建议的。 模式识别应用的一些例子 问题的领域 应用 输入模式 模式类 生物信息科学 序列分析 DNA/蛋白质(Protein)序列 基因类型/模式 数据挖掘 搜索有用的模式 多维空间的点 紧凑（Compact）且分得开的聚类 文档分类（document） Internet搜索 文本文件 语义类，如商业、体育、文娱等 模式识别应用的一些例子（续）文本图像分

6、类 盲人阅读机，OCR支票阅读，邮件分拣文本图像 字符工业自动化（计算机视觉） 印刷电路板的质量检查，装配线 灰度或距离（深度）图像 缺陷有/无，抓、装配零件 模式识别应用的一些例子（续）多媒体数据库检索 Internet搜索 Video clip Video genres，如行动、会话等 生物特征识别（biometric） 身份鉴别 指纹、面像、虹膜（iris） 人的认证，访问控制 遥感 农作物等的预测、预报 多频谱图像 地形地貌的分类，生长情况 模式识别应用的一些例子（续）语音识别 电话的自动应答，翻译机，人机通信 语音波形 语音的单字（词） 计算机辅助诊断 X片、CT、fMRI、ECG、

7、EEG、机器故障诊断一维、两维信号正常/异常三. 模式识别的方法 随着供模式识别系统使用的计算机的性能（速度和存储能力）的提高，使得使用更复杂的算法、使用多信息源、多种算法的融合与集成来处理更多的数据、更困难的问题成为可能。另一方面，现实中的问题的要求也越来越高（速度、精度、代价）。 在要解决的问题更复杂的情况下，单一的模式识别方法、单一的数据源已经达不到要求要组合不同的方法（算法）、不同传感器的信息。（Fusion，Several sensing modality)一个模式识别系统，一般都包括以下三个方面 数据的获取和预处理 数据的表示分类、决策（decision making）在解决不同的

8、具体问题时，要根据该问题的性质，确定传感器、预处理、数据表示和分类的算法 常用的模式识别方法 模板匹配（template matching）统计的方法（statistical P.R.） 句法或结构的方法（syntactic or structural P.R.）人工神经网络的方法（artificial neural network, ANN） 这些方法不是绝对独立的。同一种方法有不同的解释，有时要混合使用。 1.模板匹配 模式识别中使用最早、最简单、直观的方法 所谓匹配是一类运算，用来确定两个对象间（点集、曲线、面、形状）的相似性。在模板匹配中，要有一个模板（一般是一个二维形状）或一个模式原

9、型（prototype），待匹配的模式和这个预先存储好的模板相匹配 模板本身也是从训练样本中学习得来的 模板匹配一般要花费较大的计算量，随着计算机速度的加快，这种方法变得更可行了 1. 模板匹配(续）刚性模板匹配的缺点：处理畸变模式难畸变是由传感器的问题、视点的改变、类内偏差大等引起的使用变形模板2. 统计模式识别 在统计模式识别中，每一模式是用一个d维的测量值、特征向量来表示的，它是d维特征空间的一个点。目标是选择这样的一些特征，使同一类的模式在空间中尽量紧凑，而不同类的模式间尽量分开、不相交 给定一组样本，模式识别的任务是要确定决策（分界）面、边界，以把不同的类分开。 在统计决策理论的方法

10、下，决策边界是根据模式的概率分布确定的。这些概率分布是事先知道，或通过学习估计得到。 另外一种统计模式识别的工具是判别分析（discriminant analysis）。这种方法是先假定决策边界的数学形式（一次、二次），然后利用训练样本确定最好的边界（方程中的一些参数）。构造边界时一般利用均方差准则（mean squared error）。再一种方法是从样本中直接构造决策边界。如Vapnik的支撑向量机（support vector machine, SVM） Vapnik方法的思想（哲学，philosophy）是：“当只有有限的信息来求解某一问题时，那你就直接去解这一问题，不要试图去解一个更

11、一般的问题，然后再解决你的特殊问题。因为你手中的信息也许对解决你的具体问题是够（充分）的，但对解决更一般的问题也许就不够了。” 3. 句法或结构的方法 句法模式识别的方法来源于这样的思想：复杂的模式是由简单的子模式组成的，而子模式又是由更简单的子模式组成。最简单的子模式称为基元（primitives），复杂模式就是由这些基元以及它们间的相互关系确定。如同物体组成的原子、分子论。句法模式识别的方法来源于形式语言和自动机：模式句子，基元字母表，模式结构语法规则，模式分类语法分析。规则的产生要靠语法推断 结构模式识别的优点是它的层次结构，用少量的基元和规则来描述物体。这种方法常用在有一定结构的模式上

12、，例如心电图（ECG）、纹理图像（texture）、物体轮廓的分析上 句法模式识别的难点在于如何从噪声干扰的信号中分割出模式基元，如何从训练样本中推断出语法规则来 存在组合“爆炸”的问题，要求大的训练样本集、高计算复杂度。 “Conundrum of combinatorial complexity” 4. 人工神经网络的方法 人工神经网络是一个超大规模的并行计算系统。它由大量很简单的计算单元相互连接组成。模拟人脑的计算，它试图把学习、泛化（generalization）、自适应（adaptivity）、容错（fault tolerance）、分布式表示和计算、联想等功能实现在一个加权的有向图

13、式的结构上：图的节点神经元，有向边（加权的边）神经元的输入输出间的连接 人工神经网络的突出优点是它可以学习复杂的非线性输入输出关系（从样本序列中） 常用的神经网络有两种 : 前馈型网络：分层 多层感知器（Multilayer Perceptron) 径向基函数网（Radial Basis Function) 互连型网络：互连 Kohonen的 Self-Organization Map Hopfield型的互连网 网络学习的过程是利用提供的样本修改连接权（connection weights）或网络的结构（增减神经元 )人工神经网络的应用（如分类、特征提取）获得了很大的普及和成功，其原因在于：

14、 1. 和基于规则或模型的方法相比，较少依赖特定问题领域的知识； 2.对实际工作者来讲，有有效的学习算法可供使用。 人工神经网络为解决非线性的特征提取和分类提供了一套工具。此外，已经存在的统计模式识别方法也可以用神经网络实施，可硬件实施。 Anderson (MIT, 1990)指出：“神经网络是外行人（amateurs）的统计学”。 尽管统计的方法和人工神经网络在基本原理上有很多不同，但它们在方法上是等价或相似的 人工神经网络为外行提供了求解非线性问题的工具 四种方法的比较 StatPRSyntPRNeurPR模式发生的机理 概率模型 形式语法 稳定状态或连接权数组 模式分类（识别、描述）基

15、础 估计/决策理论 语法剖析parsing NN的特性 四种方法的比较（续）特征的组织 特征向量 基元及它们的关系 网络输入或网络状态 典型的学习训练方法有监督无监督 概率密度/分布的估计（一般是参数的）聚类分析 形成语法（启发式的或语法推断）聚类分析确定NN系统的参数，如权等聚类分析局限 较难表示结构信息 较难学习语法规则 语义信息不清楚，“黑箱”，不透明 四. 模式识别系统 有教师的模式识别系统六. 几个例子1. 字符识别 印刷的、手写的 通过OCR等设备（Optical Character Reader）得到观测向量 GG字符识别观察向量：物理的，几何的，数学的，主观的 特征空间：Rd，

16、0，1d 符号或逻辑值的2. 医疗诊断问题-心电图正常/异常 小结： 模式可以用多维向量空间中的一个矢量来表示，一个点 模式不是确定性的，带有概率性质，要用统计的方法，要用到数理统计、线性代数（矩阵）等工具。 分类就是要把特征空间划分为一些区域，不相交，类间不重迭。 R1R2R3线性（或分段线性）R1R2R3二次的R1R2R3R4一般的分类区域、形式线性（或分段线性）二次的一般的R1R2R3R3R2R2R1R1R3R43. 两类字符识别 10测量矢量:0000.3.000.6.如何确定决策的阈值：作直方图，可以得到“0”和“1”的分布NP5.5R1R2P1P05.55.5面积小结： 设计分类器

17、时不是要求没有错分类的，而是在一定意义下使错误率最小 下面我们再看一个稍微复杂的问题 4. 三类字符识别-除了“0”、“1”之外，还要识别“x” X一个特征（占的面积）就不够了。“0”、“x”的覆盖面积近似相等。加上另一特征（对角线上1、7、13、19、25面积之和）分类规则： if else 上面的分类规则还可以写成更方便的形式： 定义函数：这样，决策规则可以表示为：若分到 类 则上面的g(y)称为判别函数。这种形式特别方便计算机实施 计算各个判别函数 选择最大的判别函数值，归到该类 所形成的决策区域为： 各个分类（决策）边界可以表示为：gi(y)=gj(y), ij 小结：增加维数可以增加

18、模式识别的能力，但计算量要增加，并且需要的样本数大大增加。维数和计算量的折衷。 例3：从25维测量矢量 1维的特征矢量例4：从25维测量矢量 2维的特征矢量5.聚类问题聚类问题，是另一类模式识别问题。如遥感图像分类。这类问题，样本类别不知，甚至类别数目也不知。这类问题经常用在化学、生物、医学、心理学、社会、经济预测、预报等领域 人材预测问题： 有200个问题的答卷，每一个问题作了0-10的量化 200维的特征空间 七. 模式识别方法中的一些问题1. 机器学习人的学习能力，(如小孩认字，能分类),机器能否做到？什么是机器学习？人脑的不透明过程 机器的透明过程学习目的的一种：使模式识别系统的某个规

19、定的性能指标达到最优。所谓学习就是调整系统的参数和结构使性能指标达到最优。在P.R.中，一般采用错分率的平均值或期望作准则函数： J(c)=E R( F(y,c) 找c* F：决策规则，R()：损失函数，E：数学期望c：要学习的参数，例如“0”、“1”判别中的阈值模式的紧致性和可分性 为了能够进行分类，要求同一类的模式组成一个紧致集合。1.从一点可以均匀过渡到另一点，且途中所有点属于同一类； 2. 小邻域内仍属同一类。 如果模式满足紧致性要求，原则上P.R.没有什么困难。如果在某个特征空间不满足紧致性要求，能否找到一个线性或非线性变换，把它变到另一个空间中的紧致集？神经网络。 距离和相似性度量

20、紧致性要求定义距离度量（在相应的空间），及模式间的相似性度量相似不相似。定性、定量描述 本节小结 上面介绍了模式信息处理、模式识别的一些基本概念。 参考书：模式识别，边肇祺，张学工等著，清华大学出版社。R.O.Duda, P.E.Hart, and D.G.Stocrk, Pattern Classification. Second ed. 模式分类, 机械工业出版社K.Fukunaka, Introduction to Ststiscal Pattern Recognition,Second ed.参考书：4. S.Theodoridis, and K. koutroumbas, Patte

21、rn Recognition, Second ed.,2003.神经网络和模式识别：5. Simon Haykin, Neural Networks: a comprehensive Foundation, Second ed.,（清华大学影印版），2001。6. 人工神经网络与与模拟进化计算。 阎平凡，张长水。清华大学出版社。 神经网络和模式识别7. C.M.Bishop, Neunal Networks for Pattern Recognition. Oxford: Clarendon Press,1995.8. B.Ripley, Pattern Recognition and Neu

22、ral Networks. Cambridge, Mass: Cambridge Univ. Press,1996.An Example“Sorting incoming Fish on a conveyor according to species using optical sensing”Sea bassSpeciesSalmonProblem AnalysisSet up a camera and take some sample images to extract featuresLengthLightnessWidthNumber and shape of finsPosition

23、 of the mouth, etcThis is the set of all suggested features to explore for use in our classifier! PreprocessingUse a segmentation operation to isolate fishes from one another and from the backgroundInformation from a single fish is sent to a feature extractor whose purpose is to reduce the data by measuring certain featuresThe features are passed to a classifier ClassificationSelect the length of the fish as a possible feature for discriminationThe length is a poor feature alone!Select