粗糙集理论方法及其应用

《粗糙集理论方法及其应用》由会员分享，可在线阅读，更多相关《粗糙集理论方法及其应用（96页珍藏版）》请在金锄头文库上搜索。

1、Rough集理论方法及其应用,学生:朱 兵 导师:贺昌政,Content,一、 简 介 二、 原 理 三、 应 用 四、 评 价 五、 实 例,一、简介,在自然科学、社会科学和工程技术的 很多领域中，都不同程度地涉及到对不确定因素和对不完备信息的处理。从实际系统中采集到的数据常常包含着噪声，不精确甚至不完整。采用纯数学上的假设来消除或回避这种不确定性，效果往往不理想，反之，如果正视它，对这些信息进行合适地处理，常常有助于相关实际系统问题的解决。,一、简介,1965年，Zadeh提出了模糊集的概念处理不确定信息已应用于一些实际领域。但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或

2、者由领域专家给出，所以具有相当的主观性。,一、简介,1982年，波兰学者Z. Pawlak提出了粗糙集理论,它是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。,一、简介,粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。,一、简介,1991年波兰Pawlak教授的第一本关

3、于粗糙集的专著Rough Sets Theoretical Aspects of Reasoning about Data ; 1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集; 1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。,一、简介,刘清. Rough Set及Rough推理. 北京: 科学出版社, 2001 张文修等. Rough Set理论与方法. 北京: 科学出版社, 2001 王国胤, Rough Set理论与知识获取. 西安: 西安交通大学出版社, 2001 曾黄麟. 粗集理论及其应用(

4、修订版). 重庆: 重庆大学出版社,二、原理,预备知识: 定义: 设R是集合A上的二元关系，如果它是自反、对称和传递的，则它是A上的等价关系。 定义: 设R是A上的一个等价关系，与A中的一个元素a相关的所有元素a的集合被称做的一个等价类。 命题: R是集合S的一个等价关系，那么R的等价类形成S的一个划分。,二、原理,(一)知识系统和不可区分关系基本粗糙集理论认为知识就是人类对对象进行分类的能力。例如,医生给病人诊断,他的知识就在于辨别出病人得的是哪一种病,一种分类可以用一个等价关系描述。,二、原理,分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系。假定只用两种黑白颜色把空间中

5、的物体分割两类，黑色物体、白色物体，那么同为黑色的两个物体就是不可分辨的，因为描述它们特征同性的信息相同，都是黑色。,二、原理,如果再引入方、圆的属性，又可以将物体进一步分割为四类：黑色方物体、黑色圆物体、白色方物体、白色圆物体。这时，如果两个同为黑色方物体，则它们还是不可分辨的。,二、原理,一个知识库定义为一个关系系统 K=(U,R) 其中U是一个被称为全域或论域的所有要讨论的个体的集合，R是U上等价关系的一个族集。,二、原理,设PR，且P ，P中所有等价关系的交集称为P上的一种难区分关系，记作IND(P)，即注意，IND(P)也是等价关系且是唯一的。,二、原理,给定近似空间K=(U, R)

6、，子集XU称为U上的一个概念；非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识，相应的等价类称为基本概念.特别地，若关系QR，则关系Q就称为初等知识，相应的等价类就称为初等概念。根据上述定义可知，概念是对象的集合,分类就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。,二、原理,(二)粗糙集与近似集令XU ，R为U上的一个等价关系。当X能表达成某些R基本范畴的并时,称X是R可定义的,也称作R精确集；否则称X为R不可定义的,也称为R非精确集或R粗糙集。当存在等价关系RIND(K)且X为R精确集时，集合X U称

7、为K中的精确集；当对于任何R IND(K)，X都为R粗糙集，则X称为K中的粗糙集。,二、原理,X的下近似：R*(X)=x:(xU) (xRX ) X的上近似：R*(X)=x:(xU) (xRX )下近似包含了所有使用知识R可确切分 类到X的元素;上近似则是包含了所有那些可 能是属于X的元素的最小集合。,二、原理,X的边界区域：BNR(X)=R*(X)R*(X) X的R-正区域:POSR(X)=R*(X) X的R-反区域:NEGR(X)=UR*(X)概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。若BNR(X) ，则集合X就是一个粗糙概念。,U,set,U/RR : subset

8、 of attributes,二、原理,二、原理,近似精度表示了一个集合的粗糙程度,显然 当 时,集合X相对于R是精确的 当 时,集合X相对于R是粗糙的,例:给定一玩具积木的集合 Ex1, x2, x3, x4,x5, x6, x7, x8 按颜色分类：x1 ,x3 ,x7红;x2,x4蓝;x5, x6 ,x8 黄 按形状分类：x1 ,x5 圆;x2 ,x6 方;x3 ,x4 ,x7,x8三角,二、原理,如果我们定义颜色R1和形状R2 两个等价关系,那么可以得到两个等价类： UR1 x1 ,x3 ,x7,x2,x4 ,x5, x6 ,x8 UR2 x1 ,x5,x2,x6 ,x3, x4 ,x

9、7,x8 这些等价类是由知识库K(U,R1,R2)中的初等概念(初等范畴)构成的。,二、原理,对于R1, R2 ,它的基本范畴有 x1 ,x3 ,x7x3, x4 ,x7,x8 =x3,x7红色三角 x2,x4 x2,x6 = x2 蓝色方形 x5, x6 ,x8 x3, x4 ,x7,x8 =x8黄色三角形,二、原理,二、原理,现有一集合(概念)X=x2 , x5 , x6 它是粗糙集R1*(X)= =x2 , x4 , x5 , x6 , x8R1*(X) =x2 , x6 BNR(X)=R*(X)R*(X) =x4 , x5 , x8 ,IND(Age) = x1,x2,x6, x3,x

10、4, x5,x7 IND(LEMS) = x1, x2, x3,x4, x5,x6,x7 IND(Age,LEMS) = x1, x2, x3,x4, x5,x7, x6.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 no x4 31-45 1-25 yes x5 46-60 26-49 no x6 16-30 26-49 yes x7 46-60 26-49 no,二、原理,W = x | Walk(x) = yes. W是一个粗糙集合,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no

11、x3 31-45 1-25 no x4 31-45 1-25 yes x5 46-60 26-49 no x6 16-30 26-49 yes x7 46-60 26-49 no,二、原理,二、原理,yes,yes/no,no,x1,x6,x3,x4,x2, x5,x7,AW,二、原理,(三)粗糙集与不确定性 粗糙集理论中知识的不确定性有两方面:一是来自来自于论域上的二元关系及其产生的知识模块,即近似空间本身由于对象的可得到的信息不一定足以划分其成员类别,换句话说,这种不精确性导致了对象的不可分辨性。论域上的二元关系及其产生的知识模块越大,知识库中的知识越粗糙, 近似空间的概念和知识就越不确定

12、,这时处理知识的不确定性的方法往往用香农信息熵来刻画。,二、原理,另一个是来自于给定论域里粗糙近似的边界,当边界为空集时知识是完全确定的,边界越大知识就越粗糙或越模糊。这时处理知识不确定性就用不分明对象类形成的上近似和下近似来描述。,二、原理,粗糙集与模糊集,(四)粗糙集模型的扩展基本粗糙集理论的主要存在的问题是：1)对原始数据本身的模糊性缺乏相应处理能力；2)对于粗糙集的边界区域的刻画过于简单；3)粗糙集理论的方法的分类是确定的，但并未提供数理统计中所常用的在一个给定错误率的条件下将尽可能多的对象进行分类的方法，而实际中常常遇到这类问题。,二、原理,1.可变精度粗糙集模型,传统的粗糙集理论处

13、理的分类必须是完全正确或肯定的,因为它是严格按照等价类来分类的,因而它的分类是精确的,亦即“包含”或“不包含”，而没有某种程度上的“包含”或“属于”,这一定程度上限制了它的应用。W.Ziarko在基本粗糙集模型的基础上引入了(0 0.5)，即允许一定程度的错误分类率存在提出了一种称之为可变精度粗糙集模型。,二、原理,二、原理,一般地，集合X包含于Y并未反映出集合X的元素属于集合Y的“多少”。为此，VPRS定义了它的量度： 当card(x)0， C(X, Y)=1card(XY)/card(X) 当card(x)=0,C(X, Y)=0,二、原理,C(X, Y)表示把集合X归类于集合Y的误分类度

14、，即有C(X, Y)100%的元素归类错误。显然，C(X, Y)=0时有XY。如此，可事先给定一错误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X, Y)。在此基础上，设U为论域且R为U上的等价关系，U/R=A=X1, X2, , Xk ,二、原理,可定义集合X的-下近似为： RX=Xi (C(Xi, X), i=1, 2, , k)并且RX称为集合X的-正区域 集合X的-上近似为=Xi (C(Xi, X)1, i=1, 2, , k)， -边界区域就定义为： BNRX=Xi (C(Xi, X)1)；-负区域为：NEGRX=Xi (C(Xi, X)1)。,U,set,U/RR : subset of attributes,二、原理,2.相似关系模型在数据中存在缺失的属性值的时候，不分明关系或等价关系无法处理这种情形。为扩展粗糙集的能力，有许多作者提出了用相似关系来代替不分明关系作为粗糙集的基础。,二、原理,二、原理,在使用相似关系代替粗糙集的不分明关系后，最重要的变化就是相似类不再形成对集合的划分了，它们之间是相互重叠的。类似于等价类，可以定义相似集，即所有和某各元素x在属性集合B上相似的集合SIMb(x)。值得注意的是SIMb(x)中的元素不一定属于同一决策类， 因此还需要定义相似决策类，即相似集对应的决策类集合。,