集族等价与基于粒的下近似算子研究

胡霞，费鹏，杜卫锋

粗集理论是一种处理不协调、不完备和不精确信息的数学工具[1]，自1982年波兰数学家Pawlak首次提出以来，经过30余年的研究与发展，在理论和应用上均取得了长足的进步。

粗集理论的基础之一是从近似空间诱导出一对近似算子——上近似算子和下近似算子。经典的Pawlak粗集模型基于等价关系，这种严格的要求在一定程度上限制了粗集理论的应用。为了推广粗集模型，可以把等价关系放宽为一般二元关系，在此情况下，由一般二元关系决定的论域上的集簇不再“划分”。因此，另一种推广粗集模型的思路就是将原来由等价关系决定的“划分”放宽为“覆盖”，从而建立基于覆盖的粗集理论。但不同于经典粗集理论，基于覆盖的粗集理论不存在唯一的定义上下近似算子的方法。

已有很多文献对基于覆盖的粗集理论开展了卓有成效的研究[2-8]。姚一豫等[3]系统地研究了基于覆盖的20对上下近似算子；Mauricio Restrepo等[4]通过某些算子的相等关系将上下近似算子缩减为16对，并提出了算子精细度的概念，给了16对近似算子的精细关系，并用哈斯图进行了描述。M. Restrepo等[5]则研究了基于覆盖的具有对偶性的16对上下近似算子的拓扑性质。在数据挖掘领域，去除冗余属性，获取属性约简，从而简化知识的表示，提升数据处理效率是一个重要的研究课题。李立峰等[6]研究发现覆盖粗糙集与形式背景之间存在一一对应关系，并且证明了覆盖粗糙集的交约简可化为概念格的属性约简；C. Wang等[7]开发了一种基于覆盖粗糙集的属性约简方法，这种启发式方法可以比较高效地获得近似最优约简的属性集；Yang Bin等[8]则将包含度的概念引入覆盖粗糙集，探索了一种新的覆盖近似空间的若干性质。在覆盖粗集理论中，我们有基于元素、基于粒和基于子系统的3类定义上下近似的途径，以往大多数的文献往往从基于元素的角度出发进行定义，本文则以后继邻域作为基本研究对象“粒”，并以此为出发点，借鉴格论中既约元、可约元等概念[9–10]，探讨了(覆盖)集族中的既约元、可约元、集族的约简及其算法，另外，研究了集族与其生成的下近似算子的关系，为下一步开展基于粒的公理化方法的研究做一些初步的理论方面的准备工作。

1 集族约简

下面来分析一个例子。

基于粒的广义上下近似算子定义为后继邻域的广义并，而并不考虑该后继邻域是哪一个元素的后继邻域。因此我们只需研究二元关系R诱导的集族，而勿需再去研究二元关系本身。此时，基于粒的广义上下近似算子可等效为

先对二元关系R1进行分析，令称为元素x的后继邻域，由此定义得，，，其他元素的后继邻域为空集。非空后继邻域可以构成集族为：这就是二元关系R1诱导的集族。

同理，二元关系R2诱导的集族。

由此发现，R1和R2诱导了相同的集族，因此它们定义了相同的下近似运算。

再看二元关系R3，诱导的集族。与R1、R2诱导的集族并不相同，却也定义了相同的下近似运算。下面的分析将回答该问题。

由此可见，集族中的元素可以分成既约元和可约元两类。

由命题(1)、(2)得证。

证明

由命题(1)、(2)得证。

由定理1和定理2可以得出，在一个集族中删除其中的一个可约元，并不会改变其余元素是既约元还是可约元的性态。由此，我们可以逐个删除集族中的所有可约元，只剩下既约元。

定理1和定理2实际上还保证了集族的约简是唯一的。

2 集族约简的算法

根据上节的结论，我们可以给出求一个集族约简的算法，该算法分为如下两大步骤：

1) 求集族的极小元(极小元必定是既约元)；

2) 由极小元求集族的非极小既约元。

将步骤1)、2)的结果并起来，就是该集族的约简。

2.1 求集族的极小元

算法1 求集族的极小元。

2) 基数最小的元素一定是极小元，设其基数为i，将其从集族中移除并加入极小元集合；

3) i=i+1；

2.2 由极小元再求集族的非极小既约元

算法2 求集族的非极小既约元。

2.3 根据求集族约简的算法，先求集族的极小元

2.4 根据算法2由极小元再求集族的非极小既约元

3 集族等价与下近似运算

4 结束语

本文从集族约简出发，探讨了关于集族的若干性质，得出了两个集族等价是两个集族生成相同的下近似运算的充要条件这一结论，为下一步开展基于粒的公理化方法的研究做了一些初步的理论方面的准备工作。本文借鉴格论中的概念来研究粗集，为研究粗集理论提供了一种新的思路。下一步的工作将把格论与粗集理论作更深入的结合，把格论中的一些方法和结论引入粗集理论，试图发现更多有趣的结果。另外，在此基础上将开展基于粒的粗集公理化方法的研究。

[1]张文修, 梁怡, 吴伟志. 信息系统与知识发现[M]. 北京: 科学出版社, 2003.

[2]祝峰, 王飞跃. 关于覆盖广义粗集的一些基本结果[J]. 模式识别与人工智能, 2002, 15(1): 6–13.ZHU Feng, WANG Feiyue. Some results on covering generalized rough sets[J]. Pattern recognition and artificial intelligence, 2002, 15(1): 6–13.

[3]YAO Yiyu, YAO Bingxue. Covering based rough set approximations[J]. Information sciences, 2012, 200: 91–107.

[4]RESTREPO M, CORNELIS C, GÓMEZ J. Partial order relation for approximation operators in covering based rough sets[J]. Information sciences, 2014, 284: 44–59.

[5]RESTREPO M, GÓMEZ J. Topological properties for approximation operators in covering based rough sets[C]//Proceeding of the 15th International Conference on Rough Sets,Fuzzy Sets, Data Mining, and Granular Computing. Tianjin,China, 2015: 112–123.

[6]李立峰, 俞伟. 概念格约简与覆盖约简之间的关系[J]. 陕西理工学院学报: 自然科学版, 2014, 30(3): 37–40.LI Lifeng, YU Wei. Relationships of reduction between concept lattice and covering[J]. Journal of Shaanxi university of technology: natural science edition, 2014, 30(3):37–40.

[7]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.

[8]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.

[9]彭育威. 完全分配格的并一既约元的性质及分子格的代数结构[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 mathematics, 1985, 2(2): 113–117.

[10]屈小兵, 王学平. 完备格上并既约元的性质[J]. 模糊系统与数学, 2004, 18(S1): 176–179.QU Xiaobing, WANG Xueping. Some properties of joinirreducible elements in complete lattice[J]. Fuzzy systems and mathematics, 2004, 18(S1): 176–179.