粗糙集理论ppt.ppt

《粗糙集理论ppt.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论ppt.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1 1数据挖掘原理与数据挖掘原理与SPSS Clementine应用宝典应用宝典 元昌安元昌安 主编主编 邓松李文敬刘海涛编著邓松李文敬刘海涛编著 电子工业出版社电子工业出版社第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2 2第第11章章 粗糙集理论粗糙集理论 本章包括本章包括：粗糙集的基本概念粗糙集的基本概念 知识表达知识表达 粗糙集在数据预处理中的应用粗糙集在数据预处理中的应用第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3 3v粗粗糙糙集集理理论论是是由由波波兰兰华华沙沙理理工工大

2、大学学PawlakPawlak教教授授于于2020世世纪纪8080年年代代初初提提出出的的一一种种研研究究不不完完整整、不不确确定定知知识识和和数数据据的的表表达达、学学习习、归归纳纳的的理理论论方方法法，它它是是一一种种刻刻画画不不完完整整性性和和不不确确定定性性的的数数学学工工具具，能能有有效效地地分分析析不不精精确确、不不一一致致(inconslsteni)inconslsteni)、不不完完整整(incomPlete)incomPlete)等等各各种种不不完完备备的的信信息息，还还可可以以对对数数据据进进行行分分析析和和推推理理，从从中中发发现现隐隐含含的的知知识识，揭揭示示潜潜在在的

3、的规规律。律。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4 4v粗粗糙糙集集在在机机器器学学习习、决决策策支支持持系系统统、机机器器发发现现、归归纳纳推推理理、数数据据库库中中的的知知识识发发现现、模模式式识识别别等等领领域域都都得到了广泛的应用。得到了广泛的应用。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5 511.1粗糙集基本概念粗糙集基本概念 v粗粗糙糙集集应应用用于于数数据据挖挖掘掘领领域域，能能提提高高对对大大型型数数据据库库中中的的不不完完整整数数据据进进行行分分析析和和学学习习的的能能力力，具具有有广广泛泛的应用前景和实用价值。的应

4、用前景和实用价值。v粗粗糙糙集集方方法法仅仅利利用用数数据据本本身身提提供供的的信信息息，无无须须任任何何先验知识。先验知识。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6 6v粗粗糙糙集集是是一一个个强强大大的的数数据据分分析析工工具具，它它能能表表达达和和处处理理不不完完备备信信息息；能能在在保保留留关关键键信信息息的的前前提提下下对对数数据据进进行行化化简简并并求求得得知知识识的的最最小小表表达达式式；能能识识别别并并评评估估数数据据之之间间的的依依赖赖关关系系，揭揭示示出出概概念念的的简简单单模模式式；能能从经验数据中获取易于证实的规则知识。从经验数据中获取易于证

5、实的规则知识。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:7 7v粗粗糙糙集集的的研研究究对对象象是是由由一一个个多多值值属属性性(特特征征、症症状状、特特性性等等)集集合合描描述述的的一一个个对对象象(观观察察、病病历历等等)集集合合，对对于于每每个个对对象象及及其其属属性性都都有有一一个个值值作作为为其其描描述述符符号号，对象、属性和描述符是表达决策问题的对象、属性和描述符是表达决策问题的3 3个基本要素。个基本要素。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:8 8v粗粗糙糙集集理理论论逐逐渐渐应应用用于于数数据据挖挖掘掘领领域域中中，并并在在

6、对对大大型型数数据据库库中中不不完完整整数数据据进进行行分分析析和和学学习习方方面面取取得得了了显显著著的的成成果果，使使得得粗粗糙糙集集理理论论及及数数据据挖挖掘掘的的研研究究成成为为热热点点领领域域。最最近近几几年年，粗粗糙糙集集理理论论越越来来越越受受到到众众多多研研究究人人员员的的重重视视，它它的的应应用用研研究究得得到到了了很很大大的的发发展。展。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:9 911.1.1 知识和知识库知识和知识库 v 知识是人类通过实践对客观世界的运动规律的认知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有抽象

7、和普识，是人类实践经验的总结和提炼，具有抽象和普遍的特性。遍的特性。v 从认知科学的观点来看，知识来源于人类对客从认知科学的观点来看，知识来源于人类对客观事物的分类能力，概念是事物类别的描述或者符观事物的分类能力，概念是事物类别的描述或者符号，知识则是概念之间的关系和联系。任何一个物号，知识则是概念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用物种的不种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。同属性知识描述来产生对物种的不同分类。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1010v集合上的等价关系和集合上的划分是

8、一一对应，相集合上的等价关系和集合上的划分是一一对应，相互唯一决定的。从数学意义上讲，集合上的等价关互唯一决定的。从数学意义上讲，集合上的等价关系和集合的划分是等价的概念，即划分就是分类。系和集合的划分是等价的概念，即划分就是分类。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1111v定义定义11-1 11-1 设讨论的对象组成的有限集合，称为论设讨论的对象组成的有限集合，称为论域域(Universe)Universe)，对于论域中由等价关系划分出来的对于论域中由等价关系划分出来的任意子集，都可以称为论域任意子集，都可以称为论域U U中的一个概念中的一个概念(concep

9、t)concept)或范畴或范畴(category)category)。为规范起见，认为空为规范起见，认为空集必也是一个概念。论域集必也是一个概念。论域U U中的任意概念族称为关于中的任意概念族称为关于论域的抽象知识，它代表了对论域中个体的分类，论域的抽象知识，它代表了对论域中个体的分类，简称为知识。简称为知识。v定义定义11-2 11-2 K=(U,R)K=(U,R)其中其中K K为知识库，为知识库，U U为全体对象的为全体对象的集合称为论域，集合称为论域，R R为论域为论域U U上的等价关系上的等价关系(等价关系与等价关系与分类的概念等同分类的概念等同)，它是一种属性或多种属性的集合。，它

10、是一种属性或多种属性的集合。可以根据不同的可以根据不同的R R对对U U进行不同形式的分类。知识库进行不同形式的分类。知识库也被称作近似空间。也被称作近似空间。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1212v定义定义11-3 11-3 K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)是两个知识库，若是两个知识库，若IND(P)=IND(Q)IND(P)=IND(Q)，则称则称K K和和M(M(或或Q Q和和P)P)是等价的，是等价的，记作记作 (或者或者)。因此，当。因此，当K K和和M M是同样的基本范是同样的基本范畴集时，知识库畴集时，知识库K K和

11、和M M中的知识都能使我们确切地表中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着可达关于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事实。域的完全相同的事实。v对于两个知识库对于两个知识库K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)，当当 时，称知识库时，称知识库P P比知识库比知识库Q Q更精细，或者说更精细，或者说Q Q比比P P更粗更粗糙。当糙。当P P比比Q Q更精细时，我们称更精细时，我们称P P为为Q Q的特化，的特化，Q Q为为P P的的推广。由以

12、上可知，推广是将某些范畴组合在一起，推广。由以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。而特化则是将范畴分割成更小的单元。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:131311.1.2 不可分辨关系不可分辨关系 v在粗糙集理论中，在粗糙集理论中，“知识知识”被认为是一种分类的能被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它力。不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。假定关于论域的某揭示出论域知识的颗粒状结构。假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，种知识，并使用属性和属性值来

13、描述论域中的对象，如果两个对象如果两个对象(或对象集合或对象集合)具有相同的属性和属性具有相同的属性和属性值，则它们之间具有不可分辨关系。值，则它们之间具有不可分辨关系。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1414v定义定义11-411-4设R是非空集合U上的二元系，如果它是自反的、对称的和可传递的，则称R为U上的等价关系。若，则称x与y有关系，记为 ；若 ，则称x与y没有关系，记为 。等价关系的一个重要特点是用它可以构成U的一个划分。划分即是分类，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。第第第第1111章章章章粗糙集理论粗糙集理论

14、粗糙集理论粗糙集理论:1515v定义定义11-511-5设U是一个论域，R是U上的等价关系，U/R表示U上由R导出的所有等价类。v 表示包含元素xU的R等价类。一个知识库就是一个关系系统K=U,P，其中U是论域，P是U上的一个等价类簇。如果 且 ，则 (Q的所有等价类的交也是一个等价关系)，称Q为不可分辨关系,记作IND(Q)。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:161611.1.3 上、下近似集上、下近似集 v给定论域给定论域U U，一族等价关系一族等价关系R R将将U U划分为互不相交的基划分为互不相交的基本等价类本等价类U/RU/R。令令 XgUXgU为为R

15、 R上的一个等价关系。上的一个等价关系。v当能表达成某些基本等价类的并集时，称为可定义当能表达成某些基本等价类的并集时，称为可定义的；否则称为不可定义的。的；否则称为不可定义的。R R可定义集能在这个知识可定义集能在这个知识库中被精确地定义，所以又称为库中被精确地定义，所以又称为R R精确集。精确集。vR R不可定义集不能在这个知识库中被精确定义，只能不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为通过集合逼近的方式来刻画，因此也称为R R粗糙集粗糙集 (Roughset)Roughset)。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:17

16、17v两个精确集，两个精确集，v即粗糙集的上近似集即粗糙集的上近似集(UpperApproximation)UpperApproximation)和下近和下近似集似集(LowerApproximation)LowerApproximation)来近似地定义粗糙集。来近似地定义粗糙集。v粗糙集理论引入上近似和下近似等概念来刻画知识粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。的不确定性和模糊性。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1818v定义11-6设集合 ，R是一个等价关系，称 v 为集合X的R下近似集；v称 为集合X的R上近似集；v称集合 为

17、X的R边界域；v称 为X的R正域；v称 为X的R负域。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:1919v例例11-1 11-1 设论域 ，U上的一族等价关系R=R1,R2,R1和R2是两个等价关系。根据这两个等价关系可以将论域U进行划分：v 和 。U/R1中的 ，代表 的等价类。v论域U被R划分的基本等价类为:v集合 是U上的一个子集。则X无法用基本等价类U/R的并集精确表示，所以X是U上的一个粗糙集合。故有:vX的下近似集为:；vX的上近似集为:；vX的负区域:。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:202011.2知识表达知识表达 v知

18、识表达在智能数据处理中占有十分重要的地位。知识表达在智能数据处理中占有十分重要的地位。在智能系统中，经常会碰到要处理的对象可能是用在智能系统中，经常会碰到要处理的对象可能是用语言方式表达，也可能使用数据表达；可能是精确语言方式表达，也可能使用数据表达；可能是精确的数据，可能会有一些缺省的信息或者相互矛盾的的数据，可能会有一些缺省的信息或者相互矛盾的信息。信息。v为了处理这些数据，我们需要进行知识的表达，即为了处理这些数据，我们需要进行知识的表达，即知识表达系统。决策表是特殊的知识表达系统。知识表达系统。决策表是特殊的知识表达系统。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论

19、:212111.2.1 知识表达系统知识表达系统 v定义定义11-711-7一个知识表达系统一个知识表达系统S S可以定义为，其中可以定义为，其中U U为对象的集合，称为论域；为对象的集合，称为论域；=R R为属性集合；子集为属性集合；子集C C和和D D分别称为条件属性和决策属性；分别称为条件属性和决策属性；为属性值的集合；为属性值的集合；表示了属性的属性值范围；是一个信息函数，它指表示了属性的属性值范围；是一个信息函数，它指定了定了U U中每一对象中每一对象x x的属性值。的属性值。v知识表达系统的数据以知识表达系统的数据以关系表关系表的形式表示，关系表的形式表示，关系表的行对应要研究的对

20、象，列对应对象的属性，对象的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达的信息是通过指定对象的各属性值来表达。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2222v例例11-211-2：表11.1是一个轿车信息决策表，条件属性集为e1,e2,e3,e4分别代表价格、油耗、速度和安全性，决策属性为d，表示质量。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2323 表表11.1 轿车信息决策表轿车信息决策表车型车型U Ue1e1e2e2e3e3e4e4d d1 1高低快好高2 2低高中差低3 3中中慢一般低4 4中高慢一

21、般中5 5低高中差低6高低快好高第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:242411.2.2 决策表决策表 v决决策策表表包包含含了了某某一一领领域域的的大大量量数数据据，是是领领域域的的样样本本数数据据库库。它它记记录录了了大大量量样样本本的的属属性性值值和和决决策策情情况况，是领域知识的载体。是领域知识的载体。v知知识识获获取取的的目目的的就就是是要要通通过过分分析析这这个个实实例例库库来来得得到到该该领领域域中中有有用用的的、规规律律性性知知识识。决决策策表表在在决决策策应应用用中中有有十十分分重重要要的的地地位位，可可用用于于表表达达绝绝大大多多数数决决策策问

22、问题。对于决策表，最重要的是决策规则的生成。题。对于决策表，最重要的是决策规则的生成。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2525v定义定义11-811-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 的值。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2626v定义定义11-911-9 若决策表T 中任意的dxdy,由dx|C=dy|C

23、,可得dx|D=dy|D,则称决策规则dx 是一致的,否则,称决策规则dx 是不一致的。如果T 中每条决策规则都是一致的,则称决策表T 是一致的,否则称决策表T是不一致的。v定义定义11-1011-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 的正区域，其中 。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2727v定义定义11-1111-11 如果决策表中每个条件属性都是关于D 不可省的,则

24、称条件属性集C 是关于D独立的，否则称C 是关于D 依赖的。v定义定义11-1211-12 决策表T=(U,P,C,D)中条件属性集C 的一个子集B 是关于D 独立的,并且PosB(D)=PosC(D),则称B 是C 的一个D约简。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:282811.2.3 属性约简、核集的求取属性约简、核集的求取 v所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。v一个属性集合可能有多个约简。v属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性

25、所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属性D有相同的分类能力。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:2929v属性集合P的所有约简的交集定义为P的核(Core)，记作core(P)，核是表达知识必不可少的重要属性集。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3030v核的概念具有两方面的意义:v(l)因为核包含于所有约简之中，所以核可以作为所有约简的计算基础。v(2)核在知识约简中是不能消去的特征集合。v直接由分辨矩阵来求取系统的核集Pc。不失一般性,假定系统T 对于属性集P 是可分辨的。则系统的核集由以下定理1确定。第

26、第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3131v定定理理11-111-1P 中任一属性P Pc,充要条件为:D(P)中至少存在一个元素 ,满足 。其中，元素都是属性集P的一个子集，元素Dij定义如下：v 其中i,j=1,2,3,，m。（1）v （2）第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3232v命题命题11-111-1从信息系统的决策表中将属性集P中逐一移去,每移去一个属性即刻检查其决策表,如果不出现新的不一致,则属性是可被约去的；否则属性不能约去。v命题命题11-211-2 全体不可约去属性集称为核集。v属性集合的约简和核的关系如下:v

27、式中red(P)表示P的所有约简。core(P)含有P的全部约简中共同的等价关系，是属性集合P中不可缺少的重要属性集。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:333311.2.4 属性值约简属性值约简 v属性约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类产生的影响也不同。v例如，判断人的体形(瘦、中、胖)时，体重是主要属性。但若体重属性值为75Kg时，此人的体形要结合其身高、性别等属性才能确定。如果体重属性值为160Kg时，几乎肯定其体形为胖，这时身高、性别已不重要。第第第第1111章

28、章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3434v命题11-3设 是决策表上的一条决策规则,属性值v 是一可被约去当且仅当 ,其中 和 均为决策表上的逻辑公式8。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:353511.2.5 决策规则决策规则6 v决策表包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，是领域知识的载体。v知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。v从决策表分析得到的规律性知识，通常采用决策规则的形式记录下来。下面给出决策规则的形式化描述。第第第第1111章章章章粗糙集理论粗糙集理论粗

29、糙集理论粗糙集理论:3636v定义定义11-1311-13定义公式如下：v(1)(a,v)(或写为av，aA，vVa，表示属性a的取值为v)是公式且是原子公式。v(2)如果A和B都是公式，那么 ,AB都是公式。v(3)只有按定义(1)和(2)所组成的式子是公式。v对于决策表 是决策表，A=CD属性集合，子集 和 分别为条件属性集和决策属性集，有关决策规则的定义如下：第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3737v定义定义11-1411-14公式 称为P基本公式，这里 ，P，。v定义定义11-1511-1511公式 称为Q基本公式，这里 ，。v定义定义11-1611-

30、1611公式AB为决策规则，如果A是P基本公式且B是Q基本公式，则AB是基本决策规则。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:383811.2.6 基于可辨识矩阵属性约简算法基于可辨识矩阵属性约简算法6 v可辨识矩阵（也称分明矩阵）是由波兰数学家Skowron.A教授提出的。v定义定义11-1711-17设相容决策表T=，A=CD，和D=d分别为条件属性集和决策属性集，是论域，是样本 在属性上的取值。表示可辨识矩阵中第i行j列的对象，则可辨识矩阵定义为：其中，第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:3939v由上述定义可以看出，可辨识矩阵是一

31、个对称矩阵。当两个样本的决策属性取同时，对象值为0；当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同的条件属性集合。v一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，所有的蕴含式包含的属性就是决策表的所有约简集合。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4040v算法算法11-111-1可辨识矩阵属性约简算法可辨识矩阵属性约简算法 v输入输入：相容决策表DT=，A=CD是属性集合；v输出输出：约简的属性集。v步骤：步骤：vStep1计算决策表的可辨识矩阵 ；/根据分辨矩阵的定义求元素vStep

32、 2对于可辨识矩阵中所有取值为非空集合的对象 ，建立相应的析取逻辑表达式,v ,；第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4141vStep 3将所有的析取逻辑表达式 进行合取运算，得一个合取范式T，即 ；vStep 4将合取范式L转换为析取范式的形式，得 ；vStep 5输出属性约简结果。v基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化 第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:424211.2.7 信息熵的属性约简信息熵的属性约简 v信息熵是信息论的核心内

33、容，它最早应用于通信领域。由于信息熵可以刻画信息划分粒度的大小，也被广泛应用于信息不确定性的度量。v设U为一个论域,可以认为U上任一属性集合(知识、等价关系簇)是定义在U上的子集组成的R代数上的一个随机变量,其概率分布可通过如下方法来确定。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4343v定义定义11-1811-18设P,Q在U上导出的划分分别为X,Yv则P,Q在U的子集组成的代数上的概率分布为第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4444其中，；v定义定义11-1911-19知识P的熵H(P)定义为 。第第第第1111章章章章粗糙集理论粗

34、糙集理论粗糙集理论粗糙集理论:4545v定义定义11-2011-20决策信息系统S=(U,A=CD,V,F),C、D为U上的一个等价关系集合，C、D在U上导出的划分分别为:v则D相对于C的条件信息熵H(D|C)为：v其中，第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4646v定理定理11-211-2在信息系统S=(U,A=CD,V,F)中，若H(D|B)=H(D|(B-b)则称b为B中相对于D是可省的（不必要的）；否则b为B中相对于D是不可省的。对 ,若其任一元素D都是必要的，则称B相对于D是独立的。v定义定义11-2111-21在决策信息系统S（U,A=CD,V,F）中

35、，若 ,H(D|B)=H(D|C)且B相对与D是独立的，则称B是C关于D的属性约简。v推论推论11-111-1如果一个属性a不能为属性子集R的分类增加任何信息，即 ，就可以将这个属性约简。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4747v算法算法11-211-2信息熵的求核算法信息熵的求核算法v输入输入：相容决策表T=，A=CD是属性集合；子集 和D=d分别为条件属性集和决策属性集；v输出输出：信息熵定义下的核属性 ；v步骤：步骤：vBeginBegin (1)；v(2)对于条件属性集C中的所有属性r,如果H(D|C)H(D|C-r),则 ；End End第第第第11

36、11章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4848CEBARKCC算法是一种比较典型的基于信息熵的属性约简算法。该算法是建立在决策属性集相对于条件属性集的条件熵的基础上的，以H(D|Ba)作为启发式信息，以H(D|B)=H(D|C)作为算法的终止条件。CEBARKCC算法以决策表核属性集为起点，逐次选择使H(D|Ba)最小的非核条件属性a添加到核属性集中，直到满足终止条件H(D|B)=H(D|C)第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:4949v算法算法11-311-3CEBARKCCCEBARKCC算法算法v输入：输入：相容决策表T=，A=CD是属性集合

37、；子集v 和D=d分别为条件属性集和决策属性集；v输出：输出：该决策表的一个相对约简B。v步骤：步骤：vStep1计算决策表S中决策属性集D相对条件属性集C的条件熵H(D|C)；vStep 2计算条件属性集C中相对于决策属性集D的核属性Co；vStep 3令B=C0第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5050 a 如果|B|!=0,则计算条件熵H(D|B),转d)；v b 对每个属性 ,计算决策属性集D相对条件属性集的条件熵 ；v c 选择使 c(若同时有多个属性达到则从中选取一个与B的属性值组合数最少的属性),；vd IF H(D|B)H(D|C)Then b)

38、第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5151基于信息熵的属性约简改进基于信息熵的属性约简改进算法算法2 v定定义义11-2211-22设S=(U,A=CD,V,F)是一个决策信息系统，其中C是条件属性集合，D是决策属性集合，且 ,则对于任意属性aC-R的重要度的定义为：v =,v其中 。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5252v算法算法11-411-4信息熵的属性约简改进算法信息熵的属性约简改进算法v输入：输入：相容决策表T=，A=CD是属性集合；v子集 和D=d分别为条件属性集和决策属性集；v输出：输出：决策表T的一个相对约简P

39、。v步骤：步骤：vStep1计算决策表T中决策属性集D相对条件属性集C的条件熵H(D|C)；vStep 2计算条件属性集C中相对于决策属性集D的核属性Co；Step 3 计算条件信息熵H(D|P)，转Step 6；第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5353vStep 4 对 i=1.n,biB中 的 每 个 属 性 计 算 条 件 熵H(D|Pbi)，求vSGF（bi,P,D）=H(D|P)-H(D|Pbi)得到属性bi的重要度SGF（bi,P,D）；vStep 5选择使SGF（bi,P,D）最大的属性bi（若同时有多个属性达到最小值，则从中选取一个与P的属性值

40、组合数最少的属性），把bi从B中删除，并把bi增加到P的尾部；同时从B中删除使SGF的值为零的属性bi；第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5454vStep 6如果H(D|P)H(D|C)Then Step 4 Step 7从P的尾部开始，从后向前判别每个属性的a是否可约。如果 ，则从a开始向前的属性都是核属性，不可约，算法终止；否则，如果H(D|P-a)=H(D|C)，则a是可约简的，把a从A中删除。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5555v例11-4：根据表11.5决策表所示，根据算法11-4进行信息熵的属性约简计算。表表1

41、1.5决策表决策表vU a b c d e fU a b c d e fve1 1 0 1 1 2 1ve2 0 0 1 1 1 0ve3 1 1 0 1 2 0ve4 0 1 0 1 1 1ve5 1 2 2 1 2 0ve6 2 1 0 1 0 1第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5656vStep1求出H(D|C)=0；vStep2利用求核算法求出 ；情形一：Step3求 出 H(D|P)=1;转 Step 6,if H(D|P)H(D|C)Then Step4Step4SGF(a,P,D)=H(D)-H(D|a)=0.2075;SGF(b,P,D)=H(

42、D)-H(D|b)=0.2075;SGF(c,P,D)=H(D)-H(D|c)0.2075;SGF(d,P,D)=H(D)-H(D|d)=0;SGF(e,P,D)=H(D)-H(D|e)=0.2705;P=a,B=b,c,e;Step5 选择属性a同时删除不必要的属性d。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5757情形二：Step3 H(D|P)=0.7925;转Step 6,if H(D|P)H(D|C)Then Step4Step4 SGF(b,P,D)=H(D|a)-H(D|a,b)=0.7925;SGF(c,P,D)=H(D|a)-H(D|a,c)=0.7

43、925;SGF(e,P,D)=H(D|a)-H(D|a,e)=0；P=a,b,B=c;Step5 选择属性b的同时删除不必要的属性e。H（D|P）=H（D|C）=0Step6 P中没有可删除属性。则相对约简集为P=a,b。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:585811.3粗糙集在数据预处理粗糙集在数据预处理中的应用中的应用 v基于粗糙集理论的数据预处理方法，首先对原始数据（原始决策表）进行离散化，然后可以通过两种方法对离散化的决策表进行属性约简，最后进行属性值的约简。我们以一个医疗数据记录决策表为例子，给出属性约简求核和属性值约简的过程。第第第第1111章章章章

44、粗糙集理论粗糙集理论粗糙集理论粗糙集理论:5959属性约简的两种方法属性约简的两种方法 v本节介绍属性约简的两种方法：分辨矩阵求核约简方法、直接求核集方法。v方方法法一一，分分辨辨矩矩阵阵求求核核约约简简方方法法：设D是一个m*m阶矩阵，其中每一个元素Dij都是P的一个子集，元素Dij定义如下：vDij=dij1,dij2,dij3,dijn v 其中i,j=1,2,3,，m。(1)(2)v说明：U,U表示决策表中第i行和第j行两个属性的值；k表示决策表的研究对象的个数，分辨矩阵D是一个对角线为0的对称矩阵。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6060v方法二，直

45、接求核集方法方法二，直接求核集方法：用命题11-1、命题11-2直接求核集。例例11-311-3以下决策表11.2给出了一个医疗数据记录表，通过测量人的体温、咳嗽、头痛、周身痛等症状来确定是否患了流感。表表11.2医疗记录表医疗记录表v U U 体温体温 咳嗽咳嗽 头痛头痛 周身痛周身痛 流感流感v1 正常 无 无 有 无v2 正常 无 有 无 无v3 偏高 无 有 无 有v4 高 有 有 无 有v5 高 有 无 无 有v6 偏高 有 有 无 有第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6161v其中属性及属性值的含义为：v体温a，正常0，偏高1，高2；咳嗽b，无0，有

46、1；头痛c,无0，有1；周身痛d，无1，有1；流感e，无0，有1。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6262通过对决策表通过对决策表通过对决策表通过对决策表11-211-211-211-2进行处理后，得到离散形式的决策表进行处理后，得到离散形式的决策表进行处理后，得到离散形式的决策表进行处理后，得到离散形式的决策表11.311.311.311.3如下所示：如下所示：如下所示：如下所示：v表表11.3医疗决策表医疗决策表vU a b c d eU a b c d ev1 0 0 0 1 0v2 0 0 1 0 0v3 1 0 1 0 1v4 2 1 1 0 1v5

47、 2 1 0 0 1v6 1 1 1 0 1v其中：条件属性集为a,b,c,d，决策属性集为e。根据粗糙集理论对表11.3医疗决策表进行数据预处理，处理过程分两个步骤进行，一是对决策表条件属性集进行约简求核；二是对条件属性值进行约简。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6363Step1条件属性约简求核 v下面讨论属性约简求核的两种方法：分辨矩阵直接求核约简法和用命题11-1、命题11-2求核约简法。v首先，用分辨矩阵直接求核集。用以下举例说明分辨矩阵求核约简的方法，如表11.3医疗决策表所示是一个知识系统，U=U1,U2,，Un是论域，C=a,b,c,d 是条件

48、属性集，D=e 是决策属性集，。则其相应的分辨矩阵为：vD=第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6464v从上述分辨矩阵中可以得出：由于D=e是决策集，不需要约简，约简的是条件集合C，根据定理11-1直接求出该知识系统的核集为 a,b,c。该约简求核集的方法便于计算机上实现。v其次，用方法二直接求核集集。还是以决策表11.3作为知识系统的例子，求核集的步骤为：v（1）去掉属性a,对比每一行属性值，第4、6行发生冲突，则属性a不可约；v（2）去掉属性b,对比每一行属性值，第4、6行发生冲突，则属性b不可约；第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集

49、理论:6565v（3）去掉属性c,对比每一行属性值，第4、5行发生冲突，则属性c不可约；v（4）去掉属性d,对比每一行属性值，没有发生冲突，则属性d可约；v若还有条件属性，则依次类推。经过约简后得到的核集为a,b,c。v比较两种求核集的方法，对于数据量大，采用分辨矩阵来求核集，方便计算机来实现；第二种方法简单易行，方便人工处理。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6666Step2属性值约简 v 属性值约简是在核集基础上进行的，经约简后的核集用表11.4医疗核集决策表表示如下：表表11.4医疗核集决策表医疗核集决策表 U a b c eU a b c e1 0 0

50、 0 01 0 0 0 02 0 0 1 02 0 0 1 03 1 0 1 13 1 0 1 14 2 1 1 14 2 1 1 15 2 1 0 15 2 1 0 16 1 1 1 16 1 1 1 1根据命题11-3计算决策规则中条件属性的核值,并确定出一个最小决策算法，用逻辑语义表示。第第第第1111章章章章粗糙集理论粗糙集理论粗糙集理论粗糙集理论:6767v对于决策规则1，1a=1,2,1b=1,2,3,1c=1,5,1e=1,2v其中：1a 1b=1,21,2,3=1,2 1e，则c0（表示c属性值为0）可约；v1a 1c=1,2 1,5=1 1e,则b0（表示b属性值为0）可约；