粗糙集考试资料整理

粗糙集：等价关系和分类；精确集和粗糙集；属性间的依赖程度(。一张表，互信息和依赖程度都计算)1、粗糙集基本概念：粗糙集(RoughSet)理论是波兰数学家乙Pawlak于1982年提出的，是一种新的处理含糊性和不确定性问题的数学工具。相对于概率统计、模糊集等处理含糊性和不确定性的数学工具而言，粗糙集理论有这些理论不具备的优越性。统计学需要概率分布，模糊集理论需要隶属函数，而粗糙集理论的主要优势就在于它不需要关于数据的任何预备的或额外的信息。1982年，波兰学者乙Pawlak提出了粗糙集理论，它是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确，不一致(inconsistent),不完整(incomplete)等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律.粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分.粗糙集理论将知识理解为对数据的划分.每一被划分的集合称为概念.粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画.该理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比较客观的,由于这个理论未能包含处理不精确或不确定原始数据的机制,所以这个理论与概率论,模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性.在粗糙集理论中，"知识"被认为是一种分类能力.人们的行为是基于分辨现实的或抽象的对象的能力，根据事物的特征差别将其分门别类的能力均可以看作是某种知识".2、关系、等价关系和分类关系R：设U是一个非空集合，R是U上的一个关系，如果R是UXU的一个子集。例如，实数集中的“>”关系就是2维平面中的子集｛(x,y)：x>y｝；整数集中的“整除”关系就是ZXZ中的子集｛(a,b)：存在qWZ,使得b=ra｝；等等。等价关系：满足反身性，对称性和传递性的关系。例如，相等关系，三角形的相似关系。等价关系与集合分类：一个等价关系可以给集合一个分类(等价类)；集合的一个分类也对应一个等价关系。等价类。最细的分类和最粗的分类。由等价关系R产生的关于集合U的分类(等价类)就是这个集合包含的知识。分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系(indiscernabilityrelation).假定只用两种黑白颜色把空间中的物体分割两类｛黑色物体｝,｛白色物体｝，那么同为黑色的两个物体就是不可分辨的,因为描述它们特征属性的信息相同,都是黑色.如果再引入方,圆的属性,又可以将物体进一步分割为四类:｛黑色方物体｝,｛黑色圆物体｝,｛白色方物体｝,｛白色圆物体｝.这时,如果两个同为黑色方物体,则它们还是不可分辨的.不可分辨关系也称为一个等效关系(equivalencerelationship),两个白色圆物体间的不可分辨关系可以理解为它们在白,圆两种属性下存在等效关系.3、精确集与粗糙集定义：设U为所讨论对象的非空有限集合，称为论域；R为建立在U上的一个等价关系，称二元有序组aprU,R为近似空间（ApproximateSpac）近似空间构成论域U的—个划分；若R是U上的一个等价关系，以xr表示x的R等价类，U/R表示R的所有R等价类构成的集合，即商集；R的所有等价类构成U的一个划分，划分块与等价类相对应。等价关系组成的集合为等价关系族。如果U中的两个元素x和y属于相同的等价类，则称x和y是不可分辨的。任意一个给定的集合XU，如果无法用R等价类精确地描述，则称X为R的粗糙集；反之X是R的精确集（X是等价类的并）。4、属性间的依赖程度知识的依赖性可形式化地定义如下：令K=（U，R）是一个知识库，P、QR。1） 知识Q依赖于知识P（记作PQ）当且仅当INDP）INDQ）。2） 知识Q与知识P等价（记作PQ）当且仅当PQ且QP。3） 知识Q与知识P独立（记作PQ）当且仅当PQ与Q P均不成立。当知识Q依赖于知识P时，也可以说知识Q是由知识P导出的。有时候知识的依赖性可能是部分的，这意味着知识Q仅有部分是由知识P导出的，这可以由知识的正域来定义：令2（U，R）是一个知识库，P、QR。POS（Q）|当k=P（Q）=UP时，我们称知识0是艮度依赖于知识P的，记作PkQ。当k=l时，我们称Q完全依赖于P;当o〈k〈l时，称Q粗糙依赖于P;当k=o时，称Q完全独立于P。系数P（Q）可以看作Q和P之间的依赖度。关于计算会涉及的内容：上近似和下近似：TOC\o"1-5"\h\zapr（X） [x]{x:[x] X}[x]RxR Rapr（X） [x]{x:[x]X}[x]RX R R正域、负域、边界域和粗糙集

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二CUD，CUD=①，C称为条件属性集合，D称为决策属性集。V=UV，V是属性的值域；aaaeAf:UXAtV是一个信息函数，它为每个对象的每个属性赋予一个信息值，即VaeA，xeU，f(x:,a)eV。a显然，信息系统可以用关系数据表格来表示，表格的行对应论域中的对象，列对应对象的属性。一个对象的全部信息由表中一行属性的值来反映。

信息系统有一个自然的等价关系。设P匸A且P工①，定义由属性子集P导出的二元关系如下：IND(P)=Cy)l(x,y)gUxU且VagP,有f(x,a)=f(y,a)}，可以证明IND(P)是等价关系，称其为由属性集P导出的不可分辨关系。若(x,y)gIND(P),则称x和y是P不可分辨的，这是因为依据P中所含的各属性是无法区分X和y的。特别地，当P={a}，仅含一个属性时，由属性agA导出的等价关系为：IND(a)=Cx,y)l(x,y)gUxU且f(x,a)=f(y,a)}则P匸A且P工①导出的不可分辨关系亦可定义为：IND(P)=IND(a)。agP以下只涉及属性归约问题，即用尽可能少的描述属性对决策属性进行推理(。例子讲解)UA1UA1A2100210311402512610712800A3A4A5100211100111101100211211上表是一个信息系统，其中U={1，2，3，4，5，6，7，8}；A={A1，A2，A3，A4，A5}V=VA1UVA2UVA3UVA4UVA5={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{YeU/IND(P):YcX}={4,5,7}PopT(X)二U{YeU/IND(P):YcX鼻①}二{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)= Uapr(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=CUD，条件属性集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}}12345678U/{b}={x,x,x,x,x,x},{x,x}}12346857U/{c}={x,x},{x,x,x},{x,x,x}}14257368U/{a,b}={x,x,x},{x,x,x},{x,x}}12346857U/{a,c}={x},{x},{x},{x},{x,x},{x,x}}12345768U/{b,c}={x,x},{x},{x,