4粗糙集与数据约简

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

1、智能信息处理技术,华北电力大学,第4章 粗糙集与数据约简,4.1、不确定性理论,自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。 确定性现象：在一定条件下必然会出现的现象。 不确定性的分类： 随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。用概率来度量。概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律概率规律。 模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律隶属规律。 粗糙性：因

2、为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。,4.1、不确定性理论,经典集合、模糊集合、粗糙集的关系 经典集合认为一个集合完全有其元素所决定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数X(x)0,1是二值逻辑。 模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数X(x)0,1，即在闭区间0,1可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观

3、经验给定。 粗糙集合把用于分类的知识引入集合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：x肯定不属于X；x肯定属于X；x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的关于论域的知识。粗糙集的隶属函数为阶梯 状，对不确定性信息的描述是粗糙的， 但粗糙隶属函数是可计算的。粗糙集主 要用于对信息系统进行约简和分类。,1.0,0.8,0.6,0.4,0.2,0.0,0.2,0.4,0.6,0.8,1.0,第4章 粗糙集与数据约简,4.2 粗糙集的基本理论与方法,4.2.1、粗糙集的基本概念,知识与分类 在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分辨现

4、实的或抽象的对象的能力。 假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其划分开。 粗糙集理论的核心是等价关系，通常用等价关系替代分类，根据这个等价关系划分样本集合为等价类。 从知识库的观点看，每个等价类被称为一个概念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。,4.2.1、粗糙集的基本概念,知识表达系统 一个知识表达系统或信息系统S可以表示为有序四元组 S=U,R,V,f 其中，U=x1,x2,

5、xn为论域，它是全体样本的集合； RCD 为属性集合，其中子集C是条件属性集，反映对象的特征，D为决策属性集，反映对象的类别； 为属性值的集合，Vr表示属性r的取值范围； f:URV 为一个信息函数，用于确定U中每一个对象x的属性值，即任一xiU，rR，则f(xi,r)=Vr,4.2.1、粗糙集的基本概念,不可分辨关系 在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集BR，如果对象xi,xjU，rB，当且仅当f(xi,r)=f(xj,r)时，xi和xj是不可分辨的，简记

6、为Ind(B)。不可分辨关系称为等价关系。 例如：只用黑白两种颜色把空间中的一些物体划分成两类：黑色物体、白色物体，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：黑色方物体、黑色圆物体、白色方物体、白色圆物体。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。 不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的不精确性。 另一方面，不可分辨关系反映了论域知识的颗粒性。知识库中的知识越多，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越

7、小，则导致信息量增大，存储知识库的费用越高。,4.2.1、粗糙集的基本概念,基本集合 由论域中相互不可分辨的对象组成的集合称之为基本集合，它是组成论域知识的颗粒。 例如：考虑条件属性：头疼和 肌肉疼。对于x1,x2,x3这三个 对象是不可分辨的。x4,x6在这 两个属性上也是不可分辨的。 由此构成的不可分辨集x1,x2, x3,x4,x6,x5被称为基本 集合。 设论域U为有限集，R是U的等价关系簇，则K=U,R称为知识库，知识库的知识粒度由不可分辨关系Ind(R)的等价类反映。,4.2.1、粗糙集的基本概念,下近似集和上近似集 下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成

8、的集合，即 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、粗糙集的基本概念,正域、负域和边界域 正域：Pos(X)=R-(X)，即根据知识R，U中能完全确定地归入集合X的元素的集合。 负域：Neg(X)=U-R-(X)

9、，即根据知识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、粗糙集的基本概念,粗糙度（近似精确度） 对于知识R（即属性子集），样本子集X的不确定程度可以用粗

10、糙度R(X)来表示为 R(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个数）。 0R(X)1，如果R(X)1，则称集合X相对于R是确定的，如果R(X)1则称集合X相对于R是粗糙的，R(X)可认为是在等价关系R下逼近集合X的精度。,4.2.1、粗糙集的基本概念,例：以医疗信息表为例，对于属性子集 R=头疼,肌肉疼=r1,r2,计算样本子 集X=x1,x2,x5的上近似集、下近似集、 正域、边界域。 解： 计算论域U的所有R基本集： U|Ind(R)=x1,x2,x3,x4,x6,x5 令R1=x1,x2,x3 R2=x4,x6 R3=x5 确定样本子集X与基本集的关系 XR1=x

11、1,x2 XR2= XR3=x5 计算R-(X)、R(X)、Pos(X)、Bnd(X)： R-(X)=R3=x5R(X)=R1R3=x1,x2,x3,x5 Pos(X)=R-(X)=x5Bnd(X)=R(X)-R-(X)=x1,x2,x3 计算近似精确度：,4.2.1、粗糙集的基本概念,例：右表是考生情况调查表，其中U为被调查对象，即论 域；R为高考成绩(A优，B良，C中，D差)；X为 升学情况(+为上，/为未上)。 根据高考成绩和升学情况进行分类时： 按成绩：U/R=1,6,2,3,5,4=Y1,Y2,Y3,Y4 按升学：U/X=2,3,5,6,1,4=X1,X2 分别计算出下近似集、上近似

12、集、边界域和近似精度： R-(X1)=Y2Y3=2,3,5R-(X2)=Y4=4 R-(X1)=Y2Y3Y1 =2,3,5,6,1R-(X2)=Y1Y4=4,6,1 Bnd(X1)=Y1=1,6Bnd(X2)=Y1=1,6 R(X1)=Card(R-(X1)/Card(R-(X1)=3/5 R(X2)=Card(R-(X2)/Card(R-(X2)=1/3,4.2 粗糙集的基本理论与方法,4.2.2、粗糙集的基本思想,RS的基本思想 RS认为知识就是将论域中的对象进行分类的能力。对对象的认知程度取决于所拥有的知识的多少，知识越多，则分类能力越强。知识越少，则对象间的区分越模糊。 在没有掌握所有

13、关于对象域的知识的情况下，为了刻画模糊性，RS使用了一对称为下近似与上近似的精确概念来表示每个不精确概念，即使用一对逼近来描述对象域上的集合。下近似和上近似的差是一个边界集合，它包含了所有不能确切判定是否属于给定类的对象。这种处理可以定义近似的精确度，能够很好的近似分类，得到可以接受质量的分类。 在RS中，论域中的对象可用多种知识来描述(通常描述为属性)。当两个不同的对象由相同的属性来描述时，这两个对象在系统中被归于同一类，它们的关系称之为不可分辨关系或等价关系。不可分辨关系是RS理论的基石，它反映了论域知识的颗粒性。 影响分类能力的属性很多，不同的属性重要程度不同，其中某些属性起决定性作用；

14、属性的取值不同对分类能力也会产生影响。RS理论提出知识的约简方法、在保留基本知识、对对象的分类能力不变的基础上，消除重复、冗余属性和属性值，实现了对知识的压缩和再提炼。,4.2 粗糙集的基本理论与方法,4.2.3、粗糙集的基本特点,RS的基本特点 RS的基本方法是使用等价关系将集合中的元素(对象)进行分类，生成集合的某种划分，与等价关系相对应。根据等价关系的理论，同一分类(等价类)内的元素是不可分辨的，对信息的处理可以在等价类的粒度上进行，由此可以达到对信息进行简化的目的。 RS是一种软计算方法，传统的知识处理是一种硬计算方法，使用精确、固定和不变的算法来表达和求解问题。而软计算方法则允许利用

15、不精确性、不确定性和部分真实性以得到易于处理、鲁棒性强和低成本的解决方案。 RS仅仅从数据本身进行分析，无需提供所要分析的样本数据以外的任何先验知识或附加信息，不要预先给予主观评价，如统计学中要假定概论分布，模糊集中要给定隶属度，证据理论中要赋予似然值等。 RS能分析各种数据，包括确定性和非确定性的；不精确的和不完整的以及拥有众多变量的数据，并对数据进行简化，从而发现知识、推理决策规则，不仅是一种决策分析方法，而且是一种系统建模方法。,4.2.3、粗糙集的基本特点,RS的基本特点（续） RS与其他不确定方法一样，它们都是处理含糊性和不确定性问题的数学工具。但它们又有不同之处：主观Bayes中，

16、不确定性看成概率；D/S证据理论中，不确定性是可信度；模糊集合理论中，不确定性是集合的隶属度；RS理论中，不确定性是上下近似集之差，有确定的数学公式来描述。 由于RS理论本身未包含处理不精确或不确定原始数据的机制，在实际应用中，RS方法常常需要与其他方法结合起来使用，互为补充。,第4章 粗糙集与数据约简,4.3 知识的约简,设U为所讨论对象的非空有限集论域，R为非空的属性有限集，则称二元有序组K=U,R为一个知识库，亦称近似空间。 在知识库中可能含有冗余的知识，知识约简是研究知识库中哪些知识是必要的，以及在保持分类能力不变的前提下，删除冗余的知识。特别是，当信息系统中的数据是随机采集的其冗余性更为普遍。知识约简是粗糙集理论的核心内容之一，在信息系统分析与数据挖掘等领域具有重要的应用意义。,4.3 知识的约简,4.3.1、一般约简,一般约简 在粗糙集理论中，约简与核是两个最重要的基本概念。 设R是一个等价关系族，且rR,若有 Ind(R)=Ind(R-r) 则称r在等价关系族R中是可省略的，否则r为R中不可省略的。 若族R中每一个r都是不