粗集理论是一种处理不协调、不完备和不精确信息的数学工具^[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 集族约简

下面来分析一个例子。

例1　设论域 $U = \left\{ {a,b,c,d} \right\}$ ，其上有3个不同的二元关系分别为

$\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}$

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

$\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)

先对二元关系R₁进行分析，令 $r\left( x \right) = \left\{ {y \in U|} \right.$ $\left. {\left( {x,y} \right) \in R} \right\}$ 称为元素x的后继邻域，由此定义得， ${r_1}\left( a \right) = $ $ \left\{ {a,b} \right\}$ ， ${r_1}\left( c \right) = \left\{ {b,c} \right\}$ ，其他元素的后继邻域为空集。非空后继邻域可以构成集族为： ${{\cal C}_1} = \left\{ {{r_1}\left( a \right),{r_1}\left( c \right)} \right\} = $ $ \left\{ {\left\{ {a,b} \right\},\left\{ {b,c} \right\}} \right\}$ ，这就是二元关系R₁诱导的集族。

同理，二元关系R₂诱导的集族 ${C_2} = \left\{ {\left\{ {a,b} \right\},} \right.$ $\left. {\left\{ {b,c} \right\}} \right\}$ 。

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

再看二元关系R₃，诱导的集族 ${C_3} = \left\{ {\left\{ {a,b} \right\},\left\{ {b,c} \right\},} \right.$ $\left. {\left\{ {a,b,c} \right\}} \right\}$ 。与R₁、R₂诱导的集族并不相同，却也定义了相同的下近似运算。下面的分析将回答该问题。

定义1　设 ${\cal C}$ 是论域U上的一个集族， $C \in {\cal C}$ ，如果C不能表示成 ${\cal C} - \left\{ C \right\}$ 中若干个元之并，则称C是 ${\cal C}$ 的既约元。否则，称C是可约元。

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

定理1　设 ${\cal C}$ 是论域U上的一个集族， $C \in {\cal C}$ 是一个可约元， $C' \in {\cal C} - \left\{ C \right\}$ ，则 $C'$ 是 ${\cal C}$ 的既约元当且仅当它是 ${\cal C} - \left\{ C \right\}$ 的既约元。

证明　1)如果 $C'$ 是 ${\cal C}$ 的既约元，则 $C'$ 不能表示成 ${\cal C} - \left\{ {C'} \right\}$ 中若干个元之并，那么当然也就不能表示成 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干个元之并，因此 $C'$ 是 ${\cal C} - \left\{ C \right\}$ 的既约元。

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\}$ 。下面用反证法加以证明：

假设 $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\}$ 。而C是一个可约元，故C又可表示成 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干个元之并，即 $C = {D_1} \cup {D_2} \cup \cdots \cup {D_m}$ ，其中 ${D_1},$ ${D_2}, \cdots ,{D_m} \in {\cal C} - \left\{ {C,C'} \right\}$ 。由此可得 $C' = {C_1} \cup {C_2} \cup \cdots \cup $ ${C_n} \cup {D_1} \cup {D_2} \cup \cdots \cup {D_m}$ ，其中 ${C_1},{C_2}, \cdots ,{C_n},{D_1},{D_2}, \cdots , $ ${D_m} \in {\cal C} - \left\{ {C,C'} \right\}$ 。 ${C'}$ 表示成了 ${\cal C} - \left\{ {C,C'} \right\}$ 中若干元之并，这与 ${C'}$ 是 ${\cal C} - \left\{ C \right\}$ 的既约元矛盾，故假设不成立，因此 ${C'}$ 是 ${\cal C}$ 的既约元。

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

定理2　设 ${\cal C}$ 是论域U上的一个集族， $C \in {\cal C}$ 是一个可约元， $C' \in {\cal C} - \left\{ C \right\}$ ，则 ${C'}$ 是 ${\cal C}$ 的可约元当且仅当它是 ${\cal C} - \left\{ 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，不妨设为C₁，由于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\}$ 中的可约元。

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

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

定义2　设 ${\cal C}$ 是论域U上的一个集族，如果 ${\cal C}$ 中的每一个元都是既约元，则称 ${\cal C}$ 是约简的。否则，称 ${\cal C}$ 是可约的。

定义3　对于U的一个集族 ${\cal C}$ ，通过删除集族中的所有可约元，就得到了一个约简的集族，我们将其称为集族 ${\cal C}$ 的约简，记为 ${{reduct}}\left( {\cal C} \right)$ 。

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

定义4　设 ${{\cal C}_1}$ 、 ${{\cal C}_2}$ 是论域U上的两个集族，如果 ${{reduct}}\left( {{{\cal C}_1}} \right) = {{reduct}}\left( {{{\cal C}_2}} \right)$ ，则称集族 ${{\cal C}_1}$ 与 ${{\cal C}_2}$ 等价，记为 ${{\cal C}_1} \sim {{\cal C}_2}$ 。

集族等价形成集族空间 ${\mathfrak{C}} =\left\{ {{\cal C}|{\cal C}{\text{是论域}}}U{\text{上的}} \right.$ $\left. {\text{集族}} \right\}$ 上的等价关系，其中的等价类可记为 ${\left[ {\cal C} \right]_R} = $ $\left\{ {{\cal X} \in {\mathfrak{C}}|{\cal X} \sim {\cal C}} \right\}$ ，表示与集族 ${\cal C}$ 等价的所有集族的集合。

2 集族约简的算法

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

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

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

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

2.1 求集族的极小元

算法1　求集族的极小元。

输入　论域U的一个集族 ${\cal C} = \left\{ {{C_1},{C_2}, \cdots ,{C_n}} \right\}$ ；

输出　 ${\cal C}$ 的极小元集合 ${{minimal}}\left( {\cal C} \right)$ 。

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 由极小元再求集族的非极小既约元

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

输入　算法1结束时所得的集族 ${\cal C}$ 及 ${{minimal}}\left( {\cal C} \right)$ ；

输出　非极小既约元的集合 ${{irreducible}}\left( {\cal C} \right)$ 。

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)$ 即为所求。

最后，将两步的结果并起来 ${{reduct}}\left( {\cal C} \right) \!\!=\!\! {{minimal}}\left( {\cal C} \right) \cup$ $ {{irreducible}}\left( {\cal C} \right)\,$ 就是所求的集族 ${\cal C}$ 的约简。

例2　设论域 $U = \left\{ {{x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7},{x_8},{x_9},{x_{10}},} \right.$ $\left. {{x_{11}},{x_{12}},{x_{13}},{x_{14}},{x_{15}},{x_{16}},{x_{17}},{x_{18}},{x_{19}},{x_{20}}} \right\}$ ，计算集族 $C = \left\{ {{C_1},} \right.$ $\left. {{C_2},{C_3},{C_4},{C_5},{C_6},{C_7},{C_8},{C_9},{C_{10}}} \right\}$ 的约简，其中 ${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_4} = \left\{ {{x_1},{x_2},{x_3},{x_4}} \right\}$ ， ${C_5} = \left\{ {{x_4},} \right.$ $\left. {{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_7} = \left\{ {{x_4},{x_5},{x_6},} \right.$ $\left. {{x_7},{x_8},{x_9},{x_{10}},{x_{11}},{x_{12}},{x_{13}},{x_{14}}} \right\}$ ， ${C_8} = \left\{ {{x_9},{x_{10}},{x_{11}},{x_{12}},{x_{13}},{x_{14}},} \right.$ $\left. {{x_{15}},{x_{16}},{x_{17}}} \right\}$ ， ${C_9} = \left\{ {{x_{15}},{x_{16}},{x_{17}}} \right\}$ ， ${C_{10}} = \left\{ {{x_{13}},{x_{14}},{x_{15}},{x_{16}},{x_{17}},} \right.$ $\left. {{x_{18}},{x_{19}}} \right\}$ 。

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

由算法1，将集族 ${\cal C}$ 中的元素按基数从小到大排序为

$\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}$

基数最小的元素 ${C_1} = \left\{ {{x_1},{x_2}} \right\}$ ， ${C_2} = \left\{ {{x_2},{x_3}} \right\}$ 是极小元。继续算法1，求得其余的极小元分别是 ${C_9} = $ $ \left\{ {{x_{15}},{x_{16}},{x_{17}},{x_{18}}} \right\}$ ， ${C_5} = \left\{ {{x_4},{x_5},{x_6},{x_7},{x_8}} \right\}$ ， ${C_6} = \left\{ {{x_9},{x_{10}},{x_{11}},} \right.$ $\left. {{x_{12}},{x_{13}},{x_{14}}} \right\}$ 。

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 集族等价与下近似运算

引理1　设 ${\cal C}$ 是论域U上的一个集族，C是 ${\cal C}$ 的可约元， $X \subseteq U$ ，则X在集族 ${\cal C} - \left\{ C \right\}$ 和集族 ${\cal C}$ 下生成的下近似相同。

证明　设X在集族 ${\cal C} - \left\{ C \right\}$ 和集族 ${\cal C}$ 下的下近似分别是X₁、X₂。显然有 ${X_1} \subseteq {X_2} \subseteq X$ 。另一方面，仍由下近似的定义，存在 ${\cal C}$ 中的元 ${C_1},{C_2}, \cdots ,{C_n}$ ，使得 ${X_2} = {C_1} \cup {C_2} \cup \cdots \cup {C_n}$ 。显然， ${C_1},{C_2}, \cdots ,{C_n}$ 都是X的子集。如果 ${C_1},{C_2}, \cdots ,{C_n}$ 均不等于C的话，则它们都属于 ${\cal C} - \left\{ C \right\}$ ，于是 ${C_1},{C_2}, \cdots ,{C_n}$ 都是X₁的子集。要是 ${C_1},{C_2}, \cdots ,{C_n}$ 中的某个等于C，不妨设为C₁，由于C是 ${\cal C}$ 的可约元，C可以表示成 ${\cal C} - \left\{ C \right\}$ 的若干个元 ${D_1},{D_2}, \cdots ,{D_m}$ 的并。于是， ${X_2} = {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}$ 都是X的子集，且都是 ${\cal C} - \left\{ C \right\}$ 中的元，因此它们都是X₁的子集。这样我们证明了 ${X_2} \subseteq {X_1}$ 。

推论1　设 ${\cal C}$ 是论域U上的一个集族，则 ${\cal C}$ 和 ${{reduct}}\left( {\cal C} \right)$ 生成相同的下近似运算。

定理3　设 ${{\cal C}_1}$ ， ${{\cal C}_2}$ 是论域U的两个集族，如果 ${{reduct}}\left( {{{\cal C}_1}} \right) = {{reduct}}\left( {{{\cal C}_2}} \right)$ ，即 ${{\cal C}_1}$ 和 ${{\cal C}_2}$ 等价，则 ${{\cal C}_1}$ 、 ${{\cal C}_2}$ 生成相同的下近似运算。

4 结束语

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