（计算机应用技术专业论文）集值、动态信息系统中的粒计算研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽邮电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论支作者签名：，司j l 、兰 签字日期 扣7 年岁月扣日 学位论文版权使用授权书 本学位论文作者完全了解重废整电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重废整皇太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：，刁孙兰 签字日期：小竹s 月d 日 导师签名： 调舱 签字日期：2 d t ，7 年歹月2 z 日 点。粒计算在很大程度上模拟了人脑认识和解决问题的过程。其本质思想 是通过选择合适的粒度，来实现寻找问题的一种较好的、近似的解决方案， 从而降低问题求解的复杂度。近年来，粒计算理论发展迅速，现已被广泛 地应用于机器学习、数据挖掘等领域。 人们希望能从不同领域的大量复杂信息中获得自己所需要的知识。信 息系统是承载信息的有效数据组织形式，信息隐含于这种载体之中。由于 现实数据的日趋复杂，导致信息系统也出现了许多新特点，如不完备、集 值、动态等多种复杂形式。人们尝试着寻找各种新的方法来处理这些复杂 信息。本文从粒计算的角度，主要对集值信息系统和动态信息系统进行了 研究和探讨。 首先，分析研究集值信息系统中的相容关系和优势关系，并对这两种 关系作了进一步扩展，提出了基于相容度的相容关系和基于包含度的优势 关系。本文采用覆盖的粒化方法，在不同关系下构建了集值信息系统中的 粒，得到了论域的不同覆盖，同时讨论了集值信息系统中不同层次的粒之 间的关系。通过对相容度和包含度的调节，可以实现知识在不同粒度层次 的转换，进一步丰富了粒计算的理论模型。 其次，本文研究了动态信息系统。目前，基于粒计算理论的知识获取 方法在对静态数据的处理中取得了一系列的研究成果。但是，在实际应用 领域中，数据大多是随时间动态变化的。对动态信息系统的处理，粒计算 还缺乏有效的模型。为此，本文根据粒之间的关系，通过对原知识粒的匹 配、粒子的动态学习和更新等方面的研究，提出了一种基于粒计算的增量 式知识获取算法。仿真实验表明本文提出的算法对动态信息系统的处理是 有效的。 关键字：粒计算，粗糙集，粒子，集值信息系统，动态信息系统，增量式 学习 一 重庆邮电大学硕士论文 a b s t r a c t g r a n u i a rc o m p u t i n g ( g r c ) i san e wc o n c e p ta n dc o m p u t i n gm e t h o du s e d i ni n f 0 r m a t i o np r o c e s s i n g ，w h i c hc o v e r e da l lt h et h e o r i e s ，m e t h o d o l o g i e sa n d t e c h n i q u e so fg r a n u l a r i t y i ti sah o tf e s e a r c ht o p i ci nt h ef i e l d so fa r t i f i c i a l i n t e l l i g e n c e g r a n u l a r c o m p u t i n g s i m u l a t e st h ep r o c e s so fh u m a nh o wt o u n d e r s t a n da n ds o l v et h ep r o b l e m t h ee s s e n c eo fg r a n u l a rc o m p u t i n gi st o f i n dab e t t e rs o l u t i o nb yc h o o s i n gt h em o s ta p p r o p r i a t eg r a n u l a r i t yi no f d e rt o r e d u c et h ec o m p l e x i t yo ft h e p r o b l e m i nr e c e n ty e a r s ，g r ch a sb e e n s u c c e s s f - u l l ya p p l i e di nm a c h i n el e a m i n g ，d a t am i n i n ga n ds o m eo l h e rf i e l d s p e o p l eh o p et h a tt h e yc o u i de x t r a c tm o r eu s e f u lk n o w l e d g ef r o mt h e m a s s i v eo r i g i n a ld a t ai nd i f k r e n tf i e l d s i n f o r m a t i o ns y s t e mi sa ne f f e c t i v e ， f o r mo fo r g a n i z i n gd a t a ，w h e r ep o t e n t i a lu s e f u l i n f o f m a t i o ni su n r e v e a l e d a s t h er e a l i s t i cd a t a s e t sb e c o m em o r ea n dm o r ec o m p l e x ，i n f o r m a t i o ns y s t e m s a p p e a rm u c hm o r en e wc h a r a c t e r i s t i c ss i m u l t a n e o u s i y ，s u c ha si n c o m p l e t e ， s e t v a l u e d ，d y n a m i c ，a n ds of o r t h p e o p l ea t t e m p tt of i n dv a r i o u sn e wm e t h o d s t o p r o c e s s t h e c o m p l i c a t e d i n f o m a t i o n i nt h i s p a p e r ， t h es e t - v a l u e d i n f o r m a t i o ns y s t e m s 觚dd y n a m i ci n f o r m a t i o ns y s t e m sa r es t u d i e df r o mt h e。蟹 v i e 、p o i n to fg r c f i r s t l y ，t w ok i n d so fr e l a t i o n si nt h ec l a s s i c a ls e t v a l u e di n f o r m a t i o n s y s t e m s ，t h et o l e r a n c er e l a t i o na n dt h ed o m i n a n c er e l a t i o n ，a r ea n a l y z e d t h e n ， 、 r em a k ef h r t h e re x t e n s i o n ，at o l e r a n c ef e l a t i o nb a s e do nt h et o l e r a n c ed e g r e e a n dad o m i n a n c er e l a t i o nb a s e do nt h ei n c l u s i o nd e g r e ea r ed e f i n e d b yu s i n g t h ec o v e r i n gg r a i n i n gm e t h o d ，t h eg r a n u l e so fs e t v a l u e di n f o r m a t i o ns y s t e m s a r ec o n s t r u c t e db a s e do nt h ed i f 五e r e n t r e l a t i o n s ， a n dt h e nt h ed i f f c r e n t c o v e r i n go fu n i v e r s i t yi so b t a i n e d h e n c e ，t h er e l a t i o n s h i pa m o n gg r a n u l e l e v e l si ns e t v a l u e di n f o r m a t i o ns y s t e m si sd i s c u s s e d k n o w l e d g ec a nb e c o n v e r t e di nd i f 诧r e n tl e v e l sb ya d j u s t i n gt h et o l e r a n c ed e g r e ea n dt h e i n c l u s i o nd e g r e e ，w h i c he n r i c h e dg r ct h e o r yf h r t h e r s e c o n d l y ，t h ed y n a m i ci n f o r m a t i o ns y s t e mi ss t u d i e di n t h i sp a p e r a s e r i e so fs t u d i e s ，f o rs t a t i cd a t a ，h a v eb e e no b t a i n e do ng r cb a s e dk n o w l e d g e a c q u i s i t i o na l g o r i t h ma tp r e s e n t h o w e v e r ，d a t as e t sc h a n g ew i t ht i m ei nr e a l a p p l i c a t i o nf i e l d s ，b u tt h e r ei sn o e f f c c t i v em o d e l sb a s e d o ng r cf o r p r o c e s s l n gt h ed y n a m i ci n f o r m a t i o n b a s e do nt h er e l a t i o n s h i p so fg r a n u l e s ， t h em a t c ho fo r i g i n a lk n o w l e d g eg r a n u l e s ，t h e d y n a m i cs t u d ya n du p d a t eo f g r a n u l e sa r es t u d i e d a n d t h e n ， a ni n c r e m e n t a l k n o w l e d g ea c q u i s i t i o n a l g o r l t h mb a s e do ng r ci s p r o p o s e d s i m u l a t i o nr e s u l t ss h o wt h a t t h e a l g o r i t h mi sv a l i df o rp r o c e s s i n gt h ed y n a m i ci n f o r m a t i o ns v s t e m s k e yw o r d s ：g r a n u l a rc o m p h t i n g ，r o u 曲s e t s ，g r 粕u l e ，s e t v a l u e di n f o r m a t i o n s y s t e m s ，d y n a m i ci n f o m a t i o ns y s t e m s ，i n c r e m e n t a l l e a r n i n g m 重庆邮电大学硕士论文目录 目录 摘要i a i ， ；i ：r a c t i i 第一章绪论1 1 1 引言1 1 2 粒计算理论的研究发展状况l 1 3 论文的选题背景及主要工作4 1 4 论文组织与结构5 第二章粒计算理论7 2 1 粒计算理论基础7 2 1 1 粒计算的基本概念7 2 1 2 粒计算的主要模型。9 2 2 粗糙集理论基础l l 2 2 1 知识表达信息系统1 l 2 2 2 粗糙集的基本概念1 2 2 3 信息系统的粒化1 3 2 4 基于粒计算的知识获取1 4 2 5 小结17 第三章集值信息系统中的粒计算。1 8 3 1 引言1 8 3 2 集值信息系统中粒的构建。1 9 3 2 1 相容关系和优势关系下粒的表示。1 9 3 2 2 基于相容度的相容关系下粒的表示2 l 3 2 3 基于包含度的优势关系下粒的表示2 2 3 3 集值信息系统中粒之间的关系2 3 3 4 实例分析2 6 3 5 小结2 7 第四章动态信息系统中的粒计算2 9 4 1 引言2 9 v 展，现实数据中出现了许多新特点，对信息分析工具的要求也越来越高， 如何处理这些复杂数据已成为众多研究者所追逐的热点。 当人们在面对复杂的、难于准确把握的问题时，由于能力有限，通常 不是采用系统的、精确的方法去追求问题的最优解，而是通过逐步尝试的 办法达到有限的合理的目标，也就是采用由粗到细、不断求精的多粒度分 析法，避免计算复杂度高的困难，从而获得足够满意的解，使得原来看似 非多项式难解的问题迎刃而解【l 】。粒计算作为一种新的智能信息处理理论， 在很大程度上体现了人类在问题求解过程中的智能，其本质思想是通过选 择合适的粒度，来实现寻找问题的一种较好的、近似的解决方案，从而降 低问题求解的复杂度。它覆盖了所有和粒度相关的理论、方法和技术，主 要用于对不确定、不精确、不完整信息的处理，对大规模海量数据的挖掘 以及对复杂问题的求解。 。 1 2 粒计算理论的研究发展状况 粒计算是一种理论，一套方法学，一种技术，是在处理过程中使用粒 子来描述空间或求解问题的工具，它使得空间描述或问题求解更加可行 粒计算可以说是一把伞，它覆盖了凡是可以用到粒子进行研究的相关领域 【2 1 。尽管在不同粒度层次上对问题求解几乎伴随着人类所有的问题求解， 但粒计算真正作为一个被人们广泛接受与认可的领域，还是经历了一段很 长的时期。 自z a d e hl9 7 9 年发表论文“f u z z ys e t sa n di n f o r m a t i o ng r a n u l a r i t y l j j 以来，研究人员对信息粒度化的思想就产生了浓厚的兴趣。z a d e h 认为很 多领域都存在信息粒的概念，只是在不同领域中的表现形式不同。自动机 刊朋 重庆邮电大学硕士论文第一章绪论 与系统论中的“分解与划分 ，最优控制中的“不确定性，区间分析里 的“区间数运算 ，以及d s 证据理论中的“证据一都与信息粒有密切的 联系。h o b s s 在1 9 8 5 年直接用粒度( g r a n u l a r i t y ) 这个词作为论文题目在美国 l o sa n g e l e s 举行的国际人工智能联合会议上发表论文，讨论了粒的分解和 合并，以及如何得到不同大小的粒，并提出了产生不同大小粒的模型【4 】。 l i n 在l9 8 8 年提出邻域系统并研究了邻域系统与关系数据库之间的关系1 5 】。 1 9 9 6 年，l i n 在u c b e r k e l e y 大学z a d e h 的重点实验室访问时，提出“粒计算修 ( g r a n u l a rc o m p u t i n g ，缩写为g r c ) 的概念。他论述了基于邻域系统的粒计 算在粒结构、粒表示和粒应用等方面的问题，给出了粒计算中的模糊集和 r o u g h 集方法，并将粒计算方法引入数据挖掘和机器发现领域1 6 。9 】。在l i n 的研究基础上，结合粗糙集理论，y a o 探讨了粒计算方法在机器学习、数 据分析、数据挖掘、规则提取、智能数据处理和粒逻辑等方面的应用【l o 。1 4 j 。 y a o 给出了粒计算的三种观点【1 5 】：从哲学的角度看，粒计算是一种结构化 的思想方法；从应用的角度看，粒计算是一种通用的结构化问题求解方法； 从计算的角度看，粒计算是一种结构化信息处理的典型范例方法。这从更 深层次的角度揭示了粒计算的本质。依据人们在解决问题时能从几个不同 的粒度世界去分析和观察同一个问题，并且很容易地从一个粒度世界转到 另一个粒度世界的模型，张钹和张铃在1 9 9 0 年针对复杂问题求解，从仿生 学的观点提出了问题求解理论，建立了一种商结构的形式化体系，给出一 套解决信息融合、启发式搜索、路径规划和推理等问题的理论和算法，并 已有一些相关研究和应用【1 6 ，1 7 】。1 9 9 7 年z a d e h 进一步指出三个基本概念构 成人类认识的基础【2 】：粒化、组织及因果关系。粒化是整体分解为部分； 组织是部分结合为整体；而因果关系则涉及原因与结果间的联系。 随着粒计算研究的发展，近年来国际国内很多学者加入到了粒计算研 究的领域。为了探讨r o u g h 集理论在各种环境下的应用，建立r o u g h 集理论 在各个专业领域中的应用前景，s k o w r o n 【1 3 l9 j 以包含度概念来研究粒近似 空间上的r o u g h 下近似和r o u g h 上近似。刘清【2 0 ，2 1 】提出了粒一逻辑的概念 ( g 一逻辑) ，构造近似推理系统，并将粒计算的方法成功应用于医疗诊断专 家系统。近几年来在掀起粒计算研究的热潮下，商空间理论被人们广泛认 识和推广，2 0 0 3 年张铃和张钹将z a d e h 的模糊概念与商空间理论结合，提 出模糊商空间理论，为粒计算提供了新的数学模型和工具，并把这些理论 和方法应用于数据挖掘等领域【2 2 ，2 3 1 。刘仁金等人【2 4 】提出了图像分割中的商 空间粒度原理和基于粒度合成技术原理的纹理图像分割算法，成功设计出 纹理图像的分割算法。2 0 0 2 年苗夺谦等人【2 5 】对知识的粒度计算进行了探 2 重庆邮电大学硕士论文第一章绪论 讨，引入属性的重要度以及在求最小约简方面的应用，并提出了协调度的 概念以及在构造决策树方面的应用。王国胤等人【2 昏3 0 】提出了基于容差关系 的粒计算模型，使用属性值上的容差关系给出了不完备信息系统的粒表 示、粒运算规则和粒分解算法，同时结合粗糙集中的属性约简问题，提出 了不完备信息系统在粒表示下属性必要性的判定条件，并对粒计算方法在 规则提取方面作了尝试性的应用研究。郑征等【3 l 】提出了相容粒度空间模 型，并将相容粒度空间应用到图像纹理识别中，取得了良好效果。卜东波 等人【3 2 】从信息粒度的角度剖析聚类和分类技术，试图使用信息粒度原理的 框架来统一聚类和分类，指出从信息粒度的观点来看，聚类是在一个统一 的粒度下进行计算，而分类却是在不同的粒度下进行计算，并根据粒度原 理设计了一种新的分类算法，在大规模中文文本分类的应用实践中表明这 种分类算法有较强的泛化能力。z h a n g 等人【3 3 】对粒神经网络进行了探讨， 并在高效知识发现中得到很好的应用。李道国等人【3 4 】在粒计算的基本思想 和理论基础上，研究了基于粒向量空间的人工神经网络模型，在一定程度 上提高了人工神经网络的时效性、知识表达的可理解性。杜伟林等人p 列 根据概念格与粒度划分在概念聚类的过程中都是基于不同层次的概念结 构来进行分类表示，而且粒度划分本身构成一个格结构的特点，研究了概 念格与粒度划分格在概念描述与概念层次转换之间的联系，通过对概念的 分层递阶来进行概念的泛化与例化，使概念在递阶方面忽略不必要的冗余 信息。2 0 0 7 年张文修等【3 6 】从粒计算的观点对人类认知过程作了详细的研 究，从而给出了认知的粒化描述和新的认知模型，该模型较为准确地描述 了人类的认知过程，为研究模拟人类的高级智能、形象思维能力提供了一 种新的便利工具。2 0 0 8 年张清华等【3 7 】讨论了模糊等价关系在任意阈值的情 况下对应的商空间，以及如何在不同阈值对应的商空间之间分层递阶构建 归一化等腰距离函数，得到分层递阶的商空间结构。 近年来，粒计算一直是一个非常活跃的研究领域。它借鉴并拓展了自 然科学和社会科学的很多研究成果，并逐渐形成自己独特的理论。粒计算 起源于人工智能、机器学习与数据挖掘、智能系统、粗糙集、商空间、概 念格、模糊集等领域【3 弘4 2 1 ，从更高层次上对这些结果进行综合分析，强调 对现实世界问题多视角、多层次的理解和描述，从而得到对问题的粒结构 表示。粒计算将结构化思维方式、结构化问题求解方法、结构化信息处理 模式有机地结合在一起，并导出其独特的理论、技术和工具。它的研究对 自然智能、人工智能、问题求解及智能信息系统的设计与实现有着非常重 要的指导意义1 4 瓦4 引。 重庆邮电大学硕士论文 第一章绪论 1 3 论文的选题背景及主要工作 随着计算机及网络的日益普及，丰富的信息与贫乏的知识之间的矛盾 日渐突出。不同领域的人们都希望能从复杂的信息中得到自己所需要的知 识。信息系统是承载信息的一种有效的数据组织方式，信息隐含于这种载 体之中。如何从这种数据表中挖掘出人们感兴趣的知识是基于信息系统进 行计算的一个主要目的。通常，我们所处理的信息系统中属性的值是单一 的并且是确定的，然而这只是一种理想状态，由于现实数据的复杂性，导 致信息系统也出现了许多新特点，如不完备信息系统、集值信息系统、动 态信息系统等多种复杂形式。对于这些问题，已经有很多学者进行了一系 列的研究工作。本论文基于粒计算理论的思想，主要对集值信息系统和动 态信息系统进行了研究和探讨。 集值信息系统与传统意义上的信息系统有所差别，它的属性值由取属 性域中的单个元素扩展到多个元素的集合，即“集值一。现实问题中，“属 性集值 现象广泛出现在应用领域，例如，人们所获取的数据本质上都是 近似值或者属性值缺失【4 5 4 7 】等等，使得属性值必须取集值。从某种意义上 来说集值信息系统可以用来描述完备或不完备的信息系统。对于完备的信 息系统，其每个对象在任意属性上有且仅有一个属性值，是一种特殊的集 值信息系统。对于不完备信息系统的处理【48 4 9 1 ，丢失的属性值可以用该属 性的所有可能取值表示。在集值信息系统中，元素之间的关系是不满足等 价关系的，基于划分的粒计算理论模型不适用于分析处理这类特殊的信息 系统。为此，张文修【5 0 。5 2 】等人在集值信息系统上定义了两种关系：相容关 系和优势关系。本文在此基础上引入相容度和包含度的概念，提出了基于 相容度口的相容关系和基于包含度的优势关系，并采用覆盖的粒化方法， 在不同的关系下分别构建了集值信息系统中的粒，形成了集值信息系统的 多粒层，同时讨论了不同层次的粒之间的关系，将粒的研究扩展到一个更 泛化的关系，得到更一般的粒子，进一步丰富了粒计算的理论模型。 在实际应用领域的数据库中，数据大多是随时间动态变化的。数据是 动态的，知识也应是动态的，当前的知识只能反映当前状态的信息系统， 随着新数据的不断加入，使得原来发现的知识失去效用，这就要求数据挖 掘系统能够对数据的变化做出快速响应，以提供决策支持数据挖掘系统。 由于数据的动态变化使得我们在一段时间后，就要进行知识更新，增量式 知识获取就是在原有学习结果的基础上，快速地对新增数据的学习，而且 得到的知识具有良好的使用效果，使学习的过程更符合人脑的学习过程。 4 重庆邮电大学硕士论文 第一章绪论 对于动态数据环境下的增量式学习方法，人工智能领域的研究者们做了大 量的工作。s c h l i m m e r 和f i s h e r 设计了i d 4 决策树归纳演算法i j ，该算法 可以进行渐进式学习，u t g o f f 在i d 4 算法的基础上设计了i d 5 决策树算法 【5 4 】。王志海等提出了概念格上的渐进式算法【”】。王国胤等提出了并行神经 网络学习算法【5 6 】，刘宗田等提出了基于粗糙集的增量式约简算法1 5 7 】。w a n g 等提出了基于粗糙集的分布式增量约简算法【5 引。2 0 0 3 年王国胤等提出了 基于粗糙集和规则树的增量式规则获取算法1 5 引。2 0 0 7 年杨明提出了一种 基于改进差别矩阵的属性约简增量式更新算法1 6 们。 近几年，基于粒计算理论的知识获取方法已经取得了一系列的研究成 果。2 0 0 2 年，y a o 等提出一种基于粒计算的分类规则模型【1 1 ，l 引。2 0 0 5 年， 王国胤教授等提出了基于粒计算的规则知识获取算法( r g a g c ) 峥l ，6 2 】。2 0 0 6 年，王国胤教授等提出了基于粒计算的自主式知识获取算法1 2 9 1 ，增强了 r g a g c 算法对不一致信息表的处理能力。但这些研究都是针对静态数据 的。如何根据粒之间的关系，建立动态的粒计算模型，实现增量式学习， 从而达到对动态信息系统的处理等问题，目前还没有一种具体的解决方 案。为此本文在动态信息系统中，提出了一种基于粒计算的增量式知识获 取算法，该算法通过对知识粒树的构造，加快了匹配速度，更新策略是基 于粒计算的分类思想，所以规则前件分布均匀。实验结果表明，该算法比 传统的粒计算知识获取算法不仅具有更快的学习速度，而且生成的规则对 样本的正确识别率与传统的粒计算模型知识获取算法相当。同时，该算法 较经典的i d 4 算法无论是规则的质量还是正确识别率都优于i d 4 算法。 本论文工作得到国家自然科学基金州o 6 0 5 7 3 0 6 8 ) 、重庆市教育委员会 科学技术研究项目( k j 0 6 0 5 1 7 ) 的资助，是这些项目整体研究工作中的一部 分。这些项目包含研究粒计算的基础理论和算法，试图用高效的粒计算方 法处理数据挖掘等问题，为智能计算提供新的理论工具和计算方法。 1 4 论文组织与结构 本论文的组织结构如下： 第一章介绍了粒计算理论的研究发展现状，以及本论文的选题背景和 主要工作内容等。 第二章中为了便于后面的叙述，首先对粒计算、粗糙集理论的基本概 念进行了介绍，然后简要回顾了现有的基于粒计算理论的知识获取方法， 5 重庆邮电大学硕士论文 第一章绪论 详细讨论了r g a r c 算法。 第三章研究了集值信息系统，对相容关系和优势关系进行了扩展，提 出了基于相容度口的相容关系和基于包含度的优势关系，并构建了集值 信息系统中的粒，同时讨论了不同层次的粒之间的关系。 第四章在动态信息系统中，提出了基于粒计算的增量式知识获取算 法，实现了对动态数据的处理，并通过仿真实验验证了算法的有效性。 第五章对全文进行总结。 6 重庆邮电大学硕士论文 第二章粒计算理论 第二章粒计算理论 2 1 粒计算理论基础 粒计算是一种描述空间或求解问题的方法，能够在不同粒度下描述空 间或求解问题，使得空间的描述或问题的求解更加可行。它覆盖了所有和 粒度相关的理论、方法和技术，主要用于对不确定、模糊的、不精确、部 分真的和海量信息以及对复杂问题的求解。目前该方向已成为人工智能领 域的研究热点之一，并已取得了大量的理论研究成果1 2 卜4 4 1 ，而且有望成为 复杂系统中智能信息处理的一种有效理论框架。 2 1 1 粒计算的基本概念 不同的领域以不同的形式在不同程度上都体现了粒计算的基本思想， 给出一个毫无争议的粒计算的定义是困难的。然而，依然可以从这些不同 的粒计算模型中抽取出一些共性的东西。下面将从粒计算的基本组成元素 以及粒计算的基本问题两个方面进行论述。 粒计算的组成元素包括粒、粒层及粒结构。粒是构成粒计算模型的最 基本元素【6 3 1 ，是求解问题的最基本单位。一个粒可以被解释为由许多小颗 粒构成的一个大个体，或者理解为由或难以区分、或很相似、或接近、或 因某种功能而结合在一起的一个团。粒具有双重身份，既可以是某个整体 相对独立的一个部分，又可以被看作是由其他一些粒组成的整体。粒存在 于特定的层次中，按照某个实际需求的粒化准则得到的所有粒子的全体构 成一个粒层，人们在粒计算的不同层次中研究不同类型的粒，同一层的粒 子内部往往具有相同的某种性质或功能。一个粒化准则对应一个粒层，不 同的粒化准则对应多个粒层，所有粒层之间的相互联系构成一个关系结 构，称为粒结构【1 3 1 。粒结构给出了一个系统或者问题的结构化描述。它反 应了人们从不同角度、不同侧面来观察问题、理解问题、求解问题。粒结 构的形式包括【4 3 】：直线型、树型和网络型，如图2 1 所示。图中的圆形表 示粒；同一个高度的粒形成一个层；一个多分层结构是对一个问题系统的、 近似的描述。对于同一个系统或者同一个问题，许多解释和描述可能是同 时存在的。所以，粒结构需要被模型化为多种层次结构，以及在一个层次 7 图2 1 粒结构的形式 目前，粒计算中存在两个最基本的问题，即粒化和粒的计算。前者处 理粒的形成、表示和解释，后者处理问题求解方面粒计算的应用。 粒化是问题求解空间的一个构造性过程，它可以简单理解为在给定粒 化准则下得到一个粒层的过程，是粒计算基础单元的构建，包括粒子、粒 视图、粒网和层次结构。在不同的粒化准则下就得到多个粒层，进而得到 粒层的网络结构。通常的粒化方法有自顶而下通过分解粗粒子得到细粒子 的方法，和自底向上将细粒子通过合并得到粗粒子的方法。粒化过程是粒 计算的必要过程。问题空间的粒化过程主要涉及粒化准则、粒化算法( 方 法) 、粒子和粒结构的表示( 描述) 以及粒子和粒结构的定性( 定量) 描述等问 题【6 3 1 。粒化准则主要是语义方面的问题，解决为什么两个对象能放进同一 个粒子内的问题。它是根据实际问题求解的具体需求和具体精度要求得到 的。粒化准则的一个基本要求是忽略掉那些无关紧要的细节，从而达到降 低问题求解复杂度的目的。粒化方法面对实际问题，回答如何对问题空间 进行粒化，采用什么算法或工具实现粒层的构造，它属于算法方面的问题。 粒子的结构描述主要是用粒化方法得到的粒子，如何用形式化的语言表述 出来，以便后面进行计算。粒子和粒结构的定性，定量描述主要指粒子和粒 结构的大小和复杂性度量。 以粒子为运算对象进行问题的求解或推理，是狭义的粒计算。粒计算 可以通过系统访问粒结构来解决问题，包括在层次结构中向上和向下两个 方向的交互，以及在统一层次内的移动。主要分为两种【6 3 】：同一粒层上粒 子之间相互转换和推理，不同粒层上粒子之间的转换或推理。不同粒层之 间的联系可以由映射来表示，在不同粒层上同一问题以不同的粒度、不同 的细节表示，粒层之间的映射就建立了同一问题的不同细节描述之间的关 系。粒计算的主要特点是同一问题的解可以在不同粒层之间自由转化。正 是基于这一点，人们才能用粒计算方法高效地实现复杂问题的求解。在转 化的过程中，问题求解的重要性质必须能在不同粒层上表现出来，这也是 评价粒化方法好坏的一个重要指标。如果在粒化后粒层之间的相互转化过 程中，某些重要属性不能体现出来，这不但不利于问题的求解，反而会导 8 卅憎 重庆邮电大学硕士论文第二章粒计算理论 致问题求解过程发散，从而增加问题求解的复杂度。 2 1 2 粒计算的主要模型 近年来，粒计算模型的种类层出不穷，粒计算的快速发展和广泛应用 与其模型的不断完善是不无关系的。粒计算模型可以简单地分为模糊的粒 计算模型和分明的粒计算模型，前者以词计算理论为代表，而后者以粗糙 集理论和商空间理论为代表，这三种模型都是在集合论这个大的框架下讨 论粒计算的，即它们都把粒看作是论域的子集。下面介绍这三种主要的理 论模型。 ( 1 ) 词计算理论 z a d e h 提出的基于模糊集合论的词计算模型f 2 ， j ，粒在一般约束的概念 下被构建和定义。z a d e h 认为人类在进行思考、判断、推理时主要是用语 言进行的，而语言是一个很粗的粒，如何利用语言进行推理判断，这需要 由词计算来完成。词计算是用词语代替数进行计算及推理的方法u7 1 。信息 粒化为词计算提供了前提条件，词计算在信息粒度、语言变量和约束概念 上产生了自己的理论与方法。以模糊集合表示一个粒，表示知识的粒子用 一个。词一( 即模糊子集) 来表示，不同程度的知识可以通过不同的程度词 进行刻画。词计算的一般形式化模型如下：矿x 括厂l 彳，抛拧】，括吒b 。它描述 的是如果石被彳约束，则y 被曰约束。其中x ，l r 为论域u 上的变量，和厂， 是用来确定约束形式的索引变量，主要有等式约束、可能约束、真实约束、 概率约束、概率值约束、随机集约束、模糊图约束等。通过这些约束来定 义模糊粒：g = f x i x 豇，r l ，根据约束的不同可得到不同类型的粒。再利用 自然语言对粒进行标记，从而建立了词计算的理论基础。由于自然语言表 示的命题包含的信息过于复杂，如果只用简单的、非模糊的约束方式来表 达命题，无法完整地表达其完整语义，所以需要这些更为详细的广义约束。 广义约束为概念的模糊粒的分类提供了基础。在模糊信息粒化理论中，粒 的类型由定义它的约束类型来确定，主要有：可能粒、真实粒、概率粒和 广义粒。 基于词计算理论的推理、决策和识别方式是最贴近人类的思维形式来 求解问题，对复杂系统的信息处理有着广阔的应用前景。在解决利用自然 语言进行模糊推理判断，实现模糊控制【6 4 1 ，以及在语言动力学系统【6 5 】和医 疗诊断等应用领域已经获得了一些成功。 ( 2 ) 粗糙集理论 9 重庆邮电大学硕士论文 第二章粒计算理论 波兰学者p a w l a k 【3 8 】在二十世纪八十年代提出了粗糙集理论。粗糙集理 论主要解决信息粒的近似方面的问题。它把知识看作是关于论域的划分， 以某种等价关系对论域进行划分，每个划分块是一个粒，对于任意一个集 合，可以用这些粒的组合从两个方面逼近该集合，给该集合一个近似描述。 给定集合u 上的一个划分等价于在u 上给定一个等价关系尺。u r 表示u 上由r 导出的所有等价类，【x 】露表示包含元素x 的等价类，其中x u 。 p a w l a k 称之为在论域上给定了一个知识基( u ，r ) ，然后讨论一个一般的概 念x ( u 中的一个子集) 如何用知识基中的知识来表示。对那些无法用( u ，r ) 中的集合的并来表示的集合，借用拓扑中的内核和闭包的概念，引入下近 似和上近似的概念：足= 缸卅田和f ( 嗣= 缸卅他囝。下近似 足( x ) 是x 的子集的所有等价粒的集合，相当于x 的内核。上近似r 一( x ) 是 同x 的交集不为空集的所有等价粒的集合，相当于x 的闭包。 戤= f 一足称为x 的天边界域，集合只舳= 足称为x 的尺正域， 集合朋粥膏( x ) = u 一天一( x ) 为x 的r 负域。当足( x ) r 一( 柳时，就称工为粗 糙集，从而创立了。粗糙集理论一。 粗糙集理论无需提供问题所需处理的数据集合之外的任何先验信息， 对问题的不确定性的描述或处理是比较客观的。目前粗糙集理论已被广泛 应用于神经网络、数据挖掘、系统分析、二元粒算法等领域。 ( 3 ) 商空间理论 张钹和张铃在研究问题求解时，提出了商空间理论【1 4 ，2 2 1 ，他们指出“人 类智能的公认特点，就是人们能从极不相同的粒度上观察和分析同一问 题。人们不仅能在不同粒度的世界上进行问题求解，而且能够很快地从一 个粒度世界跳到另一个粒度的世界，往返自如，毫无困难。这种处理不同 世界的能力，正是人类问题求解的强有力的表现。斗商空间理论就是基于 上述逻辑出发点、借助于数学上的商结构而得到的。商空间理论把概念用 子集表示，不同粒的概念体现为不同粒的子集，一簇概念构成空间的一个 划分一商空间，不同的概念簇就构成不同的商空间。粒计算就是研究在给 定知识基上的各种子集合之间的关系和转换，以及对同一问题取不同的适 当的粒，在对不同的粒的研究中，综合获取对原问题的解。商空间理论模 型可用一个三元组来表示，即( x ，f ，r ) 。其中，x 是论域，f 是属性集，r 是x 上的拓扑结构，指论域中各元素的相互关系。当取粗粒度时，即给定 一个等价关系尺( 或说一个划分) ，得到一个对应于r 的商集( 记为【x 】) ，它 对应于三元组( 【x 】，【用，【明) ，称之为对应于j j c 的商空间。商空间理论就 是研究各商空间之间的关系、各商空间的合成、分解和在商空间中的推理。 l o j 重庆邮电大学硕士论文 第二章粒计算理论 在这个模型下，所有的商空间必须满足两个重要的性质：“保假原理 和 “保真原理一。所谓“保假原理 是指若一个命题在粗粒度空间中是假 的，则该命题在比它细的商空间中也一定为假。所谓“保真原理一，是指 若一个命题在两个较粗粒度的商空间中是真的，则( 在一定条件下) 在其合 成的商空间中对应的问题也是真的。这两个原理在商空间模型的推理中起 到了很重要的作用。在此基础上建立了“粒度世界模型一以及一整套理论 和相应的算法，并将其应用于启发式搜索、路径规划等方面，取得一定成 效。商空间理论在系统性能分析、数据库、模式识别、图像处理【2 4 】等领域 中获得了成功。 上述的三个模型是主要的粒计算模型。在这三个模型的基础上，人们 提出了很多新的模型，如基于划分的粒计算模型【l 们，基于相容关系的粒计 算模型【2 6 ，2 7 1 ，基于概念格的粒计算模型【3 5 1 和基于覆盖的粒计算模型【6 6 】等。 关于粒计算的准确定义，国际上并没有一致的意见或统一的模型，现有的 理论都是从具体的模型和方法来研究粒计算，并没有对其进行总结概括。 如今，从大量的研究中抽象出粒计算的一般理论而不受具体模型的限制已 成为一项迫切的任务。 2 2 粗糙集理论基础 粗糙集【3 8 】是一种处理不精确、不相容和不完备数据的新型数学工具。 这一理论以新的视角出发对知识进行了定义，它把知识看成是关于论域的 划分，从而使知识具有粒度，知识的这种颗粒状结构是通过等价类来表示 的。正是由于知识的这种颗粒状，导致了知识表示的粗糙性。粗糙集是一 个特别的粒计算理论【4 3 j ，它的很多应用都可以看作是关于粒进行计算和推 理的具体体现。粗糙集的创立和发展为粒计算的研究提供了理论基础和应 用模型，大大地影响和推动了粒计算的研究和发展。 2 2 1 知识表达信息系统 知识是对事物运动状态及变化规律的概括性描述，具有抽象性和普遍 性。知识由信息经过加工处理、解释、挑选和改造而形成。信息系统是承 载信息的一种有效数据组织方式，信息隐含于这种载体之中。如何从信息 系统中抽取出知识是基于信息系统进行计算的一个主要目的。 重庆邮电大学硕士论文第二章粒计算理论 信息系统，又称信息表，可以用二维数据表格来表示。表格的行对应 论域中的对象，列对应描述对象的属性。一个对象的全部信息通过该对象 所对应行中各属性来描述。 定义2 1 称四元组s = 为信息系统，其中u 是论域，是对象 的非空有限集合，即u = 西，而，矗 ；彳= 口i ，口2 ， 是属性的非空有限集 合；y = u 圪是属性值的集合，圪表示属性口彳的属性值范围，即属性口的 “一 值域；，：u 么呻y 是一个信息函数，它指定u 中每一个对象x 的属性值。 定义2 2 称s u ，彳，以厂 为决策信息系统，若么= c u d 是属性集合， 子集c 和d 分别称为条件属性集和决策属性集，c n d = f 2 j 且d 1 2 i 。 在本文以后章节的讨论中，我们主要考虑决策信息系统。 2 2 2 粗糙集的基本概念 粗糙集理论中对知识进行表达和处理的基本工具就是信息系统。其形 式化定义为：给定一组数据( 集合) u 和等价关系集合天，在等价关系集合太 下对