粗糙集理论方法及其应用

Rough集理论方法及其应用学生:朱兵导师:贺昌政Content•一、简介•二、原理•三、应用•四、评价•五、实例一、简介•在自然科学、社会科学和工程技术的很多领域中，都不同程度地涉及到对不确定因素和对不完备信息的处理。从实际系统中采集到的数据常常包含着噪声，不精确甚至不完整。采用纯数学上的假设来消除或回避这种不确定性，效果往往不理想，反之，如果正视它，对这些信息进行合适地处理，常常有助于相关实际系统问题的解决。一、简介•1965年，Zadeh提出了模糊集的概念处理不确定信息已应用于一些实际领域。•但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。一、简介•1982年，波兰学者Z.Pawlak提出了粗糙集理论,它是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。一、简介•粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。一、简介•1991年波兰Pawlak教授的第一本关于粗糙集的专著《RoughSetsTheoreticalAspectsofReasoningaboutData》;•1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集;•1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。一、简介刘清.RoughSet及Rough推理.北京:科学出版社,2001张文修等.RoughSet理论与方法.北京:科学出版社,2001王国胤,RoughSet理论与知识获取.西安:西安交通大学出版社,2001曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社二、原理★预备知识:•定义:设R是集合A上的二元关系，如果它是自反、对称和传递的，则它是A上的等价关系。•定义:设R是A上的一个等价关系，与A中的一个元素a相关的所有元素a的集合被称做的一个等价类。•命题:R是集合S的一个等价关系，那么R的等价类形成S的一个划分。二、原理•(一)知识系统和不可区分关系•基本粗糙集理论认为知识就是人类对对象进行分类的能力。例如,医生给病人诊断,他的知识就在于辨别出病人得的是哪一种病,一种分类可以用一个等价关系描述。二、原理•分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系。•假定只用两种黑白颜色把空间中的物体分割两类，{黑色物体}、{白色物体}，那么同为黑色的两个物体就是不可分辨的，因为描述它们特征同性的信息相同，都是黑色。二、原理•如果再引入方、圆的属性，又可以将物体进一步分割为四类：{黑色方物体}、{黑色圆物体}、{白色方物体}、{白色圆物体}。这时，如果两个同为黑色方物体，则它们还是不可分辨的。二、原理•一个知识库定义为一个关系系统K=(U,R)其中U是一个被称为全域或论域的所有要讨论的个体的集合，R是U上等价关系的一个族集。二、原理设PR，且P，P中所有等价关系的交集称为P上的一种难区分关系，记作IND(P)，即注意，IND(P)也是等价关系且是唯一的。IND(p)RRP[x]=[x]∩二、原理给定近似空间K=(U,R)，子集XU称为U上的一个概念；非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识，相应的等价类称为基本概念.特别地，若关系QR，则关系Q就称为初等知识，相应的等价类就称为初等概念。根据上述定义可知，概念是对象的集合,分类就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。二、原理•(二)粗糙集与近似集•令XU，R为U上的一个等价关系。当X能表达成某些R基本范畴的并时,称X是R可定义的,也称作R精确集；否则称X为R不可定义的,也称为R非精确集或R粗糙集。•当存在等价关系RIND(K)且X为R精确集时，集合XU称为K中的精确集；当对于任何RIND(K)，X都为R粗糙集，则X称为K中的粗糙集。二、原理X的下近似：R*(X)={x:(xU)([x]RX)}X的上近似：R*(X)={x:(xU)([x]RX)}下近似包含了所有使用知识R可确切分类到X的元素;上近似则是包含了所有那些可能是属于X的元素的最小集合。二、原理•X的边界区域：BNR(X)=R*(X)–R*(X)•X的R-正区域:POSR(X)=R*(X)•X的R-反区域:NEGR(X)=U–R*(X)概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。若BNR(X)，则集合X就是一个粗糙概念。UsetＸU/RR:subsetofattributesXRXXR二、原理二、原理近似精度表示了一个集合的粗糙程度,显然当时,集合X相对于R是精确的当时,集合X相对于R是粗糙的|)(||)(|)(XBXBXB.XB0α1Bα(X)=1Bα(X)1Bα(X)•例:•给定一玩具积木的集合E＝{x1,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两个等价关系,那么可以得到两个等价类：•U／R1＝•{{x1,x3,x7},{x2,x4},{x5,x6,x8}}•U／R2＝•{{x1,x5},{x2,x6},{x3,x4,x7,x8}}•这些等价类是由知识库K＝(U,{R1,R2})中的初等概念(初等范畴)构成的。二、原理•对于{R1,R2},它的基本范畴有•{x1,x3,x7}∩{x3,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,x8}R1*(X)={x2,x6}BNR(X)=R*(X)–R*(X)={x4,x5,x8}•IND({Age})={{x1,x2,x6},{x3,x4},{x5,x7}}•IND({LEMS})={{x1},{x2},{x3,x4},{x5,x6,x7}}•IND({Age,LEMS})={{x1},{x2},{x3,x4},{x5,x7},{x6}}.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no二、原理•W={x|Walk(x)=yes}.•W是一个粗糙集合AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no}.7,5,2{},4,3{)(},6,4,3,1{},6,1{xxxWAUxxWBNxxxxWAxxWAA二、原理二、原理yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AWWA二、原理•(三)粗糙集与不确定性•粗糙集理论中知识的不确定性有两方面:一是来自来自于论域上的二元关系及其产生的知识模块,即近似空间本身由于对象的可得到的信息不一定足以划分其成员类别,换句话说,这种不精确性导致了对象的不可分辨性。论域上的二元关系及其产生的知识模块越大,知识库中的知识越粗糙,近似空间的概念和知识就越不确定,这时处理知识的不确定性的方法往往用香农信息熵来刻画。二、原理•另一个是来自于给定论域里粗糙近似的边界,当边界为空集时知识是完全确定的,边界越大知识就越粗糙或越模糊。这时处理知识不确定性就用不分明对象类形成的上近似和下近似来描述。二、原理粗糙集与模糊集模糊集理论粗糙集理论对象间关系的基础概念边界的不分明性对象间不可分辨关系不精确刻画方法隶属程度粗糙度研究方法隶属函数对象的分类对知识的近似描述隶属程度上、下近似集对象间关系集合边界的病态定义和边界的不分明性不可分辨关系先验知识需要不需要与普通集合的联系λ截集上近似、下近似计算方法连续特征函数产生知识表达和简约(四)粗糙集模型的扩展基本粗糙集理论的主要存在的问题是：1)对原始数据本身的模糊性缺乏相应处理能力；2)对于粗糙集的边界区域的刻画过于简单；3)粗糙集理论的方法的分类是确定的，但并未提供数理统计中所常用的在一个给定错误率的条件下将尽可能多的对象进行分类的方法，而实际中常常遇到这类问题。二、原理1.可变精度粗糙集模型传统的粗糙集理论处理的分类必须是完全正确或肯定的,因为它是严格按照等价类来分类的,因而它的分类是精确的,亦即“包含”或“不包含”，而没有某种程度上的“包含”或“属于”,这一定程度上限制了它的应用。W.Ziarko在基本粗糙集模型的基础上引入了β(0＜β＜0.5)，即允许一定程度的错误分类率存在．提出了一种称之为可变精度粗糙集模型。二、原理二、原理•一般地，集合X包含于Y并未反映出集合X的元素属于集合Y的“多少”。为此，VPRS定义了它的量度：•当card(x)0，C(X,Y)=1–card(XY)/card(X)•当card(x)=0,C(X,Y)=0二、原理•C(X,Y)表示把集合X归类于集合Y的误分类度，即有C(X,Y)100%的元素归类错误。显然，C(X,Y)=0时有XY。如此，可事先给定一错误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X,Y)。•在此基础上，设U为论域且R为U上的等价关系，U/R=A={X1,X2,…,Xk}二、原理•可定义集合X的-下近似为：RX=Xi(C(Xi,X),i=1,2,…,k)并且RX称为集合X的-正区域集合X的-上近似为=Xi(C(Xi,X)1–,i=1,2,…,k)，-边界区域就定义为：BNRX=Xi(C(Xi,X)1–)；-负区域为：NEGRX=Xi(C(Xi,X)1–)。RXβUsetＸU/RR:subsetofattributesRXβRXβ二、原理2.相似关系模型在数据中存在缺失的属性值的时候，不分明关系或等价关系无法处理这种情形。为扩展粗糙集的能力，有许多作者提出了用相似关系来代替不分明关系作为粗糙集的基础。二、原理二、原理•在使用相似关系代替粗糙集的不分明关系后，最重要的变化就是相似类不再形成对集合的划分了，它们之间是相互重叠的。类似于等价类，可以定义相似集，即所有和某各元素x在属性集合B上相似的集合SIMb(x)。值得注意的是SIMb(x)中的元素不一定属于同一决策类，因此还需要定义相似决策类，即相似集对应的决策类集合。•Roughsets的研究对象是由一个多值属性(特征、症状、特性等)集合描述的一个对象(观察、病历等)集合,通常我们一个信息系统(二维表格)来表示。•使用Roughsets研究问题主要有三步:•(1)信息系统的生成;(2)知识的约简;(3)知识提取;三、应用•根据信息系统的不同,粗糙集的应用大都可以归入两类任务：无决策的分析和有决策的分析。•无决策分析主要是属性约简，去除多余属性，分析提取有用信息，尤其是从大型数据库进行知识发现；•有决策分析主要是规则获取，即利用粗糙集提供的值约简方法由实例集直接获取规则。三、应用（一）无决策分析无决策分析中的是属性约简主要使用的是绝对约简:设R是等价关系的一个族集，且设rR。若IND(R)=I