关于偏序、格等
偏序
定义
- Partiallyordered set，简写poset
- 设$R$是集合$A$上的一个二元关系，若$R$满足：
自反性
反对称性
传递性
则称$R$为$A$上的偏序关系，通常记作$\preccurlyeq$。注意这里的$\preccurlyeq$不必是指一般意义上的“小于或等于”。
若然有$x\preccurlyeq y$，我们也说$x$排在$y$前面（x precedes y）
分类
严格偏序，反自反偏序
- 给定集合$S$，$\prec$是$S$上的二元关系，若$\prec$满足：
反自反性
反对称性
传递性
则称$\prec$为$S$上的严格偏序关系，通常记作$\prec$
- 严格偏序与有向无环图（dag）有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己
- 给定集合$S$，$\prec$是$S$上的二元关系，若$\prec$满足：
非严格偏序，自反偏序
全序
定义
- 如果$R$是$A$上的偏序关系，那么对于任意的A集合上的 $x,y$，都有$x\preccurlyeq y$，或者$y\preccurlyeq x$，二者必居其一，那么则称$R$是$A$上的全序关系
设集合$X$上有一全序关系，如果我们把这种关系用$\preccurlyeq$表述，则下列陈述对于$X$中的所有$a,b,c$成立：
如果$a\preccurlyeq b$且$b\preccurlyeq a$则$a=b$(反对称性)
如果$a\preccurlyeq b$且$b\preccurlyeq c$则$a\preccurlyeq c$(传递性)
$a\preccurlyeq b$或$b\preccurlyeq a$(完全性)
区别
偏序集合：配备了偏序关系的集合。
偏序：只对部分要元素成立关系（部分可比）
集合内只有部分元素之间在这个关系下是可以比较的。
比如：比如复数集中并不是所有的数都可以比较大小，那么“大小”就是复数集的一个偏序关系
全序集合：配备了全序关系的集合。
全序：对集合中任意两个元素都有关系
集合内任何一对元素在在这个关系下都是相互可比较的。
比如：有限长度的序列按字典序是全序的。最常见的是单词在字典中是全序的
格
定义
格
- Lattice
- 如果一个偏序集的任意两个元素都有最小上界和最大下界，那么这一偏序集是一个格
半格
- Semi-Lattice
- 最小上界和最大下界只存在一个的偏序集称半格，只存在最小上界称为“join semilattice”，只存在最大下界称为“meet semilattice”
全格
- Complete Lattice
- 一个偏序集的任意子集均存在最小上界和最大下界，那么这个偏序集成为全格
- 特点：
- 每个全格都存在一个最大元素 top（$\top=\sqcup P$）和最小元素bottom（$\bot=\sqcap P$）
- 所有元素有限的格（finite lattice）均是全格。（反之不成立）
乘积格
Product Lattice
给定$n$个格，$L_i=(P_i,\sqsubseteq_i),i=1,2…n$，如果每个格都有对应的$\sqcup i$(最小上界)和$\sqcap i$(最大下界)，那么我们得到一个乘积格$L_n=(P,\sqsubseteq)$并有以下四个定义：
$P=P_1\times P_2 \times …\times P_n$
$(x_1,…,x_n)\sqsubseteq(y_1,…y_n) \iff (x_1 \sqsubseteq y_1) \land … \land (x_n \sqsubseteq y_n)$（乘积格中两个元素满足偏序关系，等价于对应于每一个格中的两个元素满足偏序关系的交集）
$(x_1,…,x_n)\sqcup(y_1,…y_n) = (x_1 \sqcup_1 y_1,…,x_n \sqcup_n y_n)$乘积格中两个元素的 上确界，等价于对应于每一个格中的两个元素的 上确界 的集合）
$(x_1,…,x_n)\sqcap(y_1,…y_n) = (x_1 \sqcap_1 y_1,…,x_n \sqcap_n y_n)$乘积格中两个元素的 下确界，等价于对应于每一个格中的两个元素的 下确界 的集合）
举例：
考虑下图$L_1$、$L_2$
其乘积格$L=L_1\times L_2$是
全格的乘积仍是全格。
上界和下界
略。
粗糙集
基本概念
论域
也就是数学里面的集合，我们感兴趣的对象组成的集合。（非空）
知识
论域的任何一个子集（包括空集）称为知识，是对论域进行分类的能力。一般由特征属性进行分类。
知识库
是论域中的一个个知识族组成、
不可分辨关系
如果在只是表达中，由于缺乏一定的知识，不能将已知信息系统中的某些对象区分开，那么这些对象之间就是不可分辨关系（等价关系）
比如，若在动物中，以黑白为知识区分，那么黑色的狗和黑色的猫就是不可分辨关系，也就是等价关系。
基本集
论语中互相不可分表的对象组成的集合。
精确集和粗糙集
在某一个知识下，如果论域可以由知识中的一个或者多个子集组合而成，那么就成为精确集，否则就成为粗糙集。
上近似和下近似
上近似是指包含 给定集合 X 元素的 最小可定义集。下近似则是包含于X的最大可定义集。
正域、负域与边界域
接上一条，论域被上下近似划分为三个不相交的区域
知识粒度
论域的划分构成粗糙集的一个近似空间，划分中的每一个分开成为一个知识粒度。在粗糙集中，等价类的力度越细，其划分能力就越强，近似集越精确。否则划分能力就弱，近似集越粗糙。
属性重要度
这个始于分类质量相关的，可以参考底部介绍。
举例：
| 病人 | 头疼 | 肌肉疼 | 体温 | 流感 |
|---|---|---|---|---|
| $e_{1}$ | 是 | 是 | 正常 | 否 |
| $e_{2}$ | 是 | 是 | 高 | 是 |
| $e_{3}$ | 是 | 是 | 很高 | 是 |
| $e_{4}$ | 否 | 是 | 正常 | 否 |
| $e_{5}$ | 否 | 否 | 高 | 否 |
| $e_{6}$ | 否 | 是 | 很高 | 是 |
为一个决策系统，称$U=\lbrace e_1,…,e_6\rbrace$为论域
各列中，头疼、肌肉疼、体温 均为条件属性，流感为决策属性，这些属性所区分出来的子集便是知识。当然也同样可以用集合来表示，比如：
$$C_1=\lbrace 是,是,是,否,否,否\rbrace$$
而我们的目的便是挖掘，对决策属性影响大的条件属性。
在这里，我们继续设，在体温这个条件属性下的知识为：
$$
U/c_3=\lbrace\lbrace e_1,e_4\rbrace,\lbrace e_2,e_5\rbrace,\lbrace e_3,e_6\rbrace\rbrace=\lbrace X_1,X_2,X_3 \rbrace
$$
若$X=\lbrace e_1,e_2,e_4,e_5 \rbrace=X_1\cup X_2$，则称之为精确集；
若$X=\lbrace e_1,e_2,e_4\rbrace$，则为粗糙集。
考虑$X=\lbrace e_1,e_2,e_4\rbrace$、$U/c_3=\lbrace\lbrace e_1,e_4\rbrace,\lbrace e_2,e_5\rbrace,\lbrace e_3,e_6\rbrace\rbrace=\lbrace X_1,X_2,X_3 \rbrace$的情形，不难发现：
$$
\begin{matrix}
X_3 \cap X&=& \emptyset &;& X_3 \subsetneq X\\
X_2 \cap X&=& \lbrace e_2 \rbrace &;& X_2 \subsetneq X\\
X_1 \cap X&=& \lbrace e_1,e_4 \rbrace &;& X_1 \subseteq X
\end{matrix}
$$
于是有，$X_2$ 为上近似，$X_1$为下近似。
