【智能系统】集族等价与基于粒的下近似算子研究

第13卷第2期 智能系统学报 Vol.13 No.2 2018年4月 CAAI Transactions on Intelligent Systems Apr.2018 D0:10.11992/tis.201607018 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170626.1740.012.html 集族等价与基于粒的下近似算子研究 胡霞'，费鹏2，杜卫锋 (1.苏州工业职业技术学院软件与服务外包学院，江苏苏州215104；2.苏州市创采软件有限公司，江苏苏州 215128:3.嘉兴学院数理与信息工程学院.浙江嘉兴314001) 摘要：基于覆盖的粗集是推广经典粗集理论的方法之一，有基于元素、基于粒和基于子系统的3类定义上下近似的 途径，以往大多数的文献往往从基于元素的角度出发进行定义。为了研究基于粒的近似算子特别是下近似算子的性 质，借鉴格论中既约元、可约元等概念，提出了集族约简的概念。从集族约简出发，探讨了集族等价的概念与性质，并 设计了集族约简的算法，得到了两个集族等价是两个集族生成相同的下近似运算的充要条件这一结果，为进一步开 展一般二元关系下基于粒的近似算子的公理化方法的研究做了初步的理论方面的准备工作。 关键词：近似算子：约简：粗集：既约元：可约元：覆盖：粒：集族约简 中图分类号：TP18文献标志码：A文章编号：1673-4785(2018)02-0327-04 中文引用格式：胡霞，费鹏，杜卫锋.集族等价与基于粒的下近似算子研究.智能系统学报，2018,13(2)：327-330. 英文引用格式：HU Xia,.FEI Peng,DU Weifeng..On collections equivalence and the granule based lower approximation operators[J].CAAI transactions on intelligent systems,2018,13(2):327-330. On collections equivalence and the granule based lower approximation operators HU Xia',FEI Peng',DU Weifeng' (1.School of Software and Service Outsourcing,Suzhou Institute of Industrial Technology,Suzhou 215104,China;2.Suzhou Chuangcai Software Co.,Ltd.,Suzhou 215128,China:3.School of Mathematics,Physics and Information Engineering,Jiaxing Uni- versity,Jiaxing 314001,China) Abstract:Covering based rough set is one of the methods to extend the classical rough set theory.There are three kinds of approaches,the element based definition,the granule based definition,and the subsystem based definition,to define upper and lower approximation.Most of the literature in the past tends to define based on element.In order to study the properties of the granule based approximation operators,especially the lower approximation operator,referring the con- cepts of irreducible element and reducible element from lattice theory,the concept of collections reduct is put forward. Starting from the concept of collections reduct,the concept and properties of collections equivalence are discussed,and collections reduction algorithm is designed.The result that collections equivalence is the necessary and sufficient condi- tion for generating the same lower approximation by collections is given here.The preliminary theoretical preparation is done here to further develop the axiomatization of the granule based approximation operators under general binary rela- tion. Keywords:approximation operators;reduct;rough sets;irreducible element;reducible element,covering;granule;col- lections reduct 粗集理论是一种处理不协调、不完备和不精确 次提出以来，经过30余年的研究与发展，在理论和 信息的数学工具山，自1982年波兰数学家Pawlak首 应用上均取得了长足的进步。 收稿日期：2016-07-19.网络出版日期：2017-06-26 粗集理论的基础之一是从近似空间诱导出一对 基金项目：国家自然科学基金项目(61202109) 通信作者：杜卫锋.E-mail:23031520@qq.com. 近似算子一一上近似算子和下近似算子。经典的

DOI: 10.11992/tis.201607018 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170626.1740.012.html 集族等价与基于粒的下近似算子研究 胡霞1 ，费鹏2 ，杜卫锋3 （1. 苏州工业职业技术学院 软件与服务外包学院，江苏 苏州 215104; 2. 苏州市创采软件有限公司，江苏 苏州 215128; 3. 嘉兴学院 数理与信息工程学院，浙江 嘉兴 314001） 摘 要：基于覆盖的粗集是推广经典粗集理论的方法之一，有基于元素、基于粒和基于子系统的 3 类定义上下近似的 途径，以往大多数的文献往往从基于元素的角度出发进行定义。为了研究基于粒的近似算子特别是下近似算子的性 质，借鉴格论中既约元、可约元等概念，提出了集族约简的概念。从集族约简出发，探讨了集族等价的概念与性质，并 设计了集族约简的算法，得到了两个集族等价是两个集族生成相同的下近似运算的充要条件这一结果，为进一步开 展一般二元关系下基于粒的近似算子的公理化方法的研究做了初步的理论方面的准备工作。 关键词：近似算子；约简；粗集；既约元；可约元；覆盖；粒；集族约简 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2018)02−0327−04 中文引用格式：胡霞, 费鹏, 杜卫锋. 集族等价与基于粒的下近似算子研究[J]. 智能系统学报, 2018, 13(2): 327–330. 英文引用格式：HU Xia, FEI Peng, DU Weifeng. On collections equivalence and the granule based lower approximation operators[J]. CAAI transactions on intelligent systems, 2018, 13(2): 327–330. On collections equivalence and the granule based lower approximation operators HU Xia1 ，FEI Peng2 ，DU Weifeng3 (1. School of Software and Service Outsourcing, Suzhou Institute of Industrial Technology, Suzhou 215104, China; 2. Suzhou Chuangcai Software Co., Ltd., Suzhou 215128, China; 3. School of Mathematics, Physics and Information Engineering, Jiaxing Uni￾versity, Jiaxing 314001, China) Abstract: Covering based rough set is one of the methods to extend the classical rough set theory. There are three kinds of approaches, the element based definition, the granule based definition, and the subsystem based definition, to define upper and lower approximation. Most of the literature in the past tends to define based on element. In order to study the properties of the granule based approximation operators, especially the lower approximation operator, referring the con￾cepts of irreducible element and reducible element from lattice theory, the concept of collections reduct is put forward. Starting from the concept of collections reduct, the concept and properties of collections equivalence are discussed, and collections reduction algorithm is designed. The result that collections equivalence is the necessary and sufficient condi￾tion for generating the same lower approximation by collections is given here. The preliminary theoretical preparation is done here to further develop the axiomatization of the granule based approximation operators under general binary rela￾tion. Keywords: approximation operators; reduct; rough sets; irreducible element; reducible element; covering; granule; col￾lections reduct 粗集理论是一种处理不协调、不完备和不精确 信息的数学工具[1] ，自 1982 年波兰数学家 Pawlak 首 次提出以来，经过 30 余年的研究与发展，在理论和 应用上均取得了长足的进步。 粗集理论的基础之一是从近似空间诱导出一对 近似算子——上近似算子和下近似算子。经典的 收稿日期：2016−07−19. 网络出版日期：2017−06−26. 基金项目：国家自然科学基金项目 (61202109). 通信作者：杜卫锋. E-mail: 23031520@qq.com. 第 13 卷第 2 期 智 能 系 统 学 报 Vol.13 No.2 2018 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2018

·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 卷

第2期 胡霞，等：集族等价与基于粒的下近似算子研究 ·329· 证明 1)初始化，minimal(C)=O,将集族c中的元素按 1)如果C是C-{C的可约元，则C可以用 基数从小到大排序： C-{C,C'中若干个元之并表示出来，那么当然也可 2)基数最小的元素一定是极小元，设其基数为 表示成C-{C)中若干个元之并，因此C是C的可 i,将其从集族c中移除并加人极小元集合minimal(C: 约元。 3)=+1: 2)反之，如果C是C的可约元，则C可用 4)如果集族C中已没有基数大于等于i的元 C-{C}中的若干元C1,C2,…,Cn表示出来。如果C, 素，则转5)，如果集族C中元素的基数均大于i,则 都有C:≠C,则C已经用C-{C中的若干个不等于 转3)：否则逐个检测基数为i的元素，如果任何一个 C的元之并表示出来了，因此C是C-{C的可约元。 极小元均不是它的真子集，则它是极小元，将其从 要是其中有一个元等于C,不妨设为C,由于C是 集族C中移除并加入极小元集合minimal(C),转3)： C中的可约元，于是C可以表示成C-{C的若干元 5)算法结束，minimal(C)即为所求。 D,D2,,Dm的并。于是，C'=C1UC2UUCn=DU 2.2 由极小元再求集族的非极小既约元 D2 J...UD.uc2U…UCn,其中D,D2,…,Dm,C2,… 算法2求集族的非极小既约元。 Cn既不等于C,也不等于C',这样证明了C是C-{C 输入算法I结束时所得的集族c及minimal(C: 中的可约元。 输出非极小既约元的集合irreducible(C)。 由命题(1)、(2)得证。 I)初始化，irreducible(C=O; 由定理1和定理2可以得出，在一个集族中删 2)逐个扫描集族c的元素C,找出minimal(C)中 除其中的一个可约元，并不会改变其余元素是既约 每一个满足条件mccC的极小元mC; 元还是可约元的性态。由此，我们可以逐个删除集 3)如果C≠UmC,则C是一个既约元，加入集 族中的所有可约元，只剩下既约元。 合irreducible(C); 定义2设C是论域U上的一个集族，如果C中 4)算法结束，irreducible(C)即为所求。 的每一个元都是既约元，则称C是约简的。否则，称 最后，将两步的结果并起来reduct(C)=minimal(C)U C是可约的。 irreducible(C就是所求的集族C的约简。 定义3对于U的一个集族C,通过删除集族 例2设论域U={x1,2,5,4,5,6,x7,g,,10, 中的所有可约元，就得到了一个约简的集族，我们 x1,x12,x13,x14,x15,x16,x,x18,x19,30,计算集族C=C1, 将其称为集族C的约简，记为reduct(C)。 C2,C3,C4,C5,C6,C7,C8,Cg,Co的约简，其中C1={x1,xl, 定理1和定理2实际上还保证了集族的约简是 C2={x2,x3},C3={x1,2,X3},C4={x1,X2,x3,x4},Cs={x4 唯一的。 X5,x6,x7,Xg},C6={xg,X10,X11,X12,X13,X14},C7={x4,X5,X6 定义4设C、C2是论域U上的两个集族，如果 x,xg,x9,x10,11,12,x3,14},C8={9,x10,11,x12,13,x14, reduct(C)=reduct(C2),则称集族C,与C,等价，记为 x15,x16,x17},Cg={15,x16,x1},C10={x13,14,x15,x6,7, C1~C20 X18,X19}o 集族等价形成集族空间心={CC是论域U上的 2.3根据求集族约简的算法，先求集族的极小元 集族上的等价关系，其中的等价类可记为[C]= 由算法1，将集族C中的元素按基数从小到大排 X∈CK~C,表示与集族C等价的所有集族的集合。 序为 C1={x1,x2},C2={x2,3】 2集族约简的算法 C3={,x,x3l,Cg={5,x6,x17} C4={x1,x2,x3,x4} 根据上节的结论，我们可以给出求一个集族约 C5={x4,X5,X6,x7,X8} 简的算法，该算法分为如下两大步骤： C6={9,x0,1,x2,X13,x14} C10={13,x14,15,x16,17,18,x19 1)求集族的极小元（极小元必定是既约元）： Cg={xg,x10,x,x2,x3,x14,x15,x16,x1n} 2)由极小元求集族的非极小既约元。 基数最小的元素C1={x,C2={2,3是极小 将步骤1)、2)的结果并起来，就是该集族的 元。继续算法1，求得其余的极小元分别是C,= 约简。 {X15,x16,x17,X18},C5={x4,X5,X6,x7,X8},C6={xg,x10,x1, 2.1求集族的极小元 X12,X13,X14}。 算法1求集族的极小元。 2.4。根据算法2由极小元再求集族的非极小既约元 输入论域U的一个集族C={C1,C2,…,C C4={1,2,,x4},Ci0={x3,x14,x15,x16,x7,x18,x19, 输出C的极小元集合minimal(C)。 最后结果为reduct(C)={C1,C2,C4,Cs,C6,Cg,C10lo

证明 C ′ C −{C} C ′ C −{C,C ′ } C −{C ′ } C ′ C 1) 如 果 是 的可约元，则 可以用 中若干个元之并表示出来，那么当然也可 表示成 中若干个元之并，因此 是 的可 约元。 C ′ C C ′ C −{C ′ } C1,C2,···,Cn ∀Ci Ci , C C ′ C −{C} C ′ C ′ C −{C} C C −{C} D1,D2,···,Dm C ′ = C1 ∪C2 ∪ ··· ∪Cn = D1∪ D2 ∪ ··· ∪ Dm ∪C2 ∪ ··· ∪Cn D1,D2,··· ,Dm,C2,···, Cn C ′ C ′ C −{C} 2) 反之，如果 是 的可约元，则 可 用 中的若干元 表示出来。如果 ， 都有 ，则 已经用 中的若干个不等于 的元之并表示出来了，因此 是 的可约元。 要是其中有一个元等于 C，不妨设为 C1，由于 C 是 中的可约元，于是 C 可以表示成 的若干元 的并。于是， ，其中 既不等于 C，也不等于 ，这样证明了 是 中的可约元。 由命题 (1)、(2) 得证。 由定理 1 和定理 2 可以得出，在一个集族中删 除其中的一个可约元，并不会改变其余元素是既约 元还是可约元的性态。由此，我们可以逐个删除集 族中的所有可约元，只剩下既约元。 C C C C 定义 2 设 是论域 U 上的一个集族，如果 中 的每一个元都是既约元，则称 是约简的。否则，称 是可约的。 C C reduct(C) 定义 3 对于 U 的一个集族 ，通过删除集族 中的所有可约元，就得到了一个约简的集族，我们 将其称为集族 的约简，记为 。 定理 1 和定理 2 实际上还保证了集族的约简是 唯一的。 C1 C2 reduct(C1) = reduct(C2) C1 C2 C1 ∼ C2 定义 4 设 、 是论域 U 上的两个集族，如果 ，则称集族 与 等价，记为 。 C = { C|C是论域U上的 集族} [C]R = {X ∈ C|X ∼ C} C 集族等价形成集族空间 上的等价关系，其中的等价类可记为 ，表示与集族 等价的所有集族的集合。 2 集族约简的算法 根据上节的结论，我们可以给出求一个集族约 简的算法，该算法分为如下两大步骤： 1) 求集族的极小元 (极小元必定是既约元)； 2) 由极小元求集族的非极小既约元。 将步骤 1)、2) 的结果并起来，就是该集族的 约简。 2.1 求集族的极小元 算法 1 求集族的极小元。 输入 论域 U 的一个集族 C = {C1,C2,··· ,Cn} ； 输出 C 的极小元集合 minimal(C)。 1) 初始化， minimal(C) =Ø，将集族 C 中的元素按 基数从小到大排序； C minimal(C) 2) 基数最小的元素一定是极小元，设其基数为 i，将其从集族 中移除并加入极小元集合 ； 3) i=i+1； C C C minimal(C) 4) 如果集族 中已没有基数大于等于 i 的元 素，则转 5)，如果集族 中元素的基数均大于 i，则 转 3)；否则逐个检测基数为 i 的元素，如果任何一个 极小元均不是它的真子集，则它是极小元，将其从 集族 中移除并加入极小元集合 ，转 3)； 5) 算法结束， minimal(C) 即为所求。 2.2 由极小元再求集族的非极小既约元 算法 2 求集族的非极小既约元。 输入 算法 1 结束时所得的集族 C 及 minimal(C) ； 输出 非极小既约元的集合 irreducible (C)。 1) 初始化， irreducible (C) =Ø； C minimal(C) mC ⊂ C 2) 逐个扫描集族 的元素 C，找出 中 每一个满足条件 的极小元 mC； C , ∪mC irreducible (C) 3) 如果 ，则 C 是一个既约元，加入集 合 ； 4) 算法结束， irreducible (C) 即为所求。 reduct(C)=minimal(C)∪ irreducible (C) C 最后，将两步的结果并起来 就是所求的集族 的约简。 U = {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20} C = {C1, C2,C3,C4,C5,C6,C7,C8,C9,C10} C1 = {x1, x2} C2 = {x2, x3} C3 = {x1, x2, x3} C4 = {x1, x2, x3, x4} C5 = {x4, x5, x6, x7, x8} C6 = {x9, x10, x11, x12, x13, x14} C7 = {x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14} C8 = {x9, x10, x11, x12, x13, x14, x15, x16, x17} C9 = {x15, x16, x17} C10 = {x13, x14, x15, x16, x17, x18, x19} 例 2 设论域 ，计算集族 的约简，其中 ， ， ， ， ， ， ， ， ， 。 2.3 根据求集族约简的算法，先求集族的极小元 由算法 1，将集族 C 中的元素按基数从小到大排 序为 C1 = {x1, x2}, C2 = {x2, x3} C3 = {x1, x2, x3}, C9 = {x15, x16, x17} C4 = {x1 , x2 , x3 , x4} C5 = {x4 , x5 , x6 , x7 , x8} C6 = {x9, x10, x11, x12, x13, x14} C10 = {x13, x14, x15, x16, x17, x18, x19} C8 = {x9, x10, x11, x12, x13, x14, x15, x16, x17} C1 = {x1, x2} C2 = {x2, x3} C9 = {x15, x16, x17, x18} C5 = {x4, x5, x6, x7, x8} C6 = {x9, x10, x11, x12, x13, x14} 基数最小的元素 ， 是极小 元。继续算法 1，求得其余的极小元分别是 ， ， 。 2.4 根据算法 2 由极小元再求集族的非极小既约元 C4 = {x1, x2, x3, x4} C10 ={x13, x14, x15, x16, x17, x18, x19} reduct(C) = {C1,C2,C4,C5,C6,C9,C10} ， ， 最后结果为 。 第 2 期 胡霞，等：集族等价与基于粒的下近似算子研究 ·329·

·330· 智能系统学报 第13卷 3 集族等价与下近似运算 [5]RESTREPO M,GOMEZ J.Topological properties for ap- proximation operators in covering based rough sets[Cl//Pro- 引理1设C是论域U上的一个集族，C是C的 ceeding of the 15th International Conference on Rough Sets, 可约元，XcU,则X在集族C-{C,和集族C下生成 Fuzzy Sets,Data Mining,and Granular Computing.Tianjin, 的下近似相同。 China,2015:112-123. 证明设X在集族C-{C,和集族C下的下近似 [6]李立峰，俞伟.概念格约简与覆盖约简之间的关系).陕 西理工学院学报：自然科学版，2014,30(3)：37-40 分别是X、X2。显然有X1SX2二X。另一方面，仍由 LI Lifeng,YU Wei.Relationships of reduction between 下近似的定义，存在C中的元C,C2,…,Cn,使得 concept lattice and covering[J].Journal of Shaanxi uni- X2=C1UC2U…UCm。显然，C,C2,…,Cn都是X的 versity of technology:natural science edition,2014,30(3): 子集。如果C1,C2,…,Cn均不等于C的话，则它们都 37-40. 属于C-{C,于是C,C2,…,Cn都是X的子集。要是 [7]WANG Changzhong,HE Qiang,CHEN Degang,et al.A C,C2,…,Cn中的某个等于C,不妨设为C1,由于 novel method for attribute reduction of covering decision C是C的可约元，C可以表示成C-{C的若干个元 systems[J].Information sciences,2014,254:181-196. D1,D2,…,Dm的并。于是，X2=C1UC2UUCn=D1U [8]YANG Bin,ZHU W.A new type of covering-based rough sets[C]//Proceedings of the 9th International Conference on D2 J...UD.UC2U…UCn,而D1,D2,…,Dm,C2,…,Cn Rough Sets and Knowledge Technology.Shanghai,China, 都是X的子集，且都是C-C中的元，因此它们都 2014:489-499. 是X的子集。这样我们证明了X2SX1。 [9]彭育威.完全分配格的并一既约元的性质及分子格的代 推论1设C是论域U上的一个集族，则C和 数结构).工程数学学报，1985,2(2)：113-117. reduct(C)生成相同的下近似运算。 PENG Yuwei.Charaterization of a joiet Irreducible eiement 定理3设C1,C2是论域U的两个集族，如果 of compietiy distributive lattice and agebric structure of a reduct(Ci)=reduct(Cz),即C,和C2等价，则C、C2生成 molecular lattice[J].Chinese journal of engineering math- ematics,.1985,2(2):113-117. 相同的下近似运算。 [10]屈小兵，王学平.完备格上并既约元的性质模糊系统 4结束语 与数学，2004,18(S1)少176-179. QU Xiaobing,WANG Xueping.Some properties of join- 本文从集族约简出发，探讨了关于集族的若干 irreducible elements in complete lattice[J].Fuzzy systems and mathematics,2004,18(S1):176-179. 性质，得出了两个集族等价是两个集族生成相同的 下近似运算的充要条件这一结论，为下一步开展基 作者简介： 于粒的公理化方法的研究做了一些初步的理论方面 胡霞，女，1979年生，讲师，主要 的准备工作。本文借鉴格论中的概念来研究粗集， 研究方向为粗糙集理论、信息处理。 为研究粗集理论提供了一种新的思路。下一步的工 作将把格论与粗集理论作更深入的结合，把格论中 的一些方法和结论引人粗集理论，试图发现更多有 趣的结果。另外，在此基础上将开展基于粒的粗集 公理化方法的研究。 费鹏，男，1978年生，高级工程 参考文献： 师，主要研究方向为粗糙集、大数据 处理。 []张文修，梁怡，吴伟志.信息系统与知识发现M.北京：科 学出版社.2003」 [2]祝峰，王飞跃.关于覆盖广义粗集的一些基本结果).模 式识别与人工智能，2002,15(1)：6-13. ZHU Feng,WANG Feiyue.Some results on covering gener- alized rough sets[J].Pattern recognition and artificial intelli- 杜卫锋，男，1977年生，副教授， gence,2002,15(1:6-13 博土，主要研究方向为粗糙集理论。 [3]YAO Yiyu,YAO Bingxue.Covering based rough set ap- proximations[J].Information sciences,2012,200:91-107. [4]RESTREPO M,CORNELIS C,GOMEZ J.Partial order re- lation for approximation operators in covering based rough sets[J].Information sciences,2014,284:44-59

3 集族等价与下近似运算 C C X ⊆ U C −{C} C 引理 1 设 是论域 U 上的一个集族，C 是 的 可约元， ，则 X 在集族 和集族 下生成 的下近似相同。 C −{C} C X1 ⊆ X2 ⊆ X C C1,C2,··· ,Cn X2 = C1 ∪C2 ∪ ··· ∪Cn C1,C2,··· ,Cn C1,C2,··· ,Cn C −{C} C1,C2,··· ,Cn C1,C2,··· ,Cn C C −{C} D1,D2,··· ,Dm X2 = C1 ∪C2 ∪ ··· ∪Cn = D1∪ D2 ∪ ··· ∪ Dm ∪C2 ∪ ··· ∪Cn D1,D2,··· ,Dm,C2,··· ,Cn C −{C} X2 ⊆ X1 证明 设 X 在集族 和集族 下的下近似 分别是 X1、X2。显然有 。另一方面，仍由 下近似的定义，存在 中的元 ，使得 。显然， 都是 X 的 子集。如果 均不等于 C 的话，则它们都 属于 ，于是 都是 X1 的子集。要是 中的某个等于 C，不妨设为 C1，由于 C 是 的可约元，C 可以表示成 的若干个元 的并。于是， ， 而 都是 X 的子集，且都是 中的元，因此它们都 是 X1 的子集。这样我们证明了 。 C C reduct(C) 推论 1 设 是论域 U 上的一个集族，则 和 生成相同的下近似运算。 C1 C2 reduct(C1) = reduct(C2) C1 C2 C1 C2 定理 3 设 ， 是论域 U 的两个集族，如果 ，即 和 等价，则 、 生成 相同的下近似运算。 4 结束语 本文从集族约简出发，探讨了关于集族的若干 性质，得出了两个集族等价是两个集族生成相同的 下近似运算的充要条件这一结论，为下一步开展基 于粒的公理化方法的研究做了一些初步的理论方面 的准备工作。本文借鉴格论中的概念来研究粗集， 为研究粗集理论提供了一种新的思路。下一步的工 作将把格论与粗集理论作更深入的结合，把格论中 的一些方法和结论引入粗集理论，试图发现更多有 趣的结果。另外，在此基础上将开展基于粒的粗集 公理化方法的研究。 参考文献： 张文修, 梁怡, 吴伟志. 信息系统与知识发现[M]. 北京: 科 学出版社, 2003. [1] 祝峰, 王飞跃. 关于覆盖广义粗集的一些基本结果[J]. 模 式识别与人工智能, 2002, 15(1): 6–13. ZHU Feng, WANG Feiyue. Some results on covering gener￾alized rough sets[J]. Pattern recognition and artificial intelli￾gence, 2002, 15(1): 6–13. [2] YAO Yiyu, YAO Bingxue. Covering based rough set ap￾proximations[J]. Information sciences, 2012, 200: 91–107. [3] RESTREPO M, CORNELIS C, GÓMEZ J. Partial order re￾lation for approximation operators in covering based rough sets[J]. Information sciences, 2014, 284: 44–59. [4] RESTREPO M, GÓMEZ J. Topological properties for ap￾proximation operators in covering based rough sets[C]//Pro￾ceeding of the 15th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Tianjin, China, 2015: 112–123. [5] 李立峰, 俞伟. 概念格约简与覆盖约简之间的关系[J]. 陕 西理工学院学报: 自然科学版, 2014, 30(3): 37–40. LI Lifeng, YU Wei. Relationships of reduction between concept lattice and covering[J]. Journal of Shaanxi uni￾versity of technology: natural science edition, 2014, 30(3): 37–40. [6] WANG Changzhong, HE Qiang, CHEN Degang, et al. A novel method for attribute reduction of covering decision systems[J]. Information sciences, 2014, 254: 181–196. [7] YANG Bin, ZHU W. A new type of covering-based rough sets[C]//Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai, China, 2014: 489–499. [8] 彭育威. 完全分配格的并一既约元的性质及分子格的代 数结构[J]. 工程数学学报, 1985, 2(2): 113–117. PENG Yuwei. Charaterization of a joiet lrreducible eiement of compietiy distributive lattice and agebric structure of a molecular lattice[J]. Chinese journal of engineering math￾ematics, 1985, 2(2): 113–117. [9] 屈小兵, 王学平. 完备格上并既约元的性质[J]. 模糊系统 与数学, 2004, 18(S1): 176–179. QU Xiaobing, WANG Xueping. Some properties of join￾irreducible elements in complete lattice[J]. Fuzzy systems and mathematics, 2004, 18(S1): 176–179. [10] 作者简介： 胡霞，女，1979 年生，讲师，主要 研究方向为粗糙集理论、信息处理。 费鹏，男，1978 年生，高级工程 师，主要研究方向为粗糙集、大数据 处理。 杜卫锋，男，1977 年生，副教授， 博士，主要研究方向为粗糙集理论。 ·330· 智 能 系 统 学 报 第 13 卷