1011 05 模式识别

第5部分模式识别技术第5部分模式识别第5部分模式识别技术第5部分模式识别5.1模式识别概述5.2统计模式识别第5部分模式识别技术5.1模式识别概述5.1.1模式、我们知道,被识对象都具有一些属性、状态或者说特征。例如,图形有长度、面积、颜色、边的数目等特征。声音有大小、音调的高度、频率分量的强度等特征。而对象之间的差异也就表现在这些特征的差异上。因此,可以用对象的特征来表征对象,即为对象建模。另一方面,从结构来看,有些被识对象可以看作是由若干基本成分按一定的规则组合而成。例如,一个汉字就是由若干基本笔划组成的,而一个几何图形则可以看作是由若干基本线条组合而成。因此,可以用一些基本元素的某种组合来刻画对象,即为对象建模。第5部分模式识别技术定义1能够表征或刻画被识对象类属特征的信息模型称为对象的模式(pattern)。有了模式,对实体对象的识别就转化为对其模式的识别。那么,怎样识别呢？考察我们人类对物体的识别过程,可以发现,识别其实就是分类,即辨识或判别被识对象的类属。例如,汉字“文”可以有多种形体、写法和大小,但它们都属于同一个类。而我们识别这个“文”字实际也就是在判定当前看到的对象“文”的类属。又如,同一个人的脸,从不同角度或在不同时间所看到的模样是不一样的,但这些模样属于同一类,即该人的脸像类。而我们在识别人的脸谱时,实际上就是在判定当前看到的样子应该属于哪一个脸像类。也就是在把当前看到的模样归入我们记忆中该人脸像的类中。第5部分模式识别技术定义2具有某些共同特性的模式的集合称为模式类,判定一个待识模式类属的过程称为模式识别。5.1.2最常用的模式表示形式有向量和字符串。用向量表示对象模式就是以对象的诸特征值作为分量组成的一个n维向量X，即X=(x1,x2,…,xn)Rn，其中xi(i=1,2,…,n)为相应对象的第i个特征值。例如，向量(2,10,0.8,100)就描述了一个模式。由于被识对象的特征往往都取数量值，于是，用n维向量表示对象模式就是一个很自然的选择。第5部分模式识别技术表示对象模式的n维向量称为特征向量，而相应的向量空间R*Rn称为特征空间。基于被识对象的结构特征，人们又提出了对象模式的字符串表示形式和方法。用字符串表示模式，就是先对对象的结构作适当分割，以找出其基本图元并以单字符命名，然后根据对象的结构特点，将这些基本图元的符号名按相应的逻辑顺序排成一列。这样得到的字符串即为原对象的模式。例如，对于图5-1(a)所示的数字6，根据其结构特点，该图就可以分割为两个子图(如图5-1(b)所示)；进而可以以有向线段a、b、c、d作为基本图元（5-1(c)所示）。这样，该图形就可以看作是由线段a、b、c、d按数字6的书写顺序依次首尾相连而成(如图5-1(d)所示)。于是，该图形的模式就可以用字符串S=accbda来描述。第5部分模式识别技术图5-1字符串描述模式示例第5部分模式识别技术表示模式的字符串一般是由小写字母组成的一个字符序列s1s2…sm。上面我们给出了模式的两种表示形式:特征向量和字符串。其中,特征向量反映的是对象的数量特征,或者说是用数量来描述对象的,所以,特征向量是被识对象的数量模式;字符串反映的是对象的构造特征,或者说是用形状来描述对象的,因此字符串是被识对象的结构模式。特征向量和字符串是两种最常用、最基本的模式表示形式。除此而外,模式的表示形式还有树、图等数据结构以及模糊集合等,它们一般被用来描述复杂的对象模式。第5部分模式识别技术5.1.3我们已经知道,模式识别就是判定一个待识模式的类属的过程。但是要判定一个模式的类属,首先就得存在相应的模式类。所以在正式进行模式识别之前,就得让计算机先具有相关模式类的知识。这种知识可以是一个类的标准模式(这是最直接、最自然的想法和做法),也可以是该类的判别条件(如判别函数或规则)等。有了相关模式类的知识,在遇到相应的模式时,计算机就可以根据这些知识来判定该模式的类别了。第5部分模式识别技术怎样使计算机具有某一模式类的知识呢？现在的一般做法是先让计算机自己去学习(其实是发现)。这就又归结为机器学习的问题了。而要进行机器学习,就得有作为样例的模式。在模式识别中,要得到样例模式,还要通过信息获取、预处理和特征选取或基元选取等一系列的过程。信息获取就是采集被识别对象的原始信息。这些信息一般表现为光、声、热、电等形式的信号量。所以,对所采集的信息还需进行数/模转换。另外,原始信息中可能还夹杂着一些干扰或噪声,因此还必须进行预处理,以除去噪声,修整为有用信息。第5部分模式识别技术采集来的原始数据,其数据量往往很大。这样,当把一个对象的原始数据作为对象的特征值时,将会形成维数很高的特征向量。例如,用摄像机所得到的物体图像可以是一个256×256灰度阵列,这相当于一个256×256维向量。直接使用这种高维向量进行模式识别将是十分困难的,所以需要对原始的测量数据进行适当处理(如计算或变换等),以降低其维数,或者说以形成对象的特征向量。第5部分模式识别技术然而,已经形成的诸特征,对于对象的识别来说,并非都是有用的或者并非总是有用的。例如,颜色这个特征对于汽车的识别来讲就是无关紧要的。因为颜色固然可以作为汽车的一个特征,但它并非一个物体是否为汽车的关键特征。但如果识别的目的任务是在众多的汽车中要找出一辆特定的汽车,则颜色就又变成了必不可少的重要特征了。这就是说在模式识别时,还须根据具体的识别目的和任务对已知的对象特征进行选择。第5部分模式识别技术以上过程一般称为对象的特征提取(或抽取)和特征选择,本书将其统称为特征选取。特征选取是对建立对象的数量模式即特征向量而言的。对于建立对象的结构模式,也有一个相当的过程,该过程是分析、选择被识对象的基本构造元素,一般称为基元提取(或抽取)和选择,本书将其统称为基元选取。第5部分模式识别技术这样,原始样例数据经过特征选取/基元选取便得到样例模式。有了样例模式,接下来就是通过机器学习而产生相关的分类知识。有了分类知识,对于新的待识模式,就可以进行识别了。综上所述,模式识别的原理如图5-2所示。图5-2也是模式识别系统的工作原理。图中将模式识别的全过程分为两步:第一步是分类知识的生成过程,其实是个纯粹的机器学习过程;第二步才是真正的模式识别过程。第5部分模式识别技术图5-2模式识别系统工作原理第5部分模式识别技术5.1.4从模式识别系统的工作原理可以看出,可以分别从待识模式、分类知识和类别判决等三个侧面对模式识别方法进行分类。例如,待识模式可以表示为特征向量、字符串、树、图以及模糊集合等。于是,模式识别方法就可分为面向特征向量的模式识别、面向字符串的模式识别,以及面向树、图及模糊集合的模式识别等。利用原始样例可以发现的分类知识有模式类的标准模式、模式类的判别函数、模式类的估计知识等。于是,据此模式识别方法就可分为基于标准模式的模式识别、基于判别函数的模式识别、基于统计决策的模式识别等。现在常见的模式识别方法分类都是基于待识模式的表示形式的。第5部分模式识别技术依据模式的表示形式,模式识别方法可分为基于特征向量的模式识别和基于字符串的模式识别。•统计模式识别–特点是提取待识别模式的一组统计特征，按某种决策函数进行分类判决。•结构模式识别–特点是把待识别模式看成若干个较简单子模式构成的集合，每一个子模式再分为若干个基元，基元按某种组合关系构成模式。就好像文章由单字、词、短语和句子按语法规则构成一样，因此又叫句法模式识别。•模糊模式识别•神经网络模式识别第5部分模式识别技术结构模式识别处理的是字符串或树结构的模式,模式类描述为形式语言的文法,识别器(即分类器)就是有限状态自动机。这样,有一个模式类就有一种语言的文法规则,而作为待识模式的字符串就相当于一个句子,判定一个待识模式的类别就是自动机通过推理运算判定该句子是否遵循某语言的文法规则。第5部分模式识别技术5.2统计模式识别5.2.1距离分类法1.标准模式法设由训练样例可获得c个模式类1,2,…,c，且可获得各个模式类的标准模式M1,M2,…,MC。那么，对于待识模式X，可通过计算其与各标准模式的距离d(X,Mi)(i=1,2,…,c)来决定它的归属。具体分类规则为：d(X,Mj)=mind(X,Mi)Xji=1,2,…,c（5-1）即与X距离最小的标准模式所属的模式类即为X的所属模式类。如果模式类1,2,…,c无标准模式，则可用平均距离法或最临近法进行分类判决。第5部分模式识别技术2.平均距离法平均距离法就是将待识模式X与模式类ωi(i=1,2,…,c)中所有样例模式的距离平均值作为与X的距离，然后以距离最小的模式类作为X的类属。分类规则可描述为：),(),(ijXdXdjXji(5-2)其中,ksllkkYXdsXd1),(1),((k=1,2,…,c),sk为模式类ωk中的样例模式数。第5部分模式识别技术3.最临近法是将与待识模式X距离最近的一个样例模式的模式类作为X的类属。分类规则可描述为),(),(ijXdXdjXji(5-3)其中,sk为模式类ωk中的样例模式数。),,(min),(,,2,1lslkYXdXdk第5部分模式识别技术5.2.2几何分类法一个模式类就是相应特征空间中的一个点集。一般来讲，在特征空间中一个模式类的点集总是在某种程度上与另一个模式类的点集相分离。因此，模式识别的另一个思路就是设法构造一些分界面（线），把特征空间Rn分割成若干个称为决策区域的子空间Ri(i=1,2,…,n)，使得一个模式类刚好位于一个决策区域。这样，对于待识模式X，就可以利用空间中的这些分界面来判定X的类属。分界面（线）方程gi(X)=0中的函数gi(X)称为判别函数。显然，构造分界面的关键就是构造其判别函数。分界面（线）可分为平面（直线）和曲面，相应的判别函数为线性函数和非线性函数。下面我们介绍分界平面和线性判别函数。第5部分模式识别技术对于二分类问题,显然只需一个分界平面。设判别函数为g(X)=WTX+w0其中W=(w1,w2,…,wn)T为X中各分量x1,x2,…,xn的系数组成的向量，称为权向量；w0为一个常数，称为阈值权。那么，分界平面方程为g(X)=WTX+w0=0由几何知识知,位于这个分界平面两边的点X的判别函数值g(X)符号相反。于是,可有分类规则:g(X)0X1g(X)0X2g(X)=0X属于1或2，或者不可判别(5-4)第5部分模式识别技术图5-3二分类问题的分界面(线)示意第5部分模式识别技术例5.1，设对于3维特征空间R3有一个线性可分的二分类问题，其判别函数为g(x,y,z)=8-x-2y-4z。则相应的类别分界面如图5-４所示。于是，对于待识模式p1=(1,1,1)，有g(1,1,1)=10所以，模式p1应属于类1；而对于待识模式p2=(2,2,2)，有g(2,2,2)=-60因此，模式p2应属于类2。第5部分模式识别技术图5-43维特征空间R3的二分类问题分界第5部分模式识别技术对于多分类问题有以下三种方法。（1）对每一个模式类i与其余的模式类设计一个分界平面gi(X)=WiTX+wi0=0，即构造一个线性判别函数gi(X)=WiTX+wi0，使得于是，有分类规则0)(,0)(,XgXXgXiiii当当iiXXg0)(（5-5）第5部分模式识别技术（2）在每两个类之间设计一个分界平面gij(X)=WijTX+wij0=0，即构造一个线性判别函数gij(X)=WijTX+wij0，使得，对于，有gij(X)0。从而，有分类规则ijgij(X)0，iXij(5-6)可以算得,对于一个c分类问题,采用该方法时需要设计c(c-1)/2个分界平面。第5部分模式识别技术（3）对于一个c分类问题构造c个线性判别函数gi(X)=WiTX+wi0，使得gi(X)gj(X)，ij从而有分界平面gi(X)=gj(X)亦即gi(X)-gj(X)=0在这种情况下的