粗糙集理论课程学习.pptx

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

1、会计学1粗糙集理论粗糙集理论(lln)第一页，共80页。第第11章章 粗糙集理论粗糙集理论(lln)本章包括本章包括本章包括本章包括(boku)(boku)：粗糙集的基本概念粗糙集的基本概念粗糙集的基本概念粗糙集的基本概念 知识表达知识表达知识表达知识表达 粗糙集在数据预处理中的应用粗糙集在数据预处理中的应用粗糙集在数据预处理中的应用粗糙集在数据预处理中的应用第1页/共79页第二页，共80页。n n粗粗糙糙集集理理论论是是由由波波兰兰华华沙沙理理工工大大学学PawlakPawlak教教授授于于2020世世纪纪8080年年代代初初提提出出的的一一种种研研究究不不完完整整、不不确确定定知知识识和和

2、数数据据的的表表达达、学学习习、归归纳纳的的理理论论方方法法，它它是是一一种种刻刻画画不不完完整整性性和和不不确确定定性性的的数数学学工工具具，能能有有效效地地分分析析(fnx)(fnx)不不精精确确、不不 一一 致致(inconslsteni)(inconslsteni)、不不 完完 整整(incomPlete)(incomPlete)等等各各种种不不完完备备的的信信息息，还还可可以以对对数数据据进进行行分分析析(fnx)(fnx)和和推推理理，从从中中发发现现隐含的知识，揭示潜在的规律。隐含的知识，揭示潜在的规律。第2页/共79页第三页，共80页。n n粗粗糙糙集集在在机机器器学学习习(x

3、ux)(xux)、决决策策支支持持系系统统、机机器器发发现现、归归纳纳推推理理、数数据据库库中中的的知知识识发发现现、模模式式识识别等领域都得到了广泛的应用。别等领域都得到了广泛的应用。第3页/共79页第四页，共80页。11.1粗糙集基本概念粗糙集基本概念 n n粗粗糙糙集集应应用用于于数数据据挖挖掘掘领领域域，能能提提高高对对大大型型数数据据库库中中的的不不完完整整(wnzhng)(wnzhng)数数据据进进行行分分析析和和学学习习的的能能力力，具具有广泛的应用前景和实用价值。有广泛的应用前景和实用价值。n n粗粗糙糙集集方方法法仅仅利利用用数数据据本本身身提提供供的的信信息息，无无须须任任

4、何何先先验知识。验知识。第4页/共79页第五页，共80页。n n粗粗糙糙集集是是一一个个强强大大的的数数据据分分析析工工具具，它它能能表表达达和和处处理理不不完完备备信信息息；能能在在保保留留关关键键信信息息的的前前提提(qint)(qint)下下对对数数据据进进行行化化简简并并求求得得知知识识的的最最小小表表达达式式；能能识识别别并并评评估估数数据据之之间间的的依依赖赖关关系系，揭揭示示出出概概念念的的简简单单模式；能从经验数据中获取易于证实的规则知识。模式；能从经验数据中获取易于证实的规则知识。第5页/共79页第六页，共80页。n n粗粗糙糙集集的的研研究究对对象象是是由由一一个个多多值值

5、属属性性(特特征征、症症状状、特特性性等等)集集合合描描述述的的一一个个对对象象(观观察察、病病历历等等)集集合合，对对于于每每个个对对象象及及其其属属性性都都有有一一个个值值作作为为其其描描述述符符号号(fho)(fho)，对对象象、属属性性和和描描述述符符是是表表达达决决策策问问题题的的3 3个个基本要素。基本要素。第6页/共79页第七页，共80页。n n粗粗粗粗糙糙糙糙集集集集理理理理论论论论逐逐逐逐渐渐渐渐应应应应用用用用于于于于数数数数据据据据挖挖挖挖掘掘掘掘领领领领域域域域中中中中，并并并并在在在在对对对对大大大大型型型型数数数数据据据据库库库库中中中中不不不不完完完完整整整整数数

6、数数据据据据进进进进行行行行分分分分析析析析和和和和学学学学习习习习方方方方面面面面取取取取得得得得了了了了显显显显著著著著的的的的成成成成果果果果，使使使使得得得得粗粗粗粗糙糙糙糙集集集集理理理理论论论论及及及及数数数数据据据据挖挖挖挖掘掘掘掘的的的的研研研研究究究究成成成成为为为为热热热热点点点点领领领领域域域域。最最最最近近近近(zujn)(zujn)(zujn)(zujn)几几几几年年年年，粗粗粗粗糙糙糙糙集集集集理理理理论论论论越越越越来来来来越越越越受受受受到到到到众众众众多多多多研研研研究究究究人人人人员的重视，它的应用研究得到了很大的发展。员的重视，它的应用研究得到了很大的发展

7、。员的重视，它的应用研究得到了很大的发展。员的重视，它的应用研究得到了很大的发展。第7页/共79页第八页，共80页。知识知识(zh shi)(zh shi)和知识和知识(zh shi)(zh shi)库库 n n 知识是人类通过实践对客观世界的运动规律的知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有抽象和认识，是人类实践经验的总结和提炼，具有抽象和普遍的特性。普遍的特性。n n 从认知科学的观点来看，知识来源于人类对客从认知科学的观点来看，知识来源于人类对客观事物的分类能力，概念是事物类别观事物的分类能力，概念是事物类别(libi)(libi)的描的描述或者符号

8、，知识则是概念之间的关系和联系。任述或者符号，知识则是概念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用何一个物种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。物种的不同属性知识描述来产生对物种的不同分类。第8页/共79页第九页，共80页。n n集合上的等价关系和集合上的划分是一一对应，相互唯集合上的等价关系和集合上的划分是一一对应，相互唯集合上的等价关系和集合上的划分是一一对应，相互唯集合上的等价关系和集合上的划分是一一对应，相互唯一决定的。从数学意义上讲，集合上的等价关系和集合一决定的。从数学意义上讲，集合上的等价关系和集合一决定的。从数

9、学意义上讲，集合上的等价关系和集合一决定的。从数学意义上讲，集合上的等价关系和集合的划分是等价的概念，即划分就是的划分是等价的概念，即划分就是的划分是等价的概念，即划分就是的划分是等价的概念，即划分就是(jish)(jish)(jish)(jish)分类。分类。分类。分类。第9页/共79页第十页，共80页。n n定义定义11-1 11-1 设讨论的对象组成的有限集合，称为设讨论的对象组成的有限集合，称为论域论域(Universe)(Universe)，对于论域中由等价关系划分出，对于论域中由等价关系划分出来的任意子集，都可以称为论域来的任意子集，都可以称为论域U U中的一个概念中的一个概念(c

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

11、念等同)，它是一种属性或多种属性，它是一种属性或多种属性的集合。可以根据不同的的集合。可以根据不同的R R对对U U进行不同形式的分进行不同形式的分类。知识库也被称作近似空间。类。知识库也被称作近似空间。第10页/共79页第十一页，共80页。n n定义定义11-3 K=(U,P)11-3 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是同样的基本范畴是同样的基本范畴集时，知识库集时，

12、知识库K K和和M M中的知识都能使我们确切地表达关中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着可以用不于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全同的属性集对对象进行描述，以表达关于论域的完全相同的事实。相同的事实。n n对于两个知识库对于两个知识库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为为

13、P P的推广。由的推广。由以上可知，推广是将某些范畴组合在一起，而特化则以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割是将范畴分割(fng)(fng)成更小的单元。成更小的单元。第11页/共79页第十二页，共80页。不可不可(bk)(bk)分辨关系分辨关系 n n在粗糙集理论中，在粗糙集理论中，“知识知识”被认为是一种分类的能力。被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它揭示出不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。假定关于论域的某种知识，论域知识的颗粒状结构。假定关于论域的某种知识，并使用属性并使用属性(shxng)(shxng)

14、和属性和属性(shxng)(shxng)值来描述论域值来描述论域中的对象，如果两个对象中的对象，如果两个对象(或对象集合或对象集合)具有相同的属具有相同的属性性(shxng)(shxng)和属性和属性(shxng)(shxng)值，则它们之间具有不值，则它们之间具有不可分辨关系。可分辨关系。第12页/共79页第十三页，共80页。n n定义定义11-411-4设设R R是非空集合是非空集合U U上的二元系，如果它是自上的二元系，如果它是自反的、对称的和可传递的，则称反的、对称的和可传递的，则称R R为为U U上的等价关系。上的等价关系。若，若，则称则称x x与与y y有关系，记为有关系，记为 ；

15、若；若 ，则称，则称x x与与y y没有关系，记为没有关系，记为 。等价关系的一个。等价关系的一个重要特点是用它可以构成重要特点是用它可以构成U U的一个划分。划分即是分的一个划分。划分即是分类类(fn li)(fn li)，将研究对象分成不同的类，这些类之，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。间互不相交，且每一对象均包含在某一类中。第13页/共79页第十四页，共80页。n n定义定义11-511-5设设U U是一个论域，是一个论域，R R是是U U上的等价关系，上的等价关系，U/RU/R表示表示U U上由上由R R导出的所有等价类。导出的所有等价类。n n

16、 表示包含元素表示包含元素xUxU的的R R等价类。一个知识库就是一等价类。一个知识库就是一个关系系统个关系系统K=U,PK=U,P，其中，其中(qzhng)U(qzhng)U是论域，是论域，P P是是U U上的一个等价类簇。如果上的一个等价类簇。如果 且且 ，则，则 (Q(Q的所有等价类的交也是一个等价关系的所有等价类的交也是一个等价关系)，称，称Q Q为不可为不可分辨关系分辨关系,记作记作IND(Q)IND(Q)。第14页/共79页第十五页，共80页。上、下近似上、下近似(jn s)(jn s)集集 n n给定论域给定论域U U，一族等价关系，一族等价关系R R将将U U划分为互不相交的划

17、分为互不相交的基本等价类基本等价类U/RU/R。令。令 XgU XgU为为R R上的一个等价关系。上的一个等价关系。n n当能表达成某些基本等价类的并集时，称为可定当能表达成某些基本等价类的并集时，称为可定义的；否则义的；否则(fuz)(fuz)称为不可定义的。称为不可定义的。R R可定义集可定义集能在这个知识库中被精确地定义，所以又称为能在这个知识库中被精确地定义，所以又称为R R精精确集。确集。n nR R不可定义集不能在这个知识库中被精确定义，只不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为能通过集合逼近的方式来刻画，因此也称为R R粗糙粗糙集集(Rou

18、ghset)(Roughset)。第15页/共79页第十六页，共80页。n n两个精确集，两个精确集，n n即粗糙集的上近似集即粗糙集的上近似集(UpperApproximation)(UpperApproximation)和下近和下近似集似集(LowerApproximation)(LowerApproximation)来近似地定义粗糙集。来近似地定义粗糙集。n n粗糙集理论粗糙集理论(lln)(lln)引入上近似和下近似等概念来刻引入上近似和下近似等概念来刻画知识的不确定性和模糊性。画知识的不确定性和模糊性。第16页/共79页第十七页，共80页。n n定义定义11-611-6设集合设集合(

19、jh)(jh)，R R是一个等价关系，称是一个等价关系，称 n n 为集合为集合(jh)X(jh)X的的R R下近似集；下近似集；n n称称 为集合为集合(jh)X(jh)X的的R R上近似集；上近似集；n n称集合称集合(jh)(jh)为为X X的的R R边界域；边界域；n n称称 为为X X的的R R正域；正域；n n称称 为为X X的的R R负域。负域。第17页/共79页第十八页，共80页。n n例例例例11-1 11-1 11-1 11-1 设论域设论域设论域设论域 ，U U U U上的一族等价关系上的一族等价关系上的一族等价关系上的一族等价关系R=R1,R2,R1R=R1,R2,R1

20、R=R1,R2,R1R=R1,R2,R1和和和和R2R2R2R2是两个等价关系。根据这两个等价关系可是两个等价关系。根据这两个等价关系可是两个等价关系。根据这两个等价关系可是两个等价关系。根据这两个等价关系可以将论域以将论域以将论域以将论域U U U U进行划分：进行划分：进行划分：进行划分：n n 和和和和 。U/R1U/R1U/R1U/R1中的中的中的中的 ，代表，代表，代表，代表 的等价类。的等价类。的等价类。的等价类。n n论域论域论域论域U U U U被被被被R R R R划分的基本等价类为划分的基本等价类为划分的基本等价类为划分的基本等价类为:n n集合集合集合集合 是是是是U U

21、 U U上的一个子集。则上的一个子集。则上的一个子集。则上的一个子集。则X X X X无法用基本等价无法用基本等价无法用基本等价无法用基本等价类类类类U/RU/RU/RU/R的并集精确的并集精确的并集精确的并集精确(jngqu)(jngqu)(jngqu)(jngqu)表示，所以表示，所以表示，所以表示，所以X X X X是是是是U U U U上的一个粗糙集上的一个粗糙集上的一个粗糙集上的一个粗糙集合。故有合。故有合。故有合。故有:n nX X X X的下近似集为的下近似集为的下近似集为的下近似集为:；n nX X X X的上近似集为的上近似集为的上近似集为的上近似集为:；n nX X X X

22、的负区域的负区域的负区域的负区域:。第18页/共79页第十九页，共80页。11.2知识知识(zh shi)表达表达 n n知识表达在智能数据处理中占有十分重要的地位。在知识表达在智能数据处理中占有十分重要的地位。在智能系统中，经常会碰到要处理的对象可能是用语言智能系统中，经常会碰到要处理的对象可能是用语言方式表达，也可能使用数据表达；可能是精确的数据，方式表达，也可能使用数据表达；可能是精确的数据，可能会有一些缺省的信息或者可能会有一些缺省的信息或者(huzh)(huzh)相互矛盾的信相互矛盾的信息。息。n n为了处理这些数据，我们需要进行知识的表达，即知为了处理这些数据，我们需要进行知识的表

23、达，即知识表达系统。决策表是特殊的知识表达系统。识表达系统。决策表是特殊的知识表达系统。第19页/共79页第二十页，共80页。知识知识(zh shi)(zh shi)表达系统表达系统 n n定义定义11-711-7一个知识表达系统一个知识表达系统S S可以定义为，其中可以定义为，其中U U为对象的集合，称为论域；为对象的集合，称为论域；=R=R为属性集合；子集为属性集合；子集C C和和D D分别称为条件分别称为条件(tiojin)(tiojin)属性和决策属性；属性和决策属性；为属性值的集合；表示了属性的属性值范围；是为属性值的集合；表示了属性的属性值范围；是一个信息函数，它指定了一个信息函数

24、，它指定了U U中每一对象中每一对象x x的属性值。的属性值。n n知识表达系统的数据以关系表的形式表示，关系知识表达系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。对象的信息是通过指定对象的各属性值来表达。第20页/共79页第二十一页，共80页。n n例例11-211-2：表：表11.111.1是一个轿车信息决策表，条件属性集是一个轿车信息决策表，条件属性集为为e1,e2,e3,e4e1,e2,e3,e4分别代表价格、油耗、速度分别代表价格、油耗、速度(sd)(sd)和安全性，决策

25、属性为和安全性，决策属性为d d，表示质量。，表示质量。第21页/共79页第二十二页，共80页。n n 表11.1 轿车(jioch)信息决策表车型车型U Ue1e1e2e2e3e3e4e4d d1 1高低快好高2 2低高中差低3 3中中慢一般低4 4中高慢一般中5 5低高中差低6高低快好高第22页/共79页第二十三页，共80页。决策表决策表 n n决决决决策策策策表表表表包包包包含含含含了了了了某某某某一一一一领领领领域域域域的的的的大大大大量量量量数数数数据据据据，是是是是领领领领域域域域的的的的样样样样本本本本数数数数据据据据库库库库。它它它它记记记记录录录录了了了了大大大大量量量量样样

26、样样本本本本的的的的属属属属性性性性值值值值和和和和决决决决策策策策情情情情况况况况，是是是是领领领领域域域域知知知知识的载体。识的载体。识的载体。识的载体。n n知知知知识识识识获获获获取取取取的的的的目目目目的的的的就就就就是是是是要要要要通通通通过过过过分分分分析析析析这这这这个个个个实实实实例例例例库库库库来来来来得得得得到到到到该该该该领领领领域域域域中中中中有有有有用用用用的的的的、规规规规律律律律性性性性知知知知识识识识。决决决决策策策策表表表表在在在在决决决决策策策策应应应应用用用用中中中中有有有有十十十十分分分分重重重重要要要要的的的的地地地地位位位位，可可可可用用用用于于于

27、于表表表表达达达达绝绝绝绝大大大大多多多多数数数数决决决决策策策策问问问问题题题题。对对对对于于于于决决决决策策策策表，最重要的是决策规则表，最重要的是决策规则表，最重要的是决策规则表，最重要的是决策规则(guz)(guz)(guz)(guz)的生成。的生成。的生成。的生成。第23页/共79页第二十四页，共80页。n n定义定义(dngy)11-8(dngy)11-8 设设U=U1U=U1，U2U2，U3U3，Un Un 是一个论域是一个论域,U(i=1,2,U(i=1,2,，n)n)是研究对象。是研究对象。P P是属性集是属性集,P=C+D,C,P=C+D,C 为条件属性集为条件属性集,D,

28、D 为为决策属性集决策属性集,T=(U,P,C,D),T=(U,P,C,D)是决策表。是决策表。决策表中每一行就是一条决策规则决策表中每一行就是一条决策规则:dx|C-dx:dx|C-dx|D,dx|B|D,dx|B 表示个体表示个体x x关于属性集关于属性集B B 的值。的值。第24页/共79页第二十五页，共80页。n n定义定义11-9 11-9 若决策表若决策表T T 中任意的中任意的dxdy,dxdy,由由dx|C=dx|C=dy|C,dy|C,可得可得dx|D=dy|D,dx|D=dy|D,则称决策规则则称决策规则dx dx 是一是一致的致的,否则否则,称决策规则称决策规则dx dx

29、 是不一致的。如果是不一致的。如果T T 中每中每条决策规则都是一致的条决策规则都是一致的,则称决策表则称决策表T T 是一致的是一致的,否则否则称决策表称决策表T T是不一致的。是不一致的。n n定义定义11-10 11-10 设设T=(U,P,C,D)T=(U,P,C,D)是决策表是决策表,如如果去掉条件属性果去掉条件属性PiPi，得到的表，得到的表T1=(U,P-Pi,T1=(U,P-Pi,C-Pi,D)C-Pi,D)与表与表T T 相比相比,有有PosC(D)=Pos(PosC(D)=Pos(D)D)，则称属性，则称属性PiPi是关于是关于(guny)D(guny)D可省的可省的,否则

30、称属性否则称属性Pi Pi 是关于是关于(guny)D(guny)D 不可省的不可省的,是是D D 关于关于(guny)B(guny)B 的正区域，其中的正区域，其中 。第25页/共79页第二十六页，共80页。n n定义定义11-11 11-11 如果决策表中每个条件属性都是关如果决策表中每个条件属性都是关于于D D 不可省的不可省的,则称条件属性集则称条件属性集C C 是关于是关于D D独立的，独立的，否则称否则称C C 是关于是关于D D 依赖的。依赖的。n n定义定义11-12 11-12 决策表决策表T=(U,P,C,D)T=(U,P,C,D)中条中条件属性集件属性集C C 的一个的一

31、个(y)(y)子集子集B B 是关于是关于D D 独立的独立的,并且并且PosB(D)=PosC(D),PosB(D)=PosC(D),则称则称B B 是是C C 的一个的一个(y)D(y)D约简。约简。第26页/共79页第二十七页，共80页。属性约简属性约简(yu jin)(yu jin)、核集的求取、核集的求取 n n所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。n n一个属性集合可能有多个约简。n n属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有(suyu)条件属性所形成的相对于决策属

32、性的分类一致，即和所有(suyu)条件属性相对于决策属性D有相同的分类能力。第27页/共79页第二十八页，共80页。n n属性集合P的所有约简(yu jin)的交集定义为P的核(Core)，记作core(P)，核是表达知识必不可少的重要属性集。第28页/共79页第二十九页，共80页。n n核的概念具有两方面的意义:n n(l)因为核包含于所有约简之中，所以核可以作为所有约简的计算基础。n n(2)核在知识约简中是不能消去的特征集合。n n直接由分辨矩阵来求取系统的核集Pc。不失一般性,假定系统T 对于(duy)属性集P 是可分辨的。则系统的核集由以下定理1确定。第29页/共79页第三十页，共8

33、0页。n n定定理理11-111-1P P 中中任任一一属属性性P P Pc,Pc,充充要要条条件件为为:D(P):D(P)中中至至少少存存在在一一个个元元素素 ,满满足足 。其其中中，元元素素都都是是属属性性集集P P的的一一个个子子集集，元元素素DijDij定义定义(dngy)(dngy)如下：如下：n n 其其中中i,j=1,2,3,i,j=1,2,3,，m m。（1 1）n n （2 2）第30页/共79页第三十一页，共80页。n n命题命题命题命题11-111-111-111-1从信息系统的决策表中将属性集从信息系统的决策表中将属性集从信息系统的决策表中将属性集从信息系统的决策表中将

34、属性集P P P P中逐一移中逐一移中逐一移中逐一移去去去去,每移去一个属性即刻检查每移去一个属性即刻检查每移去一个属性即刻检查每移去一个属性即刻检查(jinch)(jinch)(jinch)(jinch)其决策表其决策表其决策表其决策表,如如如如果不出现新的不一致果不出现新的不一致果不出现新的不一致果不出现新的不一致,则属性是可被约去的；否则属性则属性是可被约去的；否则属性则属性是可被约去的；否则属性则属性是可被约去的；否则属性不能约去。不能约去。不能约去。不能约去。n n命题命题命题命题11-211-211-211-2 全体不可约去属性集称为核集。全体不可约去属性集称为核集。全体不可约去属

35、性集称为核集。全体不可约去属性集称为核集。n n属性集合的约简和核的关系如下属性集合的约简和核的关系如下属性集合的约简和核的关系如下属性集合的约简和核的关系如下:n n式中式中式中式中red(P)red(P)red(P)red(P)表示表示表示表示P P P P的所有约简。的所有约简。的所有约简。的所有约简。core(P)core(P)core(P)core(P)含有含有含有含有P P P P的全部约的全部约的全部约的全部约简中共同的等价关系，是属性集合简中共同的等价关系，是属性集合简中共同的等价关系，是属性集合简中共同的等价关系，是属性集合P P P P中不可缺少的重要中不可缺少的重要中不可

36、缺少的重要中不可缺少的重要属性集。属性集。属性集。属性集。第31页/共79页第三十二页，共80页。属性属性(shxng)(shxng)值约简值约简 n n属性约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类(fn li)产生的影响也不同。n n例如，判断人的体形(瘦、中、胖)时，体重是主要属性。但若体重属性值为75Kg时，此人的体形要结合其身高、性别等属性才能确定。如果体重属性值为160Kg时，几乎肯定其体形为胖，这时身高、性别已不重要。第32页/共79页第三十三页，共80页。n n命题11-3设 是决策表上的一

37、条决策规则,n n 属性值v 是一可被约去当且仅当 ,其中(qzhng)和 均为决策表上的逻辑公式8。第33页/共79页第三十四页，共80页。决策决策(juc)(juc)规则规则6 6 n n决策表包含了某一领域的大量数据，是领域的样本数据决策表包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，是领域知库。它记录了大量样本的属性值和决策情况，是领域知识的载体识的载体(zit)(zit)。n n知识获取的目的就是要通过分析这个实例库来得到该领知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。域中有用的、规律性知识。n n从决策表分析得到的规律

38、性知识，通常采用决策规则的从决策表分析得到的规律性知识，通常采用决策规则的形式记录下来。下面给出决策规则的形式化描述。形式记录下来。下面给出决策规则的形式化描述。第34页/共79页第三十五页，共80页。n n定义定义11-1311-13定义公式如下：定义公式如下：n n(1)(a,v)(1)(a,v)(或写为或写为avav，aAaA，vVavVa，表示属性，表示属性a a的的取值为取值为v)v)是公式且是原子公式。是公式且是原子公式。n n(2)(2)如果如果A A和和B B都是公式，那么都是公式，那么(n me)(n me),AB,AB都是公式。都是公式。n n(3)(3)只有按定义只有按定

39、义(1)(1)和和(2)(2)所组成的式子是公式。所组成的式子是公式。n n对于决策表对于决策表 是决策表，是决策表，A=CDA=CD属性属性集合，子集集合，子集 和和 分别为条件分别为条件属性集和决策属性集，有关决策规则的定义如下：属性集和决策属性集，有关决策规则的定义如下：第35页/共79页第三十六页，共80页。n n定义定义定义定义11-1411-1411-1411-14公式公式公式公式(gngsh)(gngsh)(gngsh)(gngsh)称为称为称为称为P P P P基本公式基本公式基本公式基本公式(gngsh)(gngsh)(gngsh)(gngsh)，这里，这里，这里，这里 ，P

40、 P P P，。n n定义定义定义定义11-151111-151111-151111-1511公式公式公式公式(gngsh)(gngsh)(gngsh)(gngsh)称为称为称为称为Q Q Q Q基本公式基本公式基本公式基本公式(gngsh)(gngsh)(gngsh)(gngsh)，这里，这里，这里，这里 ，。n n定义定义定义定义11-161111-161111-161111-1611公式公式公式公式(gngsh)AB(gngsh)AB(gngsh)AB(gngsh)AB为决策规则，如果为决策规则，如果为决策规则，如果为决策规则，如果A A A A是是是是P P P P基本基本基本基本公式

41、公式公式公式(gngsh)(gngsh)(gngsh)(gngsh)且且且且B B B B是是是是Q Q Q Q基本公式基本公式基本公式基本公式(gngsh)(gngsh)(gngsh)(gngsh)，则，则，则，则ABABABAB是基本决策规是基本决策规是基本决策规是基本决策规则。则。则。则。第36页/共79页第三十七页，共80页。基于基于(jy)(jy)可辨识矩阵属性约简算法可辨识矩阵属性约简算法6 6 n n可辨识矩阵（也称分明矩阵）是由波兰数学家可辨识矩阵（也称分明矩阵）是由波兰数学家Skowron.ASkowron.A教授提出的。教授提出的。n n定义定义11-1711-17设相容决

42、策设相容决策(juc)(juc)表表T=T=，A=CDA=CD，n n 和和D=dD=d分别为条件属性集和决策分别为条件属性集和决策(juc)(juc)属性集，属性集，是论域，是论域，是样是样本本 在属性上的取值。在属性上的取值。表示可辨识矩阵中第表示可辨识矩阵中第i i行行j j列的对象，则可辨识矩阵定义为：列的对象，则可辨识矩阵定义为：n n其中，其中，第37页/共79页第三十八页，共80页。n n由上述(shngsh)定义可以看出，可辨识矩阵是一个对称矩阵。当两个样本的决策属性取同时，对象值为0；当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同

43、的条件属性集合。n n一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，所有的蕴含式包含的属性就是决策表的所有约简集合。第38页/共79页第三十九页，共80页。n n算法算法算法算法11-111-111-111-1可辨识矩阵属性约简算法可辨识矩阵属性约简算法可辨识矩阵属性约简算法可辨识矩阵属性约简算法 n n输入：相容决策表输入：相容决策表输入：相容决策表输入：相容决策表DT=DT=DT=DT=，A=CDA=CDA=CDA=CD是属性集合；是属性集合；是属性集合；是属性集合；n n输出：约简的属性集。输出：约简的属性集。输出：约简的属性集。输出：约简的属性集。n

44、n步骤：步骤：步骤：步骤：n nStep1Step1Step1Step1计算决策表的可辨识矩阵计算决策表的可辨识矩阵计算决策表的可辨识矩阵计算决策表的可辨识矩阵 ；/根据分辨矩阵的定根据分辨矩阵的定根据分辨矩阵的定根据分辨矩阵的定义求元素义求元素义求元素义求元素n nStep 2Step 2Step 2Step 2对于可辨识矩阵中所有取值为非空集合的对象对于可辨识矩阵中所有取值为非空集合的对象对于可辨识矩阵中所有取值为非空集合的对象对于可辨识矩阵中所有取值为非空集合的对象 ，建立，建立，建立，建立(jinl)(jinl)(jinl)(jinl)相应的析取逻辑表达式相应的析取逻辑表达式相应的析取

45、逻辑表达式相应的析取逻辑表达式,n n ,；第39页/共79页第四十页，共80页。n nStep 3Step 3将所有的析取逻辑表达式将所有的析取逻辑表达式 进行合取运算，得一个合进行合取运算，得一个合取范式取范式T T，即，即 n n ；n nStep 4Step 4将合取范式将合取范式L L转换为析取范式的形式，得转换为析取范式的形式，得 ；n nStep 5Step 5输出属性约简结果。输出属性约简结果。n n基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演有可能的属性

46、约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式变成为逻辑公式(gngsh)(gngsh)的简化的简化 第40页/共79页第四十一页，共80页。信息熵的属性信息熵的属性(shxng)(shxng)约简约简 n n信息熵是信息论的核心内容，它最早应用于通信领域。信息熵是信息论的核心内容，它最早应用于通信领域。由于信息熵可以刻画信息划分由于信息熵可以刻画信息划分(hu fn)(hu fn)粒度的大小，粒度的大小，也被广泛应用于信息不确定性的度量。也被广泛应用于信息不确定性的度量。n n设设U U为一个论域为一个论域,可以认为可以认为U U上任一属性集合上任一属性集合(知识、等价知识、等价

47、关系簇关系簇)是定义在是定义在U U上的子集组成的上的子集组成的R R代数上的一个随机代数上的一个随机变量变量,其概率分布可通过如下方法来确定。其概率分布可通过如下方法来确定。第41页/共79页第四十二页，共80页。n n定义定义定义定义11-1811-1811-1811-18设设设设P,QP,QP,QP,Q在在在在U U U U上导出的划分分别为上导出的划分分别为上导出的划分分别为上导出的划分分别为X,YX,YX,YX,Yn nn nn n则则则则P,QP,QP,QP,Q在在在在U U U U的子集组成的子集组成的子集组成的子集组成(z chn)(z chn)(z chn)(z chn)的代

48、数上的概率分布为的代数上的概率分布为的代数上的概率分布为的代数上的概率分布为第42页/共79页第四十三页，共80页。其中，；定义(dngy)11-19知识P的熵H(P)定义(dngy)为 。第43页/共79页第四十四页，共80页。n n定义定义定义定义11-2011-2011-2011-20决策信息系统决策信息系统决策信息系统决策信息系统S=(U,A=CD,V,F),CS=(U,A=CD,V,F),CS=(U,A=CD,V,F),CS=(U,A=CD,V,F),C、D D D D为为为为U U U U上的一上的一上的一上的一个等价关系集合，个等价关系集合，个等价关系集合，个等价关系集合，C C

49、 C C、D D D D在在在在U U U U上导出的划分分别上导出的划分分别上导出的划分分别上导出的划分分别(fnbi)(fnbi)(fnbi)(fnbi)为为为为:n n则则则则D D D D相对于相对于相对于相对于C C C C的条件信息熵的条件信息熵的条件信息熵的条件信息熵H(D|C)H(D|C)H(D|C)H(D|C)为：为：为：为：n n其中，其中，其中，其中，第44页/共79页第四十五页，共80页。n n定理定理定理定理11-211-211-211-2在信息系统在信息系统在信息系统在信息系统S=(U,A=CD,V,F)S=(U,A=CD,V,F)S=(U,A=CD,V,F)S=(

50、U,A=CD,V,F)中，中，中，中，若，若，若，若H(D|B)=H(D|(B-b)H(D|B)=H(D|(B-b)H(D|B)=H(D|(B-b)H(D|B)=H(D|(B-b)则称则称则称则称b b b b为为为为B B B B中相对于中相对于中相对于中相对于D D D D是可省的是可省的是可省的是可省的（不必要（不必要（不必要（不必要(byo)(byo)(byo)(byo)的）；否则的）；否则的）；否则的）；否则b b b b为为为为B B B B中相对于中相对于中相对于中相对于D D D D是不可省的。是不可省的。是不可省的。是不可省的。对对对对 ,若其任一元素若其任一元素若其任一元素