粗糙集
什么是粗糙集
1982年波兰学者Z. Pawlak 提出了粗糙集理论——它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确，不一致（inconsistent)、不完整（incomplete) 等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。已被广泛应用于知识发现、机器学习、决策支持、模式识别、专家系统及归纳推理等领域。
从数学的角度看，粗糙集是研究集合的；从编程的角度看，粗糙集的研究对象是矩阵,只不过是一些特殊的矩阵；从人工智能的角度来看，粗糙集研究的是决策表。
举一个例子
| 学生 | 食堂饭钱 | 超市花销 | 其他佐证 | 贫困 |
|---|---|---|---|---|
| s1 | 高 | 高 | 无 | 否 |
| s2 | 高 | 高 | 有 | 否 |
| s3 | 高 | 低 | 无 | 存疑 |
| s4 | 高 | 低 | 有 | 存疑 |
| s5 | 低 | 高 | 无 | 存疑 |
| s6 | 低 | 高 | 有 | 存疑 |
| s7 | 低 | 低 | 无 | 是 |
| s8 | 低 | 低 | 有 | 是 |
论域
（记作
U
）：病人，比如在这个表格中，就是从
s1
到
s8
属性
：分为
条件属性
和
决策属性
（记作
C
）。
其中，条件属性又有食堂属性、教超属性以及证明属性。
这些条件属性又被称为
论域上的知识
。
我们把这个记作
信息系统
S
以决策属性C分类的论域S，记作
U / C=
{ {
s
1
s_1
s
1
,
s
2
s_2
s
2
}, {
s
3
,
s
4
,
s
5
,
s
6
s_3, s_4, s_5, s_6
s
3
,
s
4
,
s
5
,
s
6
}, {
s
7
s_7
s
7
,
s
8
s_8
s
8
} } = {
X
1
,
X
2
,
X
3
X_1, X_2, X_3
X
1
,
X
2
,
X
3
}
X
1
X_1
X
1
= {
s
1
,
s
2
s_1, s_2
s
1
,
s
2
}
不妨把它称作
非贫困类
X
2
X_2
X
2
= {
s
3
,
s
4
,
s
5
,
s
6
s_3, s_4, s_5, s_6
s
3
,
s
4
,
s
5
,
s
6
}
不妨把它称作
存疑贫困类
X
3
X_3
X
3
= {
s
7
,
s
8
s_7, s_8
s
7
,
s
8
}
不妨把它称作
贫困类
随机给出一个集合X = {
s
1
,
s
2
,
s
7
s_1, s_2, s_7
s
1
,
s
2
,
s
7
} ，显然 X 是
C
的粗糙集，因为不能通过组合的方法从
X
1
，
X
2
，
X
3
X_1， X_2， X_3
X
1
，
X
2
，
X
3
得出
X
的。
上近似
对于上文随机给出的一个粗糙集 X={
s
1
,
s
2
,
s
7
s_1, s_2, s_7
s
1
,
s
2
,
s
7
}：
非贫困类
：
{
s
1
，
s
2
}
∩
X
=
{
s
1
,
s
2
}
→
X
1
∩
X
=
{
s
1
,
s
2
}
\{s1， s2\} ∩ X = \{s1, s2\} → X_1 ∩ X = \{s1, s2\}
{
s
1
，
s
2
}
∩
X
=
{
s
1
,
s
2
}
→
X
1
∩
X
=
{
s
1
,
s
2
}
存疑贫困类：
{
s
3
,
s
4
,
s
5
,
s
6
}
∩
X
=
∅
→
X
2
∩
X
=
Ø
\{s3, s4, s5, s6\} ∩ X = \empty→ X_2 ∩ X = Ø
{
s
3
,
s
4
,
s
5
,
s
6
}
∩
X
=
∅
→
X
2
∩
X
=
Ø
贫困类：
{
s
7
,
s
8
}
∩
X
=
{
s
7
}
→
X
3
∩
X
=
{
s
7
}
\{s7, s8\} ∩ X = \{s7\} → X_3 ∩ X = \{s7\}
{
s
7
,
s
8
}
∩
X
=
{
s
7
}
→
X
3
∩
X
=
{
s
7
}
把
X
1
X_1
X
1
和
X
3
X_3
X
3
称作是 X 关于
C
的
上近似
。记作
R
‾
X
\overline{R}X
R
X
.
下近似
对于上文随机给出的一个粗糙集
X={s1, s2, s7}
：
非贫困类
：{s1, s2}
⊆
\subseteq
⊆
X →
X
1
X_1
X
1
⊆
\subseteq
⊆
X
存疑贫困类：
{s3, s4, s5, s6}
⊈
\nsubseteq
⊈
X →
X
2
X_2
X
2
⊈
\nsubseteq
⊈
X
贫困类：
{s7, s8}
⊈
\nsubseteq
⊈
X →
X
3
X_3
X
3
⊈
\nsubseteq
⊈
X
把
X
1
X_1
X
1
和
X
3
X_3
X
3
称作是
X
关于
C
的
下近似
。记作
R
‾
X
\underline{R}X
R
X
.
正域、负域、边界域
论域
U
被X的上近似以及下近似集划分为正域
P
O
S
R
(
X
)
POS_R(X)
P
O
S
R
(
X
)
，负域
N
E
G
R
(
X
)
NEG_R(X)
N
E
G
R
(
X
)
以及边界域
B
N
D
R
(
X
)
BND_R(X)
B
N
D
R
(
X
)
三个互不相交的区域。
正域：
P
O
S
R
(
X
)
=
R
‾
X
POS_R(X) = \underline{R}X
P
O
S
R
(
X
)
=
R
X
负域：
N
E
G
R
(
X
)
=
U
−
R
‾
X
NEG_R(X) = U – \overline{R}X
N
E
G
R
(
X
)
=
U
−
R
X
边界域：
B
N
D
R
(
X
)
=
R
‾
X
−
R
‾
X
BND_R(X) = \overline{R}X – \underline{R}X
B
N
D
R
(
X
)
=
R
X
−
R
X
不难看出
P
O
S
R
(
X
)
∩
N
E
G
R
(
X
)
∩
B
N
D
R
(
X
)
=
U
POS_R(X) \cap NEG_R(X) \cap BND_R(X) = U
P
O
S
R
(
X
)
∩
N
E
G
R
(
X
)
∩
B
N
D
R
(
X
)
=
U
系统的定义
在一个决策的信息系统
S
里:
论域
就是数学里的集合，我们研究的对象构成的集合。
知识
论域中的任何一个子集都可以被称作是知识，这是一种对于论域进行分类的能力，一般是由特征属性进行分类。
不可分辨关系
在指定的知识下，不可以被区分开来的对象之间构成了不可分辨关系，也就是等价关系。举个例子，如果以是否为贫困生作为标准，那么贫困生中的各个年级的学生都构成了不可分辨关系。
精确集与粗糙集
在一个知识下，如果论域可以由若干子集组合而成，那么论域就构成了精确集，否则，则为粗糙集。
上近似与下近似
上近似就是包含指定的集合X的元素最小可定义集；下近似就是包含X的最大可定义集。
知识粒度：
属性重要度：
知识粒度
在一个决策信息系统
S
中，存在一种知识
B
⊂
\sub
⊂
C
，使得
U
/
B
=
{
x
1
,
x
2
,
x
3
,
…
,
x
m
}
U / B = \{x1, x2, x3, …, x_m\}
U
/
B
=
{
x
1
,
x
2
,
x
3
,
…
,
x
m
}
，一共区分出了
m
个等价类。则
B
的知识粒度
G
P
u
(
B
)
GP_u(B)
G
P
u
(
B
)
为:
G
P
U
(
B
)
=
∑
i
=
1
m
∣
X
i
∣
2
∣
U
∣
2
GP_U(B) = \sum_{i=1}^m\frac{|X_i|^2}{|U|^2}
G
P
U
(
B
)
=
i
=
1
∑
m
∣
U
∣
2
∣
X
i
∣
2
在粗糙集中，等价类的知识粒度越细，划分的能力就越强，近似集就会越精确；否则，划分能力就弱，近似集越粗糙。
1
∣
U
∣
≤
G
P
u
(
B
)
≤
1
\frac{1}{|U|} \leq GP_u(B) \leq 1
∣
U
∣
1
≤
G
P
u
(
B
)
≤
1
当
U
/
B
=
{
X
1
,
X
2
,
…
,
X
{
∣
U
∣
}
}
U/B = \{X_1, X_2, …, X_\{|U|\}\}
U
/
B
=
{
X
1
,
X
2
,
…
,
X
{
∣
U
∣
}
}
时，
∣
U
∣
|U|
∣
U
∣
是U元素的个数，这是知识粒度最小，为
1
∣
U
∣
\frac{1}{|U|}
∣
U
∣
1
，划分能力最强；当U / B = {U} ，此时知识粒度最大，为1，划分能力最弱。
|
U U U |
a a a |
b b b |
c c c |
e e e |
f f f |
d d 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
/
C
=
{
{
1
}
,
{
2
,
4
}
{
3
,
5
}
{
6
,
7
}
,
{
8
,
9
}
}
U/C = \{\{1\}, \{2, 4\}\, \{3, 5\}\{6,7\},\{8,9\}\}
U
/
C
=
{
{
1
}
,
{
2
,
4
}
{
3
,
5
}
{
6
,
7
}
,
{
8
,
9
}
}
则C的知识粒度为：
G
P
U
(
C
)
=
∑
i
=
1
5
∣
X
i
∣
2
∣
U
∣
2
GP_U(C) = \sum_{i = 1}^5\frac{|X_i|^2}{|U|^2}
G
P
U
(
C
)
=
∑
i
=
1
5
∣
U
∣
2
∣
X
i
∣
2
C
的知识粒度为：
G
P
U
(
C
)
=
∑
i
=
1
5
∣
X
i
∣
2
∣
U
∣
2
=
1
2
+
2
2
+
2
2
+
2
2
+
2
2
9
2
=
17
81
GP_U(C) = \sum_{i = 1}^5\frac{|X_i|^2}{|U|^2}\\ =\frac{1^2+2^2+2^2+2^2+2^2}{9^2}\\ =\frac{17}{81}
G
P
U
(
C
)
=
i
=
1
∑
5
∣
U
∣
2
∣
X
i
∣
2
=
9
2
1
2
+
2
2
+
2
2
+
2
2
+
2
2
=
8
1
1
7
相对知识粒度
若
U
/
P
=
{
X
1
,
X
2
,
X
3
,
…
,
X
m
}
U/P = \{X_1, X_2, X_3, …, X_m\}
U
/
P
=
{
X
1
,
X
2
,
X
3
,
…
,
X
m
}
，
U
/
Q
=
{
Y
1
,
Y
2
,
Y
3
,
…
,
Y
m
}
U/Q = \{Y_1, Y_2, Y_3, …,Y_m\}
U
/
Q
=
{
Y
1
,
Y
2
,
Y
3
,
…
,
Y
m
}
，则Q相对于P的相对知识粒度为：
G
P
U
(
Q
∣
P
)
=
G
P
U
(
P
)
−
G
P
U
(
P
∪
Q
)
GP_U(Q|P)=GP_U(P)-GP_U(P \cup Q)
G
P
U
(
Q
∣
P
)
=
G
P
U
(
P
)
−
G
P
U
(
P
∪
Q
)
例如上表中的数据，条件属性集C以及决策属性图D，有：
U
/
C
=
{
{
1
}
,
{
2
,
4
}
,
{
3
,
5
}
,
{
6
,
7
}
,
{
8
,
9
}
}
U/C=\{\{1\},\{2,4\},\{3,5\},\{6,7\},\{8,9\}\}
U
/
C
=
{
{
1
}
,
{
2
,
4
}
,
{
3
,
5
}
,
{
6
,
7
}
,
{
8
,
9
}
}
U
/
C
∪
D
=
{
{
1
}
{
2
,
4
}
{
3
,
5
}
,
{
6
,
7
}
.
{
8
}
,
{
9
}
}
U/C\cup D=\{\{1\}\{2,4\}\{3,5\},\{6,7\}.\{8\},\{9\}\}
U
/
C
∪
D
=
{
{
1
}
{
2
,
4
}
{
3
,
5
}
,
{
6
,
7
}
.
{
8
}
,
{
9
}
}
则D关于C的知识粒度为：
G
P
U
(
D
∣
C
)
=
G
P
U
(
C
)
−
G
P
U
(
C
∪
D
)
=
17
81
−
15
81
=
2
81
GP_U(D|C)=GP_U(C)-GP_U(C \cup D)\\=\frac{17}{81}- \frac{15}{81}\\=\frac{2}{81}
G
P
U
(
D
∣
C
)
=
G
P
U
(
C
)
−
G
P
U
(
C
∪
D
)
=
8
1
1
7
−
8
1
1
5
=
8
1
2
G
P
U
(
Q
∣
P
)
GP_U(Q|P)
G
P
U
(
Q
∣
P
)
表示了Q相对于P的分类能力。
G
P
U
(
Q
∣
P
)
GP_U(Q|P)
G
P
U
(
Q
∣
P
)
的值越大，表示Q相对于P对于论域U的分类能力就越强；反之，分类能力越弱。
属性重要度
内部属性重要定义如下
给定了一个决策信息系统S，U为论域，B
⊆
\subseteq
⊆
C，若
∀
a
∈
B
\forall a \in B
∀
a
∈
B
则属性a关于条件属性集B相对于决策属性集D的内部属性重要度为：
S
i
g
U
i
n
n
e
r
=
G
P
U
(
D
∣
B
−
{
a
}
)
−
G
P
U
(
D
∣
B
)
Sig_{U}^{inner} = GP_U(D|B-\{a\})-GP_U(D|B)
S
i
g
U
i
n
n
e
r
=
G
P
U
(
D
∣
B
−
{
a
}
)
−
G
P
U
(
D
∣
B
)
能力就越强；反之，分类能力越弱。
属性重要度
内部属性重要定义如下
给定了一个决策信息系统S，U为论域，B
⊆
\subseteq
⊆
C，若
∀
a
∈
B
\forall a \in B
∀
a
∈
B
则属性a关于条件属性集B相对于决策属性集D的内部属性重要度为：
S
i
g
U
i
n
n
e
r
=
G
P
U
(
D
∣
B
−
{
a
}
)
−
G
P
U
(
D
∣
B
)
Sig_{U}^{inner} = GP_U(D|B-\{a\})-GP_U(D|B)
S
i
g
U
i
n
n
e
r
=
G
P
U
(
D
∣
B
−
{
a
}
)
−
G
P
U
(
D
∣
B
)