第11章粗糙集理论.

第11章©粗糙集理论:1数据挖掘原理与SPSSClementine应用宝典元昌安主编邓松李文敬刘海涛编著电子工业出版社第11章©粗糙集理论:2第11章粗糙集理论本章包括：粗糙集的基本概念知识表达粗糙集在数据预处理中的应用第11章©粗糙集理论:3粗糙集理论是由波兰华沙理工大学Pawlak教授于20世纪80年代初提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致(inconslsteni)、不完整(incomPlete)等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。第11章©粗糙集理论:4粗糙集在机器学习、决策支持系统、机器发现、归纳推理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。第11章©粗糙集理论:511.1粗糙集基本概念粗糙集应用于数据挖掘领域，能提高对大型数据库中的不完整数据进行分析和学习的能力，具有广泛的应用前景和实用价值。粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。第11章©粗糙集理论:6粗糙集是一个强大的数据分析工具，它能表达和处理不完备信息；能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估数据之间的依赖关系，揭示出概念的简单模式；能从经验数据中获取易于证实的规则知识。第11章©粗糙集理论:7粗糙集的研究对象是由一个多值属性(特征、症状、特性等)集合描述的一个对象(观察、病历等)集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符是表达决策问题的3个基本要素。第11章©粗糙集理论:8粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙集理论及数据挖掘的研究成为热点领域。最近几年，粗糙集理论越来越受到众多研究人员的重视，它的应用研究得到了很大的发展。第11章©粗糙集理论:911.1.1知识和知识库知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有抽象和普遍的特性。从认知科学的观点来看，知识来源于人类对客观事物的分类能力，概念是事物类别的描述或者符号，知识则是概念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。第11章©粗糙集理论:10集合上的等价关系和集合上的划分是一一对应，相互唯一决定的。从数学意义上讲，集合上的等价关系和集合的划分是等价的概念，即划分就是分类。第11章©粗糙集理论:11定义11-1设讨论的对象组成的有限集合，称为论域(Universe)，对于论域中由等价关系划分出来的任意子集，都可以称为论域U中的一个概念(concept)或范畴(category)。为规范起见，认为空集必也是一个概念。论域U中的任意概念族称为关于论域的抽象知识，它代表了对论域中个体的分类，简称为知识。定义11-2K=(U,R)其中K为知识库，U为全体对象的集合称为论域，R为论域U上的等价关系(等价关系与分类的概念等同)，它是一种属性或多种属性的集合。可以根据不同的R对U进行不同形式的分类。知识库也被称作近似空间。U第11章©粗糙集理论:12定义11-3K=(U,P)和M=(U,Q)是两个知识库，若IND(P)=IND(Q)，则称K和M(或Q和P)是等价的，记作(或者)。因此，当K和M是同样的基本范畴集时，知识库K和M中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事实。对于两个知识库K=(U,P)和M=(U,Q)，当时，称知识库P比知识库Q更精细，或者说Q比P更粗糙。当P比Q更精细时，我们称P为Q的特化，Q为P的推广。由以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。KMPQIND(P)IND(Q)第11章©粗糙集理论:1311.1.2不可分辨关系在粗糙集理论中，“知识”被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，如果两个对象(或对象集合)具有相同的属性和属性值，则它们之间具有不可分辨关系。第11章©粗糙集理论:14定义11-4设R是非空集合U上的二元系，如果它是自反的、对称的和可传递的，则称R为U上的等价关系。若，则称x与y有关系，记为；若，则称x与y没有关系，记为。等价关系的一个重要特点是用它可以构成U的一个划分。划分即是分类，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。xRy(x,y)R(x,y)R_xRy第11章©粗糙集理论:15定义11-5设U是一个论域，R是U上的等价关系，U/R表示U上由R导出的所有等价类。表示包含元素x∈U的R等价类。一个知识库就是一个关系系统K={U,P}，其中U是论域，P是U上的一个等价类簇。如果且，则(Q的所有等价类的交也是一个等价关系)，称Q为不可分辨关系,记作IND(Q)。[]RxQPQQ第11章©粗糙集理论:1611.1.3上、下近似集给定论域U，一族等价关系R将U划分为互不相交的基本等价类U/R。令XgU为R上的一个等价关系。当能表达成某些基本等价类的并集时，称为可定义的；否则称为不可定义的。R可定义集能在这个知识库中被精确地定义，所以又称为R精确集。R不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为R粗糙集(Roughset)。第11章©粗糙集理论:17两个精确集，即粗糙集的上近似集(UpperApproximation)和下近似集(LowerApproximation)来近似地定义粗糙集。粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。第11章©粗糙集理论:18定义11-6设集合，R是一个等价关系，称为集合X的R下近似集；称为集合X的R上近似集；称集合为X的R边界域；称为X的R正域；称为X的R负域。XURRX={x|xU|,[x]X}且RRX={x|xU|,[x]X}且()RBNXRXRXRPOS(X)=RXRNEG(X)=U-RX第11章©粗糙集理论:19例11-1设论域，U上的一族等价关系R={R1,R2},R1和R2是两个等价关系。根据这两个等价关系可以将论域U进行划分：和。U/R1中的，代表的等价类。论域U被R划分的基本等价类为:集合是U上的一个子集。则X无法用基本等价类U/R的并集精确表示，所以X是U上的一个粗糙集合。故有:X的下近似集为:；X的上近似集为:；X的负区域:。12345678U={e,e,e,e,e,e,e,e}212345678U/R={{e,e},{e,e},{e,e,e,e}}1234{e,e,e,e}11[]Re12345678U/R={{e,e},{e,e},{e},{e,e,e}}23678X={e,e,e,e,e}678Pos(X)=R(X)={e,e,e}12345678R(X)={e,e,e,e,e,e,e,e}R5NEG(X)={e}112345678U/R={{e,e,e,e},{e,e,e,e}}第11章©粗糙集理论:2011.2知识表达知识表达在智能数据处理中占有十分重要的地位。在智能系统中，经常会碰到要处理的对象可能是用语言方式表达，也可能使用数据表达；可能是精确的数据，可能会有一些缺省的信息或者相互矛盾的信息。为了处理这些数据，我们需要进行知识的表达，即知识表达系统。决策表是特殊的知识表达系统。第11章©粗糙集理论:2111.2.1知识表达系统定义11-7一个知识表达系统S可以定义为，其中U为对象的集合，称为论域；=R为属性集合；子集C和D分别称为条件属性和决策属性；为属性值的集合；表示了属性的属性值范围；是一个信息函数，它指定了U中每一对象x的属性值。知识表达系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。第11章©粗糙集理论:22例11-2：表11.1是一个轿车信息决策表，条件属性集为{e1,e2,e3,e4}分别代表价格、油耗、速度和安全性，决策属性为d，表示质量。第11章©粗糙集理论:23表11.1轿车信息决策表车型Ue1e2e3e4d1高低快好高2低高中差低3中中慢一般低4中高慢一般中5低高中差低6高低快好高第11章©粗糙集理论:2411.2.2决策表决策表包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，是领域知识的载体。知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。决策表在决策应用中有十分重要的地位，可用于表达绝大多数决策问题。对于决策表，最重要的是决策规则的生成。第11章©粗糙集理论:25定义11-8设U={U1，U2，U3，…，Un}是一个论域,U(i=1,2,…，n)是研究对象。P是属性集,P=C+D,C为条件属性集,D为决策属性集,T=(U,P,C,D)是决策表。决策表中每一行就是一条决策规则:dx|C-dx|D,dx|B表示个体x关于属性集B的值。第11章©粗糙集理论:26定义11-9若决策表T中任意的dx≠dy,由dx|C=dy|C,可得dx|D=dy|D,则称决策规则dx是一致的,否则,称决策规则dx是不一致的。如果T中每条决策规则都是一致的,则称决策表T是一致的,否则称决策表T是不一致的。定义11-10设T=(U,P,C,D)是决策表,如果去掉条件属性Pi，得到的表T1=(U,P-{Pi},C-{Pi},D)与表T相比,有PosC(D)=Pos(D)，则称属性Pi是关于D可省的,否则称属性Pi是关于D不可省的,是D关于B的正区域，其中。PosB(D)=YU/IND(D)B(Y)B(Y)={XU/IND(B):XY}第11章©粗糙集理论:27定义11-11如果决策表中每个条件属性都是关于D不可省的,则称条件属性集C是关于D独立的，否则称C是关于D依赖的。定义11-12决策表T=(U,P,C,D)中条件属性集C的一个子集B是关于D独立的,并且PosB(D)=PosC(D),则称B是C的一个D约简。第11章©粗糙集理论:2811.2.3属性约简、核集的求取所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。一个属性集合可能有多个约简。属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属性D有相同的分类能力。第11章©粗糙集理论:29属性集合P的所有约简的交集定义为P的核(Core)，记作core(P)，核是表达知识必不可少的重要属性集。第11章©粗糙集理论:30核的概念具有两方面的意义:(l)因为核包含于所有约简之中，所以核可以作为所有约简的计算基础。(2)核在知识约简中是不能消去的特征集合。直接由分辨矩阵来求取系统的核集Pc。不失一般性,假定系统T对于属性集P是可分辨的。则系统的核集由以下定理1确定。第11章©粗糙集理论:31定理11-1P中任一属性P∈Pc,充要条件为:D(P)中至少存在一个元素,满足。其中，元素都是属性集P的一个子集，元素Dij定义如下：其中i,j=1,2,3,…，m。（1）（2）ijD(P)ijkD(P)={P}ijDijij1ij2ij3ijnD={d,d,d,,d}ijk,d=1,2,3,,.,,ikjkkikjkUUknPUU第11章©粗糙集理论:32命题11-1从信息系统的决策表中将属性集P中逐一移去,每移去一个属性即刻检查其决策表,如果不出现新的不一致,则属性是可被约去