第9章-粗糙集理论

第9章粗糙集理论粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确、不一致和不完整等各种不完备的信息。还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。9.1粗糙集理论概述9.1.1粗糙集理论的产生1970年，Z.Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集（RoughSet）理论的思想。1982年，Z.Pawlak发表经典论文“RoughSets”，标志着该理论正式诞生。1991年，Z.Pawlak的第一本关于粗糙集理论的专著《Roughsets：theoreticalaspectsofreasoningaboutdata》。1992年，Slowinski主编的《Intelligencedecisionsupport：handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的《Foundationofcomputinganddecisionsciences》上。1995年，Z.Pawlak等人在《ACMCommunications》上发表“Roughsets”，极大地扩大了该理论的国际影响。1996～1999年，分别在日本、美国、美国、日本召开了第4～7届粗糙集理论国际研讨会。目前，粗糙集理论受到了国际上越来越多的学者的关注，不仅在数学上具有独立的地位，并发展出Rough代数学、Rough逻辑学等，而且在智能数据分析、知识发现和数据挖掘中得到广泛的研究和应用。9.1.2粗糙集理论的特点粗糙集理论是一种数据分析工具。粗糙集理论不需要先验知识。粗糙集理论是一种软计算方法。9.1.3粗糙集理论在数据挖掘中的应用在数据预处理过程中，粗糙集理论可以用于对特征更准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。9.2粗糙集理论中的基本概念9.2.1集合的基本概念定义9.1设R是集合U中的二元关系，若R是自反的、对称的和传递的，则称R是等价关系。定义9.2设R是非空集合U中的等价关系，对于任一确定的x∈U，均可构造一个U的子集[x]R。称为由x生成（或以x为代表元素）的R等价类：[x]R={y|y∈X且xRy}由此定义可知，集合U中与x有等价关系R的所有元素构成的集合就是[x]R。等价关系也称为不可分辨关系，也就是说，x1∈[x]R，x2∈[x]R，则x1和x2相对于等价关系R来说是不可分辨的。定义9.3设R是非空集合U中的等价关系。由U的各元素生成的R等价类所构成的集合{{[x]R|x∈U}，称为U关于R的商集。记作U/R。【例9.1】集合A={1，2，3，4}，有二元关系：R1={(1，1)，(2，2)，(3，3)，(4，4)，(2，3)，(3，2)，(3，4)，(4，3)，(2，4)，(4，2)}，R2={(1，1)，(2，2)，(3，3)，(4，4)，(1，2)，(2，1)，(1，3)，(3，1)，(2，3)，(3，2)}，显然R1和R2都是A上的等价关系。【例9.2】在例9.1中，则有：A/R1={{1}，{2，3，4}}，A/R2={{1，2，3}，{4}}。定义9.4设U是非空集合。A={A1，A2，…，Am}，其中集合AiU且Ai≠（i＝1，2，…，m）且=U，则称A是U的覆盖。定义9.5设A是U的覆盖，且满足Ai∩Aj=（i≠j），则称A是U的划分。A的任一元素ai，都称为A的一个类或划分的一个块。miiA1R1关系的划分R2关系的划分定义9.6设A={A1，A2，…，Am}与B={B1，B2，…，Bn}是非空集合U的两种划分。如果对于划分B的每一个类Bi，都存在划分A的一个类Aj，使得BiAj，则称B是A的细分。定义9.7设A={A1，A2，…，Am}与B={B1，B2，…，Bn}是非空集合U的两种划分，若U的划分C满足：（1）C是A和B的细分；（2）称C是划分A和B的积，记为C=A·B。且C=A·B={Ai∩Bj|i=1，2，…，m，j=1，2，…，n，Ai∩Bj≠}。R1关系的划分R2关系的划分R1·R2关系的划分9.2.2信息系统和粗糙集定义9.8信息系统I可以形式化表达为四元组I=(U，A，V，f)，其中，U为对象非空有限集合，称为论域，U中每个元素唯一标识一个对象；A为属性的非空有限集合，A={A1，A2，…，Am}；V=∪Vi，Vi是属性Ai的值域；f：U×A→V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即aA，xU，f(x，a)Va。信息系统也称为知识表达系统或信息表，可以简记为I=（U，A），如表9.1所示的是一个积木信息表I1，其中，U={1，2，3，4，5，6，7，8}，A={颜色，形状，大小}，U={1，2，3，4，5，6，7，8}。A={颜色，形状，大小}。V颜色={红色，蓝色，黄色}，V形状={圆形，方形，三角形}，V大小={大，小}。信息函数f对应该关系表。U颜色形状大小1红色圆形小2蓝色方形大3红色三角形小4蓝色三角形小5黄色圆形小6黄色方形小7红色三角形大8蓝色三角形大定义9.9设I=（U，A）是一个信息系统，对于PA，xi、xjU，定义二元关系INDP称为等价关系：)}()(,|),{()(jijixpxpPpUUxxPIND称对象xi、xj在信息系统I中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi、xj不能用P中的属性加以区别。例如，表9.1中，对象4和8关于属性集{颜色，形状}是等价的，因为它们的颜色均为“蓝色”、形状均为“三角形”。实际上，信息系统I中每个属性或者属性子集都可以对所有的对象产生划分，也就是说可以将A中一个属性或者属性子集看成是一个等价关系。从中看到，等价关系体现出一种分类能力，所以说等价关系就是一种知识。粗糙集理论就是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。定义9.10设I=（U，A）是一个信息系统，使用等价关系R对U进行划分，产生的等价类集合称为关于U的知识库，记为K=(U，R)，其中每个等价类称为知识库K的知识。由此可见，一个信息系统I=（U，A），可以看作是一个知识库K=（U，A），若PA且P≠Φ，则∩P（P中所有等价关系的交集）也是一个等价关系，P上的不可分辨关系IND(P)由以下等价类构成：RPRPINDxx][][)(或者说：RUPINDUPR/)(/【例9.4】对于表9.1所示的信息表I1，定义这样的三个等价关系：R1={颜色}，R2={形状}，R3={大小}，则：U/R1={{1，3，7}，{2，4}，{5，6，8}}，对应知识库为K1=（U，R1）U/R2={{1，5}，{2，6}，{3，4，7，8}}，对应知识库为K2=（U，R2）U/R3={{2，7，8}，{1，3，4，5，6}}，对应知识库为K3=（U，R3）U颜色形状大小1红色圆形小2蓝色方形大3红色三角形小4蓝色三角形小5黄色圆形小6黄色方形小7红色三角形大8蓝色三角形大而U/{R1，R2，R3}=U/R1∩U/R2∩U/R3={{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}}。所以说U/R1、U/R2和U/R3中的每个等价类是知识库K=(U，{R1，R2，R3})中的初等概念。U颜色形状大小1红色圆形小2蓝色方形大3红色三角形小4蓝色三角形小5黄色圆形小6黄色方形小7红色三角形大8蓝色三角形大基于R1的初等概念如下：{1，3，7}：红色积木{2，4}：蓝色积木{5，6，8}：黄色积木基于R2的初等概念如下：{1，5}：圆形积木{2，6}：方形积木{3，4，7，8}：三角形积木基于R3的初等概念如下：{2，7，8}：大积木{1，3，4，5，6}：小积木基本概念是初等概念的交集。基于{R1，R2}的基本概念如下：{1，3，7}∩{1，5}={1}：红色圆形积木{1，3，7}∩{3，4，7，8}={3，7}：红色三角形积木{2，4}∩{2，6}={2}：蓝色方形积木{2，4}∩{3，4，7，8}={4}：蓝色三角形积木{5，6，8}∩{1，5}={5}：黄色圆形积木{5，6，8}∩{2，6}={6}：黄色方形积木{5，6，8}∩{3，4，7，8}={8}：黄色三角形积木由U/R1、U/R2的初等概念构成U/{R1，R2}的基本概念如下图所示。定义9.11设K=（U，R）是一个知识库，对于一个集合XU，当X能表达成某些基本等价类（初等概念）的并集时，称为可定义的；否则称为不可定义的。R可定义集X能在这个知识库中被精确地定义，所以又称X为R精确集。R不可定义集X不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称X为R粗糙集。例如，一个知识库为（U，R），并有U/R={{1，4，8}，{2，5，7}，{3}，{6}}。则集合X={2，3，5，7}是R精确集，因为{2，5，7}∪{3}=X，而{2，5，7}和{3}均为知识库中的知识；而集合Y={1，7}是R粗糙集，因为不能由U/R中任何等价类通过并集得到。定义9.12设K=（U，R）是一个知识库，对于一个集合XU，则：集合X的R下近似（集）定义为：R_(X)=∪{yiU/R|yiX}集合X的R上近似（集）定义为：R-(X)=∪{yiU/R|yi∩X≠Φ}集合X的R边界域：BNR(X)=R-(X)-R_(X)集合X的R正域：POSR(X)=R_(X)集合X的R负域：NEGR(X)=U-R-(X)集合X是R精确的，当且仅当R-(X)=R_(X)。集合X是R粗糙的，当且仅当R-(X)≠R_(X)。粗糙集中相关概念的示意图【例9.5】设论域U={1，2，3，4，5，6，7，8}，U上有R1、R2和R三个等价关系，且R=R1·R2：U/R1={{1，2，3，4}，{5}，{6，7，8}}U/R2={{1，2}，{3，4}，{5，6，7，8}}问集合X={2，3，6，7，8}关于R是否是精确的？如果不是，则求出相应的上近似、下近似、边界域和负区域。由R=R1·R2，可求出：U/R=U/{R1，R2}={{1，2}，{3，4}，{5}，{6，7，8}}因为X无法用U/R的等价类并集精确表示，所以X关于R是U上的一个粗糙集。X的下近似集为：R_(X)={6，7，8}X的上近似集为：R-(X)={1，2}∪{3，4}∪{6，7，8}={1，2，3，4，6，7，8}X的边界域：BNR(X)=R-(X)-R_(X)={1，2，3，4}X的负区域：NEGR(X)=U-R-(X)={5}定义9.13设K=（U，R）是一个知识库，对于U中的两个集合X和Y，当R_(X)=R_(Y)时，称集合X、Y为R下相等；当R-(X)=R-(Y)时，称集合X、Y为R上相等。粗相等关系拓展了传统的相等关系，描述了任何不可分辨关系R的粗等价情况。9.2.3分类的近似度量定义9.14设K=（U，R）是一个知识库，对于U中的非空集合X，由等价关系R描述X的精确度定义为：|)(||)(|)(__XRXRXdR显然，0≤dR(X)≤1。如果dR(X)=1，则称集合X相对于R是精确的，此时，X的R边界域为空，X为全部R可定义的。如果dR(X)1，则称集合X相对于R是粗糙的。如果dR(X)=0，则集合X是全部R不可定义的。可用另一形式即X的R粗糙度rR(X)来定义X的不确定义，即：|)(||)(||)(||)(|1)(1)(___XRXBNXRXRXdXrRRRX的R粗糙度rR(X)与精确度dR(X)恰恰相反，它反映用R的类价类描述集合X的不完全程