第一章模式识别引论.PDF

第一章 模式识别引论 2009.09.15 模式识别：（人、动物或机器）获取关于某一事 物的信息（数据），并将其归为某一类别的过程 。 模式识别能力普遍存在于人和动物的认知系统， 是人和动物获取外部环境知识，并与环境进行交 互的重要基础。 通过感知环境，人类时时刻刻都在完成某种模式 识别的任务：辨认人脸或物体、区分声音、理解 语言的内容、根据气味辨别食物的类别或好坏等。 信息来源 83 11 6 视觉 听觉 其他（触觉、 味觉等） 概述 概述 模式识别作为一门学科，是研究用机器完成自动 识别事物的工作。 人们希望赋予机器类似的感知、识别、理解、自 学习、自适应等能力。 模式识别是使计算机模仿人的感知能力，从感知 数据中提取信息（判别物体和行为）的过程。 是由数学、控制理论、信息处理、计算机技术、 生物生理学和心理学等众多学科交叉融合产生。 是理论和应用并重的学科。 概述 模式识别的意义 计算机能比人类更快速地处理海量数据。 数字化感知数据：来源丰富、数量巨大。 处理人类难以解决的识别问题。 研究机器模式识别的能力可以帮助理解人脑中的 模式识别过程。（反之亦然） 概述 模式识别的难点 感知数据：非结构化（像素、波纹等） 概述 模式识别的发展简史 1929 年 G. Tauschek 发明阅读机，能够阅 读0-9 的数字。 30 年代 Fisher 提出统计分类理论，奠定了 统计模式识别的基础。在随后的60 70 年代， 统计模式识别发展很快；但是由于被识别的模式 越来越复杂，特征也越多，因而出现“ 维数灾难” 。 不过由于计算机运算速度的迅猛发展，这个问题 得到了一定的克服。统计模式识别至今仍是模式 识别的主要理论。概述 模式识别的发展简史 50 年代 N. Chomsky 提出了形式语言理 论；美籍华人付京荪提出句法结构模式识别。 60 年代 L.A.Zadeh 提出了模糊集理论，模 糊模式识别理论得到了较为广泛的应用。 80 年代 Hopfield 提出神经元网络模型理论。 近些年人工神经元网络在模式识别和人工智能上 得到较广泛的应用。 90 年代 小样本学习理论，支持向量机也受 到了很大的重视。 概述 相关的学术组织 1973 年 IEEE 发起了第一次关于模式识别的国际 会议“ICPR” ，成立了国际模式识别协会 “IAPR” ，每2 年召开一次国际学术会议。 1977 年 IEEE 的计算机学会成立了模式分析与机 器智能（PAMI ）委员会，每2 年召开一次模式识 别与图象处理学术会议。 国内的组织有电子学会，通信学会，自动化学 会，人工智能学会，中文信息学会 概述 主要期刊 IEEE Trans. on PAMI ，1978-，IEEE Computer Society Pattern Recognition ，1968-，PR Society, Elsevier Pattern Recognition Letter ，1980- ，IAPR, Elsevier Machine Learning ，Neural Computation ，IEEE Trans. On NN Int. Journal of PR and AI, 1988- (World Scientific) Pattern Analysis and Applications, 1997- (Springer) Int. J. Document Analysis with some degree of correspondence in successive trials or observations. 美国传统词典 A reresentative sample 模式识别和模式的概念 什么是模式（pattern ）？ * Watanabe defines a pattern “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name.” fingerprint image handwritten word human face speech signal DNA sequence *S. Watanabe, Pattern Recognition: Human and Mechanical, 1985. 模式识别和模式的概念 什么是模式（pattern ）？ 广义地说，存在于时间和空间中可观察的物 体，如果我们可以区别它们是否相同或是否相 似，都可以称之为模式。 模式所指的不是事物本身，而是从事物获得的 信息。因此，模式往往表现为具有时间和空间 分布的信息。 模式的直观特性: 可观察性 可区分性 相似性 模式识别和模式的概念 模式表示一类事物。 如印刷体A 与手写体A 属同一模式。B 与A 则属于 不同模式。 样本是具体的事物，而模式是对同一类事物概念 性的概括。 如每一个具体的字母A 、B 是其模式的具体体现。 模式类与模式联合使用时，模式表示具体的事 物，而模式类则是对这一类事物的概念性描述。 模式识别是从样本到类别的映射。 模式识别和模式的概念 常见模式举例 模式识别和模式的概念 常见模式举例 人脸的模式 共性：人脸作为一类目标区别于其他； 个性：每个人作为一类区别于其他。 模式识别和模式的概念 常见模式举例 Texture Patterns模式识别和模式的概念 常见模式举例 社会模式 信用：收入、消费习惯、贷款 保险：驾龄、出险次数、车型、驾驶习惯 信息服务：爱好、浏览习惯、文化程度 择偶：背景、爱好、性格、经济状况 性格： 文化： 事件： 政治： 模式识别和模式的概念 什么是模式（pattern）？ 对象的组成成分或影响因素中存在的直接或间接 的规律性的关系; or 存在确定性或随机规律的对象、过程或事件的集 合; 模式识别和模式的概念 什么是识别（recognition ） 说文 识，知也。 别，分解也。 现代英汉词典 The act or process of identifying (or associating) an input with one of a set of know possible alternatives. 美国传统词典 An awareness that something perceived has been perceived before. 模式识别和模式的概念 什么是识别（recognition ） 即再认知 re-cognition; 识别是人把具体事物归类，是时刻发生的活动： 周围物体的认知：桌子、椅子 人的识别：张三、李四 声音的辨别：汽车、火车、狗叫、人语 气味的分辨：炸带鱼、红烧肉、臭豆腐 本课程讨论机器对模式类的分辨，判断，分类； 主要研究 相似 和分类 问题。 人和动物的模式识别能力是极其平常的，但对计算机 来说却是非常困难的。 模式识别学科的目的：提高机器的感知能力，开拓更 广泛的应用。 模式识别和模式的概念 什么是模式识别？ Pattern Recognition The recognition of patterns To see something 1 as something 2 通过对事物的观察对其 某种性质的认识. 尤指 分类性质 模式识别和模式的概念 Anil K. Jain ：Pattern recognition is the study of how machines can: observe the environment; learn to distinguish patterns of interest from their background; make sound and reasonable decisions about the categories of the patterns. 模式识别和模式的概念 什么是模式识别？ 模式识别和模式的概念 什么是模式识别？ 对象：样本 sample ( 模式） 模式：类 class ( 模式类） 观察：特征 features ( 属性） 模式识别： 把样本根据其特征归类；又称模式分类（pattern classification) 例如: 硬币分类 三类：1 角、5 角、1 元 特征：重量、体积、文字、图案 模式识别系统 执行模式识别的计算机系统，该系统被用来执行 模式分类的具体任务。 模式识别系统 数据获取（data acquisition ） 由不同形式的传感器（摄像机、话筒等）构成； 实现信息获取以及信息在不同媒介之间的转换； 将非电信息转换成电信号 一维波形：话筒将声音信号转换成电信号（声波）， 脑电图，心电图，震动波形等； 二维图像：景物信息在摄像机靶面成像并转换成二维 的像素矩阵（照片），文字，指纹，地图等； 物理参量和逻辑值：各种化验数据，某参量正常与否、 症状有无等； 过程包括测量、采样和量化。 模式识别系统 预处理 （preprocessing ） 去除所获数据中的噪声； 增强有用的信息； 对输入测量仪器或其他因素所造成的退化现象进 行复原。 模式识别系统 特征选择和提取 （feature extraction and selection ） 对所获取的信息实现从测量空间到特征空间的转 换。 将所获取的原始量测数据转换成 能反映事物本质 并将其最有效分类的特征 表示。 输入：原始的测量数据（经过必要的预处理）； 输出：将原始测量数据转换成有效方式表示的信 息，从而使分类器能根据这些信息决定样本的类 别。模式识别系统 分类决策（classification decision ） 在特征空间根据事先确定的判决规则把被识别的 对象分类。 原则：最小化引发的损失或者错误识别率。 两种工作方式： 训练方式：在确定的特征空间，对一定数量的训练样 本数据进行特征选择与提取，得到它们在特征空间的 分布，依据这些分布设计分类器（即确定判决规则）。 分类决策方式：分类器在分界形式及其具体参数都确 定后，对待分类样本进行分类决策的过程。 模式识别系统示例 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 数据获取：通过光学感知手段，架设一个摄像 机，采集一些样本图像，获取样本数据。 预处理 ：去除噪声，用一个分割操作把鱼和鱼之 间以及鱼和背景之间分开。 特征提取和选择 ：对单个鱼的信息进行特征选 择，通过测量某些特征来简化原始数据，从而减 少信息量。 长度、亮度、宽度、鱼翅的数量和形状、嘴的位置等。 分类决策：把提取的特征送入决策分类器。 模式识别系统示例 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 模式识别系统示例 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 长度 作为分类特征 不存在单一的阈值能完美分类。 图：训练样本的长度特征直方图 模式识别系统示例 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 光泽度 作为分类特征 不存在单一的阈值能完美分类。 图：训练样本的光泽度特征直方图 图：训练样本的光泽度特征和宽度特征的散布图 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 光泽度 和 宽度 作为分类特征（二维特征向量） 图中斜线可作为分类判别的边界（decision boundary ）。 模式识别系统示例模式识别系统示例 自动按品种分类传送带上的鱼类（鲈鱼和鲑鱼） 光泽度 和 宽度 作为分类特征（二维特征向量） 复杂的判决边界过度“ 调谐” （tune ）到训练样 本，因而缺乏“ 推广能力” （generalization ）。 过拟和（overfitting ），应允许特例的存在，无需完 全适应训练样本。 可视为违反奥卡姆剃刀（Occams razor ）原则。 判决曲线需要平衡分类性能和分界面复杂度。 模式识别研究内容 数据预处理 视频、图像、信号处理 模式分割 模式/背景分离、模式-模式分离 运动分析 目标跟踪、运动模式描述 模式描述与分类 特征提取/选择、模式分类、聚类、机器学习 模式识别应用研究 针对具体应用的方法与系统 模式识别的一些基本问题 学习 模式类的紧致性 相似和分类 特征生成 模式识别的一些基本问题 学习 让一个机器有分类决策能力，需要找到具体的分 类决策方法。确定分类决策方法的过程就是 学习 。 人类的学习过程： 在日常生活中进行模式识别的活动，在学习过程中掌 握了很强的分辨事物的能力。 机器的学习过程： 有监督学习（Supervised learning ） 非监督学习（Unsupervised learning ） 模式识别的一些基本问题 学习 有监督学习 给出若干已知类别的训练样本（training samples ）； 由机器从这些样本中进行学习（训练 training/learning ）； 学习的目的在于从这些样本中勾画出各类事物在特征 空间分布的规律性，从而能够对新的样本进行判断。 确定分类使用的具体数学公式及其参数。 监督模式识别 模式识别的一些基本问题 学习 非监督（无指导）学习 所面对的只有未知类别的样本； 由机器从这些样本中进行学习（自学习）； 学习的目的在于从这些样本中发现规律：这种规律应 该是某种固有的关系，或者依据这种规律对对象的分 类有某种功用。 确定分类使用的具体数学公式及其参数。 非监督模式识别 聚类分析（cluster analysis or clustering ）模式识别的一些基本问题 学习 原则一：只要条件允许就要使用较 简单的分类方法。 线性分类器：用一条直线作为分界线。 原则二：错分类最小，损失最小。 不同准则函数的最优解对应不同的学习 结果，得到性能不同的分类器。 确定数学公式中的参数也是一个学 习过程。 如果当前采用的分类函数会造成分类错 误，利用错误提供应如何纠正的信息， 纠正分类函数。 模式识别的一些基本问题 模式类的紧致性 分类器设计的难易程度与模式在特征空间的分布 方式有密切关系。 下面三图分别表示了两类样本在空间分布的三种状况 图1 中两类样本存在各自明确的区域，它们之间的分界 线( 或面，超曲面) 具有简单的形式，因而也较易区分。 图2 中两类虽有各自不同的区域，但分界面的形式比较 复杂，因而设计分类器的难度要大得多。 图3 中类的情况已经到了无法将它们正确分类的地步。 用模式类的紧致性描述 模式识别的一些基本问题 模式类的紧致性 例：图中有一个立方体的8 个端点，是8 个 样本。它们由000 ，001 ，010 ，011 ， 100 ，101 ，110 ，111 八个点集组成。如 果我们希望用平面将它们划分为A1 与A1 两 类，显然这与它们的集合组成有关。 如果A1 由111 ，101 ，110 ，100 组成， 而A2 由其余四个点组成，则只需要一个平 面就可将它们分开。 若要分开A1=111,001,100,010 与 A2=000,011,101,110 这样两个集 合，则需要三个平面。在这种情况下，A1 集合中任一点的一位码变化，如111 变成 101 ，它就成为A2 集合的成员。对A2 也有 如此情况。 模式识别的一些基本问题 模式类的紧致性 通常称位于两类的边界上的点为 临界点 ，它们略 一改变就会改变它们的类别，越过边界。 非临界点则称为集合的 内点 ，它们略有变化不会 有类别变更的情况发生。 图1 中只有少量的临界点；而图2 中临界点的数量 已经在总点数中占很高的比例，其模式的紧致性 就很差了。 模式识别的一些基本问题 模式类的紧致性 紧致集的性质 一 临界点的数量与总的点数相比很少； 二 集合中任意两个内点可以用光滑线连接，在该连线 上的点也属于这个集合； 三 每个内点都有一个足够大的邻域，在该邻域中只包 含同一集合中的点。 形象的说法：类间没有混叠，分界面干净利索。 模式识别的一些基本问题 模式类的紧致性 假如每个模式类都满足紧致性假设，则解决模式 识别问题就不会碰到什么原则上的困难。但对于 很多实际问题这个假设是不成立的。 只要各个模式类是可分的，总存在这样一个特征 空间，使变换到该空间中的集合满足紧致性要求。 这样的变换和具体问题密切相关，还没有普遍有效的 理论和方法。 影响数据紧致性的因素：数据本身特性、数据描 述方法。模式识别的一些基本问题 相似和分类 人们依据物体之间的 相似程度 将其归类。 在特征空间中，用 特征向量 描述样本的属性，用 某种 距离度量 作为样本间相似性度量。 相似性度量非负； 样本本身间的相似性度量应最大； 相似性度量具对称性； 在满足紧致性的条件下，相似性度量应是点间距离的 单调函数。 统计模式识别的各种方法实际上都是直接或间接 以距离度量为基础的。 模式识别的一些基本问题 相似和分类 几种可作相似性度量的距离度量 欧式距离 绝对值距离（absolute value distance ） 向量夹角 模式识别的一些基本问题 相似和分类 分类具有主观性 ：目的不同，分类不同，常缺乏 纯客观的分类标准。依据哪些特征决定相似并进 行分类，取决于行为的目的和方法。 例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳 类，但是从产业角度来讲鲸鱼属于水产业，牛和马属 于畜牧业。 分类的客观性 ：科学性，判断分类必须有客观标 准。 分类追求客观性，但主观性也很难避免，这就是 分类的复杂性。 模式识别的一些基本问题 特征生成 模式识别系统设计的任务就是要寻找一种变换， 即选择一种特征空间，使不同类别的样本在相应 的特征空间能正确地分开（ 满足紧致性 ）。 低层特征：最靠近信息输入端。 无序尺度：有明确的数量和数值； 有序尺度：有先后、好坏的次序关系； 名义尺度：无数量、无次序关系，如有红，黄颜色。 中层特征：经过计算，变换得到的特征。 高层特征：在中层特征的基础上有目的的经过运 算形成。 例：椅子的重量= 体积* 比重 （体积与长，宽，高有 关；比重与材料，纹理，颜色有关。因此包含了低、 中、高三层特征。） 模式识别的一些基本问题 特征生成 选择特征须适应特定的行为目的，是认知和识别 的核心问题。 模式识别的一些基本问题 特征生成 选择特征须适应特定的行为目的，是认知和识别 的核心问题。 要判别一个病人是否发炎，应用什么特征？ 身高、体重、血压 ？ 否 体温？ 可能 白血球数目? 是 要从一段语音识别说话人的性别，应用什么特征？ 直接利用声音信号（时间序列）？ 否 声音大小？说话快慢？说话内容？ 否 音调高低（频率）？ 可能