（计算机应用技术专业论文）信息粒及其在脱机手写识别中应用的研究.pdf

信息粒及其在脱机手写识别中应用的研究 摘要 信息粒和粒计算是近几年国际上发展较迅速的一个学科，它在许多方面都有 其特别的理论意义和应用价值。 本文详细分析研究了粒计算的基本理论与技术，并将其应用于模式识别特别 是脱机手写识别字符领域，构建脱机手写识别字符的特征信息系统。着重研究了 特征信息粒的提取、特征信息粒的处理，以及基于信息粒的分类器的构建等方面 的内容。提出基于信息粒技术的邻域拓展及约简方案和模版匹配的m a x n e t 网络分 类器模型。并采用上述方案和分类模型对1 0 个脱机手写阿拉伯数字进行识别实验 和与传统识别方法进行对比研究试验，实验结果表明所提出的分类模型不仅是有 用的，而且是有效的，识别效果达到了预期的目标。 论文的最后部分分析了所给方案中的一些不足之处，并展望了信息粒和粒计 算技术在模式识别领域的未来发展趋势。 关键词：信息粒，粒计算，决策规则，分类 lil 信息粒及其在脱机手写识别中应用的研究 a b s t r a c t i n f o r m a t i o ng r a n u l e s a n do rg r a n u l a rc o m p u t i n g i san e w s u b j e c tt h a td e v e l o p e d l a s t l yi nr e c e n ty e a r sa n dh a si t ss p e c i a lm e a n i n g si nm a n ya s p e c t s t h i sp a p e ra n a l y s e sa n dr e s e a r c h e st h eb a s i ct h e o r ya n dt e c h n o l o g yo fi n f o r m m i o n g r a n u l e s a n da n dp r e s e n t sa ni n f o r m a t i o ng r a n u l e s a n ds y s t e mt o r e c o g n i z eo f f - l i n e h a n d w r i t i n gd i g i t s w ec a r e f u l l yd i s c u s st h ea b s t r a c t i o no ft h ec h a r a c t e r i s t i ci n f o r m a t i o n g r a n u l e s a n d ，t h ep r o c e s s i n go ft h ec h a r a c t e r i s t i ci n f o r m a t i o ng r a n u l e s a n da n dt h e c o n s t r u c t i o no fc l a s s i f y i n gd e v i c eb a s e do ni n f o r m a t i o ng r a n u l e s a n d ，e t c f i r s t l y , t h i sp a p e rp r o v i d e san e i g h b o r h o o de x p a n d i n gs c h e m eo ft h ei n f o r m a t i o n g r a n u l e s a n da n das c h e m eo fi n f o r m a t i o n r e d u c t i o n s e c o n d l y i t c o n s t r u c t s g m a x n e tn e t w o r kc l a s s i f y i n gd e v i c em o d e lb a s e do nt h et e c h n o l o g yo fi n f o r m m i o n g r a n u l e s a n d f i n a l l yam a t c h i n ga l g o r i t h mb yu s i n gi n f o r m a t i o ng r a n u l e s a n dt e m p l a t e f o rd e c i s i o nr u l e si sa l s o p r o p o s e d t h ee f f e c t i v e n e s so ft h ea p p r o a c hh a sb e e n d e m o n s t r a t e db ye x p e r i m e n t s t h el a s tp a r to ft h ea r t i c l eh a sa n a l y s e ds o m ew e a ka s p e c t so ft h es c h e m ea n dh a s l o o k e df o r w a r dt ot h ed e v e l o p m e n tt r e n di nt h ef i e l do f p a t t e r n r e c o g n i t i o nb a s e do nt h e i n f o r m a t i o ng r a n u l e s a n da n dg r a n u l a rc o m p u t i n g k e yw o r d s ：i n f o r m a t i o ng r a n u l e s a n d ， g r a n u l a rc o m p u t i n g ，d e c i s i o nr u l e ， c l a s s i f i c a t i o n -i 独创性声明 y 928769 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得直昌太堂或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者虢彳考s 哲签字日期力口磊月。日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权直昌太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：舒，诧毒务导师签名：谚7 秒祭 签字日期多年乡月 日 签字日期：d 年占月 日 学位论文作者毕业后去向： 工作单位： 电话： 通讯地址：邮编： 信息粒及其在脱机手写识别中应用的研究 1 1 背景介绍 第一章引言 本课题来源于国家和江西省自然科学基金项目( # 6 0 1 7 3 0 5 4 ，# 0 3 1 1 1 0 1 ) ，属 于理论与实践紧密结合的研究。 信息粒和粒计算n 倒是近几年国际上发展较迅速的一个学科，它在许多方面得 到重要应用，诸如区间分析，数据推理，整体分解，r o u g h 集理论，d s 证据理论， 从例子学习，定性处理理论，决策树，语义网络，约束程序设计，图像分割，群 体分类等等。如何从不同的信息源及不同的背景知识中提取新的信息粒结构模式， 使之更加合理，更加有效地基于粒的快速计算，实现近似推理及应用将是粒计算 理论进一步的研究方向。 脱机手写识别文字瞄2 ，船3 的概念诞生于1 9 2 9 年，是一个经典的问题。但是， 它又是一个实用性极强的技术，它直接服务于最终用户。而随着信息化建设的高 速发展，最终用户的需求也在不断地变化和扩充，比如说支票数据处理，邮政系 统等。因此，脱机手写识别文字技术也应随之而变。由于不能象联机手写识别那 样有时间笔序等动态信息可以利用，它能处理的基本上是二维点阵图像，同时手 写字体具有因不同人的笔迹而千差万别，笔画各异变动性非常大的特点，在这种 情况下，要想做到高精度的识别难度相对较大。因此根本谈不上轻松识别，而这 也是目前字符识别领域最后一个没有完全攻克的难题。近年来手写识别也出现了 很多新的方法，例如在预处理方面有基于数学形态学的笔划粗细调整和倾斜矫正， 以及置信分析等。在主体处理方面有：b p 网络和s o f m 网络分类器，基于向量基 ( s v m ) 的方法，伪二阶隐马尔可夫模型等等应用。但与目前脱机手写识别文字 应用市场的发展空间相比，大量用户的需求并没有得到充分的满足，例如字符识 别率较低、内存占有率较高等诸多问题都还在困扰着绝大多数的用户，因此脱机 手写识别文字技术还有着极大的发展空间。 我们在脱机手写识别字符领域引进信息粒和粒计算的概念，构建脱机手写识别 字符的特征信息系统。在这个系统中对特征信息粒的提取，特征信息粒的处理，特 别是提出基于信息粒的分类器的模型等几个方面展开分析研究和进行对比实验。 信息粒及其在脱机手写识别中应用的研究 1 2 本文的主要创新点 l 构建脱机手写识别信息粒系统。 2 提出决策规则信息粒属性取值邻域拓展方法。 3 给出g - m a x n e t 全局决策规则网络分类器模型。 4 进行了有效的脱机手写数字识别的实验。 1 3 本文章节划分 本文章节安排如下： 第一章：引言 介绍了本课题的背景、意义，课题来源，并简单介绍了脱机手写识别在国内 外的研究现状，以及本人的主要工作。 第二章：信息粒及粒计算 详细阐述了信息粒及粒计算的研究现状及粒逻辑的研究趋势，提出了从不同 的信息源及不同的背景知识中提取新的信息粒结构模式。使之更加合理，更加有 效地进行粒的快速计算，实现近似推理。 第三章：脱机手写字符识别 简要介绍了脱机手写字符识别的相关理论。 第四章：脱机手写识别信息系统的信息粒处理 构建脱机手写识别信息系统，并在这个特殊的系统进行信息粒处理展开分析 研究 第五章：脱机手写数字识别分类器试验系统 提出g m a x n e t 网络识别分类器并进行脱机手写数字识别分类器实验，在本实 验中对比采用第四章提出的信息粒处理方法进行了验证。 第六章：结束语 本章分析了在整个论文的实施过程中遇到的问题和某些期待完善的内容。 论文最后部分是“致谢”和“参考文献”。 信息粒及其在脱机手写识别中应用的研究 2 1 概述 第二章信息粒及粒计算 信息粒( i n f o r m a t i o ng r a n u l e s ) 是指人类在解决和处理大量复杂信息问题 时，由于人类的能力有限，把大量复杂信息按其各自的特征和性能将其划分成若 干较简单的块，而每个如此划分出来的块被称做一个粒。这种处理信息的过程， 就被称做信息粒( g r a n u l a t i n g ) 。 通过不分明性、相似性、近似性或功能性将信息分成各种不同的粒，被划分 的粒是清晰的还是模糊的，完全依赖于被用来划分的不分明性、相似性、近似性 或功能性关系是否被准确地定义。 描述粒计算的三个英文单词：g r a n u l a r i t y 、g r a n u l e s 和g r a n u l a t i o n 的意义 和区别讨论如下。 “g r a n u l a r i t y ”被解释为“粒度”。这在早期关于粒的研究文献中多是用这 个词，如a l z a d e h 于1 9 7 9 年发表的论文就用这个词n 1 ，也许这是第一篇论述信息 粒的原始论文。就这个词在该文中描述的内容可以看出粒计算是研究被划分的类 或块的大小。s t a n f o r d 大学教授j r h o b s s 于1 9 8 5 年发表于在美国l o sa n g e l e s 举行的国际人工智能联合会议上的论文1 ，直接用这个词作论文题目。我国较早研 究粒计算的学者张钹和张铃于1 9 9 0 年出版的专著也是用“粒度”( g r a n u l a r i t y ) 这个词h 5 1 。从这二文献中描述的内容可以理解粒计算除了研究颗粒的大小外，还 研究不同层次的粒度之间关系，粒的分解和合并等。 “g r a n u l e ”被解释为“基本粒”，是紧紧凝结在一起的“粞”、“颗粒”和 “块”等，近些年都用“i n f o r m a t i o ng r a n u l e s ”这个词。是研究将信息集切割 成互不相交的“片”、“块”等，或划分成互不相交的“子集”、“组”、“类” 和“群”等，实质上是“划分” ( p a r t i t i o n ) 的意义，表示颗粒之间是清晰、互不相交的。可见用这个词研究 粒计算是研究信息划分。 “g r a n u l a t i o n ”被解释为“粒”。就a l z a d e h 于1 9 9 7 年发表的另一篇论 文中用了这个词乜3 。“i n f o r m a t i o ng r a n u l a t i o n ”意思是将信息切割或分成可能 信息粒及其在脱机手写识别中应用的研究 两两有交的“类”和“块”等，他从模糊集观点讨论，所以被分成的粒可能是模糊 的或边缘不清晰的“块”。 所以，粒计算是研究信息分类、被分成的块是两两分离的划分，还是两两可能 有交的模糊分割：研究分成的粒的大小、不同粒度层之间的关系。大的整体粒被分 解成小的以及小的粒合并成大的整体粒等。 粒计算( g r a n u l a rc o m p u t i n g ) 名词来源于t y l i n ，他于1 9 9 6 年在 u c b e r k e l e y 大学z a d e h 的重点实验室做客作教授时，z a d e h 教授要求他做 “g r a n u l a rm a t h e m a t i c s ”，而他提出要作“g r a n u l a rc o m p u t i n g ”的研究。当 时z a d e h 便将“g r a n u l a rm a t h e m a t i c s ”改称“g r a n u l a rc o m p u t i n g ”，并且缩写 成g r c 。所以“粒计算”成为今天的一个热门研究领域，就这个名词而言应归功于 l i n 的贡献乜6 3 。 2 2 粒计算的研究现状 粒计算自z a d e h 发表第一篇论文以来，至今已有2 0 多年的研究历史了。其研 究进展情况大致可分成如下几种观点和方法进行研究。 2 2 1 以模糊集理论、邻域观点研究信息粒 z a d e h 于1 9 7 9 年在他的原始论文中n 1 ，定义信息粒为一个命题：x 的值是以程 度九隶 属于模糊子集g u ，其中x 是u 上的变量，x 的值是u 上的一个实体，写成： g=xi sgi s 九 形式上被记成： g = u e u ：x 的值( v ( x ) = u ，v 是u 上的赋值符号) u 是以程度九隶属于模子 集g u ) 。 很显然，0 九1 。以模糊集的观点，此处的九是模糊隶属函数：而从逻辑的 观点，此处的九是所建立的命题的模糊真值或概率：所以，在这篇文章中，除了定 义模糊粒度外，还讨论了模糊粒度的概率分布及其概率的计算方法。 l i n 于1 9 9 8 年在他发表的论文及其随后的一系列关于粒计算的文章中12 | ，是 以邻域观点、通过二元关系定义了粒。设s = ( u ，a ，v ，f ) 是信息系统，b ：v j u 二元关系，其中u 是所讨论对象的全集，a 是属性集，v 是属性值集，f 是信息函数。 ： 4 信息粒及其在脱机手写识别中应用的研究 用b 定义粒是如下形式： g d 2 u u ：ubp ，p v 显然g d 是清晰还是模糊的，完全取决于二元关系b 的特性。所以，两个二元关 系b 和d ，如果b d ，则按b 将全域划分的粒度比按d 将全域划分的粒度更细，在 这种情况下，也可将不同大小的粒度分成不同粒度层，并在不同层上分别进行各自 的粒计算研究吲。 2 2 2 以逻辑观点研究信息粒的划分以及粒度分解和合并 h o b b s 在他发表的文章中口1 ，讨论了粒度的分解和合并，以及如何得到不同大 小的粒度，因此他提出了产生不同大小粒度的模型，这就是： ( i ) ( f i x ，y ) ( x y ) 三( v p r ) ( p ( x ) 三p ( y ) ) ： ( i i )( v x ，y ) ( x y ) 三lf ( x ) 一f ( y ) l ： ( i i i )( x y ) i f f 对于一个p r ，如果p ( x ) 和p ( y ) 都是可以确定的， 则p ( x ) 三p ( y ) 。 其中r 是所讨论的逻辑公式中出现的全体谓词的集合，f 是出现在所讨论的逻 辑公式中的函数项，是任给定小的正实数。 在上述模型中，公式( i ) 意味着将引导一种具有传递性的不可区分关系“”， 因此可产生整体粒度的粒度层。不过这是一个二阶问题，由于二阶逻辑至今仍是困 难问题，所以h o b s s 的整体粒度模型无法被引用。模型中公式( i 工) 和( i i i ) 将用偏 序谓词引导出具有非传递性的相容关系“”，由此可得到较粗的粒度层上的粒。 由此可见，h o b s s 的这个模型是从逻辑的观点研究不同层次上的粒度，这将对a i 中的问题求解产生影响，引导我们在不同层上找到各个子问题的解。从这个模型或 这篇文献可以看出h o b s s 没有讨论粒度的运算规则，所以研究粒的分解和合并仍 然是不方便的。 2 2 3 以代数格划分信息粒并通过映射研究不同层上粒度之间的关系 我国较早的粒计算研究学者张钹和张铃于1 9 9 0 年出版的专著一书n 1 ，以及随 后发表的论文嫡1 ，是从代数格研究如何产生不同大小的粒度空间，并讨论不同空间 上的粒度之间函数关系。从给定的原始问题空间( x ，f ，f ) ，可找到它的对应的商空 ： 5 信息粒及其在脱机手写识别中应用的研究 间( x ， f ， f ) 。观察当前粒度空间是否可解，以决定是否进入更细粒度的更深 一层粒度空间。随后将不同大小粒度世界上的粒度( 子问题) 的解组合成整体粒 度的解。 h o b s s 和张氏兄弟分别以不同观点和方法产生不同大小的粒度层，其意义都是 在于人们能从极不相同的粒度世界观察和分析同一个问题，并能对此求解，最后归 - n 整体问题的解，这也是a i 中问题求解的宗旨。 y y y a o 对粒计算进行了一系列的研究，而且兴趣广泛。在他诸多论文中 1 3 - 1 7 似乎都是以区间集、代数格和决策逻辑语言来定义粒的划分。用逻辑语言定义一 个基本粒。设s = ( u ，a ) 是信息系统，x u ，如果至少存在一个公式( p l ，其中l 是s 上的决策逻辑语言，使得m ( c p ) = ue u ：ub ( p ) ，表示满足( p 的u 上的元素集 合，则这个集合m ( c p ) 被称做可定义的基本粒：( q ，m ( c p ) ) 被称做紧紧链接在一起的 块，并把它作为公式，讨论了它的可满足性。而把可定义的划分记成p ，即，由p 将 全集u 划分得到的每个等价类都是可定义的粒，则称这个划分p 是可定义的，所有 可定义的划分的集合形成一个划分族兀，( u ) ，它被称做是一个格或半格。在这个格 或半格上，可以讨论分类问题的一般解和特殊解，也就是设7 【1 ，n 2 e 兀p 是一致分 类问题的两个解，如果x l 匠2 则称x ll l n 2 更特殊：反之，兀2 比兀1 更一般。 2 2 4 以包含度、m e r e o l o g y 概念研究粒计算 s k o w r o n 以包含度概念研究粒近似空间上的r o u g h 下近似和上近似，并发表了 一系列的信息粒和粒计算的文章n 8 2 2 l 。设x ，y e u 是u 上的两个子集，x 至少以r 程 度包含于y ，记成x r y ，形式上， r _ c a r d ( x n y ) c a r d ( x ) ，x 囝 i v r ( x ，y ) = 弋 l 1o t h e r w i s e 于是粒近似空间是3 一元组：g a s = ( g s ，g ，t r ) ，其中g s = ( e ，0 ，g ，v ) ，e = ( g l ，g n ) 是基本粒的集合：0 = o l ，0 m ) 是粒运算的集合：g = g 1 ，g h ) 是经0 上的运算 组合e 上的基本粒而得到的组合粒的集合：v ：g g 一 0 ，1 是r o u g h 包含函数，它 被解释为一个粒被包含于另一个粒的程度的量度。 设g = g s l ，g s t ) 是信息粒 6 信息粒及其在脱机手写识别中应用的研究 系统族：t rg f x f 是g 上的二元传递关系。由此，可在粒近似空间g a s 上建立粒关 于t r 的下和上近似集的定义： a p p 哳( a s ，x ，q ) = x e u v ( i ( x )