模式识别（作业）报告

模式识别综述与展望浅析 学 号： 模式识别课程论文 题 目 模式识别综述与展望浅析 学 院 专 业 班 级 姓 名 指导教师 年 月 日 模式识别综述与展望浅析 ABSTRACT: The pattern recognition is the process to process and analyze various form (value, writing and logical relation) of information which attributes to the thing or the phenomenon , so as to describe, identify, classify and explain the thing or the phenomenon, which is the important component of the information science and the artificial intelligence. This paper introduces the difference and links between the pattern recognition and the knowledge guidance pattern recognition system, and the application of the pattern recognition and its development potential. KEYWORDS: Pattern Recognition; Information Science;Artificial Intelligence 摘要：模式识别是指对 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。文章介绍了模式识别和知识引导的模式识别系统的区别和联系、模式识别中涉及到的经典算法以及模式识别的应用及其发展潜力。 关键词：模式识别;信息科学;人工智能；模式识别算法 1 引言 什么是模式和模式识别？广义地说，存在于时间和空间中可观察的事物，如果可以区别它们是否相同或相似，都可以称之为模式；狭义地说，模式是通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息；把模式所属的类别或同一类中模式的总体称为模式类(或简称为类)。而“模式识别”则是在某些一定量度或观测基础上把待识模式划分到各自的模式类中去。 模式识别的研究主要集中在两方面，即研究生物体(包括人)是如何感知对象的，以及在给定的任务下，如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家、神经生理学家的研究内容，属于认知科学的范畴；后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力，已经取得了系统的研究成果。 本文将介绍传统的模式识别和知识引导的模式识别系统的区别和联系、模式识别所涉及到的经典算法，模式识别的应用及其近乎无限的发展潜力。 2 传统的模式识别方法—统计方法与句法方法 把图像或图像系列分割为线条、边缘，结点，区域等并提供相应的特征，诸如灰度值、颜色、形状、纹理，深度等。目的是要利用这些信息对模式进行分类或者对模式进行分析(描述)。分类是实现一个模式与一个类别号的对应。分析(描述，解释)则是实现一个模式与一个符号描述的对应。模式分析一般包括：解释模式的组成部份，说明各个组成部份的时间和空间关系，甚至给出作出特定解释的理由。 2.1 用统计方法发展起来的模式识别系统如图2.1所示。 图2.1 统计模式识别系统 在用统计方法研究模式识别问题时，大体上侧重于特征抽取与选择以及模式分类与学习两个方面。 （一）特征选择与特征抽取 特征选择与特征抽取的一般方法主要分为两种:特征空间变换以及信息和距离的测度。特征空间变换这个方法目的是将原始特征空间变换为较低维数的特征空间，以便于模式的表示与模式的分类。当着眼于模式表示时，常用最小均方误差与嫡准则作为确定最优变换的最佳准则。当着眼于分类判别时，往往以最大类间距离和最小类内距离为最佳准则。至于变换方法本身可以是线性的也可以是非线性的。可利用的变换有:Courier变换，Welsh-Hallmark变换，Mar变换。为了压缩特征空间的维数常利用Karhunen-love展开式和主分量分析法。衡量变换结果好坏的标准之一是要看是否增加模式类的可分性。就增加模式类的可分性而言，一般非线性变换比线性变换好。然而就计算复杂性而言，。线性变换要比非线性变换简单得多。 信息和距离的测度与识别率的上界和下界有关。为了比较各种信息和距离的测度，Can't以误识率的上界为准则，把各种信息和距离测度的定义按其重要性以递增顺序排列起来。对于两个模式类的识别问题，这个顺序是: 就计算的困难性而言，计算Bhattacharyya距离比计算其他距离测度要容易些。 （二）分类和学习 对模式进行分类和描述是模式识别系统的根本目标。对于每类模式，当已经知道或者虽不确切知道但能精确估计出其特征向量的条件概率密度函数时(亦称类密度函数)，就可以导出贝叶斯分类规则，它使平均风险或误识率最小。实际上，当可以得到大量模式样本时，可以比较精确的估计出类密度函数，或者从样本学习到类密度函数。比较实用的非参数分类 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 有:最近邻分类规则(NN规则)和K最近邻分类规则(K-NN规则，以及其他种种变态的NN规则。非参数分类方案一般是从样本中直接学习分类规则。 学习类密度函数或判决边界线的方法可以用Lesbian估值法、随机逼近法、势函数法等。Littler研究了一种将判函数归入模式特征空间的一个子空间的方法，它可以在缺少任意数目的分量的情况下使模式分类仍为最佳(平均方差最小)。 对于无人管理的学习，特别是模式的类射数不确切知道时，这时的分类就是集群分析。各种相似性和距离测度都可用作集群划分的准则。集群划分准则和集群参数的选择往往需要探索性地或交互式地进行。 运用句法(或结构)方法的模式识别系统的框图如图2.2所示。 图2.2 句法模式识别系统 图中的“基元”类似于统计方法中的特征。在句法方法中。用一个“句子”表示一个模式。句子构成语言语言具有特定的文法。文法就是用基元构成模式的规则。文法推断是一个 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 由基元构成模式的规律性。从而得到规则即文法的过程，类似于学习。句法分析则是分析输入模式是否符合某种文法规则的过程。也就是分析能否用该文法生成输入模式。分析结果为肯定则对输入模式完成了分类。分析结果为否定，则拒绝输入模式。也可以用关系图来表示模式结构信息。 （一）基元选择和基元抽取 通常需在基元抽取的复杂性和文法复杂性两者之间折衷，也可以用曲线线段的长度和曲率等表示曲线线段的特征。对于区域范围的模式，一个区域内存在两个特征互异的子区域时称这个区域为边缘，存在着小于一定距离的两个边缘时称这个区域为线，边缘闭合时称为区。常用的特征可以取灰度特征。也可以用形状和纹理测度来描述区域。其他还有一些方法亦可用来描述图像基元，例如灰度矩阵、灰度共生矩阵、梯度共生矩阵、点测度等。 （二）文法 已经有了各种专门的语言来描述特定的模式。例如描述中外文字字符、染色体图像、火花室图像、二维数学化学结构、颈动脉脉冲波形、二维飞机外形、口语单词、指纹图像等。对于多维模式，用多维文法来描述。其他如网状文法(web)、图文法、树文法、形状文法等都已有了应用。有两个因素决定了文法的选择，一个是所选基元的情况，另一个是要权衡文法的描述能力与文法分析的效率。 在实际应用中，往往存在某些不确定性。例如测量中的噪声和抖动会引起分割误差和基元抽取误差，从而使描述模式的语言产生二义性。在二义性存在的情况下，可以用随机语言来描述模式。产生随机语言的文法称作随机文法。在随机文法中引进了概串方法，即用具有概率分布的语句来描述模式。 （三）句法分析 在选择文法时需考虑文法的描述能力与句法分析复杂性之间的矛盾。同样，在研究句法分析问题时，也应考虑如何从句法分析的角度处理这种矛盾。进行分析的识别器就要采用由扩充的或变换的模式文法组成的识别器，这时分析器的效率显然会降低很多。事实上，要在提高纠错能力和降低分析效率之间进行权衡，实际困难较大。 在句法分析中，还可以采用距离或加权距离的方法。利用两个语句之间的距离或加权距离作为两个模式之间相似性的测度，只要有了相似性测度就可以应用现有的任一种搜索集群的方法作集群分析。这也是一种无人管理的方法。完成集群分析以后，就可以应用文法推断技术来推断每一个群的文法，并构造出相应的句法分析器。 3 知识引导的模式识别 模式识别过程可以看成是下面的规则： 描述::>识别类 在统计决策理论方法中，描述通常是一些解析表达式。表达式中包含先验地选取的变量集合，这些变量分布于整个决策空间中。当被研究模式的特征不是数值特征，而变量之间存在互相强烈依赖的各种关系时。决策理论方法就显得不太适用。在这样的情况下，可以用结构方法。决策理论方法和句法方法两着几乎没有利用被研究问题的语义信息。所以它们能表现和识别的模式类别是有限制的。 在设计模式识别系统时，不但要充分利用模式的数值特征和结构特征。还需要利用和问题有关的知识来描述和分析模式，这种理论系统和方法适宜于处理各种类型的描述，它能充分地利用问题的语义，并且能较好地满足人们在易于接受方面的要求。这种系统能表现被研究问题的知识，具有演绎、归纳能力。所以它能产生不包含在原始特征中的新描述，并能给出演绎推理的过程。这种新型的模式识别系统称为知识(或规则)引导的模式识别系统，其系统结构如图3.1所示 图3.1 知识引导的模式识别系统 由知识引导的模式识别系统应由下面几个部份组成:特征抽取部份、数据库、知识库、演绎机构以及控制机构。特征抽取部分负责抽取模式的数值特征与关系特征。数据库有定义、加载、修改、检索等模块。由于数据库具有完备的数据结构，对每个关键属性设有索引。知识库中包含有事实和规则。事实用来描述被研究的模式，规则是关于被研究的模式和模式之间关系的一般性描述〕这些事实与规则和具体问题紧密相关。演绎和控制机构是知识引导的模式识别系统的重要部份。根据问题所处的当前状态，控制机构选择合适的规则进行演绎和推理。 随着研究的发展，被研究的对象变得复杂起来。就出现了以模型为基础的视觉识别技术。例如，Mockworth提出的方案，认为识别过程是个感知循环。在这个方案中，识别是个叠代过程:精细地描述模型、发现提示、引用模型、验证模型。根据各种拓扑图像，提炼出提示。 4 模式识别的经典算法——C4.5，k-means算法以及SVM 1、C4.5 算法 机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。 决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。 决策树一般都是自上而下的来生成的。选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。 从根到叶子节点都有一条路径，这条路径就是一条“规则”。 决策树可以是二叉的，也可以是多叉的。 对每个节点的衡量： 1) 通过该节点的记录数 2) 如果是叶子节点的话，分类的路径 3) 对叶子节点正确分类的比例。 由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了，这里就不做介绍。 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。来自搜索的其他内容。 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. 分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是: 根: 学习的事例集. 枝: 分类的判定条件. 叶: 分好的各个类. ID3算法 1.概念提取算法CLS 1) 初始化参数C={E},E包括所有的例子,为根. 2) IF C中的任一元素e同属于同一个决策类则创建一个叶子 节点YES终止. ELSE 依启发式标准,选择特征Fi={V1,V2,V3,．．．Vn}并创建判定节点 划分C为互不相交的N个集合C1,C2,C3,．．．,Cn； 对任一个Ci递归. 2.ID3算法 1) 随机选择C的一个子集W (窗口). 2) 调用CLS生成W的分类树DT(强调的启发式标准在后). 3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子). 4) 组合W与已发现的意外,形成新的W. 5) 重复2)到4),直到无例外为止. 启发式标准: 只跟本身与其子树有关,采取信息理论用熵来量度. 熵是选择事件时选择自由度的量度,其计算方法为 P = freq(Cj,S)/|S|; INFO(S)= - SUM( P*LOG(P) ) ; SUM()函数是求j从1到n和. Gain(X)=Info(X)-Infox(X); Infox(X)=SUM( (|Ti|/|T|)*Info(X); 为保证生成的决策树最小,ID3算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的的特征来生成子树. 3 .ID3算法对数据的要求 1. 所有属性必须为离散量. 2. 所有的训练例的所有属性必须有一个明确的值. 3. 相同的因素必须得到相同的结论且训练例必须唯一. C4.5对ID3算法的改进: (1). 熵的改进,加上了子树的信息. Split_Infox(X)= -SUM((|T|/|Ti| )*LOG(|Ti|/|T|) ); Gain ratio(X)= Gain(X)/Split Infox(X); (2). 在输入数据上的改进. 1) 因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理,但结论属性的值必须是离散值. 2) 训练例的因素属性值可以是不确定的,以 ? 表示,但结论必须是确定的. 3). 对已生成的决策树进行裁剪,减小生成树的规模. 2、The k-means algorithm k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。假设有k个群组Si, i=1,2,...,k。μi是群组Si内所有元素xj的重心，或叫中心点。 　　k平均聚类发明于1956年， 该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。 　　劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。（上面函数中存在的不同的最优解） 　　虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。 　　从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。 3、SVM算法 支持向量机，英文为Support Vector Machine，简称SV机。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。 支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化（Tikhonov Regularization）方法的一个特例.这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。 Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine,简称SVM)。支持向量机的提出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法。 SVM的主要思想可以概括为两点： (1) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。 (2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。 5模式识别的应用 5.1文字识别 汉字已有数千年的历史，也是世界上使用人数最多的文字，对于中华民族灿烂文化的形成和发展有着不可磨灭的功勋。所以在信息技术及计算机技术日益普及的今天，如何将文字方便、快速地输入到计算机中已成为影响人机接口效率的一个重要瓶颈，也关系到计算机能否真正在我过得到普及的应用。目前，汉字输入主要分为人工键盘输入和机器自动识别输入两种。其中人工键入速度慢而且劳动强度大；自动输入又分为汉字识别输入及语音识别输入。从识别技术的难度来说，手写体识别的难度高于印刷体识别，而在手写体识别中，脱机手写体的难度又远远超过了连机手写体识别。到目前为止，除了脱机手写体数字的识别已有实际应用外，汉字等文字的脱机手写体识别还处在实验室阶段。 5.2 语音识别 语音识别技术技术所涉及的领域包括：信号处理、模式识别、概率论和信息论、发声机理和听觉机理、人工智能等等。近年来，在生物识别技术领域中，声纹识别技术以其独特的方便性、经济性和准确性等优势受到世人瞩目，并日益成为人们日常生活和工作中重要且普及的安验证方式。而且利用基因算法训练连续隐马尔柯夫模型的语音识别方法现已成为语音识别的主流技术，该方法在语音识别时识别速度较快，也有较高的识别率。 5.3 指纹识别 我们手掌及其手指、脚、脚趾内侧表面的皮肤凹凸不平产生的纹路会形成各种各样的图案。而这些皮肤的纹路在图案、断点和交叉点上各不相同，是唯一的。依靠这种唯一性，就可以将一个人同他的指纹对应起来，通过比较他的指纹和预先保存的指纹进行比较，便可以验证他的真实身份。一般的指纹分成有以下几个大的类别:left loop,right loop,twin loop,whorl,arch和tented arch,这样就可以将每个人的指纹分别归类，进行检索。指纹识别基本上可分成：预处理、特征选择和模式分类几个大的步骤。 6 模式识别技术的发展趋势 模式识别技术是人工智能的基础技术，21世纪是智能化、信息化、计算化、网络化的世纪，在这个以数字计算为特征的世纪里，作为人工智能技术基础学科的模式识别技术，必将获得巨大的发展空间。在国际上，各大权威研究机构，各大公司都纷纷开始将模式识别技术作为公司的战略研发重点加以重视。 6.1语音识别技术 语音识别技术正逐步成为信息技术中人机接口的关键技术，语音技术的应用已经成为一个具有竞争性的新兴高技术产业。中国互联网中心的市场预测：未来5年，中文语音技术领域将会有超过400亿人民币的市场容量,然后每年以超过30%的速度增长。 6.2生物认证技术 生物认证技术本世纪最受关注的安全认证技术，它的发展是大势所趋。人们愿意忘掉所有的密码、扔掉所有的磁卡，凭借自身的唯一性来标识身份与保密。国际数据集团（IDC）预测：作为未来的必然发展方向的移动电子商务基础核心技术的生物识别技术在未来10年的时间里将达到100美元的市场规模。 6.3数字水印技术 90年代以来才在国际上开始发展起来的数字水印技术是最具发展潜力与优势的数字媒体版权保护技术。IDC预测，数字水印技术在未来的5年内全球市场容量超过80亿美元。 7 结语 模式识别从2 0世纪2 0年代发展至今，并不是要对所有模式识别问题都适用的单一模型和解决识别问题，而是结合具体问题把统计的和句法的识别结合起来，把统计模式识别或句法模式识别与人工智能中的启发式搜索结合起来，把统计模式识别或句法模式识别与支持向量机的机器学习结合起来，把人工神经元网络与各种已有技术以及人工智能中的专家系统、不确定推理方法结合起来，深入掌握各种工具的效能和应有的可能性，互相取长补短，开创模式识别应用的新局面。