《粒计算下的粗糙集模型对比.doc》由会员分享，可在线阅读，更多相关《粒计算下的粗糙集模型对比.doc（12页珍藏版）》请在三一文库上搜索。
1、粒计算下的粗糙集模型对比摘 要:提出了几种组合粒下的粗糙集模型，并将其与单一粒下的粗糙集进行了对 比,同时又与粒逻辑运算下的粗糙集模型进行比对 ，创造性地得到了组合粒、单一 粒以及粒逻辑运算下的粗糙集模型之间的关系。结果表明，组合粒与粒逻辑运算构成了一个链结构，这为探讨基于信息粒的知识获取以及动态粒的推理奠定了基 础。关键词:组合粒;粒逻辑运算；单一粒;粗糙集;近似Comparis on of rough set model un der granu lar computi ngZHANG Xiao-feng, ZOU Hai-lin, JIA Shi-xiang(School of In f
2、ormati on Scie nee & Engin eeri ng, Lud ong Uni versity.Ya ntai Sha ndo ng 264025, Chi na)Abstract:This paper proposed the rough set model un der comb in ati ongranule, and compared it with that under single granular, also with rough set model un der logical comput ing of granu le, which con tri
3、buted to therelatio nship betwee n rough set models un der comb in ati on granu le, sin gular granu les and logical computi ng of granu les. Results show that comb in ati on granule and logical comput ing of granule con struct a cha in, which will lay a foun dati on for kno wledge acquisiti on based
4、 on in formati on granule and in duct ion based on dyn amic granu le.Key words:combination granule; logical computing of granule; single granu lar; rough set; approximati on0引言粒度计算是由Zadeh1于1996年提出,他认为，人类认识主要基于三个主要 概念,即粒度、组织和因果。其中粒度计算是一把伞，涵盖了有关粒度计算的理论、方法论、技术和工具的研究，在粗糙集理论、概念格、知识工程、数据挖掘、人 工智能、机器学习等领域有潜
5、在的应用，已成为信息科学的研究热点之一 2职称 论文。粗糙集3定义为给定关系上集合的上近似与下近似构成的有序对，已被成功地应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域4 o传统的粗糙集理论是基于单一粒定义的，即静态粒。文献57提出了多粒运算下 的粗糙集理论模型,即 MGRS(multi-granulations rough set,MGRS),并讨论了相关的数学性质。考虑到文献57中主要讨论了集合在粒度 P和Q的P+Q PA Q 运算下的上下近似集合，本文对多粒运算下的粗糙集模型进行了进一步的讨论，并将其与单一粒度下的粗糙集模型进行了比较；同时,将多粒运算下的粗糙集模型与组合粒
6、度下的粗糙集模型进行了 ？比较。1相关概念本章给出的相关概念对于后续部分给出的讨论是必要的。定义1命题逻辑中,命题P和Q的合取记为PA QPA Q为真当且仅当P和Q 同时为真；命题P和Q的析取记为PV Q,PV Q为假当且仅当P和Q同时为假。定义2信息系统是一个四元组(U,A,V,f)。其中,U是对象的集合,称为域 (universe);A 是用来描述对象的属性的集合；V是属性集A的值域；f:U x A V 反映的是某个对象在某个属性上的取值，信息系统通常略写为(U,A) o定义3给定一个非空的域U,UX U的子集EUX U表示域U上的一个关系。有 序对(U,E)称为一个近似空间8(appro
7、ximation space) 。如果关系E满足自反性、对称性和传递性，则E称为一个等价关系9 o等价 关系E对域U可以形成一个划分，记为U/Eo可以证明，等价关系和划分是等价的， 即给定一个等价关系，可以构造域的划分；同样,给定域的一个划分，可以构造域 上的一个等价关系。信息系统(U,A)中,如果两个体x,y U在属性a A上取值相同，则称两者在 属性a上是不可分辨的。如果x,y在集合BA中的每一个属性b B都是不可分辨 的,则称两者在集合B上是不可分辨的。与x在集合B上不可分辨的所有个体的 集合称为x在集合B上生成的等价类,记为x?B,它可以看成是由与x不可分辨 的元素构成的信息粒8(in
8、formation granule)。定理1域U上所有元素在集合A上生成的等价类满足以下三个条件9:a) ?x U,有x?A 工?;b) ?x,y U,或者x?A=y?A 成立，或者x?A n y?A=?成立；c) U x Ux?A=U。该定理表明，在集合A上生成的所有等价类构成了域的一个划分，这些等价 类称为基本等价类。定义4对域U的任一子集XU而言,如果它可以表示成某些等价类的并集,称 x是精确的(或者称为可定义的),否则称为粗糙的。如果一个概念 XU是粗糙的， 则可以用两个精确定义的集合来近似，分别称为X的下近似或上近似，记为PX和 X,定义如下：PX=J x?PXx?Px=u x?P
9、n xm ?x?P其中:x?P=y|f(x,P)=f(x,P) 是由x在属性集P上生成的等价类。显然有 下式成立：PXXX定义5如果集合X是粗糙的，有序对PX,X称为它的粗糙集。该粗糙集的 近似质量a ?P(X)定义如下：a ?P(X)=|PX|/|X|2几种基于粒运算的粗糙集模型定义6给定信息系统(U,A),P,QA。假设由P,Q对域可以构造相应的划分为U/IND(P)=x?1?P,x?2?P,x|U|?PU/IND(Q)=x?1?Q,x?2?Q,x|U|?Q则由P和Q构成的两个组合粒定义为u/ind(p n Q)=x?1?P n x?1?Q,x|U|?P nx|U|?Q(1)U/IND(P
10、 U Q)=x?1?P Ux?1?Q,x|U|?P U凶 U|?Q(2)例女口信息系统(U,A)中,XU 且 P,QA 。 其中U=e?1,e?2,e?3,e?4,e?5,e?6,e?7,e?8,X=e?1,e?2,e?5,e?7,e?8 。由 P,Q 对域形成的划分分别为U/IND(P)=e?1,e?7,e?2,e?3,e?4,e?5,e?6,e?8U/IND(Q)=e?1,e?2,e?3,e?4,e?5,e?6,e?7,e?8因此有U/IND(P n Q)=e?1,e?2,e?3,e?4,e?5,e?6,e?7,e?8U/IND(PUQ)=e?1,e?2,e?7,e?1,e?2,e?3,e
11、?4,e?5,e?6,e?2,e?3,e?4,e?5,e?6,?e?2,e?3,e?4,e?5,e?6,e?7,e?8,e?1,e?6,e?7,e?8,e?8定理2 U/IND(P n Q)形成域的划分,而U/IND(PU Q)形成域的覆盖。证明由于等价关系满足自反性,对由P,Q构造的等价类x?i?P和x?i?Q, 有 x?i x?i?P 且 x?i x?i?Q。因此有? U x?i(x?i?P n x?i?Q)= U x?ix?i?P U x?i?Q)=U 成立,同时有？x?i?P n x?i?Q 工？,x?i?P U x?i?Q 丰?,即 U/IND(P n Q)和 U/IND(P U Q
12、)形成了域的覆盖。进一步考虑,如果x?j x?i?P n x?i?Q,如果x?j工x?i,则有x?j x?i?P,x?j x?i?Q。由于x?i?P 和x?i?Q 均是等价类，根据定理1可得x?i x?j?P,x?i x?j?Q 成立,即 x?i x?i?P n x?i?Q 成立。女口果 x?j?x?i?P n x?i?Q, 则可能有以下三种情 况：a)x?j?x?i?P,x?j?x?i?Q;b)x?j?x?i?P,x?j x?i?Q;c)x?jx?i?P,x?j?x?i?Q。 相应地,根据等价类的性质可得：a)x?i?x?j?P,x?i?x?j?Q;b)x?i?x?j?P,x?i x?j?Q
13、;c)x?i文章来源网，仅供分享学习参考x?j?P,x?j?x?i?Q, 因此有 x?i?x?j?P n x?j?Q 。通过上述两种情况可得,或者x?i?P n x?i?Q=x?j?P n x?j?Q 成立, 或者(x?i?P n x?i?Q) n (x?j?P n x?j?Q)=?成立，因此 U/IND(Pn Q)构成 了域的一个划分。证毕。定义7给定信息系统(U,A),P,QA,XU,定义组合粒下的粗糙集如下：Pn qx=j(x?P n x?q)x(x?P n x?Q)Pn qx=j(x?P n x?Q)n x?(x?P n x?Q)PU QX=J (x?P n x?Q)X(x?P U x
14、?Q)pu qx=u(x?P n x?Q) n xm?(x?P U x?Q)文献10中曾经定义了粒逻辑运算下的粗糙集模型，如定义&定义8给定信息系统(U,A),P和Q是信息系统的两个信息粒,则粒逻辑运算 下的粗糙集模型定义为PA QX=U x|(x?PX)A (x?QX)PA QX=U x|(x?Pn Xm ?) A (x?Q n Xm ?)PV QX=U x|(x?PX)V (x?QX)PV QX=U x|(x?Pn Xm ?) V (x?Q n Xm ?)下面将讨论组合粒下的粗糙集与单粒下的粗糙集模型之间的关系以及组合 粒下的粗糙集与粒逻辑运算下的粗糙集之间的关系。3单一粒与多粒运
15、算下粗糙集的关系笔者已经证明了下面的定理。定理3给定信息系统(U,A),P,QA,XU，则有PA QX=PX1 QXPA QX=X XPV QX=PXJ QXPV QX=XJ X运用本文提出的组合粒，并将其与粒逻辑运算下的粗糙集模型进行进一步比 对,可以得到下面的定理。定理4给定信息系统(U,A),P,QA,XU则有PXA QX?P QXPn qxx x证明a) ?x PXn QX根据定义有x?PX且x?PX成立,因此有x?P n x?QX,即 x ?pn qx成立。因此有 Pxn ?Qx?n qxb) ?x ?pn QX有(x?P n x?Q) n X ?。由于x?P n x?Qx?P,x?
16、Pn x?Qx?Q,有x?P n “ ?并且x?Q n x ?,因此有 x xn x,即 Pn qxx x。 证毕。该定理说明两个粒度 P,Q组合产生的商空间U/IND(P n Q)比组合粒度PA Q 构造的知识更细，因而对集合X的逼近更为准确。定理5给定信息系统(U,A),P,QA,XU，则有PU QX=Pn QXPU QX=XJ X证明a) ?x ?P U QX,有x?P U x?QX 成立。由于x?Px?P Ux?Q,x?Qx?P U x?Q,有x?PX 和x?QX 成立,即x PX且 x QX 因此有 x PXn QX即卩PU QXPK QX成立。?x PXn QX根据定义有x PX且
17、x QX,因此有x?PX和x?QX成立。由 于x?PX 和x?QX 成立，有x?P U x?QX 成立。因此有 x ?PU QX即卩 PXn QX?P U QX综合上述两点可得？P U QX=Pn QXb) ?x ?PU QX有 (x?P Ux?Q) n X ?,因此有x?P n X ?或x?Q n X ?,即 x X 或 x X成立,x XU X。因而可得?PU QXXJ X成立。?x XU X,有 x X 或 x X 成立,即x?P n X ?或x?Q n X ?。由于 x?Px?P U x?Q,x?Qx?P U x?Q,可得(x?P U x?Q) n X ?成立。因此 有 x ?PU Q
18、X即卩 XU X?PU QX根据上述两点可得PU QX=XJ X。证毕。该定理表明组合粒PU Q下的粗糙集模型可以由单一粒下的粗糙集模型构造 出。4不同粒运算下的粗糙集模型的关系既然可以在组合粒、粒逻辑运算等不同的粒运算下都可形式化相应的粗糙集，那么产生一个问题：不同粒运算下的粗糙集之间有什么关系 ？定理6给定信息系统(U,A),P,QA,XU，则有PU QX?n QXPn QX?PJ QXa PU Q< a Pn Q证明a) ?x ?PU QX有x?P U x?QX,因此可得x?PX且x?QX。由此可以推断 出x?P n x?qx,即 x ?pn qx 因此有 pu Qx?n qxb)
19、 ?x ?p n qx,根据 定义有(x?p n x?q)n x 丰?；又由于x?p n x?Qx?P U x?Q,有(x?P U x?Q) n XM ?,可得?x ?PU QX,因此有？Pn QX?PJ QXc) 由于pu Qx?n qx,有|?P U QX|< |?P n QX|;由于Pn qx?u qx,有|?p n qx|< |?p u qx。因此,? a pu q< a Pn q证毕。定理7给定信息系统(U,A),P,QA,XU，则有PA QX?n QXpn QX?A QXa PA Q< a Pn Q证明a) ?x ?PA QX有x?PX 且x?QX 成立，因
20、此可得(x?P n x?Q)X 成立。 因此有PV QX?n QXb) P n qx=u x|(x?pn x?Q) n xm ?,?p a qx=?j x|(x?p n xm ?)a(x?q n x ?)。?x ?pn qx有(x?p n x?Q) n xm ?。由于x?p n x?Qx?p且x?p n x?qx?q,可得x?p n xm ?且？x?Q n XM ?,有 x ?PA QX 因此有 pn QX?A QXc) 由于 pv Qx?n qx,有|?p v qx|< |?p n qx|；同时,由于 pn qx?a qx,有 |?P n QX|< |?P A QX| o 因此
21、a PA Q< a Pn Q成立。证毕。定理8给定信息系统(U,A),P,QA,XU，则有PV QX?P QXPn QX?V QXa PV Q a Pn Q证明a) ?x ?PV QX有x?PX 或x?QX 成立。由于？x?P n x?Qx?P 且x?P n x?Qx?Q,有x?P n x?QX 成立,则有 x ?pn QX成立。因此有 PV QX?n QXb) ?x ?pn QX有(x?P n x?Q) n XM ?。由于x?P n x?Qx?P 且x?P n x?Qx?Q。有x?P n X ?和 x?Q n X ?成立,则有 x ?PV QX 因此有 P n QX?V QXc) 由于
22、 pv Qx?n qx,有|?p v qx|< |?p n qx|；由于 Pn qx?fv qx,有|?p n QX|< |?P V QX|。因此 a PV Q< a pn Qo证毕。定理9给定信息系统(U,A),P,QA,XU，则有PA QX=?RJ QXPA QX?PJ QXa PU Q< a PA Q证明a)?x ?PU QX根据定义可得(x?P U x?Q)X 成立,根据集合之间的关系可得x?PX和x?QX成立。因此有x PA QX成立，即PU QX?A QX?x ?PA QX有(x?PX 和x?QX 成立,因此有(x?P U x?Q)X,即 x ?PU QX,
23、因此 PA QX?U QX综合这两种情况有PA QX=?U QXb) ?x ?PA QX有x?P n Xm ?且x?Q n Xm ?成立。由于x?Px?P U x?Q,必然有(x?P U x?P) n XM ?,即 x ?PU QX。因此有 PA QX?U QX成立。c) 由于 PA QX=?PJ QX有 |?P A QX|=|?P U QX|;由于 PA QX?FU QX有|?P A QX|< |?P U QX|。因此可得 a PU CK a PA Q。证毕。定理10给定信息系统(U,A),P,QA,XU，则有PU QX?P/ QXPV QX?PJ QXa PV QK a PU Q证明
24、a) ?x ?PU QX有 x?P U x?QX 成立;由于x?Px?P U x?Q,可得x?PX,即 x ?PV QX因此有PU QX?P/ QXb) ?x ?PV QX有x?P n Xm ?或x?Q n XM ?成立。由于x?Px?P U x?Q,x?Qx?P U x?Q,上述两种情况中的任何一种均可推导出(x?P U x?Q) n Xm ?。因此有 PV QX?PJ QXc) 由于 PU QX?P QX有|?P U QX|W |?P V QX|;由于 PV QX?PJ QX,有 |?P V QX|?PU QX|。因此可得 a PV CKa PU Q证毕。通过上述各定理可以得到组合粒下的粗
25、糙集模型与粒逻辑运算下的粗糙集 模型之间的关系，并且发现在相关粒下的知识粗糙度具有如下关系：a PV Q a PU Q< a PA Q< a PA Q基于此,从另一个角度给出知识粗细的形式化定义。定义9给定信息系统(U,A),P,Q是两个信息粒构造的商空间，称P?Q,如果对 任意集合XU,均有a ?CK a ?P成立。实际上,如果P?Q则由粒集合P提供的知识比由Q提供的知识更细。基于上 述相关定理，可以得到下面的结论。定理 11P V Q,PU Q,PA Q,PA Q,?是一个链。证明略。5结束语本文讨论了单粒运算与多粒运算下粗糙集之间的关系以及不同的多粒运算 下粗糙集之间的关系这
26、两个问题，对于进一步研究动态粒的结构以及基于动态粒 的知识获取奠定了良好的基础。参考文献：1 ZADEH L A.Fuzzy logic=computing with wordsJ.IEEE Trans on Fuzzy System, 1996,4(1):103-111.2 梁吉业，钱宇华.信息系统中的信息粒与熵理论J.中国科学E 辑,2008,38(12):2048-2065.3 PAWLAK 乙Rough setsJ.InternationalJournal of Computer andIn formation Scie nces,1982,11(5):341-356.4 张文修，吴伟
27、志，梁吉业，等.粗糙集理论与方法M.北京：科学出版 社,2001.5 QIAN Yu-hua,LIANG Ji-ye.Rough set method based on multi-granulationsC/Procof the 5th IEEE Conference on CognitiveIn forma-?tics.New York:IEEE Press,2006:297-304.6 QIAN Yu-hua 丄 IANG Ji-ye,DANG Cha ng-yi n.MGRS in in complete information systemsC/Proc of IEEE Intern
28、ationalConference onGran ular Computi ng.New York:IEEE Press,2007:163-168.7 QIAN Yu-hua,LIANG Ji-ye,YAO Yi-yu,et al.MGRS:a multi-granulation rough setJ.Information Sciences,2009,180(6):949-970.8 YAO Yi-yu.Stratified rough sets and granu lar computi ngC/Procof the 18th InternationalConference of the North American FuzzyIn formation Processi ng Society.New York:IEEE Press,1999:800-804.9 傅彦,顾小丰,刘启和,等.离散数学M.北京：高等教育出版社,2008.文章来源网，仅供分享学习参考