·328· 智能系统学报 第13卷 Pawlak粗集模型基于等价关系，这种严格的要求在 族C,而勿需再去研究二元关系本身。此时，基于粒 一定程度上限制了粗集理论的应用。为了推广粗集 的广义上下近似算子可等效为 模型，可以把等价关系放宽为一般二元关系，在此 R()=U{C∈CICCX) (1) 情况下，由一般二元关系决定的论域上的集簇不再 R(X)=UC∈CCnX≠O) (2) “划分”。因此，另一种推广粗集模型的思路就是将 先对二元关系R,进行分析，令r(x)=y∈U川 原来由等价关系决定的“划分”放宽为“覆盖”，从而 (x,y)∈R称为元素x的后继邻域，由此定义得，r1(a)= 建立基于覆盖的粗集理论。但不同于经典粗集理 {a,b,n(c)=b,ch,其他元素的后继邻域为空集。非 论，基于覆盖的粗集理论不存在唯一的定义上下近 空后继邻域可以构成集族为：C={n(a),n(c)》= 似算子的方法。 {a,b1,{b,c},这就是二元关系R1诱导的集族。 已有很多文献对基于覆盖的粗集理论开展了卓 同理，二元关系R2诱导的集族C2={a,b, 有成效的研究-。姚一豫等系统地研究了基于覆 b.clo 盖的20对上下近似算子；Mauricio Restrepo等通 由此发现，R和R2诱导了相同的集族，因此它 过某些算子的相等关系将上下近似算子缩减为 们定义了相同的下近似运算。 再看二元关系R3,诱导的集族C3={a,b1,{b,c, 16对，并提出了算子精细度的概念，给了16对近似 {a,b,c}。与R1、R2诱导的集族并不相同，却也定义 算子的精细关系，并用哈斯图进行了描述。M.Res- trepo等则研究了基于覆盖的具有对偶性的l6对 了相同的下近似运算。下面的分析将回答该问题。 定义1设C是论域U上的一个集族，C∈C,如 上下近似算子的拓扑性质。在数据挖掘领域，去除 果C不能表示成C-{C中若干个元之并，则称C是 冗余属性，获取属性约简，从而简化知识的表示，提 C的既约元。否则，称C是可约元。 升数据处理效率是一个重要的研究课题。李立峰等阿 由此可见，集族中的元素可以分成既约元和可 研究发现覆盖粗糙集与形式背景之间存在一一对应 约元两类。 关系，并且证明了覆盖粗糙集的交约简可化为概念 定理1设C是论域U上的一个集族，C∈C是 格的属性约简；C.Wang等开发了一种基于覆盖粗 一个可约元，C'∈C-{C,则C是C的既约元当且仅 糙集的属性约简方法，这种启发式方法可以比较高 当它是C-(C,的既约元。 效地获得近似最优约简的属性集；Yang Bin等I8则 证明1)如果C是C的既约元，则C'不能表示成 将包含度的概念引入覆盖粗糙集，探索了一种新的 C-{C中若干个元之并，那么当然也就不能表示成 覆盖近似空间的若干性质。在覆盖粗集理论中，我 C-{C,C}中若干个元之并，因此C是C-{C,的既 们有基于元素、基于粒和基于子系统的3类定义上 约元。 下近似的途径，以往大多数的文献往往从基于元素 2)反之，如果C是C-{C的既约元，则C不能表 的角度出发进行定义，本文则以后继邻域作为基本 示成C-{C,C中若干个元之并，下面要证明C同样 研究对象“粒”，并以此为出发点，借鉴格论中既约 也不能表示成C-(C'}中若干个元之并，而这只需证 元、可约元等概念：0，探讨了（覆盖）集族中的既约 明C不能表示成C-C,C中若干个元之并与C的并 元、可约元、集族的约简及其算法，另外，研究了集 即可，即C不可能表示成CUC2 J...UCUC,其中 族与其生成的下近似算子的关系，为下一步开展基 C,C2,,Cn∈C-{C,C}。下面用反证法加以证明： 于粒的公理化方法的研究做一些初步的理论方面的 假设C能表示成C-{C,C中若干元与C之并， 准备工作。 即C'=C1UC2 U...UC.UC,其中C1,C2,…,Cn∈C- {C,C'。而C是一个可约元，故C又可表标成C-{C,C) 1 集族约简 中若干个元之并，即C=D1UD2UUDm,其中D, 下面来分析一个例子。 D2,…,Dm∈C-{C,C}。由此可得C'=CUC2UU 例1设论域U={a,b,c,d,其上有3个不同的 CnUD1UD2UUDm,其中C1,C2,…,Cm,D,D2,…, 二元关系分别为 Dm∈C-{C,C1。C表示成了C-C,C)中若干元之 并，这与C是C-{C的既约元矛盾，故假设不成立， R1={(a,a),(a,b),(c,b),(c,c)} R2={(b,a),(b,b),(c,b),(c,c)} 因此C是C的既约元。 R3={(a,a),(a,b),(c,b),(c,c),(d,a,(d,b),(d,c)} 由命题(1)、(2)得证。 基于粒的广义上下近似算子定义为后继邻域的 定理2设C是论域U上的一个集族，C∈C是 广义并，而并不考虑该后继邻域是哪一个元素的后 一个可约元，C∈C-{C,则C是C的可约元当且仅 继邻域。因此我们只需研究二元关系R诱导的集 当它是C-{C的可约元。Pawlak 粗集模型基于等价关系，这种严格的要求在 一定程度上限制了粗集理论的应用。为了推广粗集 模型，可以把等价关系放宽为一般二元关系，在此 情况下，由一般二元关系决定的论域上的集簇不再 “划分”。因此，另一种推广粗集模型的思路就是将 原来由等价关系决定的“划分”放宽为“覆盖”，从而 建立基于覆盖的粗集理论。但不同于经典粗集理 论，基于覆盖的粗集理论不存在唯一的定义上下近 似算子的方法。 已有很多文献对基于覆盖的粗集理论开展了卓 有成效的研究[2-8]。姚一豫等[3]系统地研究了基于覆 盖的 20 对上下近似算子；Mauricio Restrepo 等 [4]通 过某些算子的相等关系将上下近似算子缩减为 16 对，并提出了算子精细度的概念，给了 16 对近似 算子的精细关系，并用哈斯图进行了描述。M. Res￾trepo 等 [5]则研究了基于覆盖的具有对偶性的 16 对 上下近似算子的拓扑性质。在数据挖掘领域，去除 冗余属性，获取属性约简，从而简化知识的表示，提 升数据处理效率是一个重要的研究课题。李立峰等[6] 研究发现覆盖粗糙集与形式背景之间存在一一对应 关系，并且证明了覆盖粗糙集的交约简可化为概念 格的属性约简；C. Wang 等 [7]开发了一种基于覆盖粗 糙集的属性约简方法，这种启发式方法可以比较高 效地获得近似最优约简的属性集；Yang Bin 等 [8]则 将包含度的概念引入覆盖粗糙集，探索了一种新的 覆盖近似空间的若干性质。在覆盖粗集理论中，我 们有基于元素、基于粒和基于子系统的 3 类定义上 下近似的途径，以往大多数的文献往往从基于元素 的角度出发进行定义，本文则以后继邻域作为基本 研究对象“粒”，并以此为出发点，借鉴格论中既约 元、可约元等概念[9–10] ，探讨了 (覆盖) 集族中的既约 元、可约元、集族的约简及其算法，另外，研究了集 族与其生成的下近似算子的关系，为下一步开展基 于粒的公理化方法的研究做一些初步的理论方面的 准备工作。 1 集族约简 下面来分析一个例子。 例 1 设论域 U = {a,b, c,d} ，其上有 3 个不同的 二元关系分别为 R1 = {(a,a),(a,b),(c,b),(c, c)} R2 = {(b,a),(b,b),(c,b),(c, c)} R3 = {(a,a),(a,b),(c,b),(c, c),(d,a),(d,b),(d, c)} 基于粒的广义上下近似算子定义为后继邻域的 广义并，而并不考虑该后继邻域是哪一个元素的后 继邻域。因此我们只需研究二元关系 R 诱导的集 族 C ，而勿需再去研究二元关系本身。此时，基于粒 的广义上下近似算子可等效为 R(X) = ∪{C ∈ C|C ⊆ X} (1) R¯ (X) = ∪{C ∈ C|C∩X , Ø} (2) r(x) = {y ∈ U| (x, y) ∈ R} r1 (a) = {a,b} r1 (c) = {b, c} C1 = {r1 (a),r1 (c)} = {{a,b},{b, c}} 先对二元关系 R1 进行分析，令 称为元素 x 的后继邻域，由此定义得， ， ，其他元素的后继邻域为空集。非 空后继邻域可以构成集族为： ，这就是二元关系 R1 诱导的集族。 C2 = {{a,b}, {b, c}} 同理，二元关 系 R 2 诱导的集族 。 由此发现，R1 和 R2 诱导了相同的集族，因此它 们定义了相同的下近似运算。 C3 = {{a,b},{b, c}, {a,b, c}} 再看二元关系 R3，诱导的集族 。与 R1、R2 诱导的集族并不相同，却也定义 了相同的下近似运算。下面的分析将回答该问题。 C C ∈ C C −{C} C 定义 1 设 是论域 U 上的一个集族， ，如 果 C 不能表示成 中若干个元之并，则称 C 是 的既约元。否则，称 C 是可约元。 由此可见，集族中的元素可以分成既约元和可 约元两类。 C C ∈ C C ′ ∈ C −{C} C ′ C C −{C} 定理 1 设 是论域 U 上的一个集族， 是 一个可约元， ，则 是 的既约元当且仅 当它是 的既约元。 C ′ C C ′ C −{C ′ } C −{C,C ′ } C ′ C −{C} 证明 1) 如果 是 的既约元，则 不能表示成 中若干个元之并，那么当然也就不能表示成 中若干个元之并，因此 是 的既 约元。 C ′ C −{C} C ′ C −{C,C ′ } C ′ C −{C ′ } C ′ C −{C,C ′ } C ′ C1 ∪C2 ∪ ··· ∪Cn ∪C C1,C2,···,Cn ∈ C −{C,C ′ } 2) 反之，如果 是 的既约元，则 不能表 示成 中若干个元之并，下面要证明 同样 也不能表示成 中若干个元之并，而这只需证 明 不能表示成 中若干个元之并与 C 的并 即可，即 不可能表示成 ，其中 。下面用反证法加以证明： C ′ C −{C,C ′ } C ′ = C1 ∪C2 ∪ ··· ∪Cn ∪C C1,C2,··· ,Cn ∈ C− {C,C ′ } C −{C,C ′ } C = D1 ∪ D2 ∪ ··· ∪ Dm D1, D2,··· ,Dm ∈ C −{C,C ′ } C ′ = C1 ∪C2 ∪ ···∪ Cn ∪ D1 ∪ D2 ∪ ··· ∪ Dm C1,C2,··· ,Cn,D1,D2,··· , Dm ∈ C −{C,C ′ } C ′ C −{C,C ′ } C ′ C −{C} C ′ C 假设 能表示成 中若干元与 C 之并， 即 ，其中 。而 C 是一个可约元，故 C 又可表示成 中若干个元之并，即 ，其中 。由此可得 ，其中 。 表示成了 中若干元之 并，这与 是 的既约元矛盾，故假设不成立， 因此 是 的既约元。 由命题 (1)、(2) 得证。 C C ∈ C C ′ ∈ C −{C} C ′ C C −{C} 定理 2 设 是论域 U 上的一个集族， 是 一个可约元， ，则 是 的可约元当且仅 当它是 的可约元。 ·328· 智 能 系 统 学 报 第 13 卷