粗糙集理论算法优化研究

摘要

本文回顾了 Pawlak 粗糙集理论的基础知识，对该理论框架下如等价类划分，相对正域计算，约简过程等问题朴素算法的复杂度进行分析，介绍并总结了前人针对上述问题提出的各种优化算法。

引言

20 世纪 80 年代，波兰的 Pawlak 教授提出了粗糙集的概念，并用数学形式明确了粗糙集的定义以及计算规则[@Pawlak]，为描述系统的不确定性并计算规约相关决策规则提供了一项新的工具。粗糙集理论引起了许多数学家、逻辑学家和计算机学家的兴趣，在过去的二十年中，他们在 Pawlak 提出的粗糙集理论基础上进行了大量的研究工作。主要包括粗糙集数学性质[@]、基于其他关系的粗糙集拓展模型、多属性决策分析理论和应用[@安利平]、粗糙集理论与其他不确定方法的关系和结合[@]、粗糙集上的高效算法等。其中《基于粗集理论的多属性决策分析》[@安利平]

相较于 Zadeh 于 1965 年提出的模糊集理论[@Zadeh]，粗糙集给出了可计算的，更准确的描述模糊边界的方式以及量化边界模糊元素的方法。在智能计算、数据挖掘领域，有效且可行的数学描述带来的一大便利便是可以通过计算的方式从数据中抽取有效的经验和知识，粗糙集理论也因此成为数据科学家的有效工具。对于多属性决策分析，粗糙集理论引入了集合近似、约简、核、确定性和可能性规则等新型概念及计算方法，不仅对决策分析问题提供了解释机制，如发现重要的事实和关系，而且利用决策规则形式的偏好模型可以表示决策者的决策政策，提供决策支持。

《数据分析与融合》课程中对粗糙集进行了较为系统的讲解，但是课程避开了粗糙集相关算法的具体实现和复杂度分析。事实上，现有粗糙集算法计算的低效性在一定程度上限制了粗糙集理论的广泛应用，因此寻求高效的粗糙集算法具有重要的意义，也自然成为粗糙集理论研究的一个主要研究分支。

本文首先对粗糙集理论主要内容及其相关数学性质进行回顾，总结前人的相关文献成果，分析了算法低效性的根源 ，解释并实现一种高效的粗糙集基本算法。

粗糙集的基本概念

经典粗集理论是基于不可分辨关系的，下面首先介绍粗糙集的基本概念。

信息表和不可分辨关系

定义 2.1 一个信息系统可以表示为

\[S = \langle U,A,V,f \rangle \tag{2-1}\]

其中, \(U\) 是一非空有限对象集（即论域），\(U = \{ x_1,x_2, \cdots , x_n \}\) ，\(A\) 是非空有限属性集 ，\(A = \{ a_1,a_2,a_3 \}\)，\(V_a\)表示属性 \(a\) 的值域 ，\(V = \bigcup_{a \in A} V_a\) ，\(f : U \times A \rightarrow V\) 是信息函数。它指定 \(U\) 中每一个对象 \(x\) 的属性值, 即对 \(x \in U , a \in A\) ，有 \(f(x , a) \in V_a\)。

在粗集理论中，信息系统也被称为信息表、属性值表、数据表，可简记为\(S = \langle U,A\rangle\)，或者\(S = \langle U,A,V \rangle\)。粗集理论利用信息表（决策表）来描述论域对象及其属性，它是一个二维表，每一行表示一个对象，每一列表示对象的一个属性。与数据库的“表”概念不同，粗集理论所研究的表并不要求两个对象可完全区分，即至少存在一个属性列使得两个对象对应的属性值不同。粗糙集关注的是粒度，而非单个元素。

定义 2.2 在信息系统 S 中 ,对于每个属性子集\(B \subseteq A\) ,可以定义一个不可分辨关系 \(IND(B)\)（在不引起歧义的情况下可简写为\(I_B\)）:

\[IND(B) = \{ (x,y) \in U \times U : f(x,a) = f(y,a) , \forall a \in B \} \tag{2-2}\]

如果\((x,y) \in I_B\)，则\(x\)和\(y\)称为\(B\)不可分辨，显然\(I_B\)满足自反性、对称性和传递性，根据离散数学的内容我们知道，\(I_B\)是以等价关系，\(I_B\)的所有等价类族，即由\(B\)决定的划分，用\(U/I_B\)表示，包含元素\(x\)的等价类用\(I_B(x)\) 表示

相容关系表述和转化探究

在考虑决策表时，常常会考虑是否有如下情况出现：决策表元素出现属性相同（即具备不可分辨关系）的多个元素，却有不同的决策属性值。我们常常将这样类似的性质描述为决策表的相容性。若要通过决策表为自动化程序或者固定流程提供指导，我们希望决策表是相容的，在不断约简决策表过程中，我们也希望决策表保持原有的相容性，否则，具备不可分辨关系的两元素就会出现决策差异，这与程序设计与工业流程中要求的“确定性”产生了根本的对立。当然，若是考虑引入新的知识项（属性）、关联上下文等方法，我们或许可以将不相容的决策表转化为新的相容决策表且决策能力不变，但这已经超出了基本粗糙集和决策表约简的讨论范围，在此也不考虑这种拓展情形。

相容性的刻画有很多方法，从定义上划分可以在不同资料

设\(S = \langle U,C \cup D \rangle\)为一决策表，不可分辨关系\(I_C\)将论域划分为\(U/C\)，称为条件分类（条件粒度），不可分辨关系\(I_D\)将论域划分为\(U/D\)，称为决策分类（决策粒度）。对于单属性决策，则\(D = {d}\)，若非单属性决策，则\(D\)表示所有决策属性列的集合，决策表的相容关系有如下两种表述。

定义 2.3 设\(S = \langle U,C \cup D \rangle\)为一决策表，对于其条件分类\(U/C\)与决策分类\(U/D\)，若有\(U/C\)细分\(U/D\)，则称\(S\)为相容决策表，否则成\(S\)为不相容决策表。

相关文献讨论了通过决策值归纳函数来描述决策表相容性的方法，不过讨论局限在\(D = {d}\)，即决策属性单一的情况。为了与定义 2.3 保持等价性，这里给出拓展\(D\)不仅为单属性列情况下的定义。

定义 2.4 设\(S = \langle U,C \cup D \rangle\)为一决策表，\(B \subseteq C\)，定义\(S\)的\(B\)决策值归纳函数为

\[\partial_B : U \times D \rightarrow P(V_d) \tag{2-3}\]

\[\partial_B (x,d) = \{ i: \exists x_0 \in I_B(x) , f(x,d) = i \} \tag{2-4}\]

其中\(P(V_d))\)表示对应属性列取值\(V_d\)的幂集。

如果\(\forall x \in U, \forall d \in D ,|\partial_C (x,d)| = 1\)，则\(S\)称为相容决策表，否则，\(S\)称为不相容决策表。

下面证明两定义的等价性，即证\(U/C\)细分\(U/D\)是\(\forall x \in U, \forall d \in D ,|\partial_C (x,d)| = 1\)的充要条件

证明 2.1 充分性

应用反证法：

假设\(\exists x_0 \in U, \exists d_0 \in D, | \partial_C (x_0,d_0) | \geq 2\)。由细分关系\(I_C \subseteq I_D\)。因为\(|\partial_C (x_0,d_0) | \geq 2\)，不妨设\(\partial_C (x_0,d_0) = \{r_0,r_1, \cdots \}\)，同时我们假设\(r_0\)表示为\(x_0\)在属性\(d_0\)上的值（即信息函数值），\(f(x_0,d_0) = r_0\)，则由决策归纳函数定义，必然\(\exists x_1 \in I_C(X_0), f(x_1,d_0) = r_1\)。

因为\(f(x_1,d_0)\)不等于\(f(x_0,d_0)\)，所以明显\(x_0\)不等于\(x_1\)，即表示两个论域元素。又因为决策归纳函数的限制，\((x_0,x_1)\in I_C\)也即（\(x_0 I_C x_1\)）。而根据定义 2.2，因为\(f(x_1,d_0)\)不等于\(f(x_0,d_0)\)，则对于\(I_D\)，\((x_0,x_1) \notin I_D\)，与\(I_C \subseteq I_D\)相矛盾，充分性得证。

所以\(U/C\)细分\(U/D\)是\(\forall x \in U, \forall d \in D ,|\partial_C (x,d)| = 1\)的充分条件。

证明 2.2 必要性

因为\(\forall x \in U, \forall d \in D, |\partial_C(x,d)| = 1\)，那么对于\(\forall (x_0,x_1) \in I_C\)，我们可以得到，\(\forall d \in D, |\partial_C(x_0,d)| = |\partial_C(x_1,D)| = 1\)。

对于决策属性族的任意属性\(d\)，不妨设此时\(f(x_0,d) = r, f(x_1,d) = r'\)，因为\(\partial_C(x_0,d) = \{ r \}\)，根据决策归纳函数定义，应有\(f(x_1,d) = r\)，故\(r = r'\)。综合前述，即\(\forall (x_0,x_1) \in I_C, \forall d \in D, f(x_0,d) = f(x_1,d)\)，根据定义 2.2，则\((x_0,x_1) \in I_D\)。即退出\(I_C \subseteq I_D\)，由等价关系性质可得\(U/C\)细分\(U/D\)，必要性得证，证毕。

不相容决策表可以通过决策值归纳函数转化为相容决策表\(S = \langle U, C\cup (\bigcup_{d \in D} \partial(d))\)。

集合的近似和相关性质

由于不同文献中所用的习惯表示方法不尽相同，所以这里我们用原作者 Pawlak 在[@Pawlak1982]使用的定义方式来表示集合的近似及其相关性质，并根据原文献补充部分课上未涉及的概念。

定义 2.5 设\(S\)未信息表,\(X\)为\(U\)的非空子集，属性\(A\)下\(X\)包含的最大粒度集合被称为\(X\)的\(A\)下近似\(\underline{\mathrm{Apr}_A}(X)\)，属性\(A\)下包含\(X\)的最小粒度集合被称为\(X\)的\(A\)上近似\(\overline{\mathrm{Apr}_A}(X)\)，当\(A\)均已知的时候可以省略。

\[\underline{\mathrm{Apr}_A}(X) = \{ x\in U: I_A(x) \subseteq X \} \tag{2-5}\] \[\overline{\mathrm{Apr}_A}(X) = \{ x\in U: I_A(x) \cap X \not ={\emptyset} \tag{2-6}\]

在集合近似的基础上，我们可以给出拓展的论域元素与集合近似成员关系的定义，\(\underline{\in}_{A}\)与\(\overline{\in}_{A}\)，具体定义如下：

定义 2.6 \[x \underline{\in}_{A} X \quad \mathrm{iff} \quad x \in \underline{\mathrm{Apr}_A}(X) \tag{2-7}\] \[x \overline{\in}_{A} X \quad \mathrm{iff} \quad x \in \overline{\mathrm{Apr}_A}(X) \tag{2-8}\]

如果\(x \underline{\in}_{A} X\)，我们称“在属性\(A\)下\(x\) 必然 属于\(X\)”，而如果\(x \overline{\in}_{A} X\)，我们称“在属性\(A\)下\(x\)，可能 属于\(X\)”。如此通过模态逻辑中的必然性和可能性来解释近似性。

在集合近似的基础上，我们还可以根据属性\(B\)，将论域\(U\)中的所有元素针对给定的集合\(X\)划分到不同域中。\(\underline{\mathrm{Apr}_A}(X)\)实际上是由根据已知的属性划分出的知识粒度，判断肯定属于\(X\)的论域元素所构成的最大集合，所以也被称为\(X\)的\(A\)正域，记为\(POS_A(X)\)。而根据已有知识推断的必然不属于\(X\)的论域元素称为\(X\)的\(A\)负域，记为\(NEG_A(X)\)，\(\overline{\mathrm{Apr}_A}(X)\)应为可能属于\(X\)的论域元素构成的最大集合。根据当前已有知识，既不能推断属于\(POS_A(X)\)也不能推断属于\(NEG_A(X)\)的元素则属于边界域（可域）\(BND_A(X)\)（部分资料上写为\(Bn_A(X)\)），不能肯定其中的元素是否属于\(X\)，具体定义如下：

定义 2.7

\[POS_A(X) = \underline{\mathrm{Apr}_A}(X) \tag{2-9}\] \[NEG_A(X) = U - \overline{\mathrm{Apr}_A}(X) \tag{2-10}\] \[BND_A(X) = \overline{\mathrm{Apr}_A}(X) - \underline{\mathrm{Apr}_A}(X) \tag{2-11}\]

容易得出在各属性域限制下，论域元素集合\(X,Y \subseteq U\)，符合下述性质：

\[\underline{\mathrm{Apr}}(X) \subseteq X \subseteq \overline{\mathrm{Apr}}(X) \tag{2-12}\] \[\underline{\mathrm{Apr}}(\emptyset) = \overline{\mathrm{Apr}}(\emptyset) = \emptyset \tag{2-13}\] \[\underline{\mathrm{Apr}}(U) = \overline{\mathrm{Apr}}(U) = U \tag{2-14}\] \[\underline{\mathrm{Apr}}(X \cap Y) = \underline{\mathrm{Apr}}(X) \cap \underline{\mathrm{Apr}}(Y) \tag{2-15}\] \[\overline{\mathrm{Apr}}(X \cup Y) = \overline{\mathrm{Apr}}(X) \cup \overline{\mathrm{Apr}}(Y) \tag{2-16}\] \[\underline{\mathrm{Apr}}(X \cup Y) \supseteq \underline{\mathrm{Apr}}(X) \cup \underline{\mathrm{Apr}}(Y) \tag{2-17}\] \[\overline{\mathrm{Apr}}(X \cap Y) \subseteq \overline{\mathrm{Apr}}(X) \cap \overline{\mathrm{Apr}}(Y) \tag{2-18}\] \[\underline{\mathrm{Apr}}(-X) = - \overline{\mathrm{Apr}}(X) \tag{2-19}\] \[\overline{\mathrm{Apr}}(-X) = - \underline{\mathrm{Apr}}(X) \tag{2-20}\] \[\underline{\mathrm{Apr}}(\underline{\mathrm{Apr}}(X)) = \overline{\mathrm{Apr}}(\underline{\mathrm{Apr}}(X)) = \underline{\mathrm{Apr}}(X) \tag{2-21}\] \[\overline{\mathrm{Apr}}(\overline{\mathrm{Apr}}(X)) = \underline{\mathrm{Apr}}(\overline{\mathrm{Apr}}(X)) = \overline{\mathrm{Apr}}(X) \tag{2-22}\]

其中\(-X\) 表示\(U - X\)，即以论域元素集合为全集得补集。

上述列出为常见的性质，其中性质\(\tag{2-12}\)表示，如果严肃\(x\)属于\(\underline{\mathrm{Apr}}(X)\)时，则\(x\)一定属于\(X\)，而当\(x\)属于\(\overline{\mathrm{Apr}}(X)\)时，\(x\)可能属于\(X\)，而性质\(\tag{2-17}\)与性质\(\tag{2-18}\)则表明，不同集合近似的分布计算要慎重，并集的上近似等于上近似的并集，交集的下近似等于下近似的交集，但是如果考虑交集的上近似、并集的下近似，则会出现忽略粒度和过度包含粒度的情况出现，等式关系不再成立，转而变为包含与被包含的关系，证明这里从略。在实际应用中，这提醒我们如果信息表被分成几个部分先行计算近似与整体计算近似，可能得到不同的结果。

当然，由近似引出的性质还可以继续深入研究，比如满足德摩根定律形式的一些性质，以及不同集合差集近似的性质，