（计算机应用技术专业论文）基于粗糙集的粒度计算理论与方法研究.pdf

摘要 信息粒化的基本思想出现在许多领域，如粗糙集、模糊集、证据理 论、聚类分析、数据库、机器学习、数据挖掘等。从1 9 7 9 年l a z a d e h 在世界上首次提出并讨论了模糊信息粒化问题之后，信息粒化得到人们 越来越多的关注。经过二十多年的发展，预计在不远的将来，粒度计算 将会在软计算、知识发现、数据挖掘中扮演越来越重要的角色。 本文跟踪国际学术前沿，在粗糙集理论框架下，以粒度计算方法为 前提，借鉴已有的软计算理论成果，对一些粒度计算理论与方法进行了 深入的研究，不仅从理论上丰富和发展了该理论，而且由于其广泛的应 用背景，这些结果同样具有重要的应用价值。 本论文主要研究了以下若干问题： 1 在粒度计算和粗糙集理论的融合方面，提出动态粒度原理。由于 经典粗糙集概念刻画的非动态性，本文讨论了粒度意义下的粗糙集近似， 并定义了动态粒度下的正向近似和逆向近似，给出了它们的一些性质， 为粒度计算和粗糙集理论提供了新的研究角度。另外，本文从粒度的角 度讨论了近似分类结果和原有分类对象的协调度问题，并提出了一种基 于动态粒度下正向近似的近似分类算法，实验表明该算法的有效性。基 于正向近似思想，本文还给出了一种新的决策表规则挖掘算法，实验表 明该算法相比其它算法简单有效。 2 在刻画信息系统中的粒本质方面，提出粒度公理化定义。为了刻 画和度量知识之间的贴近程度和差异程度，本文统一了完备信息系统和 不完备信息系统中的知识表示，引入了知识贴近度和知识距离的概念，证 实它们之间满足严格互补关系。考虑到知识粒度的刻画和定义潜在地遵 循一些规则，本文给出了知识粒度的公理化定义，并且证明原有的知识粒 度都是这种粒度定义下的特殊形式。从知识粒度公理化定义出发，可以 针对不同研究对象定义不同的知识粒度。此外，本文还建立了知识粒度和 信息熵之间的关系，证明知识粒度和信息熵之间满足互补关系，提出了 信息守恒猜想及其推论，认为在一个给定的知识空间中，所体现出来的 信息含量和有粒度变化所引起的隐藏信息量的总和应当是守恒的。 3 在信息熵理论研究方面，提出组合熵和组合粒度理论。首次提出 了信，宙、系统框架下一种新的信息熵( 组合熵) 定义，其增益函数足基于 直观的知识含量特性的，并且给出了它的一些性质。借鉴组合熵的思想， 相应的知识粒度( 组合粒度) 被定义，它的些重要j f 牛质被给出。由于 完备信息系统是不完备信息系统的退化，组合熵和组合粒度在信息系统 中的退化和拓广关系被证明。迸步，我们建立了组合熵和组合粒度之 间的关系，经证明表明它们之间满足严格互补关系。这些结论极人地丰 富和发展了熵理论和粒度计算理论。 4 在智能决策珲沦方面，提出两个史加深刻的评价参数。针对决策 表，基于粗糙集理论，运用粒度思想详细讨论了动态粒度下的决策规则 演变问题。由于经典的决策度量参数不反映整体决策效果的优劣，本文 给出了两个更加深刻的决策性能评价参数，并在不同类型决策表中建市 了动态粒度与评价参数之间的关系。这些结果深刻揭示了粒度意义f 规 则挖掘的内涵，可进一步应用于知识发现、数据挖掘等领域中。 最后，概括了本文的主要结果，说明本文工作的理论意义和应用， 指出有待进一步解决的问题以及以后值得注意的研究方向。 关键词：粗糙集；动态粒度；知识粒度；信息熵；决策评价 a b s t r a c t t h eb a s i ci d e a sa n dp r i n c i p l e so fg r a n u l a rc o m p u t j n g ( g r c ) h a v eb e e n s t u d i e de x p l i c i t l ) 7 o r 如1 1 p j j c j t j yj nm a n yn e l d si ni s o i a t i o ns u c ha se v i d e n c e t h e o 吼 c l u s t e “n ga j l a l y s i s ， d a t a b a s e s y s t e m ， m a c h i n el e a m i n ga n dd a t a m i n i n ga n ds oo n m o r ea n dm o r ep e o p l eh a v eb e e ni n t e r e s t e di ni n f i o r n l a t i o n g r a n u l a t i n gs i n c et h ep r o b l e mw a sf l r s t l yp r o p o s e da n dd i s c u s s e di nt h ew o r l d b yl a z a d e h w i t ht h er a p i dd e v e l o p m e n to ft h et h e o r yi nr e c e n t l yt w o d e c a d e s ， g r a n u l a rc o m p u t i n gw i l lp l a y am o r e i m p o r t a n t r o l ei ns o r c o m p u t i n g ，k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g t r a c “n gt h ei n t e m a t i o n a ir e s e a r c hs t a t u s ，b a s e do nr o u 曲s e tt h e o 吼 u s i n gf o rr e f e r e n c es o m ek n o w nt h e o r yf m i t so fs o rc o m p u t i n g ，m ep 印e r l u c u b r a t e ds o m eb a s i ct h e o r i e sa n dm e t 1 0 d so fg r a n u l a rc o m p u t i n g a c h i e v e d r e s u i t sn o t o n l y e n r i c ha n d i m p r o v eg r a n u i a rc o m p u t i n gt 1 1 e o r y a n d j n f o n n a t i o ne n 虮) p yt h e o r y ，b u ta l s oa r ee x p e c t e de n o n i l o u s 印p i i e dv a j u ed u e t om ew i d e s p r e a da p p l i e db a c k g r o u n do f t h e s et h e o r i e s s o m et h e o r e t i c a l p m b l e m sw e r em a i n l yr e s e a r c h e di n t h e p a p e r a s f o l l o w s 1 a sf o rs y n c r e t i z a t i o nb e t w e e nr o u g hs e tt h e o r ) ，a n dg r a j l u l a rc o m p u t i n 岛 d y n a m i cg r a n u l a t i o n i s p r o p o s e d 0 w i n g t o n o n d y n a m i c o f c o n c e p t d e s c r i p t i o ni nc l a s s i c a lr o u g hs e t ，r o u g hs e ta p p r o x i m a t i o nu n d e rg r a n u l a t i o n i sd i s c u s s e di nt h ep a p e r ，p o s i t i v ea p p r o x i m a t i o na n dr e v e r s ea p p r o x i m a t i o n u n d e rd y n a m i cg r a n u l a t i o na r ed e f i n e d ，t h e i rs o m ei m p o r t a n tp r o p e n i e sa r e g i v e n t h e s ei d e a sw i l lp r o v i d en e wr e s e a r c hm e t h o df o rg r a n u l a rc o m p u t i n g a n d r o u g h s e t t h e o r y i n a d d i t i o n ， m e a s u r eo f h a r n l o n y b e t w e e n a p p r o x i m a t i o nc l a s s i f i c a t i o na n do r i g i n a lu n i v e r s ec l a s s i 6 e di sa n a i y z e d ，a a p p r o x i m a t i o nc l a s s i n c a t i o na l g o r i t h mb a s e d o np o s i t i v e 印p r o x i m a t i o n i s p r e s e n t e d ，i t sv a l i d i t yi sp r o v e du s i n gac o n c r e t ei n s t a n c e 2 a sf o rd e p i c t i n gt h ee s s e n c eo ft h eg r a n u i a t i o ni ni n f o m a t i o ns y s t e m ， t h ea ) 【i o md e n n i t i o no ft h el ( n o w l e d g eg r a n u l a t i o ni sp m p o s e d k n o w l e d g ei n ac o m p l e t ei n f o r m a t i o ns y s t e ma n di na ni n c o m p l e t ei n f o h n a t i o ns y s t e mi s u n lf o r m l ye x p r e s s e dl no r d e rt od e s c r l b ea n dm e a s u r et h ee x t e n to t 。c i o s e n e s s a n dd i f f 宅r e n c ea m o n gk n o w l e d g e ，t h ec o n c e p to fk n o w l e d g ec l o s e n e s sa n d t h ec o n c e p to fk n o w l e d g ed i s t a n c ea r ei n t r o d u c e d ，t h er e l a t i o n s h i pb e t w e e n t w oc o n c e p t sw i t ho n ee q u i v aj e n c er e l a t i o no rt o l e r a n c er e l a t i o ni sr e s t “c t c o m p i e m e n t a 叮r e l a t i o n s h i pb yp r o v i n g a 1 l o w i n g f o rs o m ep o t e n t i a l l y p r i n c i p l ef o l l o w e d a b o u tt h ed e p i c t i o na n dt h ed e n n i t i o no fk n o w l e d 2 e g r a n u l a t i o n ，t h ea x i o md e n n i t i o no fk n o w l e d g eg r a n l i l a t i o ni sp r e s e n t e d ， s e v e r a 】 k 力o 、，玎k n o w j e d g eg r a n u j a t j o n a r ea s p e c j a l f o n n s u n d e rt h e d e f i n i t i o n w h e r e a r e r ，t h er e l a t i o n s h i p sb e t w e e nk n o w l e d g eg r a n u l a t i o na n d i n f o r m a t i o ne n t r o p ya r ee s t a b l j s h e d ，t h e r ei sac o m p l e m e n t a ur e l a t i o n s h i p b e t w e e nt h e mb yp r o v j n gt h e o r e t i c a i i ya n dw ep r o p o s eas u p p o s es o c a l l e d i n f o m l a t i o nc o n s e r v a t i o ns u p p o s e ，t h es u mo fk n o w l e d g ec o n t e n t 印p e a r e d a n dk n o w l e d g ec o n t e n th i d e di su n c h a n g e a b l ei nak n o w l e d g es p a c e 3 a sf o rr e s e a r c ho ni n f o r n l a t i o ne n t m p yt h e o r y ，c o m b j n a t i o n e n t r o p y a n dc o m b i n a t i o n g r a n u l a t i o n a r ep r e s e m e d an e wi n f o r m a t i o n e n t r o p y ( c o m b i n a t i o ne n t r o p y ) i ni n f o r m a t i o ns y s t e mi sp r o p o s e dn r s t ly ，i t sg a i n 向n c t i o nc o n s i d e r e dh e r e p o s s e s s e s i n t u i t i o n i s t i c k n o w l e d g e c o n t e n t c h a r a c t e r i s t i c ，s o m ei m p o r t a n tp r o p e r t i e sa r ed e r i v e d a c c o r d i n 9 1 y ，an e w k n o w i e d g eg r a n u i a t j o n( c o m b j n a t j o ng f a n u l a t i o n )i sd e 疗n e d ；i t ss o m e c o r r e l a t i v ep r o p e r t i e sa r eg i v e n d e g e n e r a t i o na n de x t e n s i o nr e l a t i o n s h i po f c o m b i n a t i o n e n t r o p ya n dc o m b i n a t i o ng r a n u j “o nb e t w e e nc o m p l e t e i n f o m a t i o n s y s t e m a n d i n c o m p l e t ei n f o r m a t i o ns y s t e ma r ep r o v e d f u r t h e r m o r e ，w eb u i i dt h er e l a t i o n s h i pb e t w e e nc o m b i n a t i o ne n t r o p va n d c o m b i n a t i o n g r a n u l a t i o n ，a n dp r o v et h a tt h er e l a t i o n s h i pi sar e s t r i c t i v e c o m p i e m e n t a ur e j a t i o n s h i p t h e s er e s u l t sw i l lg r e a t l ye n r i c ha n dd e v e j o p e n t r o p yt h e o r ya n dg r a n u l a rc o m p u t i n g 4 a sf o rr e s e a r c ho n j n t e 】j j g e 力td e c j s j o nt h e o r y ，t w om o r ep m f o u n d e v a l u a t l o np a r a m e t e r sa r eg i v e n b a s e do nr o u g hs e tt h e o r y ，d e d u c t i o no f d e c i s i o nr u l ei nd e c i s i o nt a b l eu n d e rd y n a m i cg r a n u l a t i o ni sd i s c u s s e du s i n g i d e a so f 静a n u l a t i o n b e c a u s ew h o l ed e c i s i o nd e r f b r m a n c eo fd e c i s i o nt a b i e c a n tb er e f l e c t e dv i ak n o w nd e c j s i o n p a r a m e t e r s ， t w om o r ep r o f o u n d d e c l s l o n p a r a m e t e r sa r e g i v e n ， a n dt h e i r p r o p e n j e su n d e rd v n a m i c g r a n u j a t l o na r eb u i j t t h e s er e s u l t sp r o f o u n d i ye n c l o s et h e e s s e n c eo fr u l e s m l n l n gu n d e 。g r a n u l a t i o n ；w i l i b e 印p i i e df o rm a n yr e l a t i v ef i e l d ss u c ha s l o w l e d g ed i s c o v e r ) a n dd a t am i n i n ga n ds oo n 上l1 n a l l y ，a c h l e v e dm a i nr e s u l t si n t h ep a p e ra r eg e n e r a l i z e d ，t h e o r e t i c a l s l g n i f l c a n c ea n dp o t e n t i a la p p l i e dv a l u eo ft h er e s e a r c ha r ee x p l a i n e d ，s o m e p r o b l e m s a r t h e rn e e d e da n dr e m a r k a b l er e s e a r c hd i r e c t i o nf o rt h e 如t u r e a r e i n d i c a t e d k e y w o r d s ：r o u 曲s e t ；k n o w l e d g e 伊a n u la t i o n ；d y n a m i cg r a j l u l a t i o n ； i n f o m a t i o ne n t r o p y ；d e c j s i o ne v a l u a t i o n 基丁- 粗糙集的粒度计算理论与方法研究 第一章绪论 1 1 粗糙集理论及应用研究的历史和现状 粗糙集( r o u 曲s e t ，r s ) 理论是八十年代初由波兰学者z p a w l a i ( 首先提出 的一个分析数据的数学理论”一，由于最初的研究是用波兰文发表的，因此，这 项研究当时并未引起国际学术界的重视，研究地域也只局限在东欧各国。 到了八十年代术，这个理论引起了世界各国学者的关注。从1 9 9 2 年至今， 每年都召开以r o u 曲s e t 为主题的国际会议，困际上成立了粗糙集学术研究会， 并在i n t e m e t 上定期发布电子公告，加速了粗糙集理论的发展和交流。在国内， 从2 0 0 1 年开始每年召开一次粗糙集与软计算学术会议。由于粗糙集理论能够分 析处理不精确、不一致和不完备信息，因此作为一种具有极大潜力和有效的知识 获取工具受到了人工智能工作者的广泛关注。目前，对应粗糙集概念，发展了粗 糙代数、粗糙逻辑等，并与其他有关理论( 如模糊集、证据理论) 的关系也得到 了研究和阐明，明确了粗糙集在数学上的独立地位。近年来，粗糙集不但在数学 理论上得到不断完善，而且在其他领域也得到了成功的应用”，如在机器学习、 模式识别、决策分析、图像处理、医疗诊断、近似推理、过程控制、数据库知识 发现、专家系统等领域。 粗糙集理论的特点是：( 1 ) 它不需要任何预备的或额外的有关数据信息，比 如统计学中的概率分布，d e m p s t e 卜s h a f e r 理论中的基本概率赋值，或者模糊集理 论中的隶属度或概率值。( 2 ) 它本身是一个强有力的数据分析工具，它能表达和 处理不完备信息，能在保留关键信息的前提下对数据进行约简并求得知识的最小 表达，能识别并评估数据之例的依赖关系，能从经验数掘中获取易于证实的规则 知识等。( 3 ) 与己知的模糊集工具形成互补，粗糙集和模糊集分别刻画了不完备 信息的两个方面：粗糙集以不可区分关系为基础，侧重分类，模糊集基于元素对 集合隶属程度的不同，强调集合本身的含混性。从粗糙集的观点看，粗糙集合不 能清晰定义的原因是缺乏足够的论域知识，但可以用一对清晰集合逼近。 目前，对粗糙集理论研究主要集中在其数学性质、粗糙集拓广、粗糙集理论 中的度量、与其他不确定方法的关系和互补，以及有效算法等方面。 在粗糙集数学理论的研究方面，主要兴趣在于讨论粗糙集的代数性质与拓扑 结构，以及粗糙集的收敛性等问题”。一些新的数学概念( 如粗糙思想“，粗糙 半群等) 近年来不断出现。随着粗糙结构、代数结构、拓扑结构、序结构等各 种结构的不断整合必将不断涌现出新的富有生机的数学分支。 在粗糙集拓广方向的研究主要涉及变精度粗糙集模l ! 、模糊粗糙集模型与桐 糙模糊集模型、不完备信息系统f 、的粳糙集模型，以及对连续属性的离散化等 f l d h j 在粗糙集理论中的度量方面主要研究粗糙集数据分析中的度量、知识的不确 定性度量，以及相糙集与相糙关系数据库的信息度量等。1 。 在莘h 糙集理论与其他处理模糊忤或不确定性方法之间关系的研究中，主要讨 沦它与模糊集理论和d e m p s t c r - s h a f e r 证掘理论的关系与互补。1 “。神经网络与襁 糙集方法对于从数掘中进行特征提取的关系的研究也是非常有趣的课题”。 在粗糙集有效算法力面，主要集中于抽耿最优决策规则算法”，导m 规则的 增量式算法”9 ”、约简的启发式算法“”1 ，以及莘且糙集基本运算的并行算法等。 另外，由于粗糙集的逻辑是关于粗糙集的才i 确定推理的基础，发展这类逻辑 的理论基础也足目前相糙集理论研究的重要课题j ”1 。 柙糙集理论的生命力在于它具有非常强的实用性，从诞生到现在虽然只有一 十年的时问，但已经在许多领域取得了令人鼓舞的成果，例如： ( 】) 在股票数据分析方面，文f 4 6 j 应用卡n 糙集方法分析了十年| 、j 股票的历 史数据，研究了股票价格与经济指数之间的关系，获得的预测规则得到了华尔衔 证券交易专家的认司。 ( 2 ) 在医疗诊断方面，相糙集方法根据以往的病例归纳旧诊断规则，用柬 指导新的病例。现有的人工预测早产的准确率只有1 7 一3 8 ，利用粗糙集理论 则可提高到6 8 一9 0 ”1 。 ( 3 ) 在模式识别方面，文 4 7 应用粗糙集方法研究了手写字符u 别问题， 提取出了特征属性。 ( 4 ) 在决策分析方面，文4 8 ，4 9 应片j 苄h 糙集方法，生决策规则，它允许决 策对象中存在一些4 i 太精确、小太完整的属性，弥补孑常规决策方法的小足。希 腊工业发展银行f t e v a 应用粗糙集理论协助制定信贷政策，是半日糙集多准则决 策方法的一个成功范例。 ( 5 ) 在专家系统方面，文 5 0 利用粗糙集抽墩舰则，从而为构造专家系统 知识库提供了一条崭新的途径。 ( 6 ) 在数据库知识发现力面，k d d 是当前人工智能和数据_ | 车技术交叉学科 的研究热点之一。粗糙集方法已成为k d d 的一种重要方法，其导出的知识精烁 基丁粗糙集的粒度计算理论与方法研究 且更便于存储和使用。与其他知识发现方法比较，粗糙集方法有如下特点：粗糙 集方法的伸缩性强；鲁棒性和抗噪音能力强；知识的可理解性和开放性较好：比 较适合于符号信息。此外，半日糙集方法可以对数据进行预处理，去掉多余属性， 可提高发现效率，降低错误率。 虽然粗糙集理论至今只有二十年的发展历史，但取得的研究成果是令人瞩目 的。它是一种非常有前途的软计算方法，为处理不确定信息提供了强有力的分析 手段阢5 甜。我们相信粗糙集理论具有广阔的发展空间，今后会在更多的实际领域 中发挥作用。 1 2 粗糙集基本概念与记号 为了本文以后的研究需要，本节叙述一些有关粗糙集的基本概念与记掣3 1 。 1 2 1 近似集 一个近似空日js 是一个二元组s = ( u ，r ) ，其中u 是一个有限的非空集合， 称为论域，r 是u 上的一个二元关系，称为不可区分关系( 1 n d i s c e m i b i l i t y r e l “o n ) 。假设尺是一个等价关系。如果( x ，y ) r ，则说x 和y 在s 中是不可区 分的。关系r 的等价类称为s 中的基本集。假设对于每个近似空间s ，空集总是 基本集。 s 中任何有限集的并称为s 中的可定义集。s 中所有可定义集用d 旷( s ) 来表 尔。 设至u ，x 为u 中的一个对象。 x 】。表示所有与x 不可区分的对象组成的 集合，即由x 决定的等价类。集合x 关于r 的下近似定义为： 堡x = 忸u | 网re ) ， 足x 实际上是由那些根据已有知识判断肯定属于的对象所组成的最大集合，也 称为z 的j 下区域，记作尸( 姆。( ) 。由根据已有知识判断肯定不属于x 的对象所 组成的集合称为z 的负区域，记作e g 。( ) 。 集合x 关于r 的上近似定义为 尼y = x u l 【x 】nn x 奶， 砝是由那些根据已有知识判断可能属于x 的对象所组成的最小集合。显然， 砑u e g 。( x ) = u 。集合x 关于尺的边界区域定义为： b n ，t x 、= r x 一睦耳， 删。( 爿) 为集合的上近似与下近似之差。如果删。( x ) = ，则称关于r 是清 晰的；反之，如果b v 。( ) ，则称爿为关于月的半h 糙集。 州人学2 0 0 5 崩碗十学位论文 我们也可以将火x 看作为中的最大可定义集，将月看作为含何x 的最小 u ，定义集。 设s = ( ，月) 是一个近似空间，( ，且x 中。粗糙集肖关于只的近似精 度定义为”3 ： 讯卟黑c x 关于只的粗糙度定义为”1 ： ph i x l ：、“r t x ) 。 1 。2 2 信息系统与不完备信息系统 一个信息系统( i n r ) r m a t i o ns y sc e m s ) 是一个序对s = ( “爿) ，其中： ( 1 ) u 是对象的非宅有限集合； ( 2 ) 彳是属性的i 空有限集合； ( 3 ) 对于每一个d 爿，山一个映射h ，：( j 斗圪，这卑k 称为口的值集。 每一个属性子集尸爿决定了一个二元不可区分关系，a 口( 尸) ： ，d ( p ) = ( x ，y ) u u l v 口j p ，口“) = 口( ) 。 如果( x ，) 从( j d ) ，我们说x 和y 是尸不可区分的。容易证实，d ( 尸) 是 上的等价关系。 关系删d ( p ) ，p 爿，决定了u 的一个划分，我们用u n 忉( | d ) 柬表示。 u 肌，d ( p ) 中的任何元素 x 】。称为等价类或信息颗粒，这翠 【工】，2 yf ( 工，y ) ，d ( 尸) 。 令u d ，d ( j d ) 和u ，d ( q ) 是论域u j 一的不可区分关系j p 和9 导出的划 分，如果对于v f ，a 四( p ) ，存在，u ，a ，d ( 9 ) 使得。r ，7 ，则沁为 u l n d t p ) e u n d t q ) 。 信息系统s = f u 一) 也称为知泌表达系统或知识爿。 在不产生混淆的情况下，我们也丌丁，) 求代替，d ( 尸) 。 令 u 爿= 月i 月2 ，足。， 。 当然，有趣的是最小划分 爿( u ) = ( x ：茁u ， 和最大划分 ，i ( = u 。 基于粗糙集的粒度计算理论与方法研究 如果论域不会引起混淆我们也可以将爿( 和4 ( 记为爿和爿。 设，和p 是有限集u 上的划分，定义偏序关系 如下： 尸! q 铮v 只p ，j q ，q 尸互9 ， 其中p q 表示划分9 比划分p 粗糙( 或者划分j d 比划分q 精细) 。 如果尸19 且尸( 7 ，则称划分q 比划分户严格粑糙( 或者划分p 比划分q 严格精细) ，记为j d - p 。 在一些情况下，对一个对象而言，一些属性值可能是缺损的。例如，在医学 信息系统中，可能存在这样一组病人，它们不能执行所有要求的检查。一种解决 方法是这些缺损值可以通过对应属性的所有可能值的集合来表示。为了表示这种 情况，一个区分值( 即空值) 通常安排给这些属性。 如果对于至少一个属性a 爿， 包含空值，则称s 是一个不完备信息系统 ( i n c o m p l e t ei n f o m a t i o ns y s t e m ) ，否则它是完备的。这表明完备信息系统是不 完备信息系统的一种特殊情形。进一步，我们将用+ 表示空值。 设p 爿，我们定义相容关系： j s z ( p ) = ( “，v ) u u v d p ，d ( “) = 口( v ) 或d ( “) = 或日( v ) = + ) 。 易知 肼吖( p ) = f 1 脚m ( 盯 ) 。 口， 令s ，( “) 表示对象集 v ( ，i ( “，v ) s f ( p ) ) 。s ，( “) 是与“可能不可区分的 对象的最大集合( 相对尸而言) 。 设【，s ，m ( p ) 表示分类，即一族集合 s ，( “) “u ) 。u & m ( 尸) 中的元素称 为相容类或信息颗粒。u 田m ( j d ) 中的相容类一般不构成u 的划分，它们构成 u 的覆盖，即对于每一个“u 有s ，( “) m ，且u 砩( “) 2 u 。 u ， 设u 且j d 爿，则是j 的下近似，当且仅当 p = uf 一向) x 啊 x fs ，( x ) z 。 蹦是x 的上近似，当且仪当 x = x u | s ，( x ) n x 中 = u s ，j ( x ) ix x ) 。 与完备信息系统一样，蹦是肯定属于的对象的集合，而j p x 是可能属于 一的对象的集合 用u s m ( 爿) = 邑( “) l “u ) 束表示分类，有趣的是最细分类 爿( = ( s 。( “) = 拟 i “u 和最粗分类 匀( ，) = 瓦( “) = f j l “u 。 如果论域不会引起混淆，办可将j ( u ) 和j ( j ) 简记为j 和妇= 设s = ，一) 是一个不完备信息系统，尸，9 一，定义偏序关系! 如f ： ，塑对v 1 ，2 小uj ，我们有s ，( “，) s ，( “，) ，其巾尸受表示p 比 p 翔糙( 或者j d 比p 粘细) 。 如果尸二q 且尸q ，! i ! 称q 比尸严格苄h 糙( 或者，) 比9 严格精细) ，汇为 p 9 。 事实上，j d _ q 告列v f l ，2 ，“u ) ，我们有s ，( “，) es ( j ( “，) ，并且存存 1 ，2 ， | uj ，使得s ，( “，) cs ( ，( “，) 。 1 2 3 约简与核 信息系统中的知识并不是同等重要的，甚至其中某些知识是冗余的，因此需 要在保持知识库分类能力不变的条件下，删除其中不相关的知识，即知l t 约简。 独立、约简和核是利用粗糙集进行知 _ 约简时用到的三个主要概念。 定义 1 1 ”f 设s = ( u ，爿) 是一个信息系统，d 爿，如粜 n 仍( 爿) = 删d ( 爿一 “j ) ，则称d 为爿中不必要的；否则称d 为一中必要的。 定义1 2 “设s = ( u ，爿) 是一个信息系统，如果每一个“4 都为爿中必要 的，则称爿为独立的；否则称爿为依赖的。 定义1 3 。”设s = ( 爿) 是一个信息系统，尸爿。如果户是独立的，日 ，a r d ( p ) = 删d ( 爿) ，则称尸是爿的一个约简。 定义1 4 h 设s = ( u ，爿) 是一个信息系统，爿中所何必要关系组成的集合称 为爿的核，记作f o ，p ( 爿) 。 1 3 粒度计算理论的历史与现状 1 3 1 粒计算基本问题概述 粒计算中存在许多基本问题，如空问的糖化、粒的描述和使用粒的计算等： 空间的粒化是指将对象窄问分解为许多子空问，或是基于有用的信息和知识将窄 问中的个体聚集成不同的类，每一个类称为一个粒，粒中的元素可以理解为对h i 概念的实例。粒计算可以和概念生成、知识发现和数据挖掘联系起柬，冈为概念 生成的目的之一是对只有某些概念的粒表示、特征化、描述和解释，而知识发现 和数据挖掘的个重要方面就是在颗粒之间建市关联和冈果等联系。 粒计算问题可以从两人方面来进行研究：粒的构造和使用粒的计算。i 口者处 基r 牛h 糙集的粒度计算理论与方法研究 理粒的形成、表示和解释，后者处理在问题求解中运用粒。同时粒计算的研究可 以从语义和算法的层面展开”“。粒计算中这两方面都同等重要。 通俗的讲，粒计算的语义研究侧重“为什么”这类问题，侧重于粒的解释， 如为什么两个对象会在同一个粒之中，为什么不同的粒相关。一般来讲，每一个 粒中的元素满足不可分辨关系、相似性、邻近性或泛函性，同时信息粒化也基于 这些关系。由于对论域不同的分类标准( 等价、相容、泛序、异同等关系) 可能 会形成不同粒的结构，因此有必要研究这些关系的语义解释，如相似性 ( c l o s e n e s s ) 、关联性( a s s o c i a t i o n ) 、依赖性( d e p e n d e n c y ) 。粒的结构不同对论 域的任一子集的近似集和对这些基本粒的操作会有所不同，并导致算法的时间、 空问复杂度有很大差别，因此粒化要根据实际问题的需要进行。 粒计算的算法研究关注“如何”这类问题，即如何进行粒化和如何进行基于 粒的计算。很有必要研究粒计算的方法学和工具( 如近似、推理等机制) 。针对 粒的分解与合并方法的研究，是构建任何粒度体系结构的本质要求。 1 32 粒化模型 ( 1 ) 框架模型 当前存在许多信息粒化方法：集合论和区间分析、f u z z y 集、v a g u e 集、集 对分析及其相互关联、可拓集、灰度集、证据理论、神经网络、结块( c h u n k i n g ) 、 决策树、语义网络、a d 转换、约束规划、聚类分析”等。粒计算的主要形式框 架有如下五种： ( 1 ) 集合理论和区间分析 ( 2 )模糊集 ( 3 ) 耜糙集 ( 4 )概率论 ( 5 )商空间理论 虽然上述模型大多是独立发展起来的，彼此之阳j 并没有多少互相影响，但它 们最终都统一于粒计算这个框架下，这从个侧面说明粒计算本身是一种更为基 础的问题求解方法。 从更通用的观点来看，定义在某种空间五上的粒可视为空间的映射一： 工斗g f x ) 。其中，是某个空问，4 是所描述的粒，g 表示粒的形式框架”。 粒的类型是由定义它的约束类型来确定的，如模糊集、集合理论、概率约束 分别定义了模糊粒、集合粒和概率粒。 山阿人学2 0 0 5 届硕士。学何沦义 ( 2 )粒的概念和层次 直观地讲，粮的大小描述了其特异性，粒中i 素越多，它就越抽象越通用。 粒计算的研究包含一系列重大的方法学和算法上的问题。信息粒化的层次耿 决于所要求解的问题。信，皂粒用来观察和描述问题井同外界交互，它lu 视为概念 的构造块，决定了柁度的层次。在此，我们把信息粒视为一种执行有效计第的机 制。在问题求解中要选择最合适的粒度层次。信息粒在粒度的不同水平出现，通 常把最相似的粒度聚集为一层。信息粒度表明不同粒化模型的使用在某个特定的 粒度层次卜是相关的。 如何评估这些不同的构造模型呢? 一般来讲，任何评估标准都和信息粒的粒 度有关而且评估和模型测试应该和所设计模型相符合，即评估使用的信息粒在 特异性( 粒大小) 上和所评估模型构建的信息粒相比应相同或更小。 不同的粒世界很少独立存在，可以认为不同的粒计算环境对应小同的a p e n t ， 它们之间相互发生作用( 协作和竞争) ，因而粒1 廿界问的通信问题转变为这些 a g e n t 之间的通信刚题。 ( 3 ) 粒计算模审的特点、相互关系及应用 我们可以将粒度计算视为一个新的处理信息粒的多种方法的聚合体，这些疗 法( 模型) 之目存存着什么样的联系呢? 学术界在各个方面进行了- _ 系列研究 ”，因篇幅所限，本文在此不做具体分析，而只迸行概要的论述。 商空f i 口j 理论和柑糙集理论的共同点是用等价关系来描述粒，用粒来描述概 念。但商空间理论研究不同粒度世界之问的相互转换、斗爿瓦依存的关系，是描述 空间关系学的理论；而r o u 冀h 集主要是研究粒的表示、刻画和粒与概念之间的 依存关系。 经典集合论、模糊集和粗糙集都把元素与分类的关联度看成不变的，是从“静 态”的角度考察事物。可拓集考察动态的事物和变化的过程，把分类与时空变换 联系起来，元素的分类是可以改变的，其关联度也是可变的。这为矛盾问题转化 为相容问题提供了依据。 人脑思维对客观事物的识别和分类并不只有一个模式，从而描述这种能力的 方法也是多种多样的。经典集合论和区间分析是以二值逻辑为基础的，用集合中 元素的多少来描述信息粒的特异性。概率论的创立源丁博弈论，认为不确定的时 间事件之间存在某中概率关系，概率粒的特点是粒用一些概率函数柬表示。z p a w l a k 认为对事件的分类能力体现了人类智能，故他创市了基于等价关系分类 基丁粗糙集的粒度计算理论与方法研究 的r 0 u 曲集( 粗糙集) ，并用上下近似集来描述一个集合的概念。而la z a d e h 认为粒的模糊性源于属性值的模糊性和关系概念的模糊性，并认为非模糊的粒化 模型不能反映现实中推理及概念生成中的模糊问题。故他创立了f u z z y 集( 模糊 集) ，用元素对集合的隶属度来描述这种模糊的概念。模糊信息粒化也构成了人 类在不确定性环境中做出合理决策的能力的基础。张钹、张铃认为人类智能表现 为人们能从极不相同的粒度上观察和分析同一问题，故他们共同创立了商空间理 论。数学中的矛盾方程、矛盾不等式所描述的问题原形，实际上很多是有解的， 认为“无解”是因为只考虑数量关系而没有把事物和特征引入数学。因此蔡文提 出了可拓集合来描述“是”与“非”的相互转化，从而能定量的表述事物的质变 和量变的过程，这为矛盾问题的解决提供了合适的数学工具”驯。 在数据压缩、信息检索以及通讯领域，利用不精确性、不确定性以及近似表 达将起到重要作用。此时，模糊集、粗糙集模仿人类进行推理、形成概念从而提 供处理不精确信息的方法，并应用于数据挖掘、控制问题和图象处理等有连续边 界的概念的形式表述之中。 在问题求解过程中，特别是在智能系统的概念及设计中，可以同时利用粒计 算的两个或多个模型从而产生混和智能系统。目前最常见的是n e u r o