模式识别第一章绪论

1、1相关学科n统计学n概率论n线性代数（矩阵计算）n形式语言n人工智能n图像处理n计算机视觉n等等2教学目标n 掌握模式识别的基本概念和方法；n 有效地运用所学知识和方法解决实际问题；n 为研究新的模式识别的理论和方法打下基础。3考核方式n研究报告：20%n以下内容任选一个n概率分布估计；n特征选择；n识别和分类等。n提交研究报告、算法演示程序n18周课堂现场验收n考试：80%4参考教材n主教材：模式识别(第二版)，边肇祺，张学工等，清华大学出版社， 2000 n参考书：n现代模式识别（第二版），孙即祥，高等教育出版社，2008n模式识别（第四版），Sergios Theodorids等，电子工

2、业出版社20105相关期刊nIEEE Transaction on Pattern Analysis and Machine Intelligence，PAMInPattern RecognitionnPattern Recognition Lettern模式识别与人工智能6课程主要内容n 1 模式识别概述n 2 贝叶斯决策理论 n 3 概率密度函数的估计n 4 线性判别函数n 5 近邻法n 6 非监督学习方法n 7 特征的选择与提取n 8 其他模式识别方法7第一章 绪论n1.1 模式识别和模式n1.2 模式识别系统n1.3 模式识别方法n1.4 模式识别应用81.1 模式识别和模式91.1

3、模式识别和模式模式n广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。n狭义地说：是对感兴趣的客体的定量的或结构的描述；从工程角度讲是指客观事物存在形式的数学表达。n模式不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。n模式的直观特性:n可观察性n可区分性n相似性101.1 模式识别和模式模式识别n人类具有很强的模式识别能力，时刻在完成某种模式识别的任务。n周围物体的认知：桌子、椅子n人的识别：张三、李四n声音的辨别：汽车、火车，狗叫、人语n气味的分辨：炸带鱼、红烧肉n人和动物的模式识别能力是极其平常的，但对计

4、算机来说却是非常困难的。11n模式识别研究目的：利用计算机对客观对象进行分类，在一定的决策策略约束下，使识别的结果尽量与客观物体相符合。nY = F(X)nX的定义域取自特征集nY的值域为类别的标号集nF是模式识别的判别方法1.1 模式识别和模式12n计算机“模式识别”的概念n将未知的事物或现象与各种模式进行比较，看它与哪一类模式最接近，从而判断该事物或现象属于哪一类。 n用计算机模拟人的各种识别能力，完成以下认识“功能”：n 观察环境n 从背景中区分出感兴趣的“模式”n 作出适当的模式判别或者分类n模式识别（Pattern Recognition）：作为一门学科，是研究用计算机来完成事物的自

5、动识别工作。机器识别，计算机识别，机器自动识别。1.1 模式识别和模式13n 识别：就是对客观事物按其物理特征来进行分类。给定一模式，识别/分类可以由两类任务完成：n 监督分类：(判别分析Discriminant analysis)-将输入的“模式”归入已知的类别中。n 非监督分类：（聚类 clustering）-将输入的“模式”归入到划分的未知类别中。n 模式识别主要工作就是如何设计一个模式分类器。 1.1 模式识别和模式141.1 模式识别和模式n基本概念：n样本（Sample）：一个具体的研究（客观）对象。如某人写的一个汉字，一幅图片等。n模式(Pattern)：对客体（研究对象）特性的

6、描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。n模式是对同一类事物概念性的概括。样本是具体的事物。n特征：最能揭示样本属性的观测量。n特征量，如物理量（直接反映特征的实际物理或几何意义）。151.2 模式识别系统分类训练模式识别系统由：模式识别系统由：数据获取、数据获取、预处理预处理、特征提特征提取取/ /选择选择，分类器设计和分类决策分类器设计和分类决策组成。组成。161.2 模式识别系统n数据获取：用计算机可以运算的符号来表示所研究的对象。n二维图像：文字、指纹、地图、照片等n一维波形：脑电图、心电图、季节震动波形等n物理参量和逻辑值：体温、化验数据、参量正

7、常与否的描述n预处理：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原。171.2 模式识别系统n特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征n测量空间：原始数据组成的空间n特征空间：分类识别赖以进行的空间n模式表示：维数较高的测量空间-维数较低的特征空间n分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别n基本做法：在样本训练集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。181.2 模式识别系统n分类器设计：将特征空间划分成有各类占据的子空间，确定相应的类分界面或形成判决规则。使得按这种

8、规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。n分类决策：利用分类器的类分界形式或判决规则，对待分类样本的类空间归属进行判决的过程。191.2 模式识别系统n模式识别四个空间20n模式识别三大任务：n模式采集：从客观世界（对象空间）到模式空间的过程称为模式采集。n特征提取和特征选择：由模式空间到特征空间的变换和选择。n类型判别：特征空间到类型空间所作的操作。1.2 模式识别系统21模式识别系统设计步骤估计可能的误差率估计可能的误差率 性能评估性能评估 5确定分类参数确定分类参数 分类器训练分类器训练 4确定分类原理和机理确定分类原理和机理 分类器设计分类器设计 3确定哪些属性

9、可以区别不同的目标确定哪些属性可以区别不同的目标 特征选取特征选取 2确定需要分类和识别的目标确定需要分类和识别的目标设计系统目标设计系统目标1 功功 能能 步骤步骤 序号序号 1.2 模式识别系统22n模式系统设计中的有关问题模式系统设计中的有关问题n数据收集：n怎样才能知道已经收集到足够多的并有代表性的供PR系统学习训练与性能测试的数据(样本）？n特征选择：n与分析对象的问题特点有关。选择出发点：简单提取、对无相关变换保持不变性、抗干扰。n如何将先验知识与实验数据结合起来，选择有用、有效的特征？1.2 模式识别系统23n模式系统设计中的有关问题模式系统设计中的有关问题n分类器模型选择：n不

10、满意分类器的性能，采用其它不同的类别模型。n学习训练：n利用所收集的样本数据确定分类器。模式识别就是研究各种不同算法用于学习训练分类器与选择模型。n有监督学习（有教师学习）：预先已知训练样本集合中每个样本的类别标号。n无监督学习（无教师学习）：预先不知道训练样本集合中每个样本的类别标号。n是否存在一个通用的算法用于分类器学习训练。1.2 模式识别系统24n模式系统设计中的有关问题模式系统设计中的有关问题n性能评价：n测试错误率或者说误差率，以及从一个特征转换为另外一个特征后的分类器性能。n能否找到最优或最佳的分类器？其标准是什么？n计算复杂性n计算复杂性与分类器性能之间折中是什么？n如果特征维

11、数、模式与类别之间关系看作是一个函数，则算法的数量大小如何？是否存在最优？1.2 模式识别系统25模式识别过程实例n在传送带上用光学传感器件对鱼按品种分类鲈鱼(Seabass)品种鲑鱼(Salmon)26n 架设一台摄像机，拍摄若干样品的图像，抽取特征：n长度长度(Length)n光泽光泽(Lightness)n宽度宽度(Width)n鳍鳍(fins)的数目与形状的数目与形状n嘴的位置嘴的位置利用这些利用这些特征特征设计设计分类器分类器(classifier(classifier) )模式识别过程实例27u 预处理预处理(Preprocessing)(Preprocessing)采用采用分割技

12、术分割技术将不同的鱼分离开来，或者将不同的鱼分离开来，或者将鱼从背景中分来。将鱼从背景中分来。u来自单条鱼的信息送到一个来自单条鱼的信息送到一个特征抽取器特征抽取器( (筛选筛选/ /选择选择) )，其目的减少测量某些特征，其目的减少测量某些特征的数据量。的数据量。u精减的特征输入到一个精减的特征输入到一个分类器分类器。 模式识别过程实例28模式识别过程实例29选择鱼的选择鱼的长度长度作为一种可能的作为一种可能的特征特征，用，用来来区别区别鱼的品种。鱼的品种。模式识别过程实例30仅凭仅凭长度长度作为一种特征是不能精确区分两作为一种特征是不能精确区分两种鱼，选择种鱼，选择光泽度光泽度，成为另一种

13、，成为另一种特征特征。模式识别过程实例31阈值阈值判别边界判别边界(decision boundary)(decision boundary)与与代价代价(cost)(cost)关系关系 为减少将鲈鱼误判为鲑鱼的数目为减少将鲈鱼误判为鲑鱼的数目-代价代价最小化，最小化，判别边界判别边界向光泽度较小的值移向光泽度较小的值移动。动。决策理论决策理论(decision (decision theory)theory)的任务的任务模式识别过程实例32采用采用光泽度光泽度与与宽度宽度( (二维特征二维特征) )，描述鱼的数据，描述鱼的数据-模式模式鱼鱼12xXx光泽度光泽度宽度宽度模式识别过程实例33u

14、可以增加一些与上述相关独立的可以增加一些与上述相关独立的特征特征，但，但是判别性能并不是随着特征的数量增加而是判别性能并不是随着特征的数量增加而增加，相反带来计算量、决策边界复杂性增加，相反带来计算量、决策边界复杂性等其它额外开销，这些新的增特征可以看等其它额外开销，这些新的增特征可以看作是作是“噪声特征噪声特征”(noisy features)(noisy features)。注意：注意：模式识别过程实例34完美分类：理想的最好的决策边界完美分类：理想的最好的决策边界模式识别过程实例35设计一个设计一个分类器分类器(classifier)(classifier)的中心目标的中心目标是正确区分

15、是正确区分( (分类分类) )新的输入数据新的输入数据( (样本样本) )模式识别过程实例36模式识别发展史n1929年 G. Tauscher发明阅读机，能够阅读0-9的数字。n30年代 Fisher提出统计分类理论，奠定了统计模式识别的基础。n50年代傅京荪在Noam Chomsky的形式语言理论基础上提出句法结构模式识别。n60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。n80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。n90年代小样本学习理论，支持向量机受到很大重视。37概率分类法概率分类法几何

16、分类法几何分类法聚类分析聚类分析 监督分类监督分类 统计模式识别统计模式识别 模模 式式 识识 别别结构（句法）模式识别结构（句法）模式识别模糊模式识别模糊模式识别神经网络法、支持向量机、流行学习法神经网络法、支持向量机、流行学习法非监督分类非监督分类1.3 模式识别的方法38统计模式识别n模式描述方法：n特征向量 n模式判定：n模式类用条件概率分布P(X/i)表示，m类就有m个分布，然后判定未知模式属于哪一个分布。12( ,)nxx xx39n理论基础：概率论，数理统计n主要方法： 几何分类：线性分类，非线性分类统计分类：Bayes决策无教师的分类：聚类分析n主要优点1）比较成熟2）能考虑干

17、扰噪声等影响3）识别模式基元能力强n主要缺点1）对结构复杂的模式抽取特征困难2）不能反映模式的结构特征，难以描述模式的性质3）难以从整体角度考虑识别问题统计模式识别40句法（结构）方法n许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元”n每个模式都可以由基元根据一定的关系来组成n基元可以认为是语言中的字母，每个模式都可以认为是一个句子，关系可以认为是语法n模式的相似性由句子的相似性来决定41n模式描述方法：n符号串，树，图n模式判定：n是一种语言，用一个文法表示一个类，m类就有m个文法，然后判定未知模式遵循哪一个文法。句法（结构）方法42n理论基础：形式语言，自动机技术n主要方法

18、：自动机技术、CYK剖析算法、Early算法、转移图法n主要优点n适合结构性强的模式n识别方便，可以从简单的基元开始，由简至繁。n能反映模式的结构特征，能描述模式的性质。n对图象畸变的抗干扰能力较强。n主要缺点抗噪声能力差，计算复杂度高，当存在干扰及噪声时，抽取特征基元困难，且易失误。句法（结构）方法43句法（结构）方法预处理特征提取（基元提取）句法分析文法推断模式信息分类结果类别文法训练过程分类过程44句法（结构）方法如果用一种文法可以生成以下语言：如果用一种文法可以生成以下语言：L(G)=aL(G)=an nb bn nc cn n|n=1,2.|n=1,2.acbacbaaccbbaac

19、cbbacb基元基元结构相似的样本结构相似的样本45n模式描述方法：n模糊集合 A=(a,a), (b,b),. (n,n)n模式判定：n是一种集合运算。用隶属度将模糊集合划分为若干子集， m类就有m个子集，然后根据择近原则分类。模糊模式识别46模糊模式识别n理论基础：模糊数学n主要方法：模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵n主要优点：由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。n主要缺点：准确合理的隶属度函数往往难以建立，故限制了它的应用。47n理论基础：神经生理学，心理学n模式描述方法：以不同活跃

20、度表示的输入节点集n模式判定：是一个非线性动态系统。通过对样本的学习建立记忆，然后将未知模式判决为其最接近的记忆。n主要方法：BP模型、HOPField模型等n主要优点可以有效解决一些复杂的非线性问题、背景知识不清楚和推理规则不明确的问题。允许样本有较大的缺损、畸变。n主要缺点缺少有效的学习理论、目前能识别的模式类还不够多。神经网络48一.模式(样本)表示方法1.向量表示 : 假设一个样本有n个变量(特征) = (X1,X2,Xn)T2. 矩阵表示: N个样本，n个变量(特征) 变 量 样 本 x1 x2 xn X1 X11 X12 X1n X2 X21 X22 X2n XN XN1 XN2

21、XNn 有关模式识别的若干问题493. 几何表示 一维表示 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有关模式识别的若干问题50有关模式识别的若干问题n分类器设计的难易程度与模式在特征空间的分布方式有关，分布特性可用紧致性来描述。n模式类的紧致性：n集合中任意两个内点可以用光滑线连接，在该连线上的点也属于这个集合。n每个内点都有一个足够大的邻域，在该邻域中只包含同一集合中的点。n假若每个模式类都满足紧致性假设，则解决模

22、式识别间题就不会碰到什么原则上的困难。但对于很多实际问题这个假设是不成立的。n只要各个模式类是可分的，总存在这样一个空间，使变换到这个空间中的集合满足紧致性要求。51n紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。n临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）有关模式识别的若干问题52类划分情况1：A1（111，101，110，011）A2（000，010，100，001）类划分情况2：A1（111，001，100，010）A2（000，011，101，110）有关模式识别的若干问题53有关模式识别的若干问题似与分类问题远不像集合表达那样简单明