资源描述
第第1 1章章 概论概论1.11.1模式识别的基本概念模式识别的基本概念1.21.2模式识别系统模式识别系统1.31.3模式识别的基本方法模式识别的基本方法1.4 1.4 模式识别的应用模式识别的应用1.5 1.5 模式识别的基本问题模式识别的基本问题1.11.1模式识别的基本概念模式识别的基本概念定义定义(Definition)Patternrecognitionisthestudyofhowmachinescanobservetheenvironment,learntodistinguishpatternsofinterestfromtheirbackground,andmakesoundandreasonabledecisionsaboutthecategoriesofthepatterns.(AnilK.Jain)1.11.1模式识别的基本概念模式识别的基本概念模式模式(pattern)：具有某种特定性质的具有某种特定性质的观察对象观察对象。广义地，。广义地，存存在于时间、空间中可观察的事物，具有时间或空间分布的信在于时间、空间中可观察的事物，具有时间或空间分布的信息。息。观察对象举例：观察对象举例：一个数字、一个数字、一句话、一句话、一张照片等都是观一张照片等都是观察对象，都能成为模式识别中的识别对象。察对象，都能成为模式识别中的识别对象。模式识别模式识别(Pattern Recognition)：用计算机实现人对各种事用计算机实现人对各种事物或现象的分析、描述、判断、识别。物或现象的分析、描述、判断、识别。模式类模式类：具有相似特性的模式的集合。：具有相似特性的模式的集合。（模式与模式类的关系相当于集合论中的元素与集合的关系）（模式与模式类的关系相当于集合论中的元素与集合的关系）1.11.1模式识别的基本概念模式识别的基本概念模式识别与图像处理、图像识别的关系模式识别与图像处理、图像识别的关系：模式识别是模拟人的某些功能。模拟人的视觉：计算机模拟人的视觉：计算机+图像传感器图像传感器 模拟人的听觉：计算机模拟人的听觉：计算机+声音传感器声音传感器 模拟人的嗅觉和触觉：计算机模拟人的嗅觉和触觉：计算机+嗅觉嗅觉/触觉传感器触觉传感器 模式识别技术当前主要是对视觉和听觉能力的模拟。模拟人模式识别技术当前主要是对视觉和听觉能力的模拟。模拟人的视觉能力就是用计算机来做图像识别和理解工作；模拟人的视觉能力就是用计算机来做图像识别和理解工作；模拟人的听觉就是用计算机来做语音（或者各种声音）识别和理解的听觉就是用计算机来做语音（或者各种声音）识别和理解方面的工作。方面的工作。1.11.1模式识别的基本概念模式识别的基本概念 模式识别模式识别是一种智能活动，包括分析和判断两个过程。分析过程分析过程：确定用于划分模式类的特征及其表达方法；判断过程判断过程：依据待识别对象的特征，将其判属于某一个模式类。发展历史 1.11.1模式识别的基本概念模式识别的基本概念-1929年G.Tauschek发明阅读机，能够阅读0-9的数字。-20世纪30年代Fisher提出统计分类理论，奠定了统计模式识别的基础。在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。-50年代NoamChemsky提出形式语言理论，美籍华人付京荪提出句法结构模式识别。-60年代L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。-80年代Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。-90年代小样本学习理论，支持向量机也受到了很大的重视。1.11.1模式识别的基本概念模式识别的基本概念1.21.2模式识别系统模式识别系统信息获取信息获取：对于人脑识别而言,人脑通过感觉器官获取模式信息。对于机器识别来说,由于计算机只能处理数字信号,计算机获取模式信息意味着实现观察对象的数字化表达。信息获取是通过传感器，将光或声音等信息转化为电信息。信息可以是二维的图像如文字、图像等；可以是一维的波形如声波、心电图、脑电图；也可以是物理量与逻辑值。统计模式识别系统组成框图统计模式识别系统组成框图1.21.2模式识别系统模式识别系统预处理预处理：在得到模式的数字化表达后,往往需要对它进行预处理，以便去除或减少噪声的影响，突出有用信息。对于图像信息，采用数字图像处理技术作为其预处理技术，主要有二值化、图像平滑、变换、增强、恢复、滤波、几何校正等。1.21.2模式识别系统模式识别系统特征提取和选择特征提取和选择：在模式识别中，需要进行特征的抽取和选择，如，一幅6464的灰度图像可以得到4096个数据，这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。1.21.2模式识别系统模式识别系统特征是用于描述模式性质(特性)的一种定量的概念,通过对模式的分析得到一组特征,称这个过程为特征形成。特征一般有两种表达方法:(1)将特征表达为数值;(2)将特征表达为基元。1.21.2模式识别系统模式识别系统(1)当将特征表达为数值时,一个模式的d个特征值就构成了一个特征向量,记为x,即其中,x的每个分量xi(i=1,2,d)对应一个特征。(2)当特征表达为基元时,一个模式表述为一个句子,记为x,即其中，xi(i=1,2,d)为基元，反映构成模式的基本要素。1.21.2模式识别系统模式识别系统通常用于描述模式性质的特征很多,需要从一组特征中挑选出一些最有效的特征以降低特征空间维数,即特征选择。特征提取是指采用变换(或映射)实现由模式测量空间向特征空间的转变,或者将特征空间的维数从高维变成低维。1.21.2模式识别系统模式识别系统举例：通常遥感成像光谱仪波段数达数百个之多,如果直接用原始数据进行地物分类,会因数据量太大而导致计算复杂,且分类效果不一定好,可通过变换或映射的方法,由原始数据空间变换到特征空间,得到最能反映模式本质的特征,同时降低空间维数。1.21.2模式识别系统模式识别系统分类器包括分类器设计和分类决策两部分。分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。分类决策：在特征空间中对被识别对象进行分类。1.21.2模式识别系统模式识别系统说明：(1)基于机器学习的模式识别系统通常由两个过程组成,即分类器设计(简称设计)和分类判决(简称实现)。一般是用一定数量的样本进行分类器设计,这些样本的所属类别已知,称为训练样本。实现是用所设计的分类器对待识别模式进行分类判决(或分类决策)。1.21.2模式识别系统模式识别系统说明：(2)模式类是指具有相似特性的模式的集合，模式和模式类的关系就是元素和集合的关系。模式的分类过程，事实上就是判定表征观察对象的元素和指定集合的从属关系的过程。当元素只和某个集合具有从属关系时，就将该对象判属于该集合对应的类；当元素和多个集合具有从属关系时，既可以任选一类进行判决，也可以拒绝判决；当元素和任何一个集合都不具有从属关系时，不作分类判决，即拒绝判决。1.31.3模式识别的基本方法模式识别的基本方法1.模板匹配法模板匹配法(1)首先对每个类别建立一个或多个模板；(2)输入样本和数据库中每个类别的模板进行比较，求相关或距离；(3)根据相关性或距离大小进行决策。优点：直接、简单缺点：适应性差1.31.3模式识别的基本方法模式识别的基本方法2.统计模式识别法统计模式识别法统计模式识别把观察对象表达为一个随机向量(即特征向量),将模式类表达为由有穷或无穷个具有相似数值特性的模式组成的集合。识别是从模式中提取一组特性的度量,构成特征向量来表示模式,然后通过划分特征空间的方式进行分类。统计模式识别系统构成：主要由信息获取、预处理、特征提取和选择以及分类器4部分组成；其中，分类器包括分类器设计和分类决策。优点：理论较成熟，适用于用较少特征就能描述观察对象的场合，能考虑干扰、噪声等的影响缺点：对于结构复杂模式的特征提取较为困难，不能反映模式的结构特征1.31.3模式识别的基本方法模式识别的基本方法3.句法模式识别法句法模式识别法(1)许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元”(2)每个模式都可以由基元根据一定的关系来组成(3)基元可以认为是语言中的字母，每个模式都可以认为是一个句子，关系可以认为是语法或句法(4)模式的相似性由句子的相似性来决定(5)用已知类别的训练样本进行学习，产生该类或至少是这些样本的方法，该学习和训练过程称为文法推断。优点：适合结构性强的模式缺点：抗噪声能力差，计算复杂度高1.31.3模式识别的基本方法模式识别的基本方法信息获取信息获取预处理预处理模式表达模式表达文法推断文法推断句法分析句法分析图句法模式识别系统组成其中，模式表达包括两部分：模式分割和基元及关系的识别。对于一个模式，经过预处理并对模式分解提取基元后，得到表征模式的句子，然后进行句法分析，判断它是否能被代表某个模式类的文法所接受，最终给出模式结构描述和识别结果。训练过程训练过程识别过程识别过程1.31.3模式识别的基本方法模式识别的基本方法4.神经网络模式识别神经网络模式识别(1)神经网络模式识别主要利用人工神经网络的学习、记忆和归纳功能,先根据训练样本训练分类器，再利用分类器对待识别对象进行分类决策(2)大规模并行计算(3)学习、推广、自适应、容错、分布表达和计算优点：可以有效的解决一些复杂的非线性问题缺点：模型还在不断完善之中，目前能识别的模式类还不够多1.31.3模式识别的基本方法模式识别的基本方法方法表达识别函数主要理论支撑模板匹配样本、像元、曲线相关、距离度量几何学统计方法特征决策函数概率论与数理统计句法方法基元规则、语法形式语言、自动机技术神经网络样本、像元、特征网络函数神经生理学、心理学表表 几种基本模式识别方法的比较几种基本模式识别方法的比较1.41.4模式识别的应用模式识别的应用1.字符识别：包括印刷体字符的识别；手写体字符的识别（脱机），各种OCR设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入；在线手写字符的识别（联机），各种书写输入板。2.医疗诊断：心电图，脑电图，染色体，癌细胞识别，疾病诊断。3.遥感：资源卫星照片，气象卫星照片处理，数字地球，图像分辨率可以达到0.3米。1.41.4模式识别的应用模式识别的应用4.指纹识别，人脸识别5.检测污染分析，大气，水源，环境监测。6.自动检测：产品质量自动检测7.语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断。8.军事应用1.51.5模式识别的基本问题模式识别的基本问题一.模式(样本)表示方法1.向量表示:假设一个样本有n个变量(特征)=(X1,X2,Xn)T2.矩阵表示:N个样本，n个变量(特征)1.51.5模式识别的基本问题模式识别的基本问题3.几何表示 1D表示 X1=0.5 X2=3 2D表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T 3D表示 X1=(x1,x2,x3)T=(1,1,0)T X2=(x1,x2,x3)T=(1,0,1)T1.51.5模式识别的基本问题模式识别的基本问题4.基元（链码）表示：在右侧的图中八个基元分别表示0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为 X1=006666 该方法在句法模式识别中用到。1.51.5模式识别的基本问题模式识别的基本问题二二.模式类的紧致性模式类的紧致性1.紧致集同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。1.51.5模式识别的基本问题模式识别的基本问题2.临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。3.紧致集的性质要求临界点很少集合内的任意两点的连线，在线上的点属于同一集合集合内的每一个点都有足够大的邻域，在邻域内只包含同一集合的点4.模式识别的要求：满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法，以满足紧致集。1.51.5模式识别的基本问题模式识别的基本问题三三.相似与分类相似与分类1.两个样本xi，xj之间的相似度量满足以下要求：(1)应为非负值(2)样本本身相似性度量应最大(3)度量应满足对称性(4)在满足紧致性的条件下，相似性应该是点间距离的单调函数2.用各种距离表示相似性：(1)绝对值距离已知两个样本xi=(xi1,xi2,xi3,xin)Txj=(xj1,xj2,xj3,xjn)T 定义：(2)欧几里德距离(3)明考夫斯基距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离1.51.5模式识别的基本问题模式识别的基本问题(4)切比雪夫距离 明氏距离，q趋向无穷大时的极限情况(5)马哈拉诺比斯距离(Mahalanobis)其中X Xi、X Xj为特征向量集X X1,X X2,X Xm中的两个n维特征向量，为模式总体的协方差矩阵。马氏距离的使用的条件是样本符合正态分布。注：实际使用中，马氏距离中的根号有时可去掉。1.51.5模式识别的基本问题模式识别的基本问题1.51.5模式识别的基本问题模式识别的基本问题(6)夹角余弦即两样本间夹角小的为一类，具有相似性。例：x1,x2,x3的夹角如右图。因为x1,x2的夹角小，所以x1,x2最相似。1.51.5模式识别的基本问题模式识别的基本问题(7)相关系数为xixj的均值注意：在求相关系数之前，要将数据标准化。3.分类的主观性和客观性(1)分类带有主观性：目的不同，分类不同。如：鲸鱼、牛、马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。(2)分类的客观性：科学性判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。1.51.5模式识别的基本问题模式识别的基本问题四四.特征的生成特征的生成1.低层特征：(1)无序尺度：有明确的数量和数值。(2)有序尺度：有先后、好坏的次序关系，如酒分为上，中，下三个等级。(3)名义尺度：无数量、无次序关系，如有红、黄两种颜色2.中层特征：经过计算、变换得到的特征3.高层特征：在中层特征的基础上有目的的经过运算形成例如：椅子的重量=体积*比重体积与长、宽、高有关；比重与材料、纹理、颜色有关。这里低、中、高三层特征都具备了。1.51.5模式识别的基本问题模式识别的基本问题五五.数据的数据的标准化标准化1.极差标准化极差标准化 一批样本中，每个特征的最大值与最小值之差，称为极差。极差极差标准化2.方差标准化方差标准化标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。Si为方差显示结果显示结果第第2 2章章 线性判别分析线性判别分析2.12.1判别函数判别函数2.22.2线性判别函数线性判别函数2.32.3线性判别函数的性质线性判别函数的性质2.4 2.4 广义线性广义线性判别函数判别函数2.5 2.5 线性分类器设计线性分类器设计2.6 2.6 分段线性分类器设计分段线性分类器设计(*:(*:不要求不要求)在科研、生产和日常生活中，经常会遇到各种各样的判别问题，即要根据某个体的特征的观察值，判断它属于几个类别中的哪一个类。医生根据病人的指标（体温、血压、白细胞数目等）来判断病人生何种病等就属此类。其实，在生物学分类、医疗诊断、地质找矿、石油钻探、天气预报等诸多领域，判别分析方法已经成为一种有效的统计推断方法。简单地说，所谓判别分析问题，就是指在已有给定的若干个模式类（若干个总体）的观察资料的基础上，构造出一个或多个判别函数，并能由此函数对未知其所属类别的新的模式作出判断，决定其应属于哪个模式类。2.12.1判别函数判别函数 如下图：三类的分类问题，它们的边界线就是一个判别函数。2.12.1判别函数判别函数 假设对一模式X已提取n个特征，表示为：模式识别问题就是根据模式X的n个特征(指标)来判别模式属于1,2,m类中的哪一类。2.12.1判别函数判别函数判别函数包含两类：一类是线性判别函数：线性判别函数广义线性判别函数（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）分段线性判别函数另一类是非线性判别函数分别对两类问题和多类问题进行讨论。1.二维情况：取两个特征向量这种情况下判别函数：2.22.2线性判别函数线性判别函数(一)两类问题即：在两类别情况下，判别函数g(x)具有以下性质：这是二维情况下判别由判别边界分类。情况如图：2.22.2线性判别函数线性判别函数1.二维情况现提取n个特征为：判别函数：另外一种表示方法：2.22.2线性判别函数线性判别函数2.n维情况v模式分类：vg(x)=WTX=0为判别边界。当n=2时，二维情况的判别边界为一直线；当n=3时，判别边界为一平面；当n3时，则判别边界为一超平面。2.22.2线性判别函数线性判别函数2.n维情况对于多类问题，模式有1,2,m个类别。可分三种情况：1.第一种情况：每一模式类与其他模式类间可用单个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：2.22.2线性判别函数线性判别函数(二)多类问题1.第一种情况第一种情况v下图所示，每一类别可用单个判别边界与其他类别相分开。若一模式X属于1，则由图可清楚看出：这时g1(x)0而g2(x)0，g3(x)0，g2(x)0，g3(x)0，则此模式X就无法作出准确的判决。如图中 IR1,IR3，IR4区域。v另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4都为不确定区域。v问当x=(x1,x2)T=(6,5)T时属于那一类v结论：g1(x)0，g3(x)g2(x)和 g1(x)g3(x)。假设判别函数为：则判别边界为：3.第三种情况第三种情况(Cont.)(Cont.)v用上面方程组作图：v结论：不确定区间没有了，所以这种是最好的情况。3.第三种情况第三种情况(Cont.)(Cont.)v问：假设未知模式x=(x1,x2)T=(1,1)T，则x属于哪一类。把x代入判别函数：得判别函数为：因为 所以模式x=(1,1)T属于 类。.模式空间：由 构成的n维欧氏空间。.W是此空间的加权向量，它决定模式的分界面H，W与H正交。.加权空间：以 为变量构成的欧氏空间。.模式空间与加权空间的几何表示如下图：2.32.3线性判别函数的性质线性判别函数的性质由于假设权向量W与模式向量X的内积为零(g(x)=0)，故W与分界面H正交1.模式空间与加权空间模式空间1.模式空间与加权空间(Cont.)v加权空间的构造：v设 是加权空间分界面上的一点，代入上式得：，这是加权空间的边界。v该式表示一个通过加权空间原点的平面，此平面就是加权空间图中的平面,同样令g(x2)=g(x3)=g(x4)=0，分别作出通过加权空间原点的平面；图中用阴影表示的部分是各平面的正侧。1.模式空间与加权空间(Cont.)v这是一个不等式方程组，它的解 处于由1类所有模式决定的平面的正边和由2类所有模式决定的平面的负边，它的解区即为凸多面锥。v如图所示：(b)为加权空间，(c)为正规化后的加权空间。v由上可以得出结论：加权空间的所有分界面都通过坐标原点。这是加权空间的性质。v为了更清楚，下面用二维权空间来表示解向量和解区。2.解向量和解区v在三维空间里，令w3 =0 则为二维权空间。如右图：v给定一个模式X，就决定一条直线：v即分界面H，W与H正交，W称为解向量。v解向量的变动范围称为解区。v因x1,x21，x3,x42由图可见x1,x3离的最近，所以分界面H可以是x1,x3之间的任一直线，由垂直于这些直线的W就构成解区，解区为一扇形平面，即红色阴影区域。v如右图:H分界面2.解向量和解区(Cont.)v将不等式方程正规化：H分界面v正规化：3.超平面的几何性质vg(x)=WTX=0决定一个决策界面，当g(x)为线性时，这个决策界面便是一个超平面H，并有以下性质：v性质：W与H正交（见右图）.假设x1,x2是H上的两个向量.W与(x1-x2)垂直，即W与H正交。.一般说，超平面H把特征空间分成两个半空间。即1,2空间，当x在1空间时g(x)0,W指向1，为H的正侧，反之为H的负侧。12g(x)0g(x)0-X1dW1-X2dW2-W30因此g(x)=WTX0，其中W=(W1,W2,W3)T为各模式增广矩阵为N*(n+1)矩阵(此处N=4,n=2)N为样本数，n为特征数训练过程就是对已知类别的样本集求解权向量W，这是一个线性联立不等式方程组求解的过程。求解时：只有对线性可分的问题，g(x)=WTX才有解；联立方程的解是非单值，在不同条件下，有不同的解，所以就产生了求最优解问题；求解W的过程就是训练的过程。训练方法的共同点是，先给出准则函数(Criterionfunction)，再寻找使准则函数趋于极值的优化算法，不同的算法有不同的准则函数。算法可以分为迭代法和非迭代法。一一.梯度下降法梯度下降法迭代法迭代法 要对不等式方程组WTX0求解，首先定义准则函数(目标函数)J(W)，再求J(W)的极值使W优化。因此求解权向量的问题就转化为对一目标函数求极值的问题。解决此类问题的方法是梯度下降法(1847年，法国数学家Cauchy提出)。方法就是从起始值W1开始，算出W1处目标函数的梯度向量J(W1)，则下一步的W值为：W2=W1-1J(W1)W1为起始权向量1为迭代步长J(W1)为目标函数J(W1)为W1处的目标函数的梯度向量在第k步的时候 Wk+1=Wk-kJ(Wk)k为正比例因子(learningrate)这就是梯度下降法的迭代公式。这样一步步迭代就可以收敛于解向量，k取值很重要k太大，迭代太快，引起振荡，甚至发散。k太小，迭代太慢。应该选最佳k。选最佳选最佳k目标函数J(W)二阶Taylor级数展开式为：J(W)J(Wk)+JT(W-Wk)+1/2(W-Wk)TD(W-Wk)其中D为当W=Wk时J(W)的二阶偏导数矩阵将W=Wk+1=Wk-kJ(Wk)代入式得：J(Wk+1)J(Wk)-k|J|2+1/2k2JTDJ其中J=J(Wk)对k求导数，并令导数为零有最佳步长为k=|J|2/(JTDJ)这就是最佳k的计算公式，但因二阶偏导数矩阵D的计算量太大，因此此公式很少用。若令W=Wk+1，式为J(Wk+1)=J(Wk)+JT(Wk+1-Wk)+1/2(Wk+1-Wk)TD(Wk+1-Wk)对Wk+1求导，并令导数为零可得：最佳迭代公式：Wk+1=Wk-D-1J牛顿法的迭代公式D-1是D的逆阵讨论：牛顿法是基于二阶Taylor级数且比梯度下降法收敛更快，但是D的计算量大并且要计算D-1。当D为奇异矩阵时，无法用牛顿法。二.感知器法（Perceptron）感知器是由美国Rosenblatt于1957年提出的有监督学习(有导师学习)神经网络模型，其学习算法于1958年提出。感知器原理结构：通过对W的调整，可实现判别函数g(x)=WTXRT其中RT为响应阈值定义感知准则函数：只考虑错分样本定义：其中Se为被W错误分类样本集合当分类发生错误时就有WTX0，所以J(W)总是正值。错误分类愈少，J(W)就愈小。理想情况为J(W)=0即求最小值的问题。求最小值对W求梯度代入迭代公式中Wk+1=Wk-kJ即感知器迭代公式由J(W)经第k+1次迭代的时候，J(W)趋于0，收敛于所求的W值。W的训练过程：例如，x1,x2,x31，作x1,x3的垂直线可得解区(如图)假设起始权向量w1=0k=11.x1,x2,x3三个向量相加得向量2,垂直于向量2的超平面H将x3错分。2.x3与向量2相加得向量3,垂直于向量3的超平面H1，将x1错分。3.依上法得向量4,垂直于向量4做超平面，H2将x3错分。4.x3与向量4相加得向量5，向量5在解区内，垂直于向量5的超平面可以把x1,x2,x3分成一类。感知器算法：1.错误分类，修正wk若wkTx0并且x1wk+1=wk+kx若wkTx0并且x2wk+1=wk-kx2.正确分类，wk不修正若wkTx0并且x1若wkTx0并且x2wk+1=wk权值修正过程k选择准则固定增量原则k固定非负数绝对修正规则k部分修正规则k=02例：有两类样本1=(x1,x2)=(1,0,1)T,(0,1,1)T2=(x3,x4)=(1,1,0)T,(0,1,0)T解：先求四个样本的增广模式x1=(1,0,1,1)Tx2=(0,1,1,1)Tx3=(1,1,0,1)Tx4=(0,1,0,1)T假设初始权向量w1=(1,1,1,1)Tk=1第一次迭代：w1Tx1=(1,1,1,1)(1,0,1,1)T=30所以不修正w1w1Tx2=(1,1,1,1)(0,1,1,1)T=30所以不修正w1w1Tx3=(1,1,1,1)(1,1,0,1)T=30所以修正w1w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)第一次迭代后,权向量w3=(0,-1,1,-1)，再进行第2，3，次迭代，如下表所示：训练样本训练样本wkTx修正式修正式修正后的权值修正后的权值wk1迭代次数迭代次数x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+0w1w1w1-x3w2-x41 1 1 11 1 1 10 0 1 00 1 1 -1 1x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 10+0-w3+x1w4w4-x3w51 1 2 01 1 2 00 2 2 10 2 2 -1 2x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w5w5+x2w6w60 2 2 10 1 3 00 1 3 00 1 3 0 3x1 1 0 1 1x2 0 1 1 1x3 1 1 0 1x4 0 1 0 1+-w6w6w6w60 1 3 00 1 3 00 1 3 00 1 3 04直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,1,3,0)，判别函数g(x)=-x2+3x3感知器算法只对线性可分样本有收敛的解，对非线性可分样本集会造成训练过程的振荡，这是它的缺点。线性不可分样本集的分类解线性不可分样本集的分类解(取近似解取近似解)对于线性可分的样本集，可用感知器法解出正确分类的权向量。当样本集线性不可分时，用上述感知器法求权值时算法不收敛。如果我们把循环的权向量取平均值作为待求的权向量，或就取其中之一为权向量，一般可以解到较满意的近似结果。例：现有样本(见右图)1：X1=(0,2)T,X3=(2,0)TX5=(-1,-1)T2：X2=(1,1)T,X4=(0,-2)TX6=(-2,0)T试求权向量的近似解。separatingplane解：此为线性不可分问题，利用感知器法求权向量。权向量产生循环(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收敛，我们可以取循环中任一权值，例如取W=(0,2,2)T则判别函数为：g(x)=2x1+2x2判别面方程为：g(x)=2x1+2x20所以x1+x20由图看出判别面H把二类分开，但其中x2错分到1类，而x1错分到2类，但大部分分类还是正确的。三三.最小平方误差最小平方误差准则准则非迭代法非迭代法 (MSE法法:Mean Square Error,均方误差法均方误差法)前面研究了线性不等式方程组g(x)=WTX0的解法。它们共同点是企图找一个权向量W，使错分样本最小。现将不等式组变成右边的形式：WTXi=bi0则有联立方程XW=b。这是矛盾方程组，方程数大于未知数，通常没有精确解。每个样本有n个特征(通常mn，即行比列多)e=XW-b0，把平方误差作为目标函数 W的优化就是使J(W)最小。求J(W)的梯度并为0。解上方程得 XTXW=XTb 这样把求解XW=b的问题，转化为对XTXW=XTb求解，这一有名方程的最大好处是由于XTX为方阵且通常是非奇异的，因此可以得到W的唯一解。MSE准则函数 可寻找一个权向量W，使得某个关于XW和b的函数最小化。我们定义一个误差向量：只要计算出X X+就可以得到W W MSE的解是由b b决定的。若取b b为一个任意固定的值，可以通过最小化平方误差准则函数得到一个在可分和不可分情况下都很有用的判别函数。如b b可以取：选择其他的b b当然会得到不同的判决边界。最小平方误差法同后面要介绍的Fisher法是一致的。其中m/m1有m1个，m/m2有m2个(m=m1+m2)四四.韦韦霍氏法霍氏法(Widrow-Hoff)迭代法迭代法 (LMS法法:Least Mean Squared,最小均方算法最小均方算法)上节得到MSE法的W解为：W=X+b在计算X+时，1.要求XTX矩阵为非奇异 2.由于计算量太大而引入了较大误差因此考虑用迭代法来求解：求J(W)的梯度(Seeslide26)J(W)=2XT(XW-b)代入迭代公式W1任意设定 Wk+1=Wk-kXT(XWk-b)此法可收敛于W值。W满足:XT(XW-b)=0计算量大因此下降算法不论XTX是否奇异，总能产生一个解。若训练样本无限的重复出现，则简化为：W1任意任意 Wk+1=Wk+k(bk-WkTXk)Xkk随迭代次数k的增大而减少，以保证算法收敛于满意的W值。五五.何何卡氏卡氏法法(用于判断迭代过程中是否线性可分用于判断迭代过程中是否线性可分)(Ho-Kashyap算法算法)若训练样本线性可分时，感知器法可求出界面，但对不可分问题由于不收敛只能取平均。最小平方误差法不论样本是否线性可分都能给出一加权向量，但不能保证此向量就是分界向量，这里介绍一种方法可以检测迭代过程中是否线性可分。因最小平方误差法的J(W)的解为由于XW=bb0c为校正系数当(XWk-bk)0时当(XWk-bk)0时引入误差向量ekek=XWk-bk判断是否线性可分所以J(W)的解为初始条件W1=X+b1并且b10迭代时检测若ek0时，XWb，系统线性可分，迭代收敛；若ek0时，XWb，系统线性不可分，迭代不收敛。因此，式可以写成：例：1=(0,0)T,(0,1)T2=(1,0)T,(1,1)T解：正规化对2取负，有 下面举例说明ek的作用X的规范矩阵为MATLAB Pseudo inverse：X+=pinv(X)取b1=(1,1,1,1)Tc=1W1=X+b1=(-2,0,1)T所以W1为所求解e1=XW1-b1=0系统线性可分若四个样本变成：1=(0,0)T,(1,1)T2=(0,1)T,(1,0)T解：取b1=(1,1,1,1)Tc=1W1=X+b1=(0,0,0)Te1=XW1-b1=(-1,-1,-1,-1)T0系统线性不可分c为校正系数，取0c1在算法进行过程中，应在每一次迭代时，检测ek的值。只要出现ek0X1X=WTX-W00X1Y=WTX-W0W0，则X1；Y=W*T XW0，则X1；Y=W*TXW0，则X1；Y=W*TXP(2)。仅按先验概率。仅按先验概率来决策，就会把所有药品都划归为正常药品，并没有达来决策，就会把所有药品都划归为正常药品，并没有达到将正常药品和异常药品区别分开的目的。这表明由先到将正常药品和异常药品区别分开的目的。这表明由先验概率所提供的信息太少。验概率所提供的信息太少。2.类条件概率密度函数类条件概率密度函数P(X|i)类条件概率密度函数(Class-conditionalprobabilitydensityfunction)P(X|i)是指在i类条件下X的概率密度，即i类模式X的概率分布密度，简称为类概密/似然。设只用一个特征进行分类，即n=1(特征数目)，并已知这两类的类条件概率密度函数分布，见右图。类概密P(X|1)是正常药品的属性（此处n=1，故为特征数值）分布，类概密P(X|2)是异常药品的属性分布。在工程问题中，统计数据往往满足正态分布规律。若采用正态密度函数作为类概密的函数形式，则函数内的参数，如期望、方差是未知的。那么问题就变成如何利用大量样本对这些参数进行估计，只要估计出这些参数，类概密P(X|i)就确定了。3.后验概率后验概率P(i|X)-Posteriorprobability 条件概率P(i|X)表示X出现的条件下i类出现的概率，称其为类别i的后验概率，对模式识别而言可理解为X来自i类的概率。即若所观察到的某一样本的特征向量为X，而在类中又有不止一类可能呈现这一X特征数值，它属于各类的概率就是P(i|X)。4.P(1|X)、P(2|X)与P(X|1)、P(X|2)的区别(1)P(1|X)和P(2|X)是指在同一条件X下，比较1与1出现的概率，若P(1|X)P(2|X)，则有结论：在X条件下，事件1出现的可能性大，见右图。对于两类的情况，则有P(1|X)+P(2|X)=1。(2)P(X|1)和P(X|2)都是指各自条件下出现X的可能性，两者间没有联系，比较两者没有意义。P(X|1)和P(X|2)是在不同条件下讨论问题，即使只有两类1与2，P(X|1)+P(X|2)1。不能仅因为P(X|1)P(X|2)，就认为X是1类的可能性就大。只有考虑先验概率这一因素，才能决定X条件下，判别为1类或2类的可能性哪个大。3.23.2分类器的描述方法分类器的描述方法3.2.13.2.1基本假设基本假设 给定模式空间S，由m个互不相交的模式类集合1，2,m组成:(1)假定类i的先验概率为P(i);(2)样本(或模式)x x由特征向量来表示,同样记为x x,假设为d维,即x x=(x1,x2,xd);(3)特征向量x x的取值范围构成特征空间,记为R Rd;(4)特征向量x x的类条件概率密度函数为p(x x|i),表示当样本x xi时,特征向量x x的概率密度函数;(5)特征向量x x的后验概率为P(i|x x),表示在特征向量x x出现的条件下,样本x x来自类i的概率,即类i出现的概率。模式识别就是根据特征向量x x的取值,依据某个判决准则把样本x x划分到1，2,m中的一个。3.2.23.2.2模式分类器的描述模式分类器的描述 模式分类器的描述方法有多种,这里仅介绍以下三种描述方法,它们之间是统一的。1.1.映射描述法映射描述法 由于我们获取的有关观察对象的数据总量是有限的,因此,可用一个d+1维向量表示,即：(x1,x2,xd;)其中:(x1,x2,xd)为特征向量,是特征空间R Rd中的一个点;取值于集合1,2,m,表示模式的真实类别号,是未知的量,m为类别数。模式分类的实质在于实现特征空间R Rd到类别号空间1,2,m的一个映射,即 R Rd1,2,m 给定一个映射f,就给出了一种模式识别方法,不同的映射对应不同的分类方法,这就是模式识别问题的映射描述法。2.2.划分描述法划分描述法 由于每个特征向量是R Rd空间的一个点，且R Rd 1 2,m是一个多对一的映射，通过映射，本质上实现了对空间R Rd的一种划分，即把R Rd划分成个不相重叠的区域，每一个区域对应一个类别。区域Ri对应第i类i。3.3.判别函数法判别函数法 把分类问题对应为R Rd空间上的多元函数,通常称为判别函数(或称判决函数)gi(x x),i=1,2,m。将样本x判属有极大(或极小)函数值的那一类。模式分类实际上是将特征空间划分为不同的决策区域,相邻决策区域被决策面所分割,这些决策面是特征空间中的超曲面,其决策面方程满足相邻两个决策域的判别函数相等,即gi(x x)=gj(x x)分类器可被看作是一个计算m类个判别函数并选取最大(或最小)判决值对应的类别的网络或者机器，见下图。g1(x)Maxg(x)g2(x)gm(x)3.33.3最小错误率最小错误率BayesBayes决策决策(Minimum-error-rate classificationMinimum-error-rate classification)假设待识别的特征为X,样本分为m类，各类的先验概率和各类的类概密均已知，就有m个判别函数，由Bayes公式可知：在取得一个观察特征X后，在特征X的条件下，看哪个类的概率最大，应该把X归于概率最大的那个类。由此，可得到最大后验概率判决准则的几种等价形式：(1)若(2)若(3)若则xj;其中,L(x x)称为似然比,lnL(x x)称为对数似然比P(1)/P(2)称为似然比阈值【例例 3.13.1】假设在某个局部地区的细胞识别中,第一类表示正常,第二类表示异常,两类的先验概率分别为:正常P(1)=0.9,P(2)=0.1。现有一个待识别样本细胞,其观察值为x x,从类条件概率密度函数曲线p(x x|i)上可查得:p(x x|1)=0.2,p(x x|2)=0.4,试判断该细胞是否正常。解解：该细胞属于正常细胞还是异常细胞，先计算后验概率：计算p(x x|1)P(1)=0.20.9=0.18p(x x|2)P(2)=0.40.1=0.040.18 根据 Bayes 判决准则将该细胞判为第一类1,即为正常细胞。最大后验概率判决准则使决策的错误率最小 最大后验概率判决准则的一个优良性质就是使平均错误概率达到最小。因此,最大后验概率判决准则又称为最小错误概率判决准则。这里以二分类情况为例进行分析。此时,m=2,任意一个判决准则对应于特征空间R Rd的一个划分:R=R1R2,R1R2=。为了直观，假设x x只有一个特征，n=1。错误分类有两种情况：若x x原属于1类，却落入R2，称为第1类错误；若x x原属于2类，却落入R1，称为第2类错误。第1类错误概率P1(e)为：第2类错误概率P2(e)为：因此，平均错误概率P(e)为：平均错误概率计算示意图平均错误概率计算示意图t为两类的分界点，将为两类的分界点，将x轴轴分成两个区域分成两个区域R1和和R2。R1tR2若要使Pe达到最小，则x x1的决策区域R1必须满足：即：上式与最大后验概率判决准则中x1的决策区域是一致的，也就是说，最大后验概率判决使平均错误概率达到最小。证明略证明略(a)基于最小错误基于最小错误 (b)基于最小风险基于最小风险(扩大错误率，减小损失扩大错误率，减小损失)图图 基于最小错误分类和基于最小风险分类的比较基于最小错误分类和基于最小风险分类的比较3.43.4最小风险最小风险BayesBayes决策决策 上节的探讨了使错误概率最小的上节的探讨了使错误概率最小的Bayes决策规则。然决策规则。然而，当接触到实际问题时，可能发现使错误率最小并非是而，当接触到实际问题时，可能发现使错误率最小并非是普遍适用的最佳选择。见下图。普遍适用的最佳选择。见下图。图中，直线B的划分把正常药品误判为异常药品，这样扩大了总错误率，会给企业带来一定的损失；直线A的划分将异常药品误判为正常药品，虽然使错误分类最小，但会使病人因失去正确的治疗而遭受极大的损失。可见使错误率最小并不一定是最佳选择。实际应用时，从根据不同性质的错误会引起不同程度的损失考虑出发，宁可扩大一些总的错误率，但也要使总的损失减少。这时图中的直线B的划分最为实用。这会引进一个与损失有关联的概念-风险。在做决策时，要考虑所承担的风险。基于最小风险的Bayes决策规则正是为了体现这一点而产生的。若要判断某颗药品是正常(1)还是异常(2)，于是在判断中可能出现如下情况：第一种，判对(正常药品正常药品)11；第二种，判错(正常药品异常药品)21；第三种，判对(异常药品异常药品)22；第三类，判错(异常药品正常药品)12。在判断时，除了能做出“是”i类或“不是”i类的动作以外，还可以做出“拒识”的动作。为了更好地研究最小风险Bayes分类器，下面说明几个概念。几个概念几个概念行动(决策)i：表示把模式x判决为i类的一次动作（决策）。不同的动作对应于特征空间的不同决策区域Rj,j1,2,m。若xRj,则判决xj(j=1,2,m)。这里未考虑拒识情况。损失函数ii=(i,i)表示模式x本来属于i类而错判为i所受损失。因为这是正确判决，故损失最小。损失函数ij=(i,j)表示模式x本来属于j类错判为i所受损失。因为这是错误判决，故损失最大。风险R(期望损失)：对未知模式x采取一个判决行动(x)所付出的代价(损失)。设样本x来自类i,可能被判为1,2,m 中的任何一种,若允许拒绝判决,可将拒绝类看成是独立的一类,记为第m+1类,即m+1。几个概念几个概念(Cont.)在整个特征空间中定义期望风险R：条件风险只反映对某x取值的决策行动i所带来的风险。期望风险R则反映在整个特征空间不同的x取值a(x)决策可看成是随机向量x的函数，记为a(x)的决策行动所带来的平均风险。条件风险(也叫条件期望损失)：P(x)为样本向量x在Rd空间中的概率密度称之为损失矩阵。在实际应用时,可以将损失函数ij写成如下矩阵形式：几个概念几个概念(Cont.)最小风险最小风险BayesBayes决策规则：决策规则：若，则判决xk。当取0-1损失函数时,最小风险贝叶斯判决准则等价于最大后验概率判决准则(见教材P13公式2-17)。基于最小风险的基于最小风险的BayesBayes决策：决策：决策带来的损失的平均值决策带来的损失的平均值风险最小。风险最小。【例例 3.2】在例3.1的基础上,增加条件11=0,12=6,21=1,22=0,请判断该细胞是否正常解：解：若按最小风险的Bayes判决进行判断,先计算后验概率：3.5 Neyman-Pearson3.5 Neyman-Pearson决策决策 在实际遇到的模式识别问题中有可能出现这样的问题:对于两类情形,不考虑总体的情况,而只关注某一类的错误概率,要求在其中一类错误概率小于给定阈值的条件下,使另一类错误概率尽可能小。例如,在雷达目标检测中,人们可能不仅对目标出现的先验概率未知,而且对错误判断的代价也是难以估计的,甚至是难以定义的。雷达目标检测中存在两种错误:一种是虚警,即没有目标判为有目标;另一种是漏警,即有目标判为没有目标。适当的方法就是观察者确定一个允许的虚警概率,使漏警概率尽可能得小。-在一类错误率固定使另一类错误率最小的判别准则在一类错误率固定使另一类错误率最小的判别准则 Neyman-Pearson判决准则解决的就是上述问题,它只适用于两类情形。见图，在两类情况下，有两种错误概率：第1类错误概率是，样本真实类别为1，但落到了2的判决区域R2内，从而被判为2的概率，记为E1；第2类错误概率是，样本真实类别为2，但落到了1的判决区域R1内，从而被判为1的概率,记为E2。平均错误概率为 Pe=P(1)E1+P(2)E2 设限定E2不超过某个阈值，即：E2 在此前提下，求判决区域使E1达到最小值。采用Lagrange乘数法来求解，其中，约束条件为 E20=0。构造目标函数 r=E1+(E2-0)其中,为Lagrange乘数。由1与2的决策区域分别为R1与R2,可得：在不等式条件下,难以求解E1的最小值，因此，可以选择0。E2 条件下的求解问题转化为E2=0条件下的E1最小值求解问题。这是一个典型的条件极值问题。从而，目标函数可改写为：为了使r达到最小，则要求使被积函数p(x|2)p(x|1)0，所以R1=x|p(x|2)p(x|1)0的点全部落入R1中，且R1中的点使被积函数p(x|2)p(x|1)0。因此,可得到如下Neyman-Pearson判决准则：若p(x|2)p(x|1),则x2写成似然比形式：阈值是Lagrange乘数，是一个不确定的量，需要根据约束条件求解，即：因此，Neyman-Pearson准则归结为求阈值。v例例：两类的模式分布为二维正态 协方差矩阵为单位矩阵1=2=I，设E20.09求聂曼-皮尔逊准则的阈值。（教材P15）v解：解：4 2 1 4 2 1 E20.04 0.09 0.16 0.25 0.380.04 0.09 0.16 0.25 0.38v与E2的关系表如右：v此时聂曼皮尔逊分类器的分界线为：v由图可知为保证E2足够小，边界应向E1一侧靠，则E1。3.63.6 最小最大风险最小最大风险决策决策 (Minimax CriterionMinimax Criterion)在实际应用中经常遇到的是各类先验概率不能精确知道或者在分析过程中发生变动。这就使得判决结果不能达到最佳，实际分类器的平均损失要变大，甚至变得很大。在这种情况下要采用最小最大风险(Minimize the maximum Minimize the maximum possible overall riskpossible overall risk)判决准则，它的基本思想是在最差的(即最大的可能风险)情况下争取最好的结果。最小错误概率Bayes决策(最大后验概率判决准)是使分类的平均错误概率最小，最小风险Bayes决策是使分类的平均风险最小，Neyman-Pearson决策是假设在一类错误率固定的条件下使另一类的错误率最小。前面的三种判决准则讨论的都是假定先验概率不变的情况，现在讨论在P(i)变化时如何使最大可能风险最小，先验概率P(1)与期望风险期望风险(总风险：总风险：overall risk)R间的变化关系如下：条件风险条件风险(Conditional risk)：期望风险R反映对整个特征空间上所有本样x采取相应决策所带来的平均风险。这样，就得出最小风险与先验概率的关系曲线，如图所示：讨论：讨论：上式表明，所选的判别边界，使两类的概率相等：这时可使最大可能的风险为最小，这时先验概率变化，其风险不变。一旦R1、R2确定，R就是先验概率P(1)的线性函数：其中对应不同的先验概率P(1)，可以得到相应的最小Bayes风险，当P(1)遍取0,1时,就得到P(1)R曲线。在已知类概率密度函数、代价(损失)函数和某个先验概率P(1)时，按最小风险Bayes判决准则，可以确定R1和R2：P(1)1P(1)0RRR=a+bP(1)P01P(1)0RB如何选择先验概率使最大可能的平均风险(即总风险：Overallrisk)最小呢？由R=a+bP(1)式知：若b=0，则R与P(1)无关，且恒等于a，这时最大可能的平均风险达到最小值。但b=0意味着此时的平均风险直线与最小Bayes风险曲线相切于B点，平均风险R达到最小Bayes风险曲线的最大值。如右下图，B点对应的先验概率满足使最大可能的平均风险最小的要求。P(1)R3.7 3.7 正态分布正态分布决策决策一、正态分布判别函数一、正态分布判别函数 1、为什么采用正态分布：、为什么采用正态分布：a、正态分布在物理上是合理的、广泛的。b、正态分布数学上简单，N(,)只有均值和方差两个参数。2、单变量正态分布：、单变量正态分布：3、(多随机变量)多维正态分布 （1）函数形式：(2)性质性质：与对分布起决定作用P()=N(,),由n个分量组成，由n(n+1)/2(因i对称)元素组成。多维正态分布由n+n(n+1)/2个参数组成。等密度点的轨迹是一个超椭球面。区域中心由决定，区域形状由决定。不相关性等价于独立性。若xi与xj互不相关,则xi与xj一定独立。线性变换的正态性Y=AX，A为线性变换矩阵。若X为正态分布，则Y也是正态分布。线性组合的正态性。判别函数：类条件概率密度用正态来表示：二、最小错误率二、最小错误率(Bayes)分类器：从最小错误率这个角度来分析分类器：从最小错误率这个角度来分析Bayes 分类器分类器1.第一种情况：第一种情况：各个特征统计独立，且同方差情况。(最简单情况)决策面方程：判别函数：v若M类先验概率相等：最小距离分类器：未知x与i相减，找最近的i把x归类讨论：2、第二种情况：、第二种情况：i 相等，即各类协方差相等。未知x，把x与各类均值相减，把x归于最近一类。最小距离分类器。讨论：针对1，2二类情况，如图：3、第三种情况、第三种情况(一般情况)：为任意，各类协
展开阅读全文