（计算机软件与理论专业论文）基于粗糙集和粒度计算的不确定信息度量及知识约简研究.pdf

摘要 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方 法、技术和工具的研究，它是词计算理论、粗糙集理论、商空间理论、区间计算等的超 集，也是软计算的一个重要分支，它已成为模糊的、不完备的、不精确的及海量的信息 处理的重要工具和人工智能领域研究的热点之一。 自波兰学者p a w l a k 于1 9 8 2 年提出了粗糙集理论以来，由于粗糙集理论具有很强的 定性分析能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并 能利用不确定、不完整的经验知识进行推理等，因此在知识获取、机器学习、规则生成、 决策分析、智能控制等领域获得了广泛应用，特别是在数据挖掘领域获得了巨大成功， 业已成为粒度计算研究领域的主要方向之一。 本文跟踪国际学术前沿，在粗糙集和粒度计算理论框架下，对不确定信息处理及其 度量理论与知识约简方法进行了深入的研究。为了度量信息系统中属性重要性，本文从 知识粗糙性的粒度原理和经典的知识粒度及信息熵理论出发，对经典的知识粒度及信息 熵理论进行推广，给出了信息系统中知识的粒度和粒度熵原理，揭示了知识粒度和粒度 熵原理的本质和关系，为进一步研究知识的粒度计算提供了理论基础；为了度量信息系 统中属性相关性，本文借鉴集合论中对称差的概念，从粒度计算的观点出发，给出了信 息系统中知识距离的概念，分析了其相关性质，并指出利用知识距离也可以度量属性的 相关性，同时又给出了知识贴近度的概念，并分析了它与知识距离的关系；针对信息系 统中的知识约简，本文分别提出了一种基于知识粒度的属性约简算法和一种基于知识距 离的属性约简算法，这些算法针对现有知识约简算法【6 8 。7 0 】中存在的不完备性问题做了改 进，且这两个算法都不需求核，对无核的这种特殊信息系统计算约简更加有效，同时它 们的算法时间复杂度也分别较文献 6 8 】和文献 6 9 ，7 0 】中的算法时间复杂度有所降低。 关键词：粗糙集，粒度计算，不确定信息度量，知识约简，知识粒度，知识距离 a bs t r a c t g r a n u l a rc o m p u t i n gi sa l le r n e 曙i n gc o n c e p t u a la 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 np r o c e s s i n g j u s t 笛ag r e a tu m b r e l l a , i tm a yb er e g a r d e d 豁al a b e lo f t h e o r i e s ，m e t h o d o l o g i e s , t e c h n i q u e sa n dt o o l st h a t m a k eu s eo fg r a n u l e s ，i e ，g r o u p s ，c l a s s e s ，o rc l u s t e r so fau n i v e r s e ”g r c ”i sas u p e r s e to f t h et h e o 巧o f f u z z yi n f o r m a t i o ng r a n u l a t i o n , r o u g hs e tt h e o r y , t h et h e o r yo fq u o t i e n ts p a c ea n di n t e r v a lc o m p u t i n ge t c ， w h i c hi sab r a n c ho fs o f tc o m p u t i n gs c i e n c e i tp l a y sa ni m p o r t a n tr o l ei ni n f o r m a t i o np r o c e s s i n gf o r 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 du n n u m b e r e da n db e c o m e so n eo f t h em a i ns t u d ys t r e a mi nt h ef i e l do f a n i f i c i a l i n t e l l i g e n c e t h er o u g hs e tt h e o r yp r o p o s e db yp r o f e s s o rz p a w l a ki n19 8 2 ，h a sb e e na p p l i e d t om a n yf i e l d s i ti sa m a t h e m a t i c st o o li np r o c e s s i n gi n a c c u r a t e , i n c o n s i s t e n ta n d i n c o m p l e t ep r o b l e m s w h i c hc 锄f i n dm e i m p l i c i tk n o w l e d g ea n dp o t e n t i a lr e g u l a t i o n sb yd i r e c t l ya n a l y z i n ga n d d e d u c i n gt h ed a t aw i t h o u ta n yp r i o r i n f o r m a t i o ne x c e p tt h ed a t as e t s i n c et h ee n do f1 9 8 0 s ，t h et h e o r ya n da p p l i c a t i o n so f r o u g hs e tg r a d u a l l y h a v eb e c o m et h ef o c u so fi n t e l l e c t u a li n f o r m a t i o n p r o c e s s i n g ，a n du s e di nt h ef i e l d so fd a t am i n i n g ， m a c h i n el e a r n i n g ，p a t t e mr e c o g n i t i o na n dd e c i s i o n a n a l y s i s ，e t c b a s e do nr o u g hs e tt h e o r ya n dg r a n u l a rc o m p u t i n g , t r a c k i n gt h ei n t e r n a t i o n a lr e s e a r c h s t a t u s ，u s i n gf o r r e f e r e n c es o m ek n o w nt h e o r yf r u i t s ，t h ep a p e re s t a b l i s h e ss o m eb a s i ct h e o r i e s 柚dm e m o d so fu n c e r t a i n i n f o r m a t i o np r o c e s s i n ga n dk n o w l e d g er e d u c t i o n i no r d e rt om e 邪u r et h es i g n i f i c a n c eo f m ea t t r i b u t e si i l t h ei n f o r m a t i o ns y s t e m ，t h i sp a p e rr e f e r st h eg r a n u l a r i t yp r i n c i p l eo ft h ek n o w l e d g er o u g h n e s sa n dt h e c l a s s i c a lk n o w l e d g eg r a n u l a r i t ya n dt h ei n f o r m a t i o ne n t r o p yt h e o r y , c a r r i e so nt h e g e n e r a l i z a t i o nt ot h e c l a s s i c a lk n o w l e d g e g r a n u l a r i t ya n dt h ei n f o r m a t i o ne n t r o p yt h e o r y , s t u d i e so nt h ek n o w l e d g eg r a n u l a r i t y p r i n c i p l ei nt h ei n f o r m a t i o ns y s t e m ，r e v e a l st h ee s s e n c ea n dr e l a t i o n sb e t w e e nt h ek n o w l e d g eg r a n u l a r i t y a n dt h eg r a n u l a r i t ye n t r o p yp r i n c i p l e t h e s ea c h i e v e dr e s u l t s p r o v i d et h er a t i o n a l et of u r t h e rs t u d yt h e g r a n u l a rc o m p u t i n go ft h ek n o w l e d g e i no r d e rt om e a s u r et h er e l e v a n c eo ft h ea t t r i b u t e si nt h ei n f o m l a t i o n s y s t e m , t h i sp a p e rr e f e r st h ec o n c e p to f t h es y m m e t r i cd i f f e r e n c eo fs e t s ，f r o mt h ev i e w p o i n to ft h eg r a n u i a r c o m p u t i n g ，d e f i n e st h ec o n c e p to ft h ek n o w l e d g ed i s t a n c ei nt h ei n f o r m a t i o ns y s t e ma n da n a l y z e si t s p r o p e r t i e s ，a n dp o i n t so u tt h a tt h ek n o w l e d g ed i s t a n c em a ya l s om e a s u r et h ea t t r i b u t er e l e v a r l c e w h i l ei t a l s og i v e st h ec o n c e p to ft h ek n o v 、l e d g ec l o s e n e s s ，a n da n a l y z e st h er e l a t i o n sb e t w e e ni ta n dt h ek n o w l e d g e d i s t a n c e i no r d e rt ok n o w l e d g er e d u c t i o ni ni n f o r m a t i o ns y s t e m t h i sp a p e rg i v e s ak i n do fa t t r i b u t e i l l r e d u c t i o na l g o r i t h mb a s e do nt h ek n o w l e d g eg r a n u l a r i t ya n dak i n do fa t t r i b u t er e d u c t i o na l g o r i t h mb a s e d o nt h ek n o w l e d g ed i s t a n c e ，t h e s ea l g o r i t h m sm a k e st h en o n - c o m p l e t eq u e s t i o nw h i c he x i s t e di nv i e wo f e x i s t i n gk n o w l e d g er e d u c t i o na l g o r i t h m si m p r o v e m o r e ，t h e s ea l g o r i t h m sa l ee f f e c t i v en o to n l yt ot h e i n f o r m a t i o ns y s t e mw i t h c o r e ，a n de s p e c i a l l ye f f e c t i v e t ot h ei n f o r m a t i o n s y s t e mw i t h o u t c o r e s i m u l t a n e o u s l y , t h et i m ec o m p l e x i t yo ft h e s ea l g o r i t h m sh a sb e e nr e d u c e db yc o m p a r i n gt ot h et i m e c o m p l e x i t yo f t h ea l g o r i t h m si nt h el i t e r a t u r e 6 8 】a n dt h el i t e r a t u r e 【6 9 ，7 0 k e yw o r d s ：r o u g hs e t , g r a n u l a rc o m p u t i n g ，i n f o r m a t i o ns y s t e m , u n c e r t a i ni n f o r m a t i o n m e a s u r e ， 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 eg r a n u l a r i t y , k n o w l e d g ed i s t a n c e i v 独创性声明和论文使用的授权说明 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写的研究成果，也不包含为获得河南师范大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：叠鲢趑日期：塑：业 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河南师 范大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 签名：杰晕盐鲴刍导师签名： 堑釜幺型蔓日期： 弘口号，6 ，f 多 第一章绪论 第一章绪论 1 1 研究背景及意义 1 1 1 粗糙集和粒度计算的研究背景和现状分析 ( 1 ) 粗糙集的研究背景 粗糙集理论( r o u g hs e t _ 简称r s ) 是1 9 8 2 年由波兰华沙理工大学z p a w l a k 教授等人 提出的一种数学工具，已经经历了二十几年的发展。它是在集合论基础上发展起来的， 能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知 识，揭示潜在的规律。19 9 1 年z p a w l a k 出版了专著r o u g h s e t s - - t h e o r e t i e a la s p e c to f r e a s o n i n ga b o u td a t a ) ) i l j ，系统全面地阐述了r s 理论，奠定了严密的数学基础。该书 与1 9 9 2 年出版的l 峪理论应用专集较好地总结了这一时期r s 理论与实践的研究成果， 促进了它的进一步发展，现已成为学习和应用r s 理论的重要文献。 从1 9 9 2 年至今，每年都召开以粗糙集为主题的国际会议，推动了粗糙集理论的拓 展和应用。国际上成立了粗糙集学术研究会，参加的成员来自波兰、美国、加拿大、日 本、挪威、俄罗斯、乌克兰和印度等国家。目前，粗糙集理论己成为人工智能领域中一 个较新的学术热点，引起了越来越多的科研人员的关注。 国内粗糙集的研究始于1 9 9 4 年，刘清、曾黄麟、王珏、王国胤、苗夺谦等人在将 粗糙集理论引入我国方面作出了重要的贡献，现在已有许多高校和科研院所的专家、学 者对粗糙集的理论和应用进行一系列的研究，并取得了令人鼓舞的成果。刘清等探讨了 粗糙集在近似推理、模态逻辑和智能代理方面的理论研究情况；张文修、梁吉业、吴伟 志等人提出了基于随机集的粗糙集模型，并研究了粗糙集理论同包含度理论之间的关 系；马志锋、邢汉承等在粗糙控制方面作了深入的研究。 从2 0 0 1 年开始，我国也召开了每年一次的关于粗糙集理论研究方面的研讨会。2 0 0 1 年5 月第一届中国粗糙集与软计算学术研讨会( c r s s c 2 0 0 1 ) 在重庆邮电学院举行，本次 研讨会就粗糙集与软计算、知识发现、数据挖掘、智能信息系统以及非常规计算模型的 综合与分析等研究领域之问的关系进行了激烈的讨论，以后每年都有举办。同时，为了 加强与粒度计算的融合方面的探讨，从2 0 0 7 年开始召开中国羊h 糙集与软计算、中国w e b 本研究得到河南省自然科学壤台j h ( 0 5 1 1 0 1 1 5 【) o ) 和河南省高校新世纪优秀人才。支持计划( 2 0 0 6 乩气n c e l 二1 9 ) 资助。 基于粗糙集和粒度计算的不确定信息度量及知识约简研究 智能、中国粒计算联合会议( 简称c r s s c c w i c g r c ) 。 ( 2 ) 粗糙集的研究现状 目前，粗糙集的理论研究主要集中以下几个方面：粗糙集理论数学性质方面的研究 主要是对粗糙集理论中知识的不确定性问题进行理论研究，包括讨论粗糙集代数结构、 拓扑结构和粗糙逻辑以及粗糙集的收敛性等问题；粗糙集理论模型拓展方面的研究包括 可变精度模型( v p r s ) 、相似模型 s d 和连续属性离散化模型；粗糙集理论有效性算法 方面的研究主要集中于导出规则的增量式算法、约简的启发式算法、并行算法和大数据 集中的粗糙集计算实现四个方面。 粗糙集理论数学性质方面的研究 粗糙集理论数学性质方面的研究主要是对粗糙集理论中知识的不确定性问题进行 理论研究，包括讨论粗糙集代数结构【2 】、拓扑结构吲和粗糙逻辑【4 ，5 1 以及粗糙集的收敛性 等问题【6 】。对粗糙集理论的研究不断深入，它与其他数学分支的联系也更加显得紧密。 例如，从算子的观点看粗糙集理论，与之关系比较紧密的有拓扑空间、数理逻辑、模态 逻辑、格与布尔代数、算子代数等：从构造性和集合的观点看，它与概率论、模糊数学、 证据理论、图论、信息理论等联系较为密切。粗糙集的理论研究需要以这些理论作为基 础，同时也相应地带动了这些理论的发展【7 ，8 】。 纯数学理论与粗糙集理论结合的研究导致了新的数学概念的出现，例如，“粗糙逻 辑 、“粗糙理想 和“粗糙半群”等等。随着粗糙结构与代数结构、拓扑结构、序结构 等各种结构的不断整合，必将推动粗糙集理论的快速发展。 粗糙集理论模型拓展方面的研究 。 粗糙集理论模型拓展方面的研究包括可变精度模型( v p r s ：v a r i a b l ep r e c i s i o nr o u g h s e t s ) 、相似模型( r s t ：b a s e do ns i r n i l a r i t ) ，r e l m i o n ) 和连续属性离散化模型，主要解决粗 糙集理论应用于数据分析时，遇到数据噪声、数据不完备和连续数据离散化等问题。 a 可变精度模型v p r s 在数据集中存在噪声等干扰情况下，经典粗糙集理论会由于对数据的过拟合而使其 对新对象的预测能力大为降低。z i a r k o 提出一种可变精度粗糙集模型v p r s ，该模型通 过引入一个精度，允许粗糙集存在一定的误分类率，从而使粗糙集合具有一定的容错性， 增强其抗干扰能力。粗糙集理论中原有的概念和性质在可变精度模型中都成立【9 1 。 k a t z b e r g 和z i a r k 进一步提出不对称边界的v p r s 模型，从而使此模型更加一般化【1 0 l 。 j第一章绪论 陈湘晖等则构造了一种新的扩展粗糙集模型，在知识表示系统和决策表中引入数据对象 的权值函数和属性的特征函数，表示数据对象的重要性和属性的特性f l l 】。关于v p r s 比 较经典的文献，还有文献【1 2 】和【1 3 】。 b 相似模型 做为经典粗糙集理论的基础，不可分辨关系是一种很强的关系。对于数据库中普遍 存在的数据不完备情况，不可分辨关系或者等价关系就无法发挥作用。为加强粗糙集理 论的性能，m a r z e n ak 首先提出用相似关系来代替不可分辨关系【1 4 】。s l o w i s k ir 进一步 阐述相似关系模型的定义和性质15 1 。梁吉业等证明在相似模型中，粗糙熵随着知识粒度 减小而单调递减，这有助于寻找针对不完备信息系统的新的知识约简算法【1 6 1 。相似关系 代替粗糙集合中的不可分辨关系后，最主要的变化就是相似类不再形成对原集合的划 分，他们之间是相互重叠的。实践证明，相似模型在实践中具有比经典粗糙集模型更好 的性能。 c 连续属性离散化 粗糙集理论只能处理离散型属性，但是在实际应用中，经常遇到连续属性值的情况， 这就需要对连续属性进行某种离散化。l e n a r c i ka 等把一个信息系统的最优分类性质， 作为选择离散化的基本原则。连续属性的离散化，使粗糙集理论对离散和连续属性都能 处理，扩大了模型的应用范围【1 7 1 。陈湘晖等利用基于信息熵的规则不确定性度量函数构 造了一个决策规则挖掘的遗传算法，将规则挖掘与特征选取和连续属性的离散化集成在 一起【1 8 】。 粗糙集理论有效性算法方面的研究 。 粗糙集理论有效性算法方面的研究，除一些基本的算法【1 9 , 2 0 1 外，目前主要集中于以 下四个方面： a 导出规则的增量式算法 粗糙集理论原有的算法是在固定的数据集上进行的。当有新的数据增加到数据集 时，必须重新计算全部现有数据集再导出规则。增量式算法是对原有规则进行修正，从 而得到关于新数据集的规则的方法【2 1 捌。另外，动态约简算法得到的约简也具有很好“增 量特性”1 2 3 1 。 b 约简的启发式算法 一个信息系统，找出其所有的约简是n p 完全问题f 2 4 l 。很自然的想法是采用启发式 基于粗糙集和粒度计算的不确定信息度量及知识约简研究 的方法找出最优或者次优约简。这类算法的共同特点是利用属性的重要性作为启发式信 息，去求得约简，只是它们对属性重要性的度量方法不同而己。 c 粗糙集基本运算的并行算法 粗糙集的基本性质决定它的很多基本运算都可以并行计算。m u r a s z k i e q i c zm 采用格 形数组( c e l l u l a ra r r a y s ) 的s i m d 计算机形式，提出实现粗糙集理论中诸如可定义性、不 可分辨性以及上、下近似这些基本运算的并行近似结构2 5 1 。由于粗糙集理论研究的初衷 就是试图为处理大量数据提供一种数学工具，因此，并行计算的性质就显得非常重要。 d 大数据集中的粗糙集计算实现 由于粗糙集在数据挖掘中具有较大的计算复杂度，受关联规则挖掘算法的启发，有 些研究者提出将关联规则的挖掘技巧应用于粗糙集的确定和可能规则生成中，以减小粗 糙集方法的计算复杂度口6 ，2 刀。s k o w r o n 和n g u y e n 等描述了一种决策表分解方法【2 8 1 ，首 先，使用遗传算法在决策表中搜索代表性的模板( 例如：一条支持度最大的规则) ；然后， 将决策表一分为二，满足模板的为一个部分，不满足的为另一个部分；将该过程递归进 行，直至决策表的大小满足要求为止，最后再对小决策表生成规则。 ( 3 ) 粒度计算的研究背景 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方 法、技术和工具的研究，现已成为人工智能领域研究的热点之m 2 9 1 。2 0 世纪6 0 年代， 美国著名数学家z a d e h 提出模糊集理论，在此基础上，于1 9 7 9 年首次提出并讨论了模 糊信息粒度化问题，推动了模糊逻辑理论及其应用的发展，但在当时未引起足够的重视。 接着，z a d e h 在1 9 9 6 年提出“词计算理论 3 0 l ，标志着模糊粒度化理论的诞生，其旨 在解决利用自然语言进行模糊推理和判断，以实现模糊智能控制。随后，美国多特蒙德 大学的h e l m u t t h i e l e 教授于1 9 9 8 年发表了“词计算理论的语义模型1 3 ，促进了词计 算理论的发展。词计算理论对因特网上的海量信息资源的高效利用有着深远的影响。基 于z a d e h 的模糊集理论，进行粒度计算理论和方法的研究，己成为“粒度计算”的重要 研究方向之一。 波兰学者z p a w l a k 于1 9 8 2 年提出了粗糙集理论【3 2 。5 1 。由于粗糙集理论具有很强的 定性分析能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并 能利用不确定、不完整的经验知识进行推理等，因此在知识获取、机器学习、规则生成、 决策分析、智能控制等领域获得了广泛应用，特别是在数据挖掘领域获得了巨大成功， 4 第一章绪论 业已成为粒度计算研究领域的主要方向之一。加拿大r e g i n a 大学yyy a o 教授在研究 粗糙集理论的基础上，提出了基于邻域系统的粒度计算模型 3 6 1 ，并成功应用于知识发现 领域。粒度计算作为专门的术语，首次出现在z a d e h 的文献【3 7 1 中。t yl i n 、yyy a o 和z a d e h 又在文献【3 8 】中着重描述了粒度计算的重要性，这激发了人们对粒度计算的研 究兴趣。随后，大量的关于粒度计算研究的论文相继发表，而且在国际上形成了专门的 研究群体，定期召开关于粒度计算的国际研讨会。 在国内，张钹院士和张铃教授提出了基于商空间的粒度计算模型【3 9 1 ，其利用子集来 表示概念，不同粒度的概念就体现为不同粒度的子集，一簇概念就构成空间的一个划分 二商空间( 知识基) ，不同的概念簇就构成不同的商空间。而粒度计算问题，也就等价 于研究在给定知识基上的各种子集合之间的关系和转换。对同一问题，可以采取不同的 粒度，通过对不同的粒度的分析，综合获取对原问题的求解。在此基础上张钹、张铃于 2 0 0 3 年提出了模糊商空间理论【删。总的看来粒度计算的研究在国内属于起步阶段。 ( 4 ) 粒度计算的现状分析主要模型与方法【4 1 】 基于模糊集理论的词计算模型 z a d e h 认为人类在进行思考、判断、推理时主要是用语言进行的，而语言是一个很 粗的粒度，如何利用语言进行推理判断，这就要进行“词计算 。狭义的模糊词计算理 论是指利用通常意义下的数学概念和运算，诸如加、减、乘、除等构造的带有不确定或 模糊值的词计算的数学体系，它借助模糊逻辑概念和经典的群、环、域代数结构，构造 出以词为定义域的类似结构。例如，模糊数及其运算【3 0 1 。尽管这种数值型模糊粒度的理 论体系，在模糊控制、图像识别、语言处理、故障诊断、信息检索、人工智能等领域获 得了较大的成功，但由于自身存在的不足限制了它的应用范围。广义的模糊词计算理论 统指用词进行推理、用词构建原型系统和用词编程。总之，基于词计算理论的推理、决 策和识别方式是最贴近人类的思维形式来求解问题，它对复杂的系统的信息处理有着广 阔的应用前景。 基于粗糙集理论的粒度计算模型 粗糙集理论的核心思想是给定一个论域u ( 有限的非空集合) ，及论域( 厂上的一个等 价关系r u x u ，称序对( c 厶尺) 是一个近似空间或知识库。在( r ) 近似空间中，等价关 系将论域u 分割成两两互不相。气：等价类，每一个等价类对应一个粒子，等价关系的实 质是从论域u 到论域u 的；集2 上的一个映射r ：u 一2 u ，同时称商集 基于粗糙集和粒度计算的不确定信息度量及知识约简研究 u r = n 】rlv x u ) 是近似空间的组知识基，也代表了论域的一种粒度。这样对于论 域上的任何一个子集x ( 近似空间的一个概念) 就可以用它的上、下近似算子来刻画，其 中，a p r ( x ) = 墨( x ) = 秘lx x ，】rsx ) 为x 的下近似，表示论域中完全肯定隶属于x 的元素组成的集合，即代表x 包含的最大内核；a p r ( x ) = r ( 柳= 扛i x u ，【x k n x a ) 为x 的上近似，表示论域中所有肯定和有可能隶属于x 的元素组成的集合，即代表包 含x 的最小闭包。在粗糙集理论中一个对象是否隶属于某一集合( 概念) ，不是取决于该 元素的客观性质，而是取决于我们对它的了解程度。同样，集合的相等和包含也没有绝 对的意义，也是取决于我们对所研究的问题中的集合的了解程度，这更符合人类的认知 过程。 基于商空间的粒度计算模型 张钹院士和张铃教授在研究问题求解时，独立地提出了商空间理论。该模型是用一 个三元组( u 只d 来描述一个问题，其中u 表示论域，f 是属性集，r 是u 上的拓扑结构。 在该模型中，论域的一种粒度化就等同于给定一个等价关系r 或一个划分，于是得到一 个对应于r 的商集【叼，对应的三元组为( 【明， 刀， 用) 称之为对应于r 的商空间。商空间 理论就是研究各商空间之间的关系、合成、综合、分解和推理，它的最重要的性质是同 态原则，即保真原理( 或保假原理) 。当面对一个复杂问题时，常先将问题化成在一个较 粗粒度商空间对应的问题进行初步分析，若得出该问题在粗粒度空间中是无解，则由“保 假原理 立即得原问题是无解的。这样我们就可以以很少的计算量得出所要的结果，达 到“事半功倍”的目的。同样利用“保真原理也可达到降低求解的复杂性目的。在此 基础上建立了“粒度世界模型以及一整套理论和相应的算法，并将其应用于启发式搜 索、路径规划等方面取得一定成效。他们又将模糊集合论引入商空间，利用模糊等价关 系实现了商空间模型的推广。一方面，这必将有助于粒度计算的发展，能够更好地反映 人类处理不确定问题的若干特点，诸如信息的确定与不确定、概念的清晰与模糊等都是 相对的，都与问题的粒度有关，因此构造合理的分层递阶的粒度结构，可以高效地求解 问题和处理信息。另一方面，商空间理论同样缺少实现粒度与粒度之间、粒度与粒度世 界之间、粒度世界与粒度世界之间转换的手段和技术方法，如果能够探索出有效的技术 和方法来解决这个问题，将会拓宽商空间的应用范围，极大丰富粒度计算的理论。 三种模型之间的关系分析 对粗糙集、模糊集、商空间这三种主要粒度计算模型的比较分析，有益于深刻理解 6 第一章绪论 它们之间的联系与区别，有益于找到它们的融合点，从而实现构建统一的更加有效的处 理复杂和模糊的信息系统的理论平台。 模糊集理论和粗糙集理论都能够处理不确定和不精确的问题，然而它们的侧重点不 同。模糊集合论中的对象x 的隶属度不依赖于论域中的其他对象，一般是由专家直接给 出，因此带有很强的主观性且缺乏精度的概念；而粗糙集理论中对象的隶属函数值却依 赖于知识库，它可以从所需处理的数据中直接得到，所以用它来反映知识的模糊性是比 较客观的。同时二者也存在着联系，因为近似空间中的任何一个子集彳( 概念) 实际上都 对应于一个模糊集心，其下上近似分别等价于该模糊集的核和支撑，即：r ( a ) = c o r e ( 1 z a ) 一 。 = x l 心 ) = 1 ，r ( a ) = s u p p ( u a ) = x l , u a ( x ) 0 ) 。由此可见，下近似是心的1 一截集，上 近似是胁的强o 截集。总之，模糊集合论与粗糙集理论有很强的互补性，通过对这两 个理论的优化、融合来处理知识的不确定性和不完全性已显示出很强的功能。例如， s h a d o w e ds e t s 是在模糊集合的框架体系上发展起来的，但处理信息的方法却类似于粗 糙集，在一些领域的应用显示出了优势。还有许多的模糊粗糙集混合模型解决了一些单 一模型无法解决的实际问题，这说明理论的融合是求解复杂问题的一种有效途径。 商空间理论与粗糙集理论都是利用等价类来描述“粒度，再用“粒度来描述概 念，但是讨论的出发点有所不同。商空间理论的着重点是研究不同粒度世界之间的互相 转换、互相依存的关系，是描述空间关系学说的理论，而粗糙集理论主要是研究粒度的 表示、刻画和粒度与概念之间的依存关系；商空间理论是在论域元素之间存在有拓扑关 系的前提下进行研究的，即论域是一个拓扑空间，而粗糙集理论的论域只是对象的点集， 元素之间拓扑关系不在考虑之内，这些差异对问题求解都有一定的影响。 模糊集理论的粒度计算模型与商空间理论讨论的粒度问题也不尽相同，模糊集理论 模型主要讨论粒度的表示问题，即当人类进行各种思考和推理时，都离不开粒度。粒度 一般就是用语言、词来表示，这就涉及到“词计算”问题。对于词计算，目前主要是基 于模糊集合论的方法。商空间模型主要论述的是，当一个问题很复杂时，人们常从比较 “粗一的粒度层次出发来考察问题，一步步细化，直到问题得到确定解答。从商空间的 观点看，三者理论之间表面上完全不同，但本质上有着紧密的联系，粗糙集理论相当于 无拓扑结构的商空间理论，模糊粒度计算理论与商空间理论有许多等价之处，所以商空 间理论是粒度计并的重要工具之一。 基于粗糙集和粒度计算的不确定信息度量及知识约简研究 1 1 2 粗糙集和粒度计算的研究意义 粗糙集理论近年来不但在数学理论上不断完善，而且在其它研究领域中也得到了成 功的应用【4 2 4 酗，如机器学习、决策分析、近似推理、图象处理、医疗诊断、金融数据分 析、专家系统、冲突分析、过程控制和数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， k o d ) 等领域。 ( 1 ) 在专家系统研究方面，利用粗糙集进行决策规则的抽取，为构造专家系统的知 识库提供了一条崭新的途径( 4 9 1 。 ( 2 ) 在模式识别研究方面，文献【5 0 】应用粗糙集方法研究了手写字符识别问题，提 取出了相应的特征属性。 ( 3 ) 文本分类【5 1 】随着电子信息量的急剧增长，信息过滤和信息检索越发重要。而对 于目前大量的高位数据进行分类却是一个很困难的事情，当把这些高位数据运用粗糙集 属性约简技术处理之后，消除了数据集中的冗余知识，从而可以得到一个包含少量前提 条件的规则组成的规则库。这种方法既可以降低关键词集合的维数又可以保持关键词集 合中的信息。 ( 4 ) 在人工神经网络研究方面，为了克服训练时间过于漫长的固有缺点，文献 3 3 】 应用粗糙集约简神经网络训练样本数据集，使训练速度提高了4 7 7 倍，获得了较好的效 果。文献 5 2 ，5 3 将粗糙集与神经网络结合起来，充分利用粗糙集处理不确定性的特长以 增强神经网络的信息处理能力。 ( 5 ) 在医疗诊断研究方面，利用粗糙集方法，根据以往的病例归纳出诊断规则，然 后用来指导诊断新的病例。现有的人工预测早产的准确率只有1 7 0 , - 3 8 ，利用粗糙集 方法则可以提高到6 8 9 0 1 5 4 1 。 ( 6 ) 在地震预报研究方面，文献 5 5 】研究了地震前的地质和气象数据与里氏地震级别 的依赖关系，为地震预测提供了一种新的方法。 ( 7 ) 在股票数据分析研究方面，文献【5 6 】应用粗糙集方法分析了十年间股票的历史数 据，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街证券交 易专家的认可。 ( 8 ) 在冲突分析研究方面，文献【5 7 】应用粗糙集方法建立了反映以色列、巴勒斯坦、 约旦、埃及、叙利亚和沙特阿拉伯六国关于中东和平问题各自立场的谈判模型。 ( 9 ) 在决策分析研究方面，文献 5 8 ，5 9 应用粗糙集方法产生决策规则，它允许决策 8 第一章绪论 对象中存在一些不太明确、不太完整的属性，即可以存在一些不完备信息，弥补了常规 决策方法的不足。希腊工业发展银行e t e v a 应用粗糙集理论协助制定信贷政策，是粗 糙集多规则决策方法的一个成功范例1 6 0 l 。 ( 1 0 ) 在数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d o ) 研究方面，粗糙集 方法现已成为k d d 的一种重要方法，其导出的知识精练且更便于存储使用1 6 1 , 6 2 1 。与其 它知识发现方法相比，粗糙集方法有如下特点：粗糙集方法的伸缩性强；鲁棒性和抗噪 音能力强；知识的可理解性和开放性较好；比较适合于符号信息。此外，粗糙集方法可 以对数据进行预处理，去掉多余属性，提高发现效率，降低错误率。 ( 1i ) 在粗糙控制研究方面【6 3 硎，粗糙集根据观测数据获得控制策略的方法被称为从 范例中学习，属于智能控制的范畴。基本步骤是：把控制过程中的一些代表性的状态以 及操作人员在这些状态下所采取的控制策略记录下来，形成决策表，然后对其进行分析 约简，总结出控制规则。文献 6 4 ，6 5 应用粗糙控制研究了小车一倒立摆系统这一经典问 题，取得了较好的效果。在过程控制领域，文献【6 6 】应用粗糙集方法成功提取了水泥窑 炉的控制规则。粗糙控制的优点是简单迅速、容易实现，不需要像模糊控制那样进行模 糊化。因此在特别要求控制器结构与算法的场合，采取粗糙控制较为合适。另外，由于 控制算法完全来自观测数据本身，其决策和推理过程可以很容易被检验和证实。一种新 的有吸引力的控制策略一目糙控制策略正在悄然兴起，其主要思想是利用粗糙集获取 模糊控制规则【6 7 1 。 粗糙集理论的应用领域还包括：近似推理、软件工程数据分析、图像处理、材料科 学中的晶体结构分析、预测建模、结构建模、投票分析、电力系统和邮件过滤等等。 粗糙集理论从诞生到现在虽然只有二十余年时间，但已在许多领域取得了众多鼓舞 性的成果，正是因为粗糙集理论具有很强的实用性，所以研究粗糙集理论具有重要的意 义。 1 2 本文的研究内容与结构安排 1 2 1 本文的选题 本文的选题来自于河南省自然科学基金项目( n o 0 5 1 1 0 11 5 0 0 ) 和河南省高校新世纪 优秀人才支持计划( n o 。2 0 0 6 h a n c e r - 1 9 ) 其 的部分内容，主要是把粗糙集理论和粒度计 算理论运用到信息系统中，研究信息系统中各种不确定信息的特点和处理方法，分别提 基于粗糙集和粒度计算的不确定信息度量及知识约简研究 出一些相应的不确定信息处理的度量方法及其满足的性质，特别是属性重要性的度量、 属性相关性的度量等理论与方法，并给出一些基于这些度量方法的知识约简的算法。 1 2 2 本文的主要研究内容 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方 法、技术和工具的研究，它是词计算理论、粗糙集理论、商空间理论、区间计算等的超 集，也是软计算科学的一个重要分支，它已成为模糊的、不完备的、不精确的及海量的 信息处理的重要工具和人工智能领域研究的热点之一。 自波兰学者p a w l a k 于1 9 8 2 年提出了粗糙集理论以来，由于粗糙集理论具有很强的 定性分析能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并 能利用不确定、不完整的经验知识进行推理等。因此在知识获取、机器学习、规则生成、 决策分析、智能控制等领域获得了广泛应用，特别是在数据挖掘领域获得了巨大成功， 业已成为粒度计算研究领域的主要方向之一。 虽然粗糙集理论的研究有了一定进展，但深层次的理论研究还须加强，同时其理论 应用还很有限，深层次的应用研究不够。现实中很多信息都是不确定的，用粗糙集理论 解决不确定信息处理的研究方面还缺乏一些好的度量方法。如何更好地把粗糙集理论应 用于不确定信息处理及信息度量中，特别是在属性重要性、相关性的度量方面，因为它 们是讨论属性约简、知识发现的关键基础。近年来，在信息系统中属性重要性、相关性 的度量方面，国内外学者已经进行了大量深入研究并发表了一些相关文章，但都缺乏对 各种方法的系统比较和分析，以及对它们进行深入讨论。另外，这些方法缺乏从粒度计 算方面的考虑和探讨。 因此，本文针对上述问题在以下几个方面做出了研究： ( 1 ) 在信息系统中属性重要性的度量方面，本文从知识粗糙性的粒度原理和经典的 知识粒度及信息熵理论出发，对经典的知识粒度及信息熵理论进行推广，给出了信息系 统中知识的粒度和粒度熵原理，揭示了知识粒度和粒度熵原理的本质和关系，为进一步 研究知识的粒度计算提供了理论基础。 ( 2 ) 在信息系统中属性相关性的度量方面，本文借鉴集合论中对称差的概念，从粒 度计算的观点出发，给出了信息系统中知识距离的概念，分析了其相关性质，并指出知 识距离也可以度量属性的相关性。同时，又给出了知识贴近度的概念，并分析了它与知 i o 第一章绪论 识距离的关系。 ( 3 ) 在信息系统中的知识约简方面，本文分别提出了一种基于知