粗糙集与数据约简

《粗糙集与数据约简》由会员分享，可在线阅读，更多相关《粗糙集与数据约简（76页珍藏版）》请在金锄头文库上搜索。

1、智能信息处理技术华北电力大学华北电力大学第4章 粗糙集与数据约简不确定性理论1粗糙集的基本理论与方法2知识的约简3决策表的约简4粗糙集数据约简的具体实现与应用5粗糙集的研究现状与展望64.1、不确定性理论v 自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。 v 确定性现象：在一定条件下必然会出现的现象。 v 不确定性的分类： 随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确 定性。用概率来度量。概率表示事件发生可能性的大小。概率论的运用是 从随机性中去把握广义的因果律概率规律。 模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限， 导致事件呈现“亦此亦彼”的性态

2、，是事物类属的不确定性，用隶属度来 度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊 性中去确立广义的排中律隶属规律。 粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件 间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此 ，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则 问题变为确定性的。4.1、不确定性理论v 经典集合、模糊集合、粗糙集的关系 经典集合认为一个集合完全有其元素所决定，一个元素要么属于这个 集合，要么不属于这个集合。其隶属函数X(x)0,1是二值逻辑。 模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个 元素的

3、隶属函数X(x)0,1，即在闭区间0,1可以任意取值，隶属函数 可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。 但隶属函数不可计算，凭人的主观经验给定。 粗糙集合把用于分类的知识引入集合。一个元素x是否属于集合X，需 要根据现有知识来判定，可分为三个情况：x肯定不属于X；x肯定属 于X；x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握 的关于论域的知识。粗糙集的隶属函数为阶梯 状，对不确定性信息的描述是粗糙的， 但粗糙隶属函数是可计算的。粗糙集主 要用于对信息系统进行约简和分类。1.00.80.60.40.20.00.20.40.60.81.0第4章 粗糙集与数据约

4、简粗糙集的基本理论与方法2不确定性理论1知识的约简3决策表的约简4粗糙集数据约简的具体实现与应用5粗糙集的研究现状与展望64.2 粗糙集的基本理论与方法粗糙集的基本概念1粗糙集的基本思想2粗糙集的基本特点34.2.1、粗糙集的基本概念v 知识与分类 在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分 辨现实的或抽象的对象的能力。 假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要 的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个 对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其 划分开。 粗糙集理论的核心是等价关系，通常用等价关系替代分类，根

5、据这个 等价关系划分样本集合为等价类。 从知识库的观点看，每个等价类被称为一个概念，即一条知识（规则 )。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象 对该概念是不可区分的。4.2.1、粗糙集的基本概念v 知识表达系统 一个知识表达系统或信息系统S可以表示为有序四元组 S=U,R,V,f 其中，U=x1,x2,xn为论域，它是全体样本的集合； RCD 为属性集合，其中子集C是条件属性集，反映对象的特征，D 为决策属性集，反映对象的类别；为属性值的集合，Vr表示属性r的取值范围； f:URV 为一个信息函数，用于确定U中每一个对象x的属性值，即 任一xiU，rR，则f(xi,r)

6、=Vr属性 对象条件属性C决策属性D 头疼r1肌肉疼r2体温r3流感 x1是是正常否 x2是是高是 x3是是很高是 x4否是正常否 x5否否高否 x6否是很高是4.2.1、粗糙集的基本概念v 不可分辨关系 在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个 不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类 ，它们的关系称之为不可分辨关系。即对于任一属性子集BR，如果对象 xi,xjU，rB，当且仅当f(xi,r)=f(xj,r)时，xi和xj是不可分辨的，简 记为Ind(B)。不可分辨关系称为等价关系。 例如：只用黑白两种颜色把空间中的一些物体划分成两类：黑色物 体、

7、白色物体，那么同为黑色的物体就是不可分辨的，因为描述它们 特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体 进一步划分为4类：黑色方物体、黑色圆物体、白色方物体、白色 圆物体。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。 不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的 不精确性。 另一方面，不可分辨关系反映了论域知识的颗粒性。知识库中的知识 越多，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不 断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致 信息量增大，存储知识库的费用越高。4.2.1、粗糙集的基本概念v 基本集合 由论域

8、中相互不可分辨的对象组成的集合称之为基本集合，它是组成 论域知识的颗粒。 例如：考虑条件属性：头疼和 肌肉疼。对于x1,x2,x3这三个 对象是不可分辨的。x4,x6在这 两个属性上也是不可分辨的。 由此构成的不可分辨集x1,x2, x3,x4,x6,x5被称为基本 集合。 设论域U为有限集，R是U的等价关系簇，则K=U,R称为知识库，知识 库的知识粒度由不可分辨关系Ind(R)的等价类反映。属性 对象条件属性C决策属 性D 头疼r1肌肉疼r2体温r3流感 x1是是正常否 x2是是高是 x3是是很高是 x4否是正常否 x5否否高否 x6否是很高是4.2.1、粗糙集的基本概念v 下近似集和上近似

9、集 下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组 成的集合，即 R-(X)=xU,xR X 其中， xR 表示等价关系R下包含元素x的 等价类。 上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对 象所组成的集合，即 R(X)=xU,xR X 其中， xR 表示等价关系R下包含元素x的 等价类。 给定知识表达系统S=U,R,V,f，对于每个样本子集X U和等价关系 R，所有包含于X的基本集的并（逻辑和）为R-(X)；所有与X的交(逻辑积) 不为空集的基本集的并为R(X)。4.2.1、粗糙集的基本概念v 正域、负域和边界域 正域：Pos(X)=R-(X)，即根据知识

10、R，U中能完全确定地归入集合X的 元素的集合。 负域：Neg(X)=U-R-(X)，即根据知识R，U中不能确定一定属于集合X 的元素的集，它们是属于X的补集。 边界域：Bnd(X)= R-(X) - R-(X) ，边界域是某种意义上论域的不确 定域，根据知识R，U中既不是肯定归入集合X，又不能肯定归入集合X， 的元素构成的集合。 边界域为集合X的上近似与下近似之差，如果Bnd(X)是空集，则称集 合X关于R是清晰的；反之，如果Bnd(X)不是空集，则称集合X为关于R的粗 糙集。因此，粗糙集中的“粗糙”（不确定性）主要体现在边界域的存在 。集合X的边界域越大，其确定性程度就越小。4.2.1、粗糙

11、集的基本概念v 粗糙度（近似精确度） 对于知识R（即属性子集），样本子集X的不确定程度可以用粗糙度 R(X)来表示为R(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个 数）。 0R(X)1，如果R(X)1，则称集合X相对于R是确定的，如果 R(X)kQ。当k=1时，称知识Q完全依赖于知识P；当0k1时，称知识Q部分依赖于知识P；当k=0时，称知识Q完全独立于知识P。依赖度k反映了根据知识P将对象分类到Q的基本概念中去的能力。确切的说，当 PkQ时，论域中共有kCard(U)个属于Q的P正域的对象，这些对象可以依据知识P 分类到知识Q的基本概念中去。例 U=x1,x2,x8，U/

12、P=x1,x2,x3,x4,x5,x6,x7,x8，U/Q= x1,x2,x3,x4,x5,x6,x7,x8，求依赖度k。 解：PosP(Q)=x1x2x3,x4x5,x6=x1,x2,x3,x4,x5,x6k=6/8=0.75即知识Q相对于知识P的依赖度为0.75第4章 粗糙集与数据约简决策表的约简4不确定性理论1粗糙集的基本理论与方法2知识的约简3粗糙集数据约简的具体实现与应用5粗糙集的研究现状与展望64.4 决策表的约简决策表1分辨矩阵与分辨函数3属性的重要性2决策表属性约简的分辨矩阵方法4决策规则的生成54.4.1、决策表v 决策表是一类特殊的知识表达系统，它是指当满足某些条件时，决策

13、应该怎样 进行。多数决策问题都可以用决策表形式表达，这一工具在决策应用中起着重要作 用。 v 定义：设S=(U,R)为一知识表达系统，若R可划分为条件属性集C和决策属性集D ，则CD=R,CD=。具有条件属性和决策属性的知识表达系统可表示为决策表， 记作T=(U,R,C,D)或简称CD决策表。Ind(C)的等价类称为条件类，Ind(D)的等价类 称为决策类。 决策表可分为一致决策表和非一致决策表。当且仅当D依赖于C，即CD时，称决策表是一致的；当且仅当CkD(0k1)时，称决策表是不一致的。 决策表必须是一致的才能够约简。 对于不一致的决策表，首先要将其分解为两个决策表，一个为一致决策 表，另

14、一个为非一致决策表，然后再对一致决策表进行约简。4.4.1、决策表例 设论域U=x1,x2,x7，属性集R=CD，条件属性集C=a,b,c,d，决策属性集 D=e。决策表如下所示：由决策表可知：U/C=x1,x2,x3,x4,x5,x6,x7U/D=x1,x2,x7,x3,x5,x6,x4Posc(D)=x1,x2,x3,x4,x5,x6,x7故该决策表是一致决策表。Uabcde x110211 x210201 x312002 x412210 x521002 x621102 x7212114.4.1、决策表U/(a)=x1,x2,x3,x4,x5,x6,x7 Pos(a)(D)= U/(b)=

15、x1,x2,x3,x4,x5,x6,x7 Pos(b)(D)=x1,x2 U/(c)=x1,x2,x4,x7,x3,x5,x6 Pos(c)(D)=x3,x5 U/(d)=x1,x4,x7,x2,x3,x5,x6 Pos(d)(D)= U/(a,b)=x1,x2,x3,x4,x5,x6,x7 Pos(a,b)(D)=x1,x2 U/(a,c)=x1,x2,x4,x3,x5,x6,x7 Pos(a,c)(D)=x3,x5,x6,x7 U/(a,d)=x1,x4,x2,x3,x5,x6,x7 Pos(a,c)(D)=x5,x6,x7 U/(b,c)=x1,x2,x3,x4,x5,x6,x7 Pos(b,c)(D)=x1,x2,x3,x4,x5,x6,x7 U/(b,d)=x1,x2,x3,x4,x5,x6,x7 Pos(b,d)(D)=x1,x2,x3,x4,x5,x6,x7 U/(c,d)=x1,x4,x