1、粒计算下的粗糙集模型对比摘 要:提出了几种组合粒下的粗糙集模型,并将其与单一粒下的粗糙集进行了对比,同时又与粒逻辑运算下的粗糙集模型进行比对,创造性地得到了组合粒、单一粒以及粒逻辑运算下的粗糙集模型之间的关系。结果表明,组合粒与粒逻辑运算构成了一个链结构,这为探讨基于信息粒的知识获取以及动态粒的推理奠定了基础。关键词:组合粒;粒逻辑运算;单一粒;粗糙集;近似 Comparison of rough set model under granular computing ZHANG Xiao-feng, ZOU Hai-lin, JIA Shi-xiang (School of Informati
2、on Science Engineering, Ludong University, Yantai Shandong 264025, China) Abstract:This paper proposed the rough set model under combination granule, and compared it with that under single granular, also with rough set model under logical computing of granule, which contributed to the relationship b
3、etween rough set models under combination granule, singular granules and logical computing of granules. Results show that combination granule and logical computing of granule construct a chain, which will lay a foundation for knowledge acquisition based on information granule and induction based on
4、dynamic granule. Key words:combination granule; logical computing of granule; single granular; rough set; approximation 0 引言 粒度计算是由 Zadeh1于 1996 年提出,他认为,人类认识主要基于三个主要概念,即粒度、组织和因果。其中粒度计算是一把伞,涵盖了有关粒度计算的理论、方法论、技术和工具的研究,在粗糙集理论、概念格、知识工程、数据挖掘、人工智能、机器学习等领域有潜在的应用,已成为信息科学的研究热点之一2职称论文。 粗糙集3定义为给定关系上集合的上近似与下近似构成
5、的有序对,已被成功地应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域4。传统的粗糙集理论是基于单一粒定义的,即静态粒。文献57提出了多粒运算下的粗糙集理论模型,即 MGRS(multi-granulations rough set,MGRS),并讨论了相关的数学性质。考虑到文献57中主要讨论了集合在粒度 P 和 Q 的 P+Q、PQ 运算下的上下近似集合,本文对多粒运算下的粗糙集模型进行了进一步的讨论,并将其与单一粒度下的粗糙集模型进行了比较;同时,将多粒运算下的粗糙集模型与组合粒度下的粗糙集模型进行了?比较。 1 相关概念 本章给出的相关概念对于后续部分给出的讨论是必要的。 定义
6、 1 命题逻辑中,命题 P 和 Q 的合取记为 PQ。PQ 为真当且仅当 P 和 Q 同时为真;命题 P 和 Q 的析取记为 PQ,PQ 为假当且仅当 P 和Q 同时为假。 定义 2 信息系统是一个四元组(U,A,V,f)。其中,U 是对象的集合,称为域(universe);A 是用来描述对象的属性的集合;V 是属性集 A 的值域; f:UAV 反映的是某个对象在某个属性上的取值,信息系统通常略写为(U,A)。 定义 3 给定一个非空的域 U,UU 的子集 EUU 表示域 U 上的一个关系。有序对(U,E)称为一个近似空间8(approximation space)。 如果关系 E 满足自反性
7、、对称性和传递性,则 E 称为一个等价关系9。等价关系 E 对域 U 可以形成一个划分,记为 U/E。可以证明,等价关系和划分是等价的,即给定一个等价关系,可以构造域的划分;同样,给定域的一个划分,可以构造域上的一个等价关系。 信息系统(U,A)中,如果两个体 x,yU 在属性 aA 上取值相同,则称两者在属性 a 上是不可分辨的。如果 x,y 在集合 BA 中的每一个属性 bB都是不可分辨的,则称两者在集合 B 上是不可分辨的。与 x 在集合 B 上不可分辨的所有个体的集合称为 x 在集合 B 上生成的等价类,记为x?B,它可以看成是由与 x 不可分辨的元素构成的信息粒8(informati
8、on granule)。 定理 1 域 U 上所有元素在集合 A 上生成的等价类满足以下三个条件9: a)?xU,有x?A?; b)?x,yU,或者x?A=y?A 成立,或者x?Ay?A=?成立; c)xUx?A=U。 该定理表明,在集合 A 上生成的所有等价类构成了域的一个划分,这些等价类称为基本等价类。 定义 4 对域 U 的任一子集 XU 而言,如果它可以表示成某些等价类的并集,称 x 是精确的(或者称为可定义的),否则称为粗糙的。如果一个概念 XU 是粗糙的,则可以用两个精确定义的集合来近似,分别称为 X 的下近似或上近似,记为 PX 和 X,定义如下: PX=x?PXx?P X=x?
9、PX?x?P 其中:x?P=y|f(x,P)=f(x,P)是由 x 在属性集 P 上生成的等价类。显然有下式成立: PXXX 定义 5 如果集合 X 是粗糙的,有序对PX,X称为它的粗糙集。该粗糙集的近似质量 ?P(X)定义如下: ?P(X)=|PX|/|X| 2 几种基于粒运算的粗糙集模型 定义 6 给定信息系统(U,A),P,QA。假设由 P,Q 对域可以构造相应的划分为 U/IND(P)=x?1?P,x?2?P,x|U|?P U/IND(Q)=x?1?Q,x?2?Q,x|U|?Q 则由 P 和 Q 构成的两个组合粒定义为 U/IND(PQ)=x?1?Px?1?Q,x|U|?P x|U|?
10、Q(1) U/IND(PQ)=x?1?Px?1?Q,x|U|?P x|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(PQ)=e?1,e?2,e?3,e?4,e?5,e?6,e?7,e?8 U/IND(PQ)=e?1,e?2,e?7,e?1,e?2,e?3,
11、e?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(PQ)形成域的划分,而 U/IND(PQ)形成域的覆盖。 证明 由于等价关系满足自反性,对由 P,Q 构造的等价类x?i?P 和x?i?Q,有 x?ix?i?P 且 x?ix?i?Q。因此有?x?i(x?i?Px?i?Q)=x?ix?i?Px?i?Q)=U 成立,同时有?x?i?Px?i?Q?,x?i?Px?i?Q?,即 U/IND(PQ)和 U/IND(PQ)形成了域的覆盖。 进一步考虑,如果 x?jx?i?P
12、x?i?Q,如果 x?jx?i,则有x?jx?i?P,x?jx?i?Q。由于x?i?P 和x?i?Q 均是等价类,根据定理 1 可得 x?ix?j?P,x?ix?j?Q 成立,即 x?ix?i?Px?i?Q 成立。 如果 x?j?x?i?Px?i?Q,则可能有以下三种情况:a)x?j?x?i?P,x?j?x?i?Q;b)x?j?x?i?P,x?jx?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?ix?j?Q;c)x?ix?j?P,x?j?x?i?Q,因此有x?i?x?j?Px?j?Q。 通
13、过上述两种情况可得,或者x?i?Px?i?Q=x?j?Px?j?Q成立,或者(x?i?Px?i?Q)(x?j?Px?j?Q)=?成立,因此U/IND(PQ)构成了域的一个划分。 证毕。 定义 7 给定信息系统(U,A),P,QA,XU,定义组合粒下的粗糙集如下: PQX=(x?Px?Q)X (x?Px?Q) PQX=(x?Px?Q)X? (x?Px?Q) PQX=(x?Px?Q)X (x?Px?Q) PQX=(x?Px?Q)X? (x?Px?Q) 文献10中曾经定义了粒逻辑运算下的粗糙集模型,如定义 8。 定义 8 给定信息系统(U,A),P 和 Q 是信息系统的两个信息粒,则粒逻辑运算下的粗
14、糙集模型定义为 PQX=x|(x?PX)(x?QX) PQX=x|(x?PX?)(x?QX?) PQX=x|(x?PX)(x?QX) PQX=x|(x?PX?)(x?QX?) 下面将讨论组合粒下的粗糙集与单粒下的粗糙集模型之间的关系以及组合粒下的粗糙集与粒逻辑运算下的粗糙集之间的关系。 3 单一粒与多粒运算下粗糙集的关系 笔者已经证明了下面的定理。 定理 3 给定信息系统(U,A),P,QA,XU,则有 PQX=PXQX PQX=XX PQX=PXQX PQX=XX 运用本文提出的组合粒,并将其与粒逻辑运算下的粗糙集模型进行进一步比对,可以得到下面的定理。 定理 4 给定信息系统(U,A),P
15、,QA,XU 则有 PXQX?PQX PQXXX 证明 a)?xPXQX,根据定义有x?PX 且x?PX 成立,因此有x?Px?QX,即 x?PQX 成立。因此有 PX?QX?PQX。 b)?x?PQX,有(x?Px?Q)X?。由于x?Px?Qx?P,x?Px?Qx?Q,有x?PX?并且x?QX?,因此有 xXX,即 PQXXX。 证毕。该定理说明两个粒度 P,Q 组合产生的商空间 U/IND(PQ)比组合粒度 PQ 构造的知识更细,因而对集合 X 的逼近更为准确。 定理 5 给定信息系统(U,A),P,QA,XU,则有 PQX=PXQX PQX=XX 证明 a)?x?PQX,有x?Px?QX
16、 成立。由于x?Px?Px?Q,x?Qx?Px?Q,有x?PX 和x?QX 成立,即 xPX 且 xQX。因此有 xPXQX,即 PQXPXQX 成立。 ?xPXQX,根据定义有 xPX 且 xQX,因此有x?PX 和x?QX 成立。由于x?PX 和x?QX 成立,有x?Px?QX 成立。因此有x?PQX,即 PXQX?PQX。 综合上述两点可得 ?PQX=PXQX。 b)?x?PQX,有(x?Px?Q)X?,因此有x?PX?或 x?QX?,即 xX 或 xX 成立,xXX。因而可得?PQXXX 成立。 ?xXX,有 xX 或 xX 成立,即x?PX?或x?QX?。由于x?Px?Px?Q,x?
17、Qx?Px?Q,可得(x?Px?Q)X?成立。因此有 x?PQX,即 XX?PQX。 根据上述两点可得 PQX=XX。 证毕。 该定理表明组合粒 PQ 下的粗糙集模型可以由单一粒下的粗糙集模型构造出。 4 不同粒运算下的粗糙集模型的关系 既然可以在组合粒、粒逻辑运算等不同的粒运算下都可形式化相应的粗糙集,那么产生一个问题:不同粒运算下的粗糙集之间有什么关系? 定理 6 给定信息系统(U,A),P,QA,XU,则有 PQX?PQX PQX?PQX PQPQ证明 a)?x?PQX,有x?Px?QX,因此可得x?PX 且x?QX。由此可以推断出x?Px?QX,即 x?PQX。因此有 PQX?PQX。 b)?x?PQX,根据定义有(x?Px?Q)X?;又由于x?Px?Qx?Px?Q,有(x?Px?Q)X?,可得?x?PQX,因此有?PQX?PQX。 c)由于 PQX?PQX, 有|?PQX|?PQX|;由于 PQX?PQX,有|?PQX|?PQX|。因此,?PQPQ。
