粗糙集的基础理论汇总
粗糙集什么是粗糙集1982年波兰学者Z. Pawlak 提出了粗糙集理论——它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确，不一致（inconsistent)、不完整（incomplete) 等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。已被广泛应用于知识发现、机器学习、决策支持、模式识别、专家系统及归纳推理等领域。从数学的角度看，粗糙集是研究集
粗糙集
什么是粗糙集
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 s1, s 2 s_2 s2}, { s 3 , s 4 , s 5 , s 6 s_3, s_4, s_5, s_6 s3,s4,s5,s6}, { s 7 s_7 s7, s 8 s_8 s8} } = { X 1 , X 2 , X 3 X_1, X_2, X_3 X1,X2,X3}
X 1 X_1 X1 = { s 1 , s 2 s_1, s_2 s1,s2} 不妨把它称作非贫困类
X 2 X_2 X2 = { s 3 , s 4 , s 5 , s 6 s_3, s_4, s_5, s_6 s3,s4,s5,s6} 不妨把它称作存疑贫困类
X 3 X_3 X3 = { s 7 , s 8 s_7, s_8 s7,s8} 不妨把它称作贫困类
随机给出一个集合X = { s 1 , s 2 , s 7 s_1, s_2, s_7 s1,s2,s7} ，显然 X 是C 的粗糙集，因为不能通过组合的方法从 X 1 ， X 2 ， X 3 X_1， X_2， X_3 X1，X2，X3 得出 X 的。
上近似
对于上文随机给出的一个粗糙集 X={ s 1 , s 2 , s 7 s_1, s_2, s_7 s1,s2,s7}：
非贫困类 ： { 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\} {s1，s2}∩X={s1,s2}→X1∩X={s1,s2}
存疑贫困类： { s 3 , s 4 , s 5 , s 6 } ∩ X = ∅ → X 2 ∩ X = Ø \{s3, s4, s5, s6\} ∩ X = \empty→ X_2 ∩ X = Ø {s3,s4,s5,s6}∩X=∅→X2∩X=Ø
贫困类： { s 7 , s 8 } ∩ X = { s 7 } → X 3 ∩ X = { s 7 } \{s7, s8\} ∩ X = \{s7\} → X_3 ∩ X = \{s7\} {s7,s8}∩X={s7}→X3∩X={s7}
把 X 1 X_1 X1 和 X 3 X_3 X3 称作是 X 关于C 的上近似。记作 R ‾ X \overline{R}X RX.
下近似
对于上文随机给出的一个粗糙集 X={s1, s2, s7}：
非贫困类：{s1, s2}
⊆
\subseteq
⊆ X →
X
1
X_1
X1
⊆
\subseteq
⊆ X
存疑贫困类：{s3, s4, s5, s6}
⊈
\nsubseteq
⊈ X →
X
2
X_2
X2
⊈
\nsubseteq
⊈ X
贫困类：{s7, s8}
⊈
\nsubseteq
⊈ X →
X
3
X_3
X3
⊈
\nsubseteq
⊈ X
把 X 1 X_1 X1 和 X 3 X_3 X3 称作是 X 关于 C 的下近似。记作 R ‾ X \underline{R}X RX.
正域、负域、边界域
论域U被X的上近似以及下近似集划分为正域 P O S R ( X ) POS_R(X) POSR(X)，负域 N E G R ( X ) NEG_R(X) NEGR(X)以及边界域 B N D R ( X ) BND_R(X) BNDR(X)三个互不相交的区域。
正域：
P
O
S
R
(
X
)
=
R
‾
X
POS_R(X) = \underline{R}X
POSR(X)=RX
负域：
N
E
G
R
(
X
)
=
U
−
R
‾
X
NEG_R(X) = U - \overline{R}X
NEGR(X)=U−RX
边界域：
B
N
D
R
(
X
)
=
R
‾
X
−
R
‾
X
BND_R(X) = \overline{R}X - \underline{R}X
BNDR(X)=RX−RX
不难看出
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
POSR(X)∩NEGR(X)∩BNDR(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={x1,x2,x3,…,xm}，一共区分出了m个等价类。则B的知识粒度 G P u ( B ) GP_u(B) GPu(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} GPU(B)=i=1∑m∣U∣2∣Xi∣2
在粗糙集中，等价类的知识粒度越细，划分的能力就越强，近似集就会越精确；否则，划分能力就弱，近似集越粗糙。
1 ∣ U ∣ ≤ G P u ( B ) ≤ 1 \frac{1}{|U|} \leq GP_u(B) \leq 1 ∣U∣1≤GPu(B)≤1
当 U / B = { X 1 , X 2 , … , X { ∣ U ∣ } } U/B = \{X_1, X_2, …, X_\{|U|\}\} U/B={X1,X2,…,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} GPU(C)=∑i=15∣U∣2∣Xi∣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}
GPU(C)=i=1∑5∣U∣2∣Xi∣2=9212+22+22+22+22=8117
相对知识粒度
若 U / P = { X 1 , X 2 , X 3 , … , X m } U/P = \{X_1, X_2, X_3, …, X_m\} U/P={X1,X2,X3,…,Xm}， U / Q = { Y 1 , Y 2 , Y 3 , … , Y m } U/Q = \{Y_1, Y_2, Y_3, …,Y_m\} U/Q={Y1,Y2,Y3,…,Ym}，则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) GPU(Q∣P)=GPU(P)−GPU(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} GPU(D∣C)=GPU(C)−GPU(C∪D)=8117−8115=812
G P U ( Q ∣ P ) GP_U(Q|P) GPU(Q∣P)表示了Q相对于P的分类能力。 G P U ( Q ∣ P ) GP_U(Q|P) GPU(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) SigUinner=GPU(D∣B−{a})−GPU(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) SigUinner=GPU(D∣B−{a})−GPU(D∣B)
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)