第五讲：粗糙集(Rough Set)

《第五讲：粗糙集(Rough Set)》由会员分享，可在线阅读，更多相关《第五讲：粗糙集(Rough Set)（11页珍藏版）》请在装配图网上搜索。

1、第三节 粗糙集(Rough Set RS)如果我们将研究对象看成是现象，那么我们可以将这些现象分类。现象被 分为确定现象与不确定现象。不确定现象有分为随机现象，模糊现象和信息不 全的粗糙现象。如下所示：确定现象随机现象，o-1律，多种可能性满足分布规律。现象J.不确定现象模糊现象，律属度Ie(0 ,1 ),不是非此即彼。粗糙现象，研究那些因为信息不充分而导致的不确定性相对于前两种现象的处理，粗糙现象是基于不完全的信息或知识去处理不分明 的现象，因此需要基于观测或者测量到的部分信息对数据进行分类，这就需要 与概率统计和模糊数学不同的处理手段，这就是粗糙集理论。直观地讲，粗糙 集是基于一系列既不知

2、道多了还是少了，也不知道有用还是没用的不确定、不 完整乃至于部分信息相互矛盾的数据或者描述来对数据进行分析、推测未知信 息。下面我们对粗糙集的基本特征、以及数学符号进行简述。1粗糙集的特点粗糙集的特点是利用不精确、不确定、部分真实的信息来得到易于处理、 鲁棒性强、成本低廉的决策方案。因此更适合于解决某些现实系统，比如，中 医诊断，统计报表的综合处理等。粗糙集的另一个重要特点就是它只依赖于数 据本身，不需要样本之外的先验知识或者附加信息，因此挑选出来的决策属性 可以避免主观性，有英雄不问出身的意味。用粗糙集来处理的数据类型包括确 定性的、非确定性的、不精确的、不完整的、多变量的、数值的、非数值的

3、。 粗糙集使用上、下近似来刻画不确定性，使得边界有了清晰的数学意义并且降 低了算法设计的随意性。3粗糙集的基本概念粗糙集要涉及论域U (这与模糊系统相似)，还要涉及属性集合R = C D(这被认为是知识，或者知识库)。当然，也要有属性值域V，以及从U X R到V 的信息函数f。因此，一个信息系统S可以表示为一个四元组S = u , R, V, f 。 在不混淆的情况下，简记为s = (U , R)，也称为知识库。等价关系(通常用来代替分类)是不可或缺的概念，根据等价关系可以划 论域中样本为等价类。而每个等价类被称为同一个对象。但是，等价关系又是 建立在不可分辨概念之上的，为了便于描述这里的等价

4、关系，我们首先介绍不 可分辨性。设B匸R为一个非空子集，如果x , x e U，均有f (x , r) = f (x , r), V r e B成i j i j立，那么，我们称 x 和 x 关于属性子集 B 不可分辨。 B 不可分辨关系，简记为 ijInd ( B ) ，是 一种等价关系(易验证它满足等价关系的数学公理)， 于是 Ind ( B ) 可 以将论域U中的元素分成若干等价类，每一个等价类称为知识库的知识颗粒。 全体等价类组成的集合记为U / Ind (B)，称之为基本集合。若集合X可以表示成 某些基本集的并时，则称X是B精确集，否则称为B粗糙集。粗糙集中的“粗糙” 主要体现在边界域

5、的存在，而边界又是由下、上近似 来刻画的。对于任意X uU，X关于现有知识R的下、上近似分别定义为：R _( X ) = x e U , x 匸 X ， R - (x) = x e U , x c X h 。RRX的确定域Pos ( X )= R ( X )，是指论域U中那些在现有知识R之下能够确定地 归入集合x的元素的集合。反之，Neg (X )= U - R (X )被称为否定域。边界域 是某种意义上论域的不确定域，即在现有知识R之下U中那些既不能肯定在X 中，又不能肯定归入X = U X中的元素的集合，记为Bnd (X )。R样本子集X的不确定性程度可以用粗糙度a (X )来刻画，粗糙度

6、的定义为:Ra (X ) =RCardX )Card (R - (X )式中Card表示集合的基数(集合中元素的个数)。显然，0 a (X ) 1，如果Ra (X )= 1，则称集合X关于R是确定的；如果a (X ) 1，则称集合X关于R RR是粗糙的，a (X )可认为是在等价关系R下逼近集合X的精度。R为了使得上述概念具体化，下面我们举一个例子说明如何理解和计算以上相应的概念和对应量。例. 针对一下医学信息表我们来理解前面所提到的概念。表 1 某医疗信息表属性条件属性C决策属性D对象头疼r1肌肉疼r2体温r3流感x是是正常否x是是高是x是是很高是x否是正常否x否否高否x否是很高是依据此表，

7、如果取属性子集R = 头疼,肌肉疼=r , r， X = x , x , x 。那么 1 2 1 2 3我们下面给出 X 的上近似集、下近似集、确定域、边界域、粗糙度。解：计算论域U的所有R基本集： U / Ind (R) = x , x , x , x , x , x 1 2 3 4 6 5令 R =x , x , x R = x , x R = x 1 1 2 3 2 4 6 3 5确定样本子集 X 与基本集的关系X c R = x , x ； X c R =； X c R = x 1 1 2 2 3 5计算 R (X )、R (X )、Pos (X )和 Bnd (X ):R - (X

8、)= R u R = x , x x , x ； R (X )= R = x 131235-35Pos (X )= R (X )= x ； Bnd (X )= R- (X )- R (X )= x ,x ,x -5-123计算近似精确度：C ard (R ( X )a (Z ) = -= 1/4 = 0.25RCard (R- (X )与粗糙度类似，在给出了两个知识集(特征属性)的相对肯定域的概念Pos (Q)之后，我们也可以一个量来刻画两个知识集的依赖度。设K = (U , R)为P一个知识库，P, Q匸R为两个知识集。令k = r (Q) = Card (Pos (Q) / Card (U

9、 )，PP 称为知识Q依赖于知识p的依赖度。特别，当k = 1时称为完全依赖；0 k 1时, 部分依赖；k = 0时，Q完全独立于知识P。3知识约简知识约简是粗糙集的核心内容之一，它是研究知识库中哪些知识是必要的， 以及在保持分类能力不变的前提下，删除冗余的知识。在粗糙集应用中，约简 与核是两个最重要的基本概念。（1）一般约简设P, Q是属性集，Q中的每一个属性都是不可省略的。如果Q匸P且 Ind （Q） = Ind （P），则称Q是P的一个约简（Reduce ），记为Red （P ）。另外，若 以Core（p）记p中所有不可省略的属性集合称为p的核（Core），那么所有约简 Re d（P）的

10、交正好等于p的核，即Core（P）= n Re d（P）。该式的意义在于，不仅 体现了核与所有约简的关系直接由约简得到，而且也表明了核是知识库中最重 要的部分，是进行知识约简的过程中不能删除的知识。（ 2 ）相对约简 一般地，考虑一个分类相对于另一个分类的关系，这就导出了相对约简与 相对核的概念。在粗糙集中，相对约简的概念是条件属性相对决策属性的约简。 我们需要给出如下的概念：设P和Q为论域U上的两个等价关系，定义Q关于P的相对肯定域，记为Pos（Q ），为论域U中的所有那些对象构成的集合，它们可以在分类U / P的知 P识指导下，被正确地划入到U / Q的等价类之中。即Pos （Q ）=o

11、P （X ）（X e U / Q ）p-其中， P （X ）是集合 X 的下近似。设P和Q为论域U上的两个等价关系，r e P。如果Pos （Q ）= Pos（Q ）P（ P -r）那么称r关于Q可省略，否则称为Q不可省略。特别，当P - r 为P中的独立子 集(即它的每个元素都再不可省略)，且Pos(Q)二Pos(Q)。那么称P - rP(P- r )为P的关于Q的相对约简，记为Ind (P)。P的所有关于Q的相对约简之父称为QP的关于Q的核，记为Core (P)。此时有Core (P) = Ind (P)。QQQ比较相对约简与一般约简的定义，我们能够发现，前者是在不改变决策属性Q的前提下对

12、特征属性集P的约简，而后者是不改变对于论域中对象的分辨 能力的前提下对于特征属性集的约简。(3，决策表的约简决策表约简的重要内容之一是简化决策表中的条件属性使得约简前后的决 策表具有相同的功能。同样的决策可以通过基于更少量的条件，便于我们借助 一些简单的手段就能获得同样要求的结果，这是事半功倍的好事。(1，分辨矩阵和分辨函数分辩矩阵是粗糙集中又一个重要概念，它将决策表中关于属性区分的信息 浓缩进一个矩阵当中，可用于决策表的属性约简。一信息系统S =(U,R,V, f )中，U = x ,xx 为论域，R = C u D是属性12n集合，C = a , i = 1,2,., m与D = d ,

13、j = 1,2,., l分别为条件属性集和决策属性ij集，a (x )是样本x在属性a上的取值。该系统的分辨矩阵定义为一个n x n阶，其中第 i 行 j 行处元素 nkj 矩阵 M(S)= m (x )人 D (xD (x )j i ii , j = 1, 2,., nija e C, a (xa= kk ikij ，D (x )= D (x )Iij也即，分辨矩阵中元素m是能够区别对象xiji和x的所有属性的集合。但若x和jix属于同一个决策类时，则分辨矩阵中元素m的取值为空集0。由定义可见，jijM(S)=m 是一个对称矩阵， 主对角线上的元素是空集。因此只要考虑上半 ij nx n或者

14、下半三角部分足亦。每一个分辨矩阵M(S),可以诱导出一个分辨函数f如下:M (s )m H ij(a ,a a )= avm ,1 j i n,M (s )12mij它实际上是一个具有m元变量a ,aa ,(a e C,i = 1,2,., m)的布尔函数，它是12 m i(vm )的合取，而(vm )是矩阵项m.中的各元素的析取。ijijij根据分辨函数与约简的对应关系，可以得到计算信息系统S约简Red(S)的方法为：1) 计算信息系统S的分辨矩阵M (S );2) 计算分辨矩阵M (S )对应的分辨函数f ;mij3) 计算分辨函数f 的最小析取范式,其中每个析取分量对应一个约简.m(s)

15、下面举例说明如何利用分辨矩阵及分辨函数求约简及核。设有信息系统S = (U, R), U = x , x x , R= a ,b ,c ,d其数据表格如下1 2 6表所示。表 信息系统数据表解：根据式(1T1)，分辨矩阵M (S)为:表 1-5 分辨矩阵Uxxxxxxxx.b,c,dxbb,c,dxa,b,c,da,da,b,c,dxa,da,b,ca,b,db,c,d5xa,b,c,da,ba,b,c,db,c,do再根据式(1-12)，分辨函数为f(a, b, c, d ) = b v c v d ) a (b) a (a v b v c v d ) a a (a v d )m(s)人(a

16、 v b v c v d )人(b v c v d )人(a v d )人(a v b v c v d ) a (a v d ) a (a v b v c v d )人(a v b v c v d ) a (a v b v c v d )a( b v c v d )a (b v c v d )=b a (a v d ) = ad v bd因此，该信息系统有两个约简a, b和b, d,核是b。由此得到两个约简的数据表格，如表 1-6所示。表 1-6 两个约简数据表x6x 6(2) 决策表 决策表是一类特殊而重要的知识表达系统，它是指当满足某些条件时，决 策应该怎样进行，多数决策问题都可以用决策表

17、形式来表达，决策表根据知识 表达系统定义如下：设S = (u ,R )为一知识表达系统，若R可划分为条件属性集C和决策属性集 D，即 C U D = R, C C D = 0。则称为 CD 决策表，改记为T = (U, R, C,D )。Ind (C)的等价类称为条件类，Ind(D)的等价类称为决策类。决策表可分为一致决策表和非一致决策表。当D完全依赖于C( c二d )时, 称为一致的；当部分依赖(C n kD(0 k 1)时，称决策表是不一致的。特别指出，决策表是否能够约简，取决于它是否为一致决策表。这是因为不同原因可以产生相同结果，但同一个原因则不允许导致多种结果。对于一个 决策表，一般首

18、先将其分解为一个一致决策表与一个不一致的决策表，然后再 对一致决策表进行约简。约简的方法还是使用分辨矩阵的方法。此时，属性特 征集C相对于决策属性集D的核Core (C)恰为分辨矩阵中所有m为单元素集Dij决定。也即Core (C) = la IDk3ms.t m = a ,ijijk特别，如果C上C是满足条件C n m工e, V m工e， 且C是最小的，ijij那么称C:为C相对于决策属性集D的约简。约简之后的决策表具有更少的条件属性，但却没有损失知识含量。同样对 于决策属性也可以约简。但是约简后的决策表还是不能直接看出条件与决策属 性之间的关系，因此还需要挖掘出决策生成规则。为此我们引入另

19、外一个量来 刻画条件属性子集X u C与决策属性子集Y u D之间关联强度。令ijDes (X ) = (x, v ) I 3 x e U, v e V s .t. f (x, a) = v , V a e X ixxxiDes (Y ) = (x, v ) I3x eU , v eV s.t. f (x,d) = v ,Vd eY jxxxj分别称为属性子集X u C与决策属性子集Y u D的描述集。此时，Des (X )与ijiDes (Y )同在空间U x V中，于是可以作如下两件事:1.j的映射 T 。ij当 Des (X ) A Des (Y )工 e 时， 定义 Des (X )到

20、 Des (Y )ijij当Des (X ) A Des (Y )工时，定义确定因子度ij卩(X , Y ) = Card(De$ (X ) A Des (Y )/ Card (Des (X )i jiji特别，当卩(X , Y ) = 1时，T是确定的规则；当卩(X , Y ) 1时，T是不确定的i j ij i j ij规则。卩(X , Y )的大小反映的是满足属性子集X u C的对象中又能够满足决策i j i属性子集Y u D的对象所占的比例。j5基于分辨矩阵的启发式最小约简算法以上介绍的约简的理论方法虽然简单，但只有通过计算机程序实现才有应 用意义。对于决策表比较复杂，条件属性较多的情

21、况下，由于对存储空间的要 求过大，单纯使用分辨矩阵很难实现。下面建立一种基于分辨矩阵的启发式最 小约简算法，可以较好地解决这个问题。基于约简是必须能够区分所有对象的最小属性集合可以推出：一个约简与 分辨矩阵的每一项的交都不空(加入与m不相交，那么对象i与j关于该约简是 ij 不可分辨的)。 于是得出如下“准约简”算法：输入：决策表(U,CUD)，其中 C = a , i = 1,2,., mi1. 选取初始约简 R 。02. 对于所有i, j检查分辨矩阵的每一项m和候选约简集合R的交ij0m c R 判断：ij0a) 如果m c R为空集，随机从m中选择一个属性，加到候选约简ij0ij集合 R

22、 中；0b) 若不空，检查下一项。3. 重复这一过程，直到分辨矩阵中的每一项都检查过了。输出：准约简。程序完成之后，我们可以得到R = C D中的一个条件属性子集R，。但是，一般 R，仅仅是一个“准约简”因为上面的算法没有考虑它的最小性。为了使之变成 真的约简，我们需要如下的启发知识。一个简单而有效的方法是根据| m I来对条件属性进行排序。我们知道，如ij果m中只有一个属性，该属性一定是约简的成员。从分辨矩阵的定义可以看出，ij分辨矩阵中某项的长度越短，该项就对分类所起的作用越大。而且该项出现的 越频繁，该项越重要。因此，我们对分辨矩阵排序时，除了按长度外，在长度相同的情况下，出现频率高的属

23、性更重要。归结为两个重要的启发式思想:1) 属性在分辨矩阵中出现的次数越多，属性的重要性越大2) 属性出现在分辨矩阵中的项越短，属性的重要性越大。于是提出了一种新的基于分辨矩阵的计算属性重要性的方法。对于一个分辨矩阵M=( m )ij n x n，相应的属性 a 的重要性计算公式为:i-1 j-1入| m |ij0,入 a电mija e mij式中| m|为 m 包含的属性的个数。由此得到了基于分辨矩阵的启发式约简算法ijij如下:输入：决策表(U ,CUD)，其中 C - a , i - 1,2,., m i输出：约简(Reduction)。1) 计算分辨矩阵M，并找出所有不包含核属性的属性组合S;2) 将所有不包含核属性的属性集合表示为析取范式的形式，即P - av a , i - 1,2,.,s, k - 1,2, mik3) 将 P 转化为析取范式的形式，并按(1-20)式计算属性的重要性；4) 取初始约简为r，(由准约简程序提供)，对于重要性最小的属性a，令 R (1) - R a ，5) 判断Ind (R)-Ind (R)是否成立：若成立，用R (1)代替R，重复步骤4)5)；否则，以R，作为约简，结束程序。6) 以R(i +1) - R(i) a更新，重复4)5)直到程序中止。