粗糙集_学习笔记

1、大概 起源概念例子知识的约简决策表的约简、起源 含糊-模糊集-粗糙集1、在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)词，他把它归结到边界线上, 也就是说在全域上存在一些个体豹廖冥影子秦上分类,也不能在该子集的补集上分类。2、1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。3、20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集(RoughSet)'他把那些无法确认的

2、个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完全由数据决定,所以更有客观性。粗糙集理论 的主要优势之一是它不需要任何预备的或额外的有关数据信息。二、概念1、粗糙集(Rough S比也称Rough集、粗集)理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致.不完整信息与知识的数学工具.2、粗糙集理论最初的原型来源于比较简单的信息模型,它的基本思怨:通过关系数据库分类归纳形成概念和规则，通过等价关系的分类以及分类对于目标的近似实现知识发现.3、基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。4、全域或论城(

3、universe):即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在 起，这种特定部分称之为所讨论的全域或论域。5、族集(family):事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集，这个族集提 供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。6、一个近似空间(approximate space)(或知识库)定义为一个关系系统(或二元组)K=(U,R)其中U不为空集，是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R是U上等价 关系的一个族集。7、不可区分关系：设PUR,且PH0 ， P中所有等价关系的交集称为P上的一种不分明关系

4、 (indiscernbility relation)(或称不可区分关系)，记作上初(P)_ JAD < P ) _兀 _R1 e P8、概念(concept):给定近似空间K=(Uf R),子集X称为U上的一个概念(concept),形式上, 空集也视为一个概念；基本知识(basic knowledge):非空子族集P匚'R所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)相应的等价类称为基本概念初等知识(elementary knowledge):特别地，若关系Q& R ,则关系Q就称为初等知识初等概念(elementary concept):相应

5、的等价类就称为初等概念9、下近似与上近似X的下近似;R. (X) = -v: (-re U) a (-d RcX )X 的上近似：R*(X) = v: (xeU)/(OrcX#0 )X 的边界区域：(X) =R* (X) -& (X)若边界区域不为空集，则集合X就是一个粗糙概念。其中，下近似包含了所有使用知识R可确切分类到X的元素，上近似则包含了所有那些可能是属于X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。Upper Approximation:AZ=UKe UfRYoX(pL ower Approxim ation:=R-YX10、新型的隶属关系设XcU

6、 FLxeU,集合X的粗糙隶屈西数(rough membership function)定 义力 r , 、 card (X c R (工)LI (x)=严”card (J?(x)其中R是不分明关系可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率,能够从全域上的个体加以计算，而不是主观给定的。11.近似度 Accuracy of Approximation其中 # |X| denotes the cardinality(基数)of XIf 务3) 7 X is crisp with respect to 7?.If 冬QQ <L -Vis rouh w

7、ith respect to R不可走义12x 近彳以Properties of ApproximationsR(X)qXqRX£(0) =豆(0) = 0, R(U) = R(U) = U R(XjY) = R(X)<jR(Y) QcYXggc&Y)XqY implies R(X)匚 £(Y) and R(X)匸 R(Y)斤(XcF)匸斤(約c聂(F)&一 X)= -斤(X) R(_X) = -R(X) r(r(x)=P®xy)=£(x) R(R(X) = R(Rm)= R(X)where -X denotes U - X.三.

8、例子:UHeadacheTemp.FluU1YesNormalNo12YesHighYes匸3Yes'ury-highYesL4NoNormalNo15NqHighNq16NoVery-highYesU7NqHigh兀sU8NoVery highNo= u I Flu(u) = yes=u2, u3? u6 u7RX1 = 】2 u3= i2 u6t u7 h8, u5The indiscernibility classes defined by J? = Headache, Temp. are (ul9 u2, (u3 u4, u5f u79 u6t u8.X2 = u | Flu(

9、u) = no=ul, u49 u5f u8RX2 = ul, u4RX2 = ul, h4, u5, u8, u7, 116四、知识的约简(一) 般约简1、定义1设R是等价关系的一个族集,且设RR。若IND(R)=IND(R-R'),则称关系R'在族集R之中是可省的(dispensable).否则就是不可省的。若族集R中的每个关系R都是不可省的则称族集R是独立(independent).否则就是依赖的或非独立的。2、定义2若QU P是独立的，并且IND(Q)=IND(P)，则称Q是关系族集P的一个约简(reduct)。在族集P中所有不可省的关系的集合称为P的核(core)以C

10、ORE(P)来表示。显然，族集P有多个约简(约简的不唯一性)。3、定理1族集P的核等于P的所有约简的交集。即CORE(P)=ARED(P)4、例子设有F识库K二U,p,q,r其中U=xl,x2/x3/x4,x5/x6,x7/x8且U/p=xl/x4,x5/x2/x8,x3rx6,x7U/q=xl,x3,x5,x6,x2/x4 ,x7,x8U/r=xl,x5Jx6Lx2/x7lx8/x3,x4(1)若 P二pqr则 IND(P)= xl,x5/x2/x8/x3/x4,x6/x7(2 )对于U上的子集Xl=xlzx4,x7可得到下近似:P* Xl=x4Ux7=x4 ,x7上近似:P* Xl=xl

11、,x5Ux4Ux7=xl ,x4 ,x5 ,x7(3)若 P=pfq,r.则 IND(P)=xl ,x5/x2 ,x8,x3,x4,x6,x7, IND(P-p)=«xl /X5rx2 ,x7 ,x8,x3,x4,x6#IND(P) 所以p是不可省的同理可得q、r是可省的。也就说，p,qfnp, r就是P的约简而且p是P的核也就是说p是绝对不能省的(二) 相对约简1、定义3设P和Q是全域U上的等价关系的族集，所谓族集Q的P正区域(P-positive region ofQ) ”记作pa$p(Q)=U p*(x)XeU J Q族集Q的P正区域是全域U的所有那些使用分类U/P所表达的知识

12、，能够正确地分类于U/Q的等价类之中的对象的集合。2、定义4设P和Q是全域U上的等价关系的族集，RE Po若$M9(P)(Z切(Q)二P0%负？_R),则称关系R在族集P中是Q可省的；否则称为Q不可省的；如果在族集P中的每个关系R都是Q-不可省的贝I称P关于Q是独立的否则就称为是依赖的。3、定义5SC P称为P的Q约®(Q-reduct):当且仅当S是P的Q独立的子族集,且 POSs(Q)=POSp(Q)；族集P中的所有Q-不可省的初等关系的集合，称为族集P的Q核(Q-core),记作COREq(P)4、定理2族集P的Q-核等于所有P的Q-约简的交集。即COREq( P 尸 cRED

13、q(P)其中REDq(p)是所有p的q_约简的集合。5、例子设有F识库K二U,p,q,r其中U=xl,x2/x3/x4/x5/x6,x7/x8且U/p=xl, x3 ,x4,x5 x6/x7,x2,x8U/q=xl,x3/ x4 , x5 x乙 x6 ,x7,x8U/r=xl,x5,x6,x2/x7,x8fx3/x4(1)Q的P-正区域fP= Ip, Q, r,则砲(P) = xx, Xg, %, xj, h3, X4, %, x7 求并集假设U/Q= xn Xg, Xg, x2, x7, x3, xgQ的P的正域二比屯 U x3, xj U % U x7=xlrXjj x4r X5>

14、X7 求：IND(P可表示U/(廡合并集(2)可省U/ (p- p) =U/ (q, r)二xlt x5, x2> x7, x8, x3> xj, * 求u/q 和u/r并集 Pos(P-p)(Q)= xlf % U x3, x4) U 区二xlt x3, x4> Xe /Pos(P)(Q) p不是可省的注=求TND(Pt)可表示1”Q礙合并集(3 ) Q约简r Q核U/(P-q)=U/(p, r)= x"5, x6,x2, x8范34,x7Pos( p.q)(Q)= xl,x5, x6 U x3c4 U x7 = *13正4澤5/6工7 = Pos(p)(Q) :

15、 q是可省的U/(p-r)=U/(p, q)= xl, x3, x4,x5,x2, x8, x7, x6Pos( p.(r )(Q)=空 / Pos(p)(Q) ： T是不可省的p的Q的核为p, r,也是p的Q约简（三）知识的依赖性定义1设K=(U, R虚一个知识库，P, QcR,我们称知识Q以依 鞭度和05已1)依赖于知识已记作P=>&当且仅当A%(Q)="(POSp(Q)/'c“M(U)(1) 若E，则称知识Q完全依赖于知识P, P=hQ也记成P=Q;若0<Rl,则称知识Q部分依赖于知识P; 若E),则称知识Q完全独立于与知识氏例子：(1)U/P=xl

16、/x5/x2,x8,x3,x6/x4/x7U/Q 二xl,x5,x2,x8,x7,x3,x6,x4U/P U/Q, P Q(2)U二123,45,6,7,8;U/Q=X1,X2,X3,X4,X5/其中 XI = 1, X2=2,7, X3=3f6, X4=4, X5=5,8;U/P=Y1/Y2,Y3,Y4/Y5;其中 Y1 = 1,5, Y2=2,8L Y3=3), Y4=4, Y5=6;Y6=7POSp(Q)二3U4U6U7=3,4,6,7rp(Q) =card(POSP(Q)/card(U) = 4/8 =0.5五、决策表的约简1、决策表，定义S=(U, A)为一信息系统，且C, DUA是

17、两个属性子集，分别称为条件属性和决策属性，且CUD=A , CUD二空集，则该信息系统称为决策表,记作T=(U, A, C, D)或简称CD决策表。关系IND(C)和关萦IND(D)的等价类分别称为条件类和决策类2、两个命题命题1当且仅当CPD,决策表T=(UA C,。是一致的。由命题很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于1 时，我们说决策表是一致的，否则不一致。命题2每个决策表r=(UAC,D)都可以唯一分解为两个决策表T1=U1,A, C,。和T2=(U2,A, C, D.这样使得表力中 5D (完全依赖丿和7中8°D (完全独立)。这里Ui=P

18、OS(D,U徒BNc冷,由命题2可见，假设我们已计算出条件属性的依赖度，若表的结果不一致,即依赖度小于1, 则由命题2可以将表分解成两个子表:其中一个表完全不一致，依赖度为0 ;另一个表则完全致，依赖度为lo当然，只有依赖度大于0且不等于1时，这一分解才能进行。3、一致决策表的约简致决策表的约简步骤如下：(1) 对决策表逬行条件属性的约简，即从决策表中消去某一列；(主要硏究点)(2) 消去重复的行；(3) 消去每一决策规则中属性的冗余值。4、条件属性的约简A.Skowron提出了差别矩阵,使核与约简等概念的计算较为简单，主要思想：设为一个知识表示系统，其中U =gX2,. 力为所讨论的个体，/

19、=1,2，,n ,A二九毛,珈,可为个体所具有的属性J=：L2.m知识表达系统s的差别矩阵M(S) = Cijnxn ,其中矩阵项定义如下:Cjj=aeA : a(x0壬a(x» , i,j=12,n因此Cij是个体Xi与xj有区别的所有属性的集合5、差别矩阵对应的核与约简核就可以定义为差别矩阵中所有只有一个元素的矩阵项的集合，即CO/?£(A) = aeA : Cij=(a)，对一些 ij相对于集合包含关系运算而言，若属性集合BIA是满足下列条件BOcijf，对于M(S)中的任一非空项CijM的一个最小属性子集，则称属性集合BfA是A的 一个约简。换言之，约简是这样的最小

20、属性子集，它能够区分用整个属性集合A可区分的所有对象。6、Skowron的约简方法根据差别函数与约简的对应关系，A.Skowron提出了计算信息系统S的约简RED的方 法：1)计算信息系统S的差别矩阵M(S)2 )计算与差别矩阵M(S)对应的差别函数fM3 )计算差别函数fM(S)的最小析取范式,其中每个析取分量对应一个约简7、行的约简对的行要删除，因为它们的条件属性和决策属性都相同决策表中的重复，都表示同一条决策 规则。另外，决策规则的列表顺序不是本质性的8、属性值的约简对于决策表而言,属性值的约简就是决策规则的约简。决策规则的约简是利用决策逻辑消去 每个决策规则的不必要条件，它不是整体上约

21、简属性，而是针对每个决策规则，去掉表达该规则 时的冗余属性值，即要计算每条决策规则的核与约简。9、求最优或次优约简所有约简的计算是NP-hard问题，因此运用启发信息来简化计算以找出最优或次优约简是必 要的。现在在求最优或次优约简的算法一般都使用核作为计算约简的出发点，计算一个最好的或者用 户指定的最小约简。算法将属性的重要性作为启发规则，按照属性的重要度从大到小逐个加入属 性，直到该集合是一个约简为止。10、非一致决策表的约简对于一致的决策表比较容易处理，在进行约简时，只要判断去掉某个属性或某个属性值时是 否会导致不一致规则的产生。而对不一致表进行约简时就不能再使用这种方法了，一般采用下面的

22、方法：一种是考虑正域 的变化，另外一种是将不一致表分成完全一致表和完全不一致表两个子表。非一致决策表的约简步骤与一致决策表的约简步骤类似。六、粗糙集的扩展模型1、基本粗糙集理论的主要存在的问题1）对原始数据本身的模糊性缺乏相应的处理能力；2) 对于粗糙集的边界区域的刻画过于简单；3) 粗糙集理论的方法在可用信息不完全的情况下将对象们归类于某一具体的类，通常分类是 确定的，但并未提供数理统计中所常用的在一个给定错误率的条件下将尽可能多的对象进行分类的 方法，而实际中常常遇到这类问题。2、可变精度粗糙集模型W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了错误率低于预先给定值的分 类

23、策略，定义了该精度下的正区域、边界区域和负区域。3、相似模型在数据中存在缺失的属性值的时候(在数据库中很昔遍)，不分明关系或等价关系无法处理这 种情形。为扩展粗糙集的能力，有许多研究者提出了用相似关系来代替不分明关系作为粗糙集的基 础。4、基于粗糙集的耳弹调逻辑：通过粗糙集建立粗糙逻辑5、与其它数学工具的结合(1 ) D.Dudios 和 H.Prade 由此提出了 Rough Fuzzy Set 和 Fuzzy Rough Set 的概念(2 ) A.Skowron和J.Grazymala-Buss认为，粗糙集理论可以看作证据理论的基础。并在粗糙集 理论的框架上重新解释了证据理论的基本概念，

24、特别是用上近似和下近似的术语解释了信念 (belief)和似然(plausibility)函数，进而讨论了两者之间的互补问题。七、粗糙集的试验系统1、LERSLERS(Learning from examples based on Rough Set) r 系统是美国 Kansas 大学开发的基 于粗糙集的实例学习系统。它是用Common Lisp在VAX9000上实现的。LERS已经为NASA的 Johnson空间中心应用了两年。此夕卜，LERS还被广泛地用于环境保护、气候硏究和医疗研究2、ROSE波兰Poznan科技大学基于粗糙集开发了 ROSE(Rough Set data Explor

25、er),用于决策分析。 它是Rough Das & Rough Class系统的新版，其中RoughDas执行信息系统数据分析任务, RoughClass支持新对象的分类，这两个系统已经在许多实际领域中得到应用。3、KDDRKDD-R是由加拿大的Regina大学开发的基于可变精度粗糙集模型，采用知识发现的决策矩 阵方法开发了 KDD-R系统，这个系统被用来对医学数据分析，以此产生症状与病证之间新的联 系，另外它还支持电信工业的市场研究。八、粒度计算(简单引一下)1、定义粒度计算的思想是一种看待客观世界的世界观和方法论。粒度计算的基本思想就是使用粒而不是对象为计算单元从广义上来说，粒度计算是信息处理的一种新的概念和计算范式,覆盖了所有和粒度相关的理论、 方法、技术和工具的信息2、必要性(1 )从哲学的角度看Yager和Filev指出"人类已