什么是粗糙集(三)

很久之前，写过粗糙集方面的东西，然鹅鸽了......最近开始更特征选择了，因此粗糙集又重新开始更了！

粗糙集方面很久没更了，上一篇还是去年七月下旬，之后很久没更这块了，博客也很长时间没更新。最近在更特征选择，恰好最近一位读者私信我还会写粗糙集这块吗，当然会的啦。
闲话少说，开始吧！

本文与之前的博客一脉相承。

上近似和下近似

以之前病人病历为例，这里我们使用体温这个属性。

病人	体温
$e_{1}$	正常
$e_{2}$	高
$e_{3}$	很高
$e_{4}$	正常
$e_{5}$	高
$e_{6}$	很高

在这个信息系统中 $S=(U,C)$ ，其中 $U$ 为论域， $C=\{c_{3} \}$ ， $c_{3}$ 是体温这个属性。
那么，
$U/C=\{\{e_{3},e_{6} \},\{e_{2},e_{5} \},\{e_{1},e_{4}\}\}=\{X_{1},X_{2},X_{3}\}$

可以看出体温这个属性被划分成了三类，很高，高和正常。

若给定一个集合 $X$ ， $X=\{e_{1},e_{2},e_{4} \}$ ，显然 $X$ 是 $C$ 的粗糙集，因为 $X$ 不能被 $X_{1},X_{2},X_{3}$ 中的任何一个或者若干个组合构成。

先看上近似。
在 $U/C=\{X_{1},X_{2},X_{3} \}$ 中，

$\{e_{3},e_{6}\}\bigcap X =\emptyset \quad \implies \quad X_{1} \bigcap X = \emptyset$
$\{e_{2},e_{5}\} \bigcap X =\{e_{2} \} \quad \implies \quad X_{2} \bigcap X = \{e_{2}\}$
$\{e_{1},e_{4} \} \bigcap X =\{e_{1},e_{4}\} \quad \implies \quad X_{3} \bigcap X = \{e_{1},e_{4} \}$

此时，称 $\{e_{2},e_{5} \}$ 和 $\{e_{1},e_{4}\}$ 为 $X$ 关于 $C$ 的上近似。

再看下近似。
在 $U/C=\{X_{1},X_{2},X_{3} \}$ 中，

$\{e_{3},e_{6} \}\not\subseteq X \quad \implies \quad X_{1} \not\subseteq X$
$\{e_{2},e_{5} \}\not\subseteq X \quad \implies \quad X_{2} \not\subseteq X$
而
$\{e_{1},e_{4} \} \subseteq X \quad \implies \quad X_{3} \subseteq X$
此时，称 $\{e_{1},e_{4}\}$ 为 $X$ 关于 $C$ 的下近似。

给出上下近似的定义：

在一个决策信息系统中 $S=(U,A=C\bigcup D,V,f)$ 中， $R$ 是一个等价关系， $\forall X \subseteq U$ ， $X$ 关于 $R$ 的上近似和下近似的定义分别如下：

$\overline{R}X=\{x \in U \mid [x]_{R} \bigcap X \neq \emptyset \}$
$\underline{R}X= \{x \in U \mid [x]_{R} \subseteq X\}$

$[x]_{B}=\{y \mid (x,y) \in R_{B} \}$ 表示是由等价关系 $R_{B}$ 形成的等价类，在往期的博客中有相关介绍，传送门。

关于上近似和下近似的一些解释。

上近似则是将那些包含 $X$ 的知识库中的集合求并得到的(包含 $X$ 的最小可定义集)
下近似是在那些所有的包含于 $X$ 的知识库中的集合中求并得到的(包含在 $X$ 内的最大可定义集）

或者说

上近似是根据现有知识 $R$ ，判断 $U$ 中一定属于和可能属于 $X$ 的对象所组成的集合。
根据现有知识 $R$ ，判断 $U$ 中所有肯定属于 $X$ 的对象所组成的集合，即式中，表示等价关系 $R$ 下包含关系 $x$ 的等价类。

正域，负域与边界域

紧接着上下近似的概念，正域，负域与边界域的定义如下：

论域 $U$ 被 $X$ 的上下近似集划分为正域 $POS_{R}(X)$ ，负域 $NEG_{R}(X)$ 以及边界域 $BND_{R}(X)$ 三个互不相交的区域。
正域：
$POS_{R}(X)=\underline{R}X$

负域：
$NEG_{R}(X)=U-\overline{R}X$

边界域：
$BND_{R}(X)=\overline{R}X-\underline{R}X$

可以发现：
$POS_{R}(X) \bigcup NEG_{R}(X) \bigcup BND_{R}(X) =U$

我们还是以上面体温属性 $C$ 为例。
$X$ 关于 $C$ 的上近似为 $\{e_{2},e_{5}\}$ ， $\{e_{1},e_{4}\}$ ，下近似为 $\{e_{1},e_{4}\}$ ，所以
论域 $U$ 被 $X$ 的上下近似集划分为正域为：
$POS_{C}(X)=\underline{R}X=\{e_{1},e_{4}\}$

负域为：
$NEG_{R}(X)=U-\overline{R}X =\{e_{3},e_{6} \}$

边界域：
$BND_{R}(X)=\overline{R}X-\underline{R}X=\{e_{2},e_{5} \}$

用一张图来表示这个过程：

image.png

图中蓝色曲线为上近似。

实例

下表是一个决策信息系统。

$U$	$a$	$b$	$c$	$e$	$f$	$d$
1	0	1	1	1	0	1
2	1	1	0	1	0	1
3	1	0	0	0	1	0
4	1	1	0	1	0	1
5	1	0	0	0	1	0
6	0	1	1	1	1	0
7	0	1	1	1	1	0
8	1	0	0	1	0	1
9	1	0	0	1	0	0

其中论域 $U=\{1,2,3,4,5,6,7,8,9 \}$ ，条件属性集 $C=\{a,b,c,f,e \}$ ，决策属性集 $D=\{d\}$ 。

从上表中有： $U=\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9}\}$ ， $C=\{a,b,c,f,e \}$ ， $D=\{d\}$ 。
每个属性的值域都为 $\{0,1\}$ 。

$U/C=\{\{1\},\{2,4\},\{3,5\},\{6,7\},\{8,9\} \}=\{U_{1},U_{2},U_{3},U_{4},U_{5} \}$

注意， $C$ 是条件属性，未包括决策属性 $d$ 。

假设： $X=\{1,2,3,6,7 \}$ 。
则：
上近似：
$\overline{R}X=U_{1} \bigcup U_{2} \bigcup U_{3} \bigcup U_{4} =\{1,2,4,3,5,6,7 \}$

下近似：
$\underline{R}X= \{1,6,7\}$
正域为：
$POS_{C}(X)=\underline{R}X=\{1,6,7 \}$
负域为：
$NEG_{C}(X)=U-\overline{R}X =\{8,9 \}$
边界域：
$BND_{C}(X)=\overline{R}X-\underline{R}X=\{2,4,3,5\}$

本文内容暂告一段落，之后将继续更新。

本文参考了：

景运革. 基于知识粒度的动态属性约简算法研究[D].西南交通大学,2017.
苗夺谦，李国道《粗糙集理论，算法和应用》.
张文修《基于粗糙集的不确定决策》.

$U$	$a$	$b$	$c$	$e$	$f$	$d$
1	0	1	1	1	0	1
2	1	1	0	1	0	1
3	1	0	0	0	1	0
4	1	1	0	1	0	1
5	1	0	0	0	1	0
6	0	1	1	1	1	0
7	0	1	1	1	1	0
8	1	0	0	1	0	1
9	1	0	0	1	0	0

$U$	$a$	$b$	$c$	$e$	$f$	$d$
1	0	1	1	1	0	1
2	1	1	0	1	0	1
3	1	0	0	0	1	0
4	1	1	0	1	0	1
5	1	0	0	0	1	0
6	0	1	1	1	1	0
7	0	1	1	1	1	0
8	1	0	0	1	0	1
9	1	0	0	1	0	0

$U$	$a$	$b$	$c$	$e$	$f$	$d$
1	0	1	1	1	0	1
2	1	1	0	1	0	1
3	1	0	0	0	1	0
4	1	1	0	1	0	1
5	1	0	0	0	1	0
6	0	1	1	1	1	0
7	0	1	1	1	1	0
8	1	0	0	1	0	1
9	1	0	0	1	0	0