（模式识别与智能系统专业论文）信息粒度计算模型及其在智能信息处理中的应用研究.pdf

摘要 摘要 人类智能的一个公认特点，就是人们能从极不相同的粒度( g r a n u l a r i t y ) 上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，而且 能够很快地从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种 处理不同粒度世界的能力，正是人类问题求解强有力的表现。 粒度计算( g r a n u l a rc o m p u t i n g ，缩写g r c ) 是信息处理的一种新的观念和计 算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，主要用于处 理不精确的、模糊的、不确定的、部分真实的和海量的信息，它有望成为复杂 系统中信息智能处理的一种有效的、统一的理论框架。 本文首先简要介绍了粒度计算的研究背景与现状，分析讨论了它的研究动 机和现存的一些问题。其次，阐述了粒度计算的基本思想、基本问题、基本概 念和一般方法，内容包括信息粒的构建、表示和计算，信息粒大小( 抽象程度) 的度量、信息粒度的粗细等。在此基础上，详细论述了信息粒度计算的三种主 要模型( 基于粗糙集理论的粒度计算模型、基于模糊集理论的词计算模型、基 于商空间理论的问题求解模型) 中的知识表示、知识约简、知识获取等核心问 题，并获得了一些新的结果，主要有：( 1 ) 从信息粒度着手，重新形式化表示 了粗糙集的基本概念和方法，使之附有语义信息，为粒度计算提供了一个具体 而实用的框架；( 2 ) 讨论了主要模型融合的内在联系和必要性，提出了基于粗 糙集和商空间理论的分层递阶模型来求解复杂问题和处理复杂信息的一般方 案；( 3 ) 从信息熵的观点解释了知识的粒度本质，得出知识粒度越粗，其信息 熵和互信息越小，且逆命题不成立；( 4 ) 分析了嵌套决策粒度的相对核、相对 约简、信息熵、分类质量存在的相互关系，证明了粗决策粒度的一个相对约简 在满足相容性的条件下一定可以扩张成细决策粒度的一个相对约简，反之，细 决策粒度的一个相对约简一定可以缩减为粗决策粒度的一个相对约简；( 5 ) 探 索了粒度计算在决策树剪枝算法和改善人工神经网络性能中的应用；( 6 ) 以信 息粒为基元，利用位表示法，将粒度计算的方法应用到s q l 数据库中数据的智 能处理，设计开发了基于s q l 数据库的知识约简的实验系统。 关键词：粒度计算，粗糙集理论，词计算，商空间理论，信息熵，软计算 a b s t r a c t o n er e c o g n i z e df e a t u r eo fh u m a ni n t e l l i g e n c ei st h a th u m a nb e i n g sc a no b s e r v e a n da n a l y z et h es a m ep r o b l e mf r o mq u i t ed i f f e r e n tg r a n u l a r i t i e s h u m a nb e i n g sc a n n o to n l ys o l v ep r o b l e m so nd i f f e r e n tg r a n u l a r i t i e s ，b u ta l s oj u m pf a s tf r o mo n e g r a n u l a r i t yw o r l dt oa n o t h e rw i t h o u ta n yd i f f i c u l t i e s t h ea b i l i t yo fd e a l i n gw i t h d i f f e r e n tg r a n u l a r i t yw o r l d si sj u s tt h ee x h i b i t i o no f s t r o n gt op r o b l e ms o l v i n g g r a n u l a rc o m p u t i n gi san e wc o n c e p ta n dc o m p u t i n gp a r a d i g mo fi n f o r m a t i o n p r o c e s s i n g , a n dt h a tc o v e r 8a l lt h er e s e a r c ho nt h e o r i e s ，m e t h o d s ，t e c h n i q u e sa n dt o o l s r e l a t e dt og r a n u l e s ，m o r e o v e r , i ti sm a i n l yu s e dt od e a lw i t hi m p r e c i s i o n , f u z z y u n c e r t a i n t y , p a r t i a lt r u t ha n dm a s s i v ei n f o r m a t i o n i ti sh o p e f u lt ob e c o m ea ne f f e c t i v e a n du n i f o r mt h e o r yf r a m e w o r ko fi n f o r m a t i o ni n t e l l i g e n c ep r o c e s s i n gi nc o m p l i c a t e d s y s t e m s f i r s t l y , w eb r i e f l yi n t r o d u c et h eb a c k g r o u n da n dp r e s e n ts i t u a t i o no fr e s e a r c ho n i n f o r m a t i o ng r a n u l a rc o m p u t i n gt h e o r y , a n da n a l y z ei t sr e s e a r c hm o t i v a t i o na sw e l la s s o m ec u r r e n te x i s t i n gp r o b l e m s s e c o n d l y , w ed e s c r i b ei t se s s e n t i a lt h o u g h t , b a s i c i s s u e sa n dc o n c e p t sc t c i ti n c l u d e st h ec o n s t r u c t i o n , r e p r e s e n t a t i o no fi n f o r m a t i o n g r a n u l e sa n dc o m p u t i n gw i t hg r a n u l e s ，t h em e a s u r e m e mo fs i z eo fi n f o r m a t i o n g r a n u l e s ，c o a r s e n e s so fi n f o r m a t i o ng r a n u l e sa n ds o0 1 1 黼a r d s ，w ed e t a i l e d l y d i s c u s st h em a i nm o d e lo fi n f o r m a t i o ng r a n u l ec o m p u t i n gb yt h ea b o v ec o n t e n t , s u c h a s ，t h eg r a n u l a rc o m p u t i n gm o d e lb a s e do nr o u g hs e t st h e o r y , t h ec o m p u t i n gw i t h w o r d sm o d e lb a s e do nf u z z ys e t s ，t h em o d e lo fp r o b l e ms o l v i n gb a s e do nq u o t i e n t s p a c et h e o r y w eh a v es t u d i e dt h ei m p o r t a n ti s s u e si nt h em o d e l s ，f o re x a m p l e ， k n o w l e d g er e p r e s e n t a t i o n , k n o w l e d g er e d u c t i o n , k n o w l e d g ea c q u i s i t i o n , a n do b t a i n e d s o m en e wr e s u l t s t h er e s u l t sm o s t l yi n c l u d et h eb a s i cc o n c e p t sa n da p p r o a c h e so f r o u g hs e t sa l er e f o r m u l a t e di nt e r m so fi n f o r m a t i o ng r a n u l e ss t a n d p o i n ti no r d e rt o g r a n u l e sw i t hs e m a n t i c s ，c o n s e q u e n t l y , i tp r o v i d e sac o n c r e t ea n du s e f u lf r a m e w o r k f o rg r a n u l a rc o m p u t i n g ，a n dt h ei n h e r e n tc o r r e l a t i o n sa n dn e c e s s i t yo ft h em a i n m o d l e ss y n c r e t i z i n gi sd i s c u s s e da n dt h eg e n e r a ls c h e m eo fs o l v i n gc o m p l i c a t e d a b s t r a c t p r o b l e m sa n dp r o c e s s i n gc o m p l i c a t e di n f o r m a t i o ni sp r e s e n t e db a s e do nr o u g h s e t s a n dt h eh i e r a r c h ym o d e lo fq u o t i e n ts p a c et h e o r y , a n dt h ek n o w l e d g ec o a l 锄e s si s i n t e r p r e t e da c c o r d i n g t o v i e w p o i n to fi n f o r m a t i o nt h e o r y , w ec o n c l u d e t h a t i n f o r m a t i o ne n t r o p ya n dm u t u a li n f o r m a t i o nd e c r e a s em o n o t o n o u s l ya sk n o w l e d g e c o a r s e r ，t h ea b o v ei n v e r s er e l a t i o n s h i p sa r cn o tv a l i d , a n dt h er e l a t i o n sa m o n g r e l a t i v ec o r e ，r e l a t i v er e d u c t i o n , i n f o r m a t i o ne n t r o p ya n dc l a s s i f i e dq l l a l i t ya a n a l y z e da n dw ep r o v e t h a tt h er e l a t i v ec o r eo fc o a r s e rd e c i s i o ng r a n u l a r i t ym u s tb ea s u b s e to ft h er e l a t i v ec o l eo fi t sf i n e rd e c i s i o ng r a n u l a r i t y a to n et i m e ，ar e l a t i v e r e d u c t i o no fc o a r s e rd e c i s i o ng r a n u l 嘶t h a ts a t i s f i e sc o n s i s t e n tw i t hi t sf i n e r d e c i s i o ng r a n u l 呻咖e n l a r g ear e l a t i v er e d u c t i o no ft h ef i n e rd e c i s i o ng r a n u l 嘶, i n v e r s e l y , ar e l a t i v er e d u c t i o no ff i n e rd e c i s i o ng r a n u l 狮i ss u r e l yc u ts h o r ta r e d u c t i o no fi t sc o a r s e rd e c i s i o ng r a n u l 嘶 f i n a l l y , w ee x p l o r et h ea p p l i c a t i o no fg r a n u l a rc o m p u t i n gi nd e c i s i o n - m a k i n g t r e ep r u n i n ga l g o r i t h ma n da r t i f i c i a ln e u r a ln e t w o r kp e r f o r m a n c ei m p r o v e m e n t b y i n f o r m a t i o ng r a n u l e sr e g a r d e da sb a s i ce l e m e n t s ，e m p l o y i n gt h eb i tr e p r e s e n t a t i o na n d t h eg r a n u l a rc o m p u t i n gm e t h o d s ，w ed e s i g na n di m p l e m e n tae x p e r i m e n ts y s t e mo f k n o w l e d g er e d u c t i o nt od e a lw i t hi n t e l l i g e n t l yd a t ai n f o r m a t i o ni ns q l d a t a b a s e k e yw o r d s ：g r a n u l a rc o m p u t i n g ，r o u g hs e t s ，c o m p u t i n gw i t hw o r d s ，q u o t i e n t s p a c et h e o r y , i n f o r m a t i o ne n t r o p y , s o f tc o m p u t i n g i i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 墨鎏闻 缈莎年乡月多日 椴每名豫私糍： 96 年弓月1 日年 月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：李盏1 罚 卅6 年；月衫日 第1 章引言 第1 章引言 本章首先简要介绍了粒度计算( g r a n u l a rc o m p u t i n g ，缩写g r c ) 的研究背 景与现状，然后分析讨论了它的研究动机和现存的一些问题，最后概述了本文 主要的研究内容和成果，且给出了论文内容的组织结构。 1 1 粒度计算的研究背景、现状与意义 1 1 1 粒度计算的研究背景与现状 二十一世纪是信息的世纪。一方面，计算机和网络信息技术日新月异，使 得人们获取的信息和数据以指数增长的方式急剧膨胀信息爆炸。据国际数据 公司的调查报告显示：1 9 9 3 年，全球信息存储总量约为2 0 0 0 1 1 3 ，2 0 0 0 年接近3 百万t b ，增长了1 5 0 0 多倍，到2 0 0 3 年达到8 0 亿g b ，并且还在以更快的速度 增长，同时，由于人的参与使数据与信息中的不确定性更加显著，信息与数据 中的关系更加复杂( 复杂系统) 。实际上，大型企业的数据库中，仅有约7 的 数据和信息得到较好的利用，最好的也只利用了9 。面对如此可利用的丰富的 数据与信息，而我们人类却陷入了获取知识贫乏的困境，因为目前我们缺乏一 种高效的能够利用计算机及信息技术来帮助人类从中获取有用的信息和知识的 理论与方法。因此，如何处理复杂系统中那些不精确的、模糊的、不完整的和 海量的信息，并从中获取潜在的、新颖的、正确的、有利用价值的知识，这给 人工智能、认知科学、信息论、软计算和智能信息处理等众多学科提出了严峻 的挑战。 另一方面，以有生命行为占主导地位的复杂人文系统，例如经济规划系统、 生活系统、大规模社会系统、城乡规划系统以及生物系统等等，这些系统中的 许多问题无法利用精确计算( 硬计算) 的方法求解，因为硬计算的前提是我们 必须将所解决的问题形式化地表示成微分或积分方程，且目标函数是凸的、高 阶连续可微的及可行域是凸集，事实上这是不可能的。以精确计算方法处理日 益复杂的系统，突出了精确性与复杂性之间的矛盾。z a d e h 在控制论的实践中指 第1 章引言 出“所面对的系统越复杂，人们对它进行有意义的精确化的能力就越低，玎， 当复杂性超过了一定的阈限，模糊性便成为不可忽视的因素了。面对这样的矛 盾，人们思索着在极度复杂性面前从精度方面“后撤 一步。z a d e h 例举的“停 车问题一，引起了许多学者的兴趣。“停车问题 表面上看起来非常简单，但如 果要用精确的方法求解是非常复杂的，即便使用一台大型的计算机也不够用， 然而有经验的汽车司机却可以很快将车开到指定的位置。这是因为司机具有对 事物进行模糊识别和判断的能力。“停车问题 表明，在一些条件下，既使用不 太精确的手段，也可以达到精确的目的。不相容原理表明，随着系统复杂度增 加，对其行为精确而有效的判断力逐渐减弱，直至阈值，使得精确与效用不可 兼得。因此，基于精确计算方法不能有效地处理复杂系统的信息和求解复杂问 题，因为在复杂的系统和问题中，处理的要素是信息粒而非个体( 具体的对象) ， 所以，这些问题的解决有待于对信息粒度计算进行研究。 二十世纪六十年代，美国著名的控制论专家z a d e h 创立了模糊集合论。在 此基础上，他于1 9 7 9 年首次提出并讨论了模糊信息粒度化问题，推动了模糊 逻辑理论及其应用的发展，但在当时未引起足够的重视。接着，在1 9 9 6 年z a d e h 将模糊信息粒化问题扩展为“词计算理论 圆，标志着模糊粒度化理论的诞生。 随后，德国多特蒙德大学的h e l m u tt h i e l e 教授于1 9 9 8 年发表了“词计算理论 的语义模型川3 1 和z a d e h 相继发表的文献h 1 促进了词计算理论的发展。其旨在 解决利用自然语言，进行模糊推理和判断，以实现模糊智能控制。 波兰学者p a w l a k 于1 9 8 2 年提出了粗糙集理论h 羽。由于粗糙集理论具有很 强的定性分析能力，能够有效地表达不精确的或不确定的知识，善于从数据中 获取知识，并能利用不确定、不完整的经验知识进行推理等，因此在知识获取、 机器学习、规则生成、决策分析、智能控制等领域获得了广泛应用，特别是在 数据挖掘领域，获得了巨大成功，业已成为粒度计算研究领域的主要方向之一。 加拿大r e g i n a 大学教授y y y a o 和他的合作者n i n g z h o n g ，y t y a o ，cj l 地y s a i 等人，对粒度计算进行了一系列的研究n “7 】，并将它应用于知识挖掘等领域， 其研究的要点是用决策逻辑语言( d l 一语言) 来描述集合的粒度，建立概念之间的 i f t h e n 规则与粒度集合之间的包含关系的联系，并提出利用由所有划分构成 的格求解一致分类问题。这些研究为知识挖掘提供了一些新的方法和视角。粒 度计算啪1 作为正式的学术术语，首次由tyl i n 命名，该术语最初出自z a d e h 的 文献1 中。后来，tyl i n ，yyy a oa n dz a d e h 又在文献1 中着重描述了粒度 2 第l 章引言 计算的重要性，这激发了人们对它的研究兴趣。随后，大量的关于粒度计算研 究的文献相继发表，它们都是关于粒度计算在人工智能、控制科学和软计算领 域的应用，标志着粒度计算的研究在国际上成为一个研究热点。 t yl i n 在信息粒度计算的结构、表示及应用方面也进行了一系列的研究 嘞捌，主要特点是研究了二元关系( 邻域系统、r o u g h 集和信任函数) 下的粒度 计算模型，讨论了粒度计算中的模糊集和粗糙集方法，同时将粒度计算方法引 入数据挖掘和机器发现领域。 w i t o l dp e d r y c z 在模糊数学和粒度计算等计算智能领域进行了卓有成效的 研究嘲锄】，对粒度计算的方法论、数学框架、信息粒化算法、不同模型下的粒度 世界描述和应用做了总结。 g i o v a n n ac a s t e l l a n o 等人，研究了基于神经网络的学习方法和双聚类算法 对数据信息进行粒化。av a l i s h e v s k y 研究了基于粒度信息的决策以及在不确定 情况下的风险分析。htn g u y e n 等人研究了在知识系统中的粒逻辑方法。lt 。c p o l k o w s k i 和a n d r z e js k o w r e n 等人，则对信息粒的动态处理( 分解、合成) 方 法进行了研究，并讨论了信息粒的一般结构陋7 。此外，对可拓集n 2 1 及其相关研 究，近几年在国内外有了蓬勃的发展，这为粒度计算的深化提供了理论支持。 在国内，张钹院士和张铃教授在研究问题求解时，独立地提出了商空间理 论口3 伽。其利用子集来表示概念，不同粒度的概念就体现为不同粒度的子集，一 簇概念就构成空间的一个划分一一商空间，不同的概念簇就构成不同的商空间。冬 在此基础上，又将模糊集合论引入商空间理论，于2 0 0 3 年提出了模糊商空间理 论盯射。王飞跃在他的文献“词计算和语言动力学系统的计算理论框架中， 提出了建立以词计算为基础，对问题进行动态描述、分析、综合，进而设计、 控制和评估的语言动力学系统。这对于设计和实现能够处理社会、经济、政治、 管理及法律等问题的复杂的智能系统非常必要，代表着复杂系统研究的一个重 要而有意义的方向。刘清在他的专著中阐述了信息粒度及其计算盯7 用1 ，并将粒度 计算的方法成功应用于医疗诊断专家系统m 1 。总的来看，粒度计算的研究在国 内属于起步阶段，尚未引起广泛关注。但我们相信，不久的将来会有越来越多 的计算机领域的学者加入到该领域的研究中来。 3 第l 章引言 1 1 2 粒度计算研究的理论意义和应用价值 z a d e h 指出：“人类认知的三个主要概念分别是粒度( g r a n u l a t i o n ，包括将 全体分解为部分) 、组织( o r g a n i z a t i o n ，组织包括从部分合成为全体) 、因果 ( c a u s a t i o n ，包括因果的关联) ，且认为人类在进行思考、判断、推理时主要 是用语言进行的，而语言本身就是粒度一。如何利用语言进行推理判断，这就要 进行词计算。信息粒度化为词计算提供了前提条件，词计算在信息粒度、语言 变量和约束概念上发展了自己的理论与方法，旨在解决模糊集合论的数值化隶 属度函数表示法的局限性、表达的概念缺乏前后联系、逻辑表达和算子实现的 复杂性等问题，使它们能够更符合人类的思维特点。词计算对模糊智能控制和 因特网上的海量信息资源的高效利用( 如，w e b 语义服务) 有着深远的影响。 智能模拟是获得人工智能、实现智能信息处理的重要途径。人工智能的发 展还有待于进一步理解人类智能的机制。如何有效地描述不同的粒度世界，根 据求解问题的需要选择合适的粒度，实现粒度的合成与分解及不同粒度世界之 间的转换等，并使计算机也具备类似的能力，这对机器智能的发展意义重大。 从哲学的角度看，y a g e r 和f i l e v 指出“人类已经形成了世界就是一个粒度 的观点以及人们观察、度量、定义和推理的实体都是信息粒，在人类的活动中， 粒度无处不在”。复杂系统的粒度化和简单化在问题求解中的必要性或许是人们 研究粒度计算最直接的原因。事实上，由于现代系统日趋复杂，精确求解常常 很难实现，因此，实用的方法就是用足够满意的近似解替代精确解。如果近似 程度不够，则只需在更细的粒度层次上对问题进行分析和求解。 从优化论的角度来看，优化论是软计算科学的核心内容，虽然经典的优化 理论在生产计划与调度、交通运输、商业运作、金融管理等领域的应用有数不 清的成功实例，可随着信息科学的迅猛发展，现代系统越来越复杂、信息系统 常常包含着海量的、不完整、模糊及不精确的数据或对象，常常使得传统的数 学优化方法显得无能为力，例如，运筹学。这是因为传统的优化方法往往要求 目标函数是凸的、高阶连续可微的及可行域是凸集，这很大程度上限制了其适 用范围，而且其处理非确定性信息的能力很差。因此，探寻能够有效处理模糊 的、不完整的、不精确的及海量的信息，且具有智能特征的优化方法成为优化 理论的发展趋势。粒度计算的理论与方法在观念上突破了传统优化思想的束缚， 不再以数学上的精确解为目标，即：需要的是很好地理解和刻画一个问题，而 4 第l 章引言 不是沉溺于那些用处不大的细节信息上，这是观念上的创新，非常有价值。粒 度计算的方法不要求目标函数和约束函数的连续性与凸性，甚至有时连有没有 解析表达式都不要求，而且对计算中数据的不确定性也有很强的适应能力，计 算速度快，这些优点使粒度计算具有更广泛的应用前景，所以，粒度计算理论 的研究对推动优化理论的发展极其重要。 从分治策略的角度看：现实世界的许多复杂问题的求解过程中，常常需要 将问题分解为更小、更易处理的一系列子任务。在这里，粒度计算能够作为处 理上述任务的有效理论工具或模型。 粒度计算在许多领域广泛的应用前景，正是它受到世界各国的研究工作者 重视的一个重要原因。 在专家系统方面，粒度计算有着重要的应用价值。例如，依据血液粘稠度 信息诊断大出血的软件系统d s - b v s 是一个基于粒度计算的专家推理系统。在这 个动态系统中，临床医学专家的经验通过粒度计算的方法转化为数学公式描述 的推理机制，它具有自学习能力，治疗方案的“加、减、调整、更新等都是 在动态过程中完成的。该系统是智能设计的一种创新。通过几千案例测试，结 果证明：该系统比其它相似的诊断系统更高效、更完美，也比临床医生的诊断 准确率高。这显示了它强大的社会服务功效，同时也实现了粒度计算的基本思 想。 在人工神经网络方面：人工神经网络是模拟生物神经网络的计算机智能系 统，也是软计算技术之一乱1 。由于人工神经网络具有信息的分布存储、并行 处理以及自学习能力等优点，所以它在信息处理、模式识别、智能控制等领域 有着难以估量的应用价值。但标准的人工神经网络的不足之处在于( 1 ) 以精确 求解为目标，使神经网络获得全局最优的收敛速度非常缓慢或不收敛，( 2 ) 以 数字形式来表示知识分布，这样的知识非常抽象，令人难以理解。人们称之为 “黑匣子 问题，这很大程度上降低了企业对人工神经网络研究的投资热情， 制约着神经网络的发展，( 3 ) 对实际问题的求解缺乏灵活性。针对上述问题，j ty a o 提出了描述性神经网络d n n 模型眦1 来解决“黑匣子问题。d n n 通过训 练神经网络能够有效地合成提取的规则，用规则蕴含的知识来描述神经网络的 知识分布。它不仅很好地保持了神经网络的非线性性，而且能够很好地解释网 络中的基本的推理机制，已成功应用于金融变化的预测。这在某种程度上突破 了“黑匣子 的瓶颈问题。同时，s c o t td i c k 提出了一种基于语言粒度的人工 第1 章引言 神经网络设计旧1 ，利用标准的神经网络的反向传播算法，用语言的等价值替代 对应的数值，实现了网络连接权的语言描述。在一定程度上降低了神经网络的 计算复杂度和提高了收敛速度，实现了用语言粒度描述知识分布。实验完全表 明了基于粒度计算的神经网络能够很好地学习一个问题，并且克服了标准神经 网络的“瓶颈 ，这为人工神经网络的进一步广泛应用奠定了基础。 在问题求解方面：搜索是人工智能中问题求解的最基本的技术之一。在问 题规模不大时，采用盲目( 宽度、深度) 搜索策略可有效求解问题，但是一个 实际的人工智能系统，它的问题求解空间一般很大，仅靠盲目搜索策略很难奏 效。因此，启发式算法应运而生，其代表为彳算法，然而彳仍未克服计算量的 指数爆炸的困难。后j p e a r 提出了基于商空间模型的统计启发式搜索算法鲥嘲， 它是利用同一层次粒子之间的“统计差异而非“估计精度进行全局判断， 逐层深入直到获得确定的解答。它在一定条件下可以避免“指数爆炸 的问题 且比么算法收敛的条件弱。因为建立在商空间理论基础上的剐算法更接近于人 类问题求解的思维方法，具有全局观、善于学习和总结经验、计算复杂度较低。 无论对求解规模小或大的问题，黝比彳优越，而且求解规模越大，前者的优势 就越大，后尉有许多改进型。基于粒度计算的商空间模型在启发式搜索、路径 规划、时间规划、推理、信息合成和分层递阶技术等方面取得了一定成效。 通过对粒度计算的研究，有利于构建统一的、更加有效的、能够处理复杂 信息系统和问题的理论体系。 1 2 粒度计算研究现存在的问题 粒度计算是处理模糊的、不完整的、不确定的、海量的信息的有效工具。 目前，在粒度计算的研究中仍然存在着很多亟待解决的问题。分析这些存在的 问题有助于粒度计算研究的发展，以下将从几个方面加以说明： ( 1 ) 粒度的多样性：粒度的形成是粒度计算的基础。粒度的形成基于许多 模型，例如模糊集合论、粗糙集理论、商空间理论、区间计算理论嘶1 、影集理 论等，这就导致了多种理论分析以及随之而来的多种不同表示和解释的产生， 增加了理解的难度。如果能为粒度计算建立一个统一的理论框架，不仅可以为 粒度计算的研究提供方便，还有利于促进其应用层面的发展。我们可以探索综 合利用各自理论模型的优点来解决上述问题，如用粗糙集构造论域的粒度，用 6 第l 章引言 模糊集确定粒度的语义解释，借助商空间理论构造出分层递阶粒度结构，以便 求解问题。 ( 2 ) 粒度粗细的准则：粒度的粗细直接影响着问题求解的计算复杂度和效 率。既要避免粒度过粗造成求解失败，也要避免粒度过细造成信息的冗余而导 致求解效率低。所以，关于一般的复杂问题，如何确定出粒度粗细的准则，将 有助于实现粒度计算求解问题的高效性。 ( 3 ) 粒度计算的算法：粒度计算的算法设计是实现粒度计算的核心部分， 它对粒度的推理机制、控制策略、计算复杂性等有重要影响。尽管粒度计算的 各个理论模型中的一些算法在其具体的应用实例上获得了成功，例如，人工智 能的剪枝算法能够快速搜索到问题的解，这是利用了粒度中的信息粒与目标状 态之间关联程度的不同而设计的一种启发式算法。再如，一些诊断疾病和故障 的专家系统，利用粒度的加权算法降低了计算复杂度，而且诊断的正确率较高。 但是，这些方法缺乏通用性。粒度计算的算法设计是一个复杂的问题，迄今为 止，还没有一套较成熟的方法，它是我们丞待解决的难点和重点，也是粒度计 算内容最丰富的部分。我们可以借鉴现有相关理论的算法和根据实际背景设计 出许多种求解不同类型问题所需要的粒度计算的算法，逐步形成一套算法体系， 实现复杂问题的有效解决。 ( 4 ) 词计算理论：基于模糊集合论的词计算模型对因特网上的海量信息资 源的高效利用( 诸如，高质量的语义w e b 服务) 有着深远的影响。词计算理论 的研究刚刚起步，许多的问题还有待探索。面对一个实际问题，如何对论域u 选 择合理的词空间和度量空间，以便构造出好的解决实际问题的粒度计算的模 型? 一方面，我们认为确定一个满足自反性和传递性的关系是关键，要想做到 这一点，最好的办法应该是，先定义粒度的算法规则，再确定合理有效的关系。 另一方面，词计算最初是从数值型开始的，在模糊推理和控制应用中取得成功 且形成了一套比较成熟的公理化体系。毫无疑问，实数模糊粒度对我们构建语 言型词计算模型有很大的指导价值。词计算理论的发展，必将加快语言动力学 系统的实现和强化计算机处理信息的能力，最终实现用语言粒度有效描述、预 测、控制和评估复杂大系统的目的，促进信息科学的发展。 ( 5 ) 粗糙集模型：在基于粗糙集的粒度计算模型中，一个对象是否隶属于 某一集合( 概念) ，不是该元素的客观性质，而是取决于我们对它的了解程度， 同样，集合的相等和包含也没有绝对的意义，也是取决于我们对所研究的问题 7 第1 章引言 中的集合的了解程度，这更符合人类的认知过程，而且在数据挖掘领域获得了 巨大成功。因此，粗糙集理论已成为粒度计算的核心内容之一。但它同样存在 着“瓶颈 问题，诸如，知识表示依赖于论域上的关系；缺乏有效处理现实问 题的代数运算体系；缺乏基本粒度的语义解释；缺乏描述粒度之间结构信息的 方法等。如何从等价关系的泛化、知识表示的拓广、代数结构的延伸三个方面 推广粗糙集理论，建立起与其它理论模型( 如，模糊集、商空间等) 相融合的 “桥梁 将是粒度计算的一个重要研究课题。 ( 6 ) 商空间模型：张钹院士和张铃教授在研究问题求解时，独立地提出了 商空间理论。商空间理论能够很好地反映人类处理不确定问题的若干特点，认 为信息的确定与不确定、概念的清晰与模糊都是相对的，都与问题的粒度有关。 因此，构造合理的分层递阶的粒度结构，可以高效地求解问题和处理信息。另 一方面，商空间理论同样缺少实现粒度与粒度之间、粒度与粒度世界之间、粒 度世界与粒度世界之间转换的手段和技术方法。如果能够探索出有效的技术和 方法来解决这个问题，实现与模糊集和粗糙集理论模型的结合，将会拓宽商空 间的应用范围，极大丰富粒度计算的理论。 总之，粒度计算无论是在智能信息系统的设计和实现上，还是在现实世界 的问题求解上都有非常深远的影响。已有的研究成果表明了粒度计算的丰富性 和灵活性，粒度计算从实际出发，用可行的满意近似解替代精确解，改变了传 统的计算观念，使信息的处理更科学、合理、经济和易操作。它必将会成为信 息处理的一种高效实用的技术和方法，在人工智能、问题求解、知识发现、图 像压缩、神经网络、语义w e b 服务等众多领域有广阔应用前景。它的发展定会 促进信息科学的发展。因此不难相信，随着信息科学的飞速发展，它必将发挥 越来越重要的作用。 1 3 本文的研究目的 ( 1 ) 把粒度计算这种新的理论，用于处理复杂的信息系统，旨在将复杂的 问题粒度化为一系列更小的、更易处理的子问题，以便降低计算的复杂度，从 而为复杂问题的求解提供一条新的有效的途径。 ( 2 ) 从不同的粒度角度能够更好地理解和处理包含不完备、不确定、模糊 和海量数据的信息系统，避免陷入不必要的细节信息中去。对于这样的数据库、 8 第1 章引言 数据仓库和复杂的信息系统，依据粒度计算的主要模型，设计出包含不同粒度 层次的求解方案，进而实现信息的高效处理。 ( 3 ) 粒度计算的思想实质是用简单易求低成本的足够满意近似解替代精确 解，即利用不精确、模糊的、不确定、部分真实的和海量的信息的容错技术实 现智能系统或智能控制的易处理、鲁棒性、低代价和更好地刻画现实世界。 ( 4 ) 从问题求解的方法着手来深入分析及验证这一新的理论，旨在对粒度 计算的理论及实际应用作进一步探索与补充。 1 4 本文研究的主要内容和贡献 为了对本文有一个整体了解，本节首先介绍本文的主要研究内容。然后， 给出本文研究的主要贡献。 1 4 1 主要研究内容 本文的重点是研究分析有效处理不精确的、模糊的、不确定的和海量信息 的粒度计算的理论模型与应用方法，建立基于粗糙集和商空间理论的粒度计算 混合模型，其中还包括粒度语义的广义描述、粒度的构建方法、粒度计算的算 法规则。研究粒度计算在知识获取和智能信息处理等领域的应用方法和技术， 研究开发基于粒度计算模型的知识约简和规则获取的实验系统。 ( 1 ) 粒度计算基本思想、理论、方法和问题的分析研究 在对粒度计算提出的背景、发展、定义、基本概念和各种粒度计算模型系 统分析和深入理解的基础上，提出从内涵和外延两个方面共同对信息粒计算进 行研究和探讨，例如信息粒的构建、表示、语义解释、运算、推理、建模和信 息粒化粗细对知识获取和知识约简的影响。从粒度计算的研究动机着手分析了 对该理论研究的必要性和重要性，从人类智能特征的角度论证了该理论的可行 性，然后结合实际的模型加以探讨；最后给出相应的结论。 ( 2 ) 基于粗糙集理论的粒度计算模型 粗糙集理论( r o u g hs e t s ，缩写r s t ) 是关于不精确、不相容、不完备数据处 理的数学理论，是经典集合论的重要发展，为研究数据库推理提供了理论框架。 粗糙集理论是继神经网络、遗传算法之后发展起来的又一种新颖的软计算方法， 9 第1 章引言 由于它无需提供所处理数据之外的任何先验信息，在智能信息处理研究中发挥 着越来越重要的作用。该理论对不精确、不完整、不确定的真实世界数据的知 识表示、学习、挖掘和归纳等方面的研究提供了有效的处理技术和方法，将我 们带到一个逻辑近似推理和信息处理的新天地。因此，我们从粒度计算的角度， 重新形式化表示了粗糙集的基本概念和方法，这种新的形式化描述使我们能够 精确而简单的定义许多概念，且为粒度计算提供一个具体而实用的框架体系， 业已成为粒度计算的主要模型之一。 ( 3 ) 基于模糊集合论的词计算模型 一般地，客观世界中许多事物的对象的类无法用经典集合论的二值逻辑来 表达，例如动物类无疑是包含鱼、羊、鸟等，不包含矿石、石油和工厂等，而 像海星、细菌等是否隶属于动物是模糊的；再如，所有比1 大得多的整数；漂 亮的女人；高个子等等也同样无法用经典集合来表示。但是，在人工智能、模 式识别、信息传输、认知科学、信息论、软计算和复杂的人文系统等众多领域 中，这种不分明信息粒的定义和运算起着重要的作用。z a d e h 认为“我们进行各 种思考、判断和推理，都离不开信息粒，那么如何表示它们呢? 这就涉及到词 计算 。因此，词计算是粒度计算的核心内容之一。 ( 4 ) 基于商空间理论的问题求解模型 商空间模型是用一个三元组( x ，f ，乃来描述一个问题，其中x 表示论域， ，是属性集，z 是x 上的拓扑结构。在该模型中，论域的一种粒度化就等同于给 定一个等价关系r 或一种划分，于是得到一个对应于r 的商集u r ，对应的三元 组为( i x ，【用，【刀) ，称之为对应于尺的商空间。商空间理论就是研究一簇关系孵 对应的商空间之间的关系、合成、综合、分解和推理，以便将复杂问题表示为 信息粒构建的分层递阶结构的搜索问题，利用“保真或保假原理”来简化复杂 问题的求解。 ( 5 ) 粒度计算的应用探索 研究信息粒度计算在知识约简、人工神经网络和信息智能处理中的应用。 1 4 2 主要贡献 根据上面对本文主要内容的介绍，本文工作的主要贡献表现在如下几个方 面： l o 第1 章引言 ( 1 ) 较系统地讨论了粒度计算这一新理论的研究背景与现状、研究动机、基 本思想、指导原则和基本问题等，阐述了信息粒构建、表示及其运算的 一般方法。对粒度计算的主要模型，例如基于模糊集合论的词计算模型， 基于粗糙集理论的粒度计算模型，基于商空间理论的问题求解模型作了 细致的研究，分析了它们各自的特点以及内在的联系，创建了基于粗糙 集和商空间理论的多层信息粒结构，以便在不同抽象层次的信息粒上讨 论和求解复杂问题，为复杂问题的智能处理提供了一条新途径和方法。 ( 2 ) 从信息粒度计算的观点出发，重新形式化表示了粗糙集的基本概念和方 法，这种新的形式化描述使我们能够精确而简单的定义许多概念，且为 粒度计算提供一个具体而实用的框架体系。在该框架体系下，讨论了信 息粒的简化，并从信息论角度论述了知识的粗糙性本质，得到了一些新 的研究结果。 ( 3 ) 知识约简是粒度计算的核心内容之一，在信息的智能处理中占有十分重 要的地位。本文论证了基于信息粒的方法可以提高知识约简算法的效 率；同时针对人工神经网络现存在的一些不足，提出了利用粒度计算来 改进神经网络的时效性、知识表达的可理解性和增强神经网络的功能。 ( 4 ) 设计了基于粒度计算的一种集成约简算法，将粒度计算方法引入到s q l 数据库中大规模的数据集中数据信息的智能处理，这对于海量信息的智 能处理有一定的应用价值。 c a ) 基于位表示方法，开发了一个知识约筒的实验系统。 1