粗糙集考试资料整理.docx

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

例 如，实数集中的“>”关系就是2维平面中的子集｛ (x, y)： x >y｝；整数集中的“整除”关系 就是ZXZ中的子集｛ (a, b)：存在qWZ,使得b = ra｝；等等等价关系：满足反身性，对称性和传递性的关系例如，相等关系，三角形的相似关系 等价关系与集合分类：一个等价关系可以给集合一个分类(等价类)；集合的一个分类 也对应一个等价关系最细的分类和最粗的分类由等价关系R产生的关于集合U的分类(等价类)就是这个集合包含的知识分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系(indiscernability relation).假定只用两种黑白颜色把空间中的物体分割两类｛黑色物体｝,｛白色物体｝，那么同为 黑色的两个物体就是不可分辨的, 因为描述它们特征属性的信息相同, 都是黑色. 如果再引 入方,圆的属性, 又可以将物体进一步分割为四类 : ｛黑色方物体｝,｛黑色圆物体｝,｛白色方物 体｝,｛白色圆物体｝. 这时, 如果两个同为黑色方物体, 则它们还是不可分辨的. 不可分辨关系 也称为一个等效关系(equivalence relationship ),两个白色圆物体间的不可分辨关系可以 理解为它们在白,圆两种属性下存在等效关系.3、精确集与粗糙集定义：设U为所讨论对象的非空有限集合，称为论域；R为建立在U上的一个等价关 系，称二元有序组aPr = G,R)为近似空间(Approximate Space)。

近似空间构成论域U的 一个划分；若R是U上的一个等价关系，以lx]表示x的R等价类，U /R表示R的所有R等价类构成的集合，即商集；R的所有等价类构成U的一个划分，划分块与等价类相对应 等价关系组成的集合为等价关系族如果U中的两个元素x和y属于相同的等价类，则称x和y是不可分辨的任意一个给定的集合X匸U,如果无法用R等价类精确地描述，则称X为R的粗糙 集；反之X是R的精确集(X是等价类的并)4、属性间的依赖程度知识的依赖性可形式化地定义如下：令K= (U, R)是一个知识库，P、Q匚Ro1) 知识Q依赖于知识P (记作P = Q)当且仅当IND(P)UIND(Q)2) 知识Q与知识P等价(记作P三Q)当且仅当P = Q且Q = Po3) 知识Q与知识P独立(记作P丰Q)当且仅当P = Q与Q = P均不成立当知识Q依赖于知识P时，也可以说知识Q是由知识P导出的有时候知识的依赖性可能是部分的，这意味着知识Q仅有部分是由知识P导出的，这可以由知识的正域来定义：令K= (U，R)是一个知识库，P、Q匸Ro当 k = 丫 p(Q)=UI时，我们称知识Q是k度依赖于知识P的，记作P = ?Qo当 kk =1时，我们称Q完全依赖于P；当0

关于计算会涉及的内容：上近似和下近似：apr(X) = U [x] = {x: [x]匸 X}[x ]RZ X R Rapr(X) = U [x] = {x:[x] nX 鼻①}RR[x ]rA X H①正域、负域、边界域和粗糙集POS (X)二 apr(X)NEG( X)二 U - apr(X)BND(X)二 Opr(X) — apr(X)边界区域正区域负区域集合X的正区域、负区域和边界区域图中椭圆围成的区域为X,每个小矩形表示一个等价类由图可见，任何属于POS(X) 的元素x也一定属于X；任何属于NEG的元素x 一定不属于X；当x属于BND时，它可能属 于X,也可能不属于X如果BND等于空集，则X是关于R的精确集；反之，X为关于R的 粗糙集信息系统是一种知识表达方式，形式上，用四元组S = (U, A, V, f)表示一个信息系统,其中：U :对象的非空有限集合，即论域.U = {X], x2，…召} ；xA :属性的非空有限集合；通常将属性集分为两类，A二C U D，C U D =①，C称 为条件属性集合， D 称为决策属性集V=UV ， V 是属性的值域；aaaeAf : U X A t V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即Va e A， x e U， f (x:,a )e V。

a显然，信息系统可以用关系数据表格来表示，表格的行对应论域中的对象，列对应对象的属性一个对象的全部信息由表中一行属性的值来反映信息系统有一个自然的等价关系设P匸A且P工①，定义由属性子集P导出的二元关系如下：IND(P)=Cy)l (x, y) g U x U且Va g P,有f (x,a) = f (y,a)}，可以证明 IND(P)是等价关系，称其为由属性集P导出的不可分辨关系若(x, y) g IND(P),则称x和y是P不可分辨的，这是因为依据P中所含的各属性是无法区分X和y的特别地，当P = {a}，仅含一个属性时，由属性a g A导出的等价关系为： IND(a) = Cx, y)l (x, y) g U x U且f (x,a) = f (y,a)}则P匸A且P工①导出的不可分辨关系亦可定义为：IND(P) = IND(a) agP以下只涉及属性归约问题，即用尽可能少的描述属性对决策属性进行推理(例子讲解)UA1A2100210311402512610712800A3A4A5100211100111101100211211上表是一个信息系统，其中 U = {1， 2， 3， 4， 5， 6， 7， 8}；A = {A1， A2， A3， A4， A5}V = VA1U VA2 U VA3 U VA4 U VA5 = {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}，则apr (X) = U{Y e U / IND(P): Y c X} = {4,5,7}PopT(X)二 U{Y e U / IND(P): Y c X 鼻①}二{1,2,4,5,6,7,8}(2)属性的依赖度在数据归约中，利用两个属性集合P, R之间的相互依赖程度，可以确定一个属性a的重要性(P对U有一个分类，R对U也有一个分类，如果分类完全相同，则P，R对于分类 来说是一样的)属性集P对R的依赖程度用Y (P)表示定义如下：Rcard (POS (P)) ,,Y (P)= "仪 ,POS (P) = U apr (X)R card (U) R RXeU / IND(P)其中card(.)表示集合的基数，POSR(P)是属性集R在U/IND(P)中的正区域。

R例如，在上表中，令 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}}，apr ({1,3,6})=⑶,apr ({2,4,5,7,8}) = {4,5,7}从而，POSR(P)= R R R{3,4,5,7}, J (P) = 0.5 .题目为例：下面再给出一个粗糙集在知识发现中的例子下表给出一个关于八个病人的决策表，其中U = h , x , x , x , x , x , x , x }，属性集12345678A = C U D，条件属性集C =流鼻涕，咳嗽，发烧}决策属性集D =流感}U条件属性决策属性流鼻涕咳嗽发烧流感x1是是正常否x2是是高是x是是很高是x^否是正常否x否否高否x否是很高是x否否高是x否是很高否根据决策表可以得出：令a =流鼻涕，b =咳嗽，c =发烧，d =流感U/{a} = {x ,x ,x },{x ,x ,x ,x ,x }}1 2 3 4 5 6 7 8U/{b} = {x ,x ,x ,x ,x ,x },{x ,x }}1 2 3 4 6 8 5 7U/{c} = {x ,x },{x ,x ,x },{x ,x ,x }}1 4 2 5 7 3 6 8U /{a,b} = {x ,x ,x },{x ,x ,x },{x ,x }}1 2 3 4 6 8 5 7U /{a,c} = {x },{x },{x },{x },{x ,x },{x ,x }}1 2 3 4 5 7 6 8U/{b,c} = {x ,x },{x },{x ,x },{x ,x ,x }}1 4 2 5 7 3 6 8U / C 二{{x } {x } {。