模式识别及最小均方误差算法论文.doc

目录摘要2Abstract2一、绪论（introduction）3二、模式识别简介(Pattern Recognition introduction)42.1 模式识别和模式的概念42.2 模式识别系统【2】4三、模式识别的应用和发展(The application and development of pattern recognition)63.1 模式识别的应用63.2 模式识别的发展73.2.1现状73.2.2发展趋势8四、最小平方误差（LMSE）94.1 LMSE验证可分性算法的基本原理94.2 LMSE算法的迭代计算过程94.3 模式类别可分性的判别104.4 LMSE分类算法原理124.5 LMSE分类算法实现【3】12五、总结（Summary）15参考文献(References)16模式识别及最小平方误差算法Pattern recognition and the least square error algorithm武汉理工大学信息工程学院信研1206 陈维熙 1049721203164摘要本文详细介绍了模式识别系统的概念及模式识别的应用和发展。同时介绍了一种算法:最小平方误差算法（LMSE）。关键字：模式识别 应用和发展 最小平方误差AbstractThis paper describes the concept of Pattern Recognition systems as well as The application and development of Pattern Recognition。Simultaneously，It introduced an algorithm：Last Mean Square Error（LMSE）。Keywords:Pattern Recognition;The application and development;Last Mean Square Error一、绪论（introduction）模式识别诞生于20世纪20年代，随着40年代计算机的出现，50年代人工智能的兴起，模式识别在60年代初迅速发展成为一门学科。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机应用的可能性。几十年来，模式识别研究取得了大量的成果，在很多地方得到了成功的应用。但是，由于模式识别涉及到很多复杂的问题，现有的理论和方法对于解决这些问题还有很多不足之处。为了使读者更好地掌握后面的各章内容，对于这些内容的有限性和局限性有全面的认识，正确地使用这些理论和方法，进而研究新的理论和方法，本章主要讨论模式识别的一些基本概念和问题，以利于对模式识别的现状和未来的发展方向有更全面的了解。二、模式识别简介(Pattern Recognition introduction)2.1 模式识别和模式的概念 我们在生活中时时刻刻都在进行模式识别。环顾四周，我们能认出周围的物体是桌子、椅子，能认出对面的人是张三、李四；听到声音，我们能分辨出是炸带鱼还是臭豆腐。我们所具备的这些模式识别的能力看起来极为平常，谁也不会对此感到惊讶，就连狗猫也能认识它们的主人，更低等的动物也能区别食物和敌害。因此过去的心理学家也没注意到模式识别的能力是个值得研究的问题，就像苹果落地一样习惯不惊。只有在计算机出现以后，当人们企图用计算机来实现人或动物所具备的模式识别的能力时，它的难度才逐步为人们所认识。本书讨论的模式识别是指计算机实现人的模式识别能力。由于计算机的模式识别在多数方面还远不如人，因此研究人脑中的模式识别过程对提高机器的能力是有益的；反之，研究机器模式识别的能力对于理解人脑中的过程也有很大的帮助，认知心理学的很多新模型得益于此。 什么是模式呢？广义地说，存在于时间和空间中可观察的事物，如果我们可以区别它们是否相同或是否相似，都称之为模式。但模式所指的不是事物本身，而是我们从事物获得的信息。因此，模式往往表现为具有时间或空间分布的信息。由于本书主要讨论的是用计算机进行模式识别，信息进入计算机之前通常要经过取样和量化，在计算机中具有时空分布的信息表现为向量即数组。数组中元素的序号可以对应时间和空间，也可以对应其他的标识。例如，医生根据各项化验指标判断疾病种类的模式识别过程中，各种化验项目并不对应实际的时间或空间。因此，对于上面说说的时间应作更广义、更抽象的理解。 人们为了掌握客观事物，按事物相似的程度组成类别。模式识别的作用和目的就在于面对某一具体事物时将其正确地归入某一类别。例如，数字“4”可以有各种不同的字体或写法，但它们属于同一类，即使我们看到从未见过的某种写法的“4”，也能正确地将其分到“4”这一类别中去。从不同角度看人脸，视网膜上的成像也不同，但我们可以识别出这个人是谁，把所有不同角度的像都归入某个人这一类。如果给每一个类命名，并且用特定的符号来表达这个名字，那么模式识别可以看成是从具有时间和空间分布的信息向着符号所做的映射。通常，我们把通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息称为模式，而把模式所属的类别或同一类中模式的总体称为模式类（或简称为类）。也有人习惯把模式类称为模式，而把个别具体的模式称为样本，这种用词上的不同可以从上下文弄清楚其含义，并不会引起误解。2.2 模式识别系统【2】有两种基本的模式识别方法，即统计模式识别方法和结构（句法）模式识别方法，与此相应的模式识别系统都由两个过程组成，即设计和实现。设计是指用一定数量的样本（叫做训练集或学习集）进行分类器的设计。实现是指用所设计的分类器对待识别的样本进行分类决策。基于统计方法的模式识别系统主要由四个部分组成：数据获取，预处理，特征提取和选择，分类决策，如图1.1所示。信息获取预处理特征提取和选择分类器设计分类决策图 1.1 模式识别系统下面我们简单地对这几个部分作些说明。 1.数据获取 为了使计算机能够对各种现象进行分类识别，要计算机可以运算的符号来表示所研究的对象。通常输入的信息有下列3种类型，即 （1）二维图像 如文字、指纹、地图、照片这类图像。 （2）一维波形 如脑电图、心电图、机械震动波形等。 （3）物理参量和逻辑值 前者如在疾病诊断中病人的体温及各种化验数据等；后者如对某参量正常与否的判断或对症状有无的描述，如疼与不疼，可用逻辑值即0和1表示。在引入模糊逻辑的系统中，这些值还可以包括模糊逻辑值，比如很大、大和比较大等。 通过测量、采样和量化，可以用矩阵或向量表示二维图像或一维波形。这就是数据获取的过程。 2.预处理 预处理的目的是除去噪声，加强有用的信息，并对输入测量一起或其他因素所造成的退化现象进行复原。 3.特征提取和选择 由图像或波形所获得的数据量是相当大的。例如，一个文字图像可以有千万个数据，一个心电图波形也可能有千万个数据，一个卫星遥感器图像的数据量就更大。为了有效地实现分类识别，就要对原始数据进行变换，得到最能反映分类本质的特征。这就是特征提取和选择的过程。一般我们把原始数据组成的空间叫测量空间，把分类识别赖以进行的空间叫特征空间，通过变换，可以把维数较高的测量空间中表示的模式变为在维数较低的特征空间中表示的模式。在特征空间中的一个模式通常也叫做一个样本，它往往可以表示成为一个向量，即特征空间中的一个点。 4.分类决策 分类决策就是在特征空间中用统计方法把被识别的对象归为某一类别。基本作法是在样本训练集基础上确定某个判别规则，使按这种判别规则对被识别的对象进行分类所造成的错误识别率最小或引起的损失最小。三、模式识别的应用和发展(The application and development of pattern recognition)3.1 模式识别的应用 经过多年的研究和发展，模式识别技术已广泛被应用于人工智能、计算机工程、机器学、神经生物学、医学、侦探学以及高能物理、考古学、地质勘探、宇航科学和武器技术等许多重要领域，如语音识别、语音翻译、人脸识别、指纹识别、手写体字符的识别、工业故障检测、精确制导等。模式识别技术的快速发展和应用大大促进了国民经济建设和国防科技现代化建设。1.字符识别字符识别处理的信息可分为两大类：一类是文字信息，处理的主要是用各国家、各民族的文字（ 如： 汉字，英文等书写或印刷的文本信息，目前在印刷体和联机手写方面技术已趋向成熟，并推出了很多应用系统；另一类是数据信息，主要是由阿拉伯数字及少量特殊符号组成的各种编号和统计数据，如：邮政编码、统计报表财务报表、银行票据等等，处理这类信息的核心技术是手写数字识别。汉字是历史悠久的中华民族文化的重要结晶，闪烁着中国人民智慧的光芒。汉字数量众多，仅清朝编纂的康熙字典就包含了49，000 多个汉字，其数量之大，构思之精，为世界文明史所仅有。由于汉字为非字母化、非拼音化的文字，所以在信息技术及计算机技术日益普及的今天，如何将汉字方便、快速地输入到计算机中已成为关系到计算机技术能否在我国真正普及的关键问题。目前，汉字输入主要分为人工键盘输入和机器自动识别输入两种。其中人工键入速度慢而且劳动强度大；自动输入又分为汉字识别输入及语音识别输入。从识别技术的难度来说，手写体识别的难度高于印刷体识别，而在手写体识别中，脱机手写体的难度又远远超过了连机手写体识别。到目前为止，除了脱机手写体数字的识别已有实际应用外，汉字等文字的脱机手写体识别还处在实验室阶段。2.语音识别 语音识别技术技术所涉及的领域包括：信号处理、模式识别、概率论和信息论、发声机理和听觉机理、人工智能等等。近年来，在生物识别技术领域中，声纹识别技术以其独特的方便性、经济性和准确性等优势受到世人瞩目，并日益成为人们日常生活和工作中重要且普及的安全验证方式。而且利用基因算法训练连续隐马尔柯夫模型的语音识别方法现已成为语音识别的主流技术。该方法在语音识别时识别速度较快，也有较高的识别率。3.指纹识别我们手掌及其手指、脚、脚趾内侧表面的皮肤凹凸不平产生的纹路会形成各种各样的图案。而这些皮肤的纹路在图案、断点和交叉点上各不相同，是唯一的。依靠这种唯一性，就可以将一个人同他的指纹对应起来，通过比较他的指纹和预先保存的指纹进行比较，便可以验证他的真实身份。一般的指纹5个大的类别:左旋型（left loop）,右旋型（right loop）,双旋型（twin loop）,螺旋型（whorl），弓型（arch）和帐型（tented arch）,这样就可以将每个人的指纹分别归类，进行检索。指纹实现的方法有很多，大致可以分为4 类：基于神经网络的方法、基于奇异点的方法、语法分析的方法和其他的方法。在指纹识别的应用中，一对一的指纹鉴别已经获得较大的成功，但一对多的指纹识别，还存在着比对时间较长，正确率不高的特点。为了加快指纹识别的速度，无论是对简化图像的预处理，还是对算法的改进，都刻不容缓。4.细胞识别细胞识别是最近在识别技术中比较热门的一个话题。以前，对疾病的诊断仅仅通过表面现象，经验在诊断中起到了主导作用，错判率始终占有一定的比例；而今，通过对显微细胞图像的研究和分析来诊断疾病，不仅可以了解疾病的病因、研究医疗方案，还可以观测医疗疗效。如果通过人工辨识显微细胞诊断疾病也得不偿失，费力费时不说，还容易耽误治疗。基于图像区域特征，利用计算机技术对显微细胞图像进行自动识别愈来愈受到大家的关注，并且现在也获得了不错的效果。但实际中，细胞的组成是复杂的，应该选择更多的特征，建立更为完善的判别函数，可能会进一步提高分类精度。3.2 模式识别的发展3.2.1现状 以地图模式识别为例，地图模式识别是由计算机来对地图进行识别与理解, 并借助一定的技术手段, 让计算机研究和分析地图上的各种模式信息, 获取地图要素的质量意义。其计算处理的过程类似于人对地图的阅读。 地图模式识别是近年来在地图制图领域中新兴的一门高新技术, 是信息时代人工智能、模式识别技术在地图制图中的具体应用。由于它是传统地图制图迈向数字地图制图的一座桥梁, 因此,地图模式识别遥感技术、地理信息系统一起, 被称为现代地图制图的三大技术。 目前, 地图模式识别由于具有广泛的应用价值和发展潜力,因而受到了人们的普遍重视。尤其是随着现今的计算机及其外部硬件环境的不断提高, 科技不过发展的情况下，从事地图模式识别的研究也越来越多。因此在国内外都有许多政府机构、公司、大学、研究所正在致力于这方面的研究。 例如国内的许多单位也在从事地图模式识别方面的研究, 如武汉测绘科技大学的李德仁、陈晓勇的CCD扫描等高线图的自动栅格一矢量转换方法(1991), 该课题是国家自然科学基金资助项目。西安电子科技大学的赵树萝等人承担的“ 地图的计算机识别、理解与描述”的国家科研任务, 其研究成果于1991年通过了技术鉴定。上海交通大学图像处理与模式识别研究所的余松煌等人承担的国防科工委下达的“地图图形计算机识别” 的课题, 取得了一定的研究成果,1990年在北京展览了他们所开发的系统。华北计算技术研究所的方家哄、刘景超的军用地图非线状元素的自动识别(1990)。近年来,国内也有一些商品化的系统出现, 如清华大学的ANNO5.2彩色图形图像创作出版系统，它是以工程图矢量化为核心的图形识别软件，能将各类输入计算机的工程图转换成CAD系统可接受的文件格式, 能识别8种线宽,分离圆、圆弧、数字和字符, 可做滤波、降噪音、直线提取、圆弧分离和识别图形等, 能对扫描输入图像进行拼接和编辑。 以模式识别在气象领域应用，卫星云图在灾害性天气预报中的重要性已成为气象工作者的共识。如何从云图中提取有用的信息, 实现计算机的加工处理, 是本系统首先要解决的问题。我们采用数学形态学与句法模式识别相结合, 将云系结构与天气系统联系起来, 实现了台风过程不同阶段云系发展演变特征的计算机分析识别。螺旋云带、密蔽云墙和台风眼是构成近年来计算机据仿真已成为气象领域的一种主要方法, 已经取得了不少有价值的成果, 如气候成因仿真和厄尔尼诺现象的仿真等。然而在灾害性天气的仿真中出现了两方面的问题, 有些由于情况太复杂. 如暴雨. , 难于建立合适的仿真数学模型, 有些又由于数学模型太复杂, 一系列的参数很难设定. 如台风. , 因而实施有困难, 进展不明显。从实际应用的角度, 人们对一些过程发展的细节不一定必须了解, 认识和把握某些关键就可以了。就以台风路径而言, 如果能够了解在什么情况台风路径将出现异常、何时将突然转向这样两个关键问题, 台风路径的其它问题就显得不那么重要了。以目标系统模型为基础的计算机定性仿真正好在这种情况下可充分发挥其作用。 模式识别中的一个重要应用是语音识别。语音识别就是让计算机能听懂人说的话, 一个重要的例子就是七国语言( 英、日、意、韩、法、德、中) 口语自动翻译系统。其中, 中文部分的实验平台设立在中国科学院自动化所的模式识别国家重点实验室, 这是口语翻译研究跨入世界领先水平的标志。该系统实现后, 人们出国预定旅馆、购买机票、在餐馆对话和兑换外币时, 只要利用电话网络和国际互联网, 就可用手机、电话等与“老外”通话。 语音识别技术发展到今天，特别是中小词汇量非特定人语音识别系统识别精度已经大于98，对特定人语音识别系统的识别精度就更高。这些技术已经能 够满足通常应用的要求。由于大规模集成电路技术的发展，这些复杂的语音识别系统也已经完全可以制成专用芯片，大量生产。在西方经济发达国家，大量的语音识 别产品已经进入市场和服务领域。一些用户交机、电话机、手机已经包含了语音识别拨号功能，还有语音记事本、语音智能玩具等产品也包括语音识别与语音合成功 能。人们可以通过电话网络用语音识别口语对话系统查询有关的机票、旅游、银行信息，并且取得很好的结果。调查统计表明多达85以上的人对语音识别的信息 查询服务系统的性能表示满意。 当然模式识别所应用的范围不单单只有上面那些，不过从上述的例子应用中不难发现模式识别在我们身边的比重越来越重了。3.2.2发展趋势 人工智能对社会的影响可以通过回答这样两个问题来衡量： 人工智能产品对于社会的好处，有多少东西是人工智能的产物。 工业领域尤其是制造业,已成功地使用了人工智能技术。 包括智能设计、虚拟制造、柔性制造、敏捷制造、在线分析、智能调度、仿真和规划等, 这些都大大提高了生产效益。人工智能对经济和金融的影响, 专家系统的广泛使用功不可没。据估计全世界通过这项技术每年可节省10亿美元以上。 例如,股票商利用智能系统辅助其进行分析、判断和决策, 信用卡欺诈检侧系统得到普遍应用。人工智能也渗透进了人们日常生活, 如教育、医疗和通信我们已经亲眼目睹、亲身体会到智能技术给日常生活带来的深刻变化,它使得我们周围无处不在的计算机系统具有灵活而友好的多种智能用户界面,使计算机和人的交流更为容易和自然。带有嵌入式计算机的家用电器的智能化和自动化,把我们从琐碎的家务劳动中解放出来。人工智能技术帮助我们进行医疗保健帮助我们丰富儿重教育, 帮助我们在浩如烟海的因特网中寻找真实、有用的信息, 成为默默无闻的好助手它改变了传统的通信方式语。还有模式识别在各个领域的应用现在也取得较好的成绩，因此模式识别也别各国重点应用在各个领域当中，方便人们的生活。 以知识为基础的模式识别系统的出现和不断发展, 标志着模式识别方法的更加智能化,是日益受到重视的发展方向。四、最小平方误差（LMSE）4.1 LMSE验证可分性算法的基本原理 LMSE算法【1】是对准则函数引进最小均方误差这一条件而建立起来的，这种算法的主要特点是在训练过程中判定训练集是否线性可分，从而对结果的收敛性做出判断。 LMSE算法把对满足式的求解改为对满足的求解，式中是各分量均为正值的矢量，故这两个公式是互相等价的。 LMSE算法的出发点就是选择一个准则函数，使其达到极小值时，可以得到最小二乘近似解。依据这样的思路，可将准则函数定义为 可以看出，有唯一的极小值0，发生在时。准则函数的值等于与误差的平方之和，此时，我们的目标是使这个误差的平方和最小，因此称这一准则导出的算法为最小均方误差算法。4.2 LMSE算法的迭代计算过程 设初始值，需使其的每一分量都为正值，括号中的数字代表迭代次数。 式中，称为的伪逆，为阶长方阵，为阶长方阵。在上面的过程中和互相独立，因此两者计算的先后次序对计算结果没有影响。4.3 模式类别可分性的判别 可以证明，当模式类别线性可分，且校正系数满足时，该算法收敛，可求得解。因为理论上不能证明到底需要迭代多少步才能达到收敛，所以在执行时可以监视出现解的过程，从而判断是否收敛。通常的方法是每次迭代计算后检查一下的各分量和误差向量，从而可以判断是否收敛。具体分为以下几种情况： 1.如果，表明，有解。 2.如果，表明，隐含着有解。若继续迭代，可使。 3.如果，也就是说的所有分量为负数或零，但不全部为零，表明模式类别线性不可分，停止迭代，无解。此时若继续迭代，数据将不再发生变化，不能再调整。 从上面的过程可以清楚地看出，当后，若继续迭代下去，和都不会再发生变化。因此只有当中有大于零的分量时，才需要继续迭代，一旦的全部分量只有0和负数，则立即停止。 实际上，对一线性不可分模式，要达到全部分量都为非正，需要迭代很多次，往往早在全部分量都达到非正值以前就能看出其中有些分量向正值变化得极慢，这时已能估计出造成线性不可分的某些样品，及早采取对策【2】。 下面以一个实例来说明这种情况。假设有4个训练样品，共分为两类：。显然它们是线性可分的。用MATLAB软件编程采用LMSE算法来验证其可分性。w1=0 0;0 1w2=1 0;1 1x=0 0 1;0 1 1;-1 0 -1;-1 -1 -1xsharp=inv(x*x)*xB=1 1 1 1;c=1;W=xsharp*Be=x*W-Bif e0 for i=1:4 W=W+c*xsharp*abs(e) B=B+c*(e+abs(e) e=x*W-B i=i+1; end if eeps disp(模式类线性可分，解为) disp(W) end if e0 disp(模式类线性不可分，无解) end end实验结果如下：模式类线性可分，解为W =-2.0000 0.0000 1.0000实验结果分析：对所有样品增1，并对取负后可得样品矩阵为X的规范逆矩阵为取和得。因为，因而即为所求的解，这时。判别函数为。4.4 LMSE分类算法原理 LMSE算法以最小均方误差作为准则，因均方误差为 因而准则函数为 准则函数在时得的最小值。 准则函数对的偏导数为 带入迭代方程对于多类问题来说,类问题应该有个权函数方程，对于每一个权函数方程来说，如，则 否则4.5 LMSE分类算法实现【3】 1.设各个权矢量的初值为0，即。 2.输入第次样品，计算。 3.若，则，否则。 4.计算，其中。 循环执行第2步，直到属于类的所有样品都满足条件： 下面用一个实例来说明该算法的进行过程。给定两类样品：现在用MATLAB软件编写程序来实现LMSE算法计算判别函数。function y=lmseclassify(sample) load templet pattern； w=zeros(26,10); flag=1; num=0;