粗糙集：等价关系和分类；精确集和粗糙集；属性间的依赖程度。

（一张表，互信息和依赖程度都计算）1、粗糙集基本概念：粗糙集（Rough Set）理论是波兰数学家Z.Pawlak于1982年提出的，是一种新的处理含糊性和不确定性问题的数学工具。

相对于概率统计、模糊集等处理含糊性和不确定性的数学工具而言，粗糙集理论有这些理论不具备的优越性。

统计学需要概率分布，模糊集理论需要隶属函数，而粗糙集理论的主要优势就在于它不需要关于数据的任何预备的或额外的信息。

1982 年, 波兰学者Z. Paw lak 提出了粗糙集理论, 它是一种刻划不完整性和不确定性的数学工具, 能有效地分析不精确,不一致( incon sisten t),不完整( incomp lete) 等各种不完备的信息, 还可以对数据进行分析和推理, 从中发现隐含的知识, 揭示潜在的规律. 粗糙集理论是建立在分类机制的基础上的, 它将分类理解为在特定空间上的等价关系, 而等价关系构成了对该空间的划分.粗糙集理论将知识理解为对数据的划分, 每一被划分的集合称为概念.粗糙集理论的主要思想是利用已知的知识库, 将不精确或不确定的知识用已知的知识库中的知识来(近似) 刻画.该理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息, 所以对问题的不确定性的描述或处理可以说是比较客观的, 由于这个理论未能包含处理不精确或不确定原始数据的机制, 所以这个理论与概率论, 模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性.在粗糙集理论中,"知识"被认为是一种分类能力.人们的行为是基于分辨现实的或抽象的对象的能力, 根据事物的特征差别将其分门别类的能力均可以看作是某种"知识".2、关系、等价关系和分类关系R：设U是一个非空集合，R是U上的一个关系，如果R是U×U的一个子集。

例如，实数集中的“>”关系就是2维平面中的子集{（x, y）：x >y}；整数集中的“整除”关系就是Z×Z中的子集{（a, b）：存在q∈Z，使得b = ra}；等等。

等价关系：满足反身性，对称性和传递性的关系。

例如，相等关系，三角形的相似关系。

等价关系与集合分类：一个等价关系可以给集合一个分类（等价类）；集合的一个分类也对应一个等价关系。

等价类。

最细的分类和最粗的分类。

由等价关系R产生的关于集合U的分类（等价类）就是这个集合包含的知识。

分类过程中, 相差不大的个体被归于同一类, 它们的关系就是不可分辨关系( indiscernability relation). 假定只用两种黑白颜色把空间中的物体分割两类, {黑色物体},{白色物体},那么同为黑色的两个物体就是不可分辨的, 因为描述它们特征属性的信息相同, 都是黑色. 如果再引入方,圆的属性, 又可以将物体进一步分割为四类: {黑色方物体},{黑色圆物体},{白色方物体},{白色圆物体}. 这时, 如果两个同为黑色方物体, 则它们还是不可分辨的. 不可分辨关系也称为一个等效关系(equivalence relationship ), 两个白色圆物体间的不可分辨关系可以理解为它们在白,圆两种属性下存在等效关系.3、精确集与粗糙集定义：设U 为所讨论对象的非空有限集合，称为论域；R 为建立在U 上的一个等价关系，称二元有序组()R U apr ,=为近似空间（Approximate Space ）。

近似空间构成论域U 的一个划分；若R 是U 上的一个等价关系，以[]R x 表示x 的R 等价类，R U /表示R 的所有等价类构成的集合，即商集；R 的所有等价类构成U 的一个划分，划分块与等价类相对应。

等价关系组成的集合为等价关系族。

如果U 中的两个元素x 和y 属于相同的等价类，则称x 和y 是不可分辨的。

任意一个给定的集合X ⊆U ，如果无法用R 等价类精确地描述，则称X 为R 的粗糙集；反之X 是R 的精确集（X 是等价类的并）。

4、属性间的依赖程度知识的依赖性可形式化地定义如下：令K=（U ，R ）是一个知识库，P 、Q ⊆R 。

1) 知识Q 依赖于知识P （记作P ⇒Q ）当且仅当IND(P )⊆IND(Q )。

2) 知识Q 与知识P 等价（记作P ≡Q ）当且仅当P ⇒Q 且Q ⇒P 。

3) 知识Q 与知识P 独立（记作P ≠Q ）当且仅当P ⇒Q 与Q ⇒P 均不成立。

当知识Q 依赖于知识P 时，也可以说知识Q 是由知识P 导出的。

有时候知识的依赖性可能是部分的，这意味着知识Q 仅有部分是由知识P 导出的，这可以由知识的正域来定义：令K=（U ，R ）是一个知识库，P 、Q ⊆R 。

当k =)Q (P γ=U)Q (POS P 时，我们称知识Q 是k 度依赖于知识P 的，记作P k ⇒Q 。

当k =1时，我们称Q 完全依赖于P ；当0<k <1时，称Q 粗糙依赖于P ；当k =0时，称Q 完全独立于P 。

系数)Q (P γ可以看作Q 和P 之间的依赖度。

关于计算会涉及的内容：上近似和下近似：}][:{][)(][X x x x X apr R R Xx R ⊆==⊆}][:{][)(][Φ≠==Φ≠⋂X x x x X apr R R X x R正域、负域、边界域和粗糙集)()()()()()()(X apr X apr X BND X apr U X NEG X apr X POS -=-==图中椭圆围成的区域为X ，每个小矩形表示一个等价类。

由图可见，任何属于POS （X ）的元素x 也一定属于X ；任何属于NEG 的元素x 一定不属于X ；当x 属于BND 时，它可能属于X ，也可能不属于X 。

如果BND 等于空集，则X 是关于R 的精确集；反之，X 为关于R 的粗糙集。

信息系统是一种知识表达方式，形式上，用四元组),,,(f V A U S =表示一个信息系统，其中：U ：对象的非空有限集合，即论域. U = {x 1, x 2, …, x n }；A ：属性的非空有限集合；通常将属性集分为两类，D C A =，D C =Φ，C 称为条件属性集合，D 称为决策属性集。

V =a Aa V ∈ ，a V 是属性的值域；f ：V A U →⨯是一个信息函数，它为每个对象的每个属性赋予一个信息值，即A a ∈∀，U x ∈，()a V a x f ∈,。

显然，信息系统可以用关系数据表格来表示，表格的行对应论域中的对象，列对应对象的属性。

一个对象的全部信息由表中一行属性的值来反映。

负区域正区域 边界区域 集合X 的正区域、负区域和边界区域信息系统有一个自然的等价关系。

设Φ≠⊆P A P 且，定义由属性子集P 导出的二元关系如下：IND(P)=(){}),(),(,),(|,a y f a x f P a U U y x y x =∈∀⨯∈有且，可以证明IND(P)是等价关系，称其为由属性集P 导出的不可分辨关系。

若),(y x ∈IND(P), 则称x 和y 是P 不可分辨的, 这是因为依据P 中所含的各属性是无法区分x 和y 的。

特别地，当P = {a }，仅含一个属性时，由属性A a ∈导出的等价关系为：(){}),(),(),(|,)(a y f a x f U U y x y x a IND =⨯∈=且则Φ≠⊆P A P 且导出的不可分辨关系亦可定义为：IND(P) =)(a IND Pa ∈ 。

以下只涉及属性归约问题，即用尽可能少的描述属性对决策属性进行推理。

（例子讲解）上表是一个信息系统，其中U = {1，2，3，4，5，6，7，8}；A = {A1，A2，A3，A4，A5}；V = V A1∪V A2∪V A3∪V A4∪V A5 = {0，1，2}；映射函数f 将对象属性映射到它的值域。

（1）不可分辨关系和近似集根据不可分辨关系的定义，计算 U/IND(A5) = {{1, 3, 6}, {2, 4, 5, 7, 8}}U/IND(A1) = {{1,4,8},{2,3,5,6,7}} U/IND(A2) = {{1, 2, 6,8},{3}, {4, 5, 7}} U / IND(A2, A3) = {{1,6},{2,8},{3},{4,5},{7}} U / IND(A1,A2) = {{1,8},{2,6},{3},{4},{5,7}} 取X = {2,4,5,7,8}, P = {A1,A2}，则}7,5,4{}:)(/{)(=⊆∈=X Y P IND U Y X apr P}8,7,6,5,4,2,1{}:)(/{)(=Φ≠⋂∈=X Y P IND U Y X apr P（2）属性的依赖度在数据归约中，利用两个属性集合P ，R 之间的相互依赖程度，可以确定一个属性a 的重要性（P 对U 有一个分类，R 对U 也有一个分类，如果分类完全相同，则P ，R 对于分类来说是一样的）。

属性集P 对R 的依赖程度用)(P R γ表示。

定义如下：)())(()(U card P POS card P R R =γ, )(/)()(P IND U X R R X apr P POS ∈= 其中card(.)表示集合的基数，POS R (P)是属性集R 在U/IND(P)中的正区域。

例如，在上表中，令P = {A5}，R = {A1，A2}，则U/IND(P) = {{1,3,6}, {2,4,5,7,8}}，U / IND(R) = {{1,8},{2,6},{3},{4},{5,7}}，}7,5,4{})8,7,5,4,2({},3{})6,3,1({==R R apr apr 从而，POS R (P) = {3,4,5,7},5.0)(=P R γ.题目为例：下面再给出一个粗糙集在知识发现中的例子。

下表给出一个关于八个病人的决策表，其中U ={}87654321,,,,,,,x x x x x x x x ，属性集D C A =，条件属性集{}发烧咳嗽流鼻涕,,=C ，决策属性集{}流感=D 。

根据决策表可以得出：令a =流鼻涕，b =咳嗽，c =发烧，d =流感。

}/{a U ={}},,,,{},,,{87654321x x x x x x x x}/{b U ={}},{},,,,,,{75864321x x x x x x x x }/{c U ={}},,{},,,{},,{86375241x x x x x x x x },/{b a U ={}},{},,,{},,,{75864321x x x x x x x x },/{c a U ={}},{},,{},{},{},{},{86754321x x x x x x x x},/{c b U ={}},,{},,{},{},,{86375241x x x x x x x x{}{}{}{}{}{}{}86754321,,,,,,,/x x x x x x x x C U =；{}{}{}85417623,,,,,,,/x x x x x x x x D U =； 根据依赖度的定义，我们可以得到：)(POS C D ={}4321,,,x x x x ；=k UD )(POS C =0.5。