﻿ 集族等价与基于粒的下近似算子研究
«上一篇
 文章快速检索 高级检索

 智能系统学报  2018, Vol. 13 Issue (2): 327-330  DOI: 10.11992/tis.201607018 0

### 引用本文

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. DOI: 10.11992/tis.201607018.

### 文章历史

1. 苏州工业职业技术学院 软件与服务外包学院，江苏 苏州 215104;
2. 苏州市创采软件有限公司，江苏 苏州 215128;
3. 嘉兴学院 数理与信息工程学院，浙江 嘉兴 314001

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 University, 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 concepts 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 condition 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 relation.
Key words: approximation operators    reduct    rough sets    irreducible element    reducible element    covering    granule    collections reduct

1 集族约简

 $\begin{array}{c}{R_1} = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {c,b} \right),\left( {c,c} \right)} \right\}\\{R_2} = \left\{ {\left( {b,a} \right),\left( {b,b} \right),\left( {c,b} \right),\left( {c,c} \right)} \right\}\\{R_3} = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {c,b} \right),\left( {c,c} \right),\left( {d,a} \right),\left( {d,b} \right),\left( {d,c} \right)} \right\}\end{array}$

 $\underline R \left( X \right) = \mathop \cup \left\{ {C \in {\cal C}|C \subseteq X} \right\}$ (1)
 $\bar R\left( X \right) = \mathop \cup \left\{ {C \in {\cal C}|C\mathop \cap X \ne \text{Ø}} \right\}$ (2)

2) 反之，如果 $C'$ ${\cal C} - \left\{ C \right\}$ 的既约元，则 $C'$ 不能表示成 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干个元之并，下面要证明 $C'$ 同样也不能表示成 ${\cal C} - \left\{ {C'} \right\}$ 中若干个元之并，而这只需证明 $C'$ 不能表示成 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干个元之并与C的并即可，即 $C'$ 不可能表示成 ${C_1} \cup {C_2} \cup \cdots \cup {C_n} \cup C$ ，其中 ${C_1},{C_2}, \cdots \! ,{C_n} \in {\cal C} - \left\{ {C,C'} \right\}$ 。下面用反证法加以证明：

1) 如果 ${C'}$ ${\cal C} - \left\{ C \right\}$ 的可约元，则 ${C'}$ 可以用 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干个元之并表示出来，那么当然也可表示成 ${\cal C} - \left\{ {C'} \right\}$ 中若干个元之并，因此 ${C'}$ ${\cal C}$ 的可约元。

2) 反之，如果 ${C'}$ ${\cal C}$ 的可约元，则 ${C'}$ 可用 ${\cal C} - \left\{ {C'} \right\}$ 中的若干元 ${C_1},{C_2}, \cdots \! ,{C_n}$ 表示出来。如果 $\forall {C_i}$ ，都有 ${C_i} \ne C$ ，则 ${C'}$ 已经用 ${\cal C} - \left\{ C \right\}$ 中的若干个不等于 ${C'}$ 的元之并表示出来了，因此 ${C'}$ ${\cal C} - \left\{ C \right\}$ 的可约元。要是其中有一个元等于C，不妨设为C1，由于C ${\cal C}$ 中的可约元，于是C可以表示成 ${\cal C} - \left\{ C \right\}$ 的若干元 ${D_1},{D_2}, \cdots \! ,{D_m}$ 的并。于是， $C{{'}} = {C_1} \cup {C_2} \cup \cdots \cup {C_n} = {D_1} \cup$ ${D_2} \cup \cdots \cup {D_m} \cup {C_2} \cup \cdots \cup {C_n}$ ，其中 ${D_1},{D_2}, \cdots ,{D_m},{C_2}, \cdots \! ,$ ${C_n}$ 既不等于C，也不等于 ${C'}$ ，这样证明了 ${C'}$ ${\cal C} - \left\{ C \right\}$ 中的可约元。

2 集族约简的算法

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

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

2.1 求集族的极小元

1) 初始化， ${{minimal}}\left( {\cal C} \right) =$ Ø，将集族 ${\cal C}$ 中的元素按基数从小到大排序；

2) 基数最小的元素一定是极小元，设其基数为i，将其从集族 ${\cal C}$ 中移除并加入极小元集合 ${{minimal}}\left( {\cal C} \right)$

3) i=i+1；

4) 如果集族 ${\cal C}$ 中已没有基数大于等于i的元素，则转5)，如果集族 ${\cal C}$ 中元素的基数均大于i，则转3)；否则逐个检测基数为i的元素，如果任何一个极小元均不是它的真子集，则它是极小元，将其从集族 ${\cal C}$ 中移除并加入极小元集合 ${{minimal}}\left( {\cal C} \right)$ ，转3)；

5) 算法结束， ${{minimal}}\left( {\cal C} \right)$ 即为所求。

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

1) 初始化， ${{irreducible}}\left( {\cal C} \right) =$ Ø；

2) 逐个扫描集族 ${\cal C}$ 的元素C，找出 ${{minimal}}\left( {\cal C} \right)$ 中每一个满足条件 ${{mC}} \subset {{C}}$ 的极小元mC；

3) 如果 ${{C}} \ne \cup {{mC}}$ ，则C是一个既约元，加入集合 ${{irreducible}}\left( {\cal C} \right)$

4) 算法结束， ${{irreducible}}\left( {\cal C} \right)$ 即为所求。

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

 $\begin{array}{c}{C_1} = \left\{ {{x_1},{x_2}} \right\},\;{C_2} = \left\{ {{x_2},{x_3}} \right\}\\{C_3} = \left\{ {{x_1},{x_2},{x_3}} \right\},\;{C_9} = \left\{ {{x_{15}},{x_{16}},{x_{17}}} \right\}\\{C_4} = \left\{ {{x_1},{x_2},{x_3},{x_4}} \right\}\\{C_5} = \left\{ {{x_4},{x_5},{x_6},{x_7},{x_8}} \right\}\\{C_6} = \left\{ {{x_9},{x_{10}},{x_{11}},{x_{12}},{x_{13}},{x_{14}}} \right\}\\{C_{10}} = \left\{ {{x_{13}},{x_{14}},{x_{15}},{x_{16}},{x_{17}},{x_{18}},{x_{19}}} \right\}\\{C_8} = \left\{ {{x_9},{x_{10}},{x_{11}},{x_{12}},{x_{13}},{x_{14}},{x_{15}},{x_{16}},{x_{17}}} \right\}\end{array}$

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

${C_4} = \left\{ {{x_1},{x_2},{x_3},{x_4}} \right\}$ ${C_{10}} \!=\! \left\{ {{x_{13}},{x_{14}},{x_{15}},{x_{16}},{x_{17}},{x_{18}},{x_{19}}} \right\}$ ，最后结果为 ${{reduct}}\left( {\cal C} \right) = \left\{ {{C_1},{C_2},{C_4},{C_5},{C_6},{C_9},{C_{10}}} \right\}$

3 集族等价与下近似运算

4 结束语

 [1] 张文修, 梁怡, 吴伟志. 信息系统与知识发现[M]. 北京: 科学出版社, 2003. (0) [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. (0) [3] YAO Yiyu, YAO Bingxue. Covering based rough set approximations[J]. Information sciences, 2012, 200: 91-107. DOI:10.1016/j.ins.2012.02.065 (0) [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. DOI:10.1016/j.ins.2014.06.032 (0) [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. (0) [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. (0) [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. DOI:10.1016/j.ins.2013.08.057 (0) [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. (0) [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. (0) [10] 屈小兵, 王学平. 完备格上并既约元的性质[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. (0)