AI_05_16粗糙集理论人工智能课程浙江大学研究生2453.pptx

《AI_05_16粗糙集理论人工智能课程浙江大学研究生2453.pptx》由会员分享，可在线阅读，更多相关《AI_05_16粗糙集理论人工智能课程浙江大学研究生2453.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、粗糙集理论及其应用RoughSetTheoryanditsApplications徐从富徐从富浙江大学人工智能研究所浙江大学人工智能研究所20022002年年1111月月8 8日第一稿日第一稿20052005年年9 9月修改补充月修改补充研究生人工智能课件研究生人工智能课件目录：目录：Roughset快速入门方法快速入门方法Roughset发展概述发展概述Roughset理论理论课后习题课后习题课后研读论文课后研读论文Roughset快速入门方法快速入门方法认真研读认真研读RoughSetTheory的创始人、波兰数的创始人、波兰数学家学家Z.Pawlak于于1982年发表的第一篇论文年发表的

2、第一篇论文“RoughSets”。最好是直接阅读英文论文原最好是直接阅读英文论文原文。文。研读中科院自动化所的王珏等人于研读中科院自动化所的王珏等人于1996年在年在模式识别与人工智能上发表介绍粗糙集模式识别与人工智能上发表介绍粗糙集理论及其应用的综述性文章。理论及其应用的综述性文章。结合中科院计算所史忠植教授编著的高级结合中科院计算所史忠植教授编著的高级人工智能、知识发现等教材中的讨论人工智能、知识发现等教材中的讨论粗糙集的章节。粗糙集的章节。Roughset快速入门方法（续）快速入门方法（续）认真研读如下认真研读如下3篇典型的论文：篇典型的论文：1Pawlak,Z.,et al.Rough

3、setapproachtomulti-attributedecision analysis.European Journal of Operational Research,72:443-459,19942Grzymala-Busse,D.M.,et al.TheUsefulnessofamachine learning approach to knowledge acquisition.Computational Intelligence.11(2):268-279,19953Jelonek,J.,et al.Roughsetreductionofattributesand their do

4、mains for neural networks.Computational Intelligence,11(2):339-347,1995结合本课件作者于结合本课件作者于20002000年整理的举例说明年整理的举例说明粗糙集理论的有关概念及公式粗糙集理论的有关概念及公式 一、粗糙集理论的发展概述一、粗糙集理论的发展概述1.1粗糙集理论概况粗糙集理论概况自然界中大部分事物所呈现的信息都是：自然界中大部分事物所呈现的信息都是：不完整的、不确定的、模糊的和含糊的不完整的、不确定的、模糊的和含糊的经典逻辑无法准确、圆满地描述和解决经典逻辑无法准确、圆满地描述和解决1904年，谓词逻辑创始人年，谓词

5、逻辑创始人G.Frege提出：提出：“含糊含糊”（Vague）将含糊性归结到将含糊性归结到“边边界线区域界线区域”(Boundary region)上，即在全域上存上，即在全域上存在一些个体，它既不能被分类到某一个子集上，在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上。也不能被分类到该子集的补集上。1965年，美国数学家年，美国数学家L.A.Zadeh提出了提出了“模模糊集糊集”（Fuzzysets），），许多计算机科学家和逻辑许多计算机科学家和逻辑学家试图通过这一理论解决学家试图通过这一理论解决G.Frege提出的提出的“含糊含糊”问题，但模糊集没有给出数学公式描述这

6、一含问题，但模糊集没有给出数学公式描述这一含糊概念，无法计算出它的具体的含糊元素数目。糊概念，无法计算出它的具体的含糊元素数目。1982年，波兰数学家年，波兰数学家Z.Pawlak针对针对G.Frege的的“边界线区域边界线区域”思想，提出了思想，提出了“粗糙集粗糙集”（Rough Sets）。Pawlak把那些无法确认的个把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定体都归属于边界线区域，而这种边界线区域被定义为：义为：“上近似集上近似集”与与“下近似集下近似集”的差集的差集。由。由于它有确定的数学公式描述，故含糊元素的数目于它有确定的数学公式描述，故含糊元素的数目是可以计算的

7、，即是可以计算的，即在在“真真”、“假假”二值之间的二值之间的“含糊度含糊度”是可以计算的是可以计算的。粗糙集理论自诞生以来，经过许多数学家和计粗糙集理论自诞生以来，经过许多数学家和计算机科学家的努力，其理论上日趋成熟，特别是算机科学家的努力，其理论上日趋成熟，特别是在在20世纪世纪80年代末和年代末和90年代初，由于粗糙集理论年代初，由于粗糙集理论在数据挖掘、知识发现等领域得到了成功的应用，在数据挖掘、知识发现等领域得到了成功的应用，它受到了国际上的广泛关注。它受到了国际上的广泛关注。相对于其它处理不确定和模糊性的理论工具相对于其它处理不确定和模糊性的理论工具（如模糊集理论、（如模糊集理论、

8、Dempster-Shafer证据理论等）证据理论等）而言，而言，粗糙集理论有许多不可替代的优越性粗糙集理论有许多不可替代的优越性。目。目前，它在信息科学、医药科学、工程技术、金融前，它在信息科学、医药科学、工程技术、金融商业、环境科学、社会科学等领域中得到了广泛商业、环境科学、社会科学等领域中得到了广泛的、较为成功的应用，并且越来越受到其它更多的、较为成功的应用，并且越来越受到其它更多领域的重视。领域的重视。在计算机科学（特别是人工智能）领域，粗在计算机科学（特别是人工智能）领域，粗糙集理论在专家系统、决策支持系统、机器学习、糙集理论在专家系统、决策支持系统、机器学习、机器发现、归纳推理、模

9、式识别、决策表等方面机器发现、归纳推理、模式识别、决策表等方面都有非常成功的应用实例。其中，在都有非常成功的应用实例。其中，在AI中的应用中的应用可分为两大类：可分为两大类：有决策的分析有决策的分析和和无决策的分析无决策的分析。（1）有决策的分析，主要包括：）有决策的分析，主要包括：监督学习监督学习与与决策决策分析分析；（；（2）对无决策的分析，主要是）对无决策的分析，主要是数据压缩、数据压缩、化简、聚类、模式发现、机器发现化简、聚类、模式发现、机器发现等。等。Jelonek等人成功地应用粗糙集理论对神经网等人成功地应用粗糙集理论对神经网络的输入属性及属性域进行约简络的输入属性及属性域进行约简

10、。用粗糙集理论用粗糙集理论获取知识和进行机器学习的有代表性的应用实例获取知识和进行机器学习的有代表性的应用实例是，是，Kansas大学开发的大学开发的“基于粗糙集方法的学习基于粗糙集方法的学习系统系统”（LERS）。）。这个系统的规则发现能力能帮这个系统的规则发现能力能帮助那些用不完全知识进行工作的专家系统建立知助那些用不完全知识进行工作的专家系统建立知识库识库。粗糙集理论认为，粗糙集理论认为，“概念概念”就是对象的集合，就是对象的集合，“知识知识”就是将对象进行分类的能力就是将对象进行分类的能力。将概念看将概念看成是成是“对象的集合对象的集合”的思想，实质上是一种强调的思想，实质上是一种强调

11、概念的概念的“外延外延”的表达方式。假设我们对全域中的表达方式。假设我们对全域中的对象具有必要的的对象具有必要的“信息信息”或或“知识知识”，这些，这些“知识知识”可以被认为是关于对象的内涵（如属性、可以被认为是关于对象的内涵（如属性、特征或描述）的某种刻划特征或描述）的某种刻划。通过这些知识就能够。通过这些知识就能够将全域中的所有对象划分到不同的类别中。将全域中的所有对象划分到不同的类别中。如果存在两个对象具有相同的信息，即下面如果存在两个对象具有相同的信息，即下面将要论述的将要论述的“不可区分关系不可区分关系”，则根据这些已知，则根据这些已知的信息无法将它们区分开来，显然这是一种等价的信息

12、无法将它们区分开来，显然这是一种等价关系。这样的等价关系可以认为是对概念的内涵关系。这样的等价关系可以认为是对概念的内涵的描述。不可区分关系是粗糙集理论中最基本的的描述。不可区分关系是粗糙集理论中最基本的概念之一，在此基础上引入成员关系、上近似、概念之一，在此基础上引入成员关系、上近似、下近似、分类质量等来刻划知识的处理方法。下近似、分类质量等来刻划知识的处理方法。粗糙集理论在知识发现中的粗糙集理论在知识发现中的主要应用主要应用：数据之间（精确或近似）依赖关系发现数据之间（精确或近似）依赖关系发现评价某一分类（属性）的重要性。评价某一分类（属性）的重要性。数据模式发现。数据模式发现。决策规则发

13、现。决策规则发现。剔除冗余属性。剔除冗余属性。数据集的降维数据集的降维.粗糙集理论的粗糙集理论的局限性局限性主要有：主要有：（1）缺乏处理不精确或不确定原始数据的机）缺乏处理不精确或不确定原始数据的机制。制。（2）对含糊概念的刻划过于简单。）对含糊概念的刻划过于简单。（3）粗糙集理论不是万能的，它不可能解决）粗糙集理论不是万能的，它不可能解决一切含糊的、模糊的不确定性问题。一切含糊的、模糊的不确定性问题。（4）需要其它方法的补充。需要其它方法的补充。一般地，将粗糙集理论与模糊集理论、一般地，将粗糙集理论与模糊集理论、Dempster-Shafer证据理论等其它相关的不确定性证据理论等其它相关的

14、不确定性处理方法构成互补，是一种非常自然而又可行的处理方法构成互补，是一种非常自然而又可行的方法。方法。1.2粗糙集理论的发展简况粗糙集理论的发展简况（1）20世纪世纪70年代，年代，Pawlak和一些波兰科学院、华和一些波兰科学院、华沙大学的逻辑学家，在研究信息系统逻辑特性的基础上，沙大学的逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。提出了粗糙集理论的思想。（2）1982年，年，Pawlak发表了经典论文发表了经典论文“Rough sets”，标志着粗糙集理论的正式诞生。标志着粗糙集理论的正式诞生。（3）在最初的几年里，由于大多数研究论文是用波）在最初的几年里，由于大多

15、数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。仅限于东欧各国。（4）1991年年Pawlak的第一本关于粗糙集理论的专著的第一本关于粗糙集理论的专著“Rough sets:theoretical aspects of reasoning about data”和和1992年年Slowinski主编的主编的“Intelligence decision support:handbook of applications and advances of rough sets theory”的出版，奠定了粗糙集理论的基

16、础，有力地推动了国际粗的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。糙集理论与应用的深入研究。（5）1992年，在波兰召开了第一届国际粗糙集理论年，在波兰召开了第一届国际粗糙集理论研讨会，有研讨会，有15篇论文发表在篇论文发表在1993年第年第18卷的卷的“Foundationofcomputinganddecisionsciences”上。上。（6）1993和和1994年，分别在加拿大、美国召开第二、年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。三届国际粗糙集与知识发现（或软计算）研讨会。（7）1995年，年，Pawlak等人在美国

17、等人在美国ACM通讯上发表通讯上发表“Rough sets”，极大地扩大了该理论的国际影响极大地扩大了该理论的国际影响。（8）19961999年，分别在日本、美国、美国、日年，分别在日本、美国、美国、日本召开了第四七届粗糙集理论国际研讨会。本召开了第四七届粗糙集理论国际研讨会。（9）2000年，在加拿大召开了第二届粗糙集与计算年，在加拿大召开了第二届粗糙集与计算趋势国际会议。趋势国际会议。（10）20012002，中国分别在重庆、苏州召开第一、，中国分别在重庆、苏州召开第一、二届粗糙集与软件学术会议。二届粗糙集与软件学术会议。（11）2003年将在重庆召开粗糙集与软计算国际研讨年将在重庆召开粗

18、糙集与软计算国际研讨会。会。（12）2004年，在瑞典召开年，在瑞典召开RSCTC国际会议（年会）国际会议（年会）（13）2005年，在加拿大召开年，在加拿大召开RSFDGrC国际会议（年会）国际会议（年会）1.3粗糙集理论的研究现状粗糙集理论的研究现状对粗糙集理论的研究主要分为对粗糙集理论的研究主要分为理论理论和和应用应用两个两个部分。部分。（1）在理论研究方面）在理论研究方面，主要集中在如下方面：，主要集中在如下方面：数学性质数学性质：研究其代数与拓扑结构、收敛：研究其代数与拓扑结构、收敛性等。性等。粗糙集拓广粗糙集拓广：广义粗糙集模型、连续属性：广义粗糙集模型、连续属性离散化。离散化。与

19、其它不确定方法的关系和互补与其它不确定方法的关系和互补：与模糊：与模糊集理论、集理论、Dempster-Shafer证据理论的关系和互补。证据理论的关系和互补。多多Agent系统系统(MAS)中的粗糙集中的粗糙集：MAS中基中基于粗糙集理论的推理和规则合成策略。于粗糙集理论的推理和规则合成策略。粒度（粒度（Granules）计算计算：这是一种新的研：这是一种新的研究方向。究方向。有效算法有效算法：导出规则的增量式算法、简约：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进。的启发式算法、并行算法、现有算法的改进。（2）在应用研究方面）在应用研究方面，主要集中研究，主要集中研究粗

20、糙集粗糙集理论在数据挖掘或知识发现过程中的使用方法和理论在数据挖掘或知识发现过程中的使用方法和应用效果。应用效果。1.4粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用（1）在数据准备过程中，在数据进行进一步）在数据准备过程中，在数据进行进一步的分析之前，必须的分析之前，必须对数据进行预处理，粗糙集分对数据进行预处理，粗糙集分析方法可以用于对遗失数据的填补析方法可以用于对遗失数据的填补。（2）在数据准备过程中，利用粗糙集理论的）在数据准备过程中，利用粗糙集理论的数据约简特性，数据约简特性，对数据集进行降维操作对数据集进行降维操作。（3）在数据挖掘阶段，可将粗糙集分析方法）在数据挖掘阶段

21、，可将粗糙集分析方法用于分类规则的发现用于分类规则的发现。（4）在数据挖掘阶段，选择数据挖掘算法时，）在数据挖掘阶段，选择数据挖掘算法时，粗糙集分析方法主要有三个方面：粗糙集分析方法主要有三个方面：通过布尔推理通过布尔推理挖掘出约简和简洁的规则来解挖掘出约简和简洁的规则来解释决策释决策通过熵理论通过熵理论将规则的复杂性和预测的误差分将规则的复杂性和预测的误差分析溶入到无条件的度量中析溶入到无条件的度量中与模糊集理论、证据理论与模糊集理论、证据理论构成复合分析方法构成复合分析方法（5）在数据挖掘阶段，粗糙集分析方法可以）在数据挖掘阶段，粗糙集分析方法可以搜寻隐含在数据中的确定的或非确定的规则搜寻

22、隐含在数据中的确定的或非确定的规则。（6）在解释与评估过程中，粗糙集分析方法）在解释与评估过程中，粗糙集分析方法用于用于对所得到的结果进行统计评估对所得到的结果进行统计评估。二、粗糙集理论二、粗糙集理论2.1概概述述Roughset(以下简称以下简称RS)理论的理论的要点要点是将是将“分类分类”与与“知识知识”联系在一起，而作为一种数学理论，它使用联系在一起，而作为一种数学理论，它使用“等等价关系价关系”来形式化地表示分类，这样，来形式化地表示分类，这样，“知识知识”就可以理就可以理解为：解为：使用等价关系集使用等价关系集R对离散表示的空间对离散表示的空间U进行划分，进行划分，知识就是知识就是

23、R对对U划分的结果划分的结果。由此，在。由此，在U与与R的意义下，的意义下，“知识库知识库”可以定义为：属于可以定义为：属于R中的所有可能的关系对中的所有可能的关系对U的的划分，记为划分，记为K=(U,R)为了描述知识的为了描述知识的“确定程度确定程度”，RS理论引入理论引入“上近似上近似”与与“下近似下近似”的概念，并以这些概念来定义的概念，并以这些概念来定义U中的一个中的一个子集合子集合B与被关系与被关系R划分之后的划分之后的U的相合程度，称为的相合程度，称为“粗糙粗糙度度”。“粗糙集粗糙集”之名由此而来。之名由此而来。RS理论还包含了求取大量数据中最小不变集合（称为理论还包含了求取大量数

24、据中最小不变集合（称为“核核”）与求解最小规则集（称为）与求解最小规则集（称为“约简约简”）的理论，事）的理论，事实上，这就是实上，这就是KDD中所需完成的主要任务。中所需完成的主要任务。RS理论的理论的特点特点是，是，除问题所需的数据集之外，无需任除问题所需的数据集之外，无需任何先验知识（或信息）何先验知识（或信息）。这是。这是RS理论与模糊理论、证据理理论与模糊理论、证据理论的论的最主要的区别最主要的区别，也是其，也是其最重要的优点最重要的优点。证据理论证据理论需要预先设定需要预先设定先验概率分配（先验概率分配（mass函数）函数）模糊集理论模糊集理论需要预先设定需要预先设定隶属度、隶属度

25、函数隶属度、隶属度函数RS理论理论则无需任何先验知识则无需任何先验知识RS理论的理论的基本思想基本思想是：是：利用定义在数据集合利用定义在数据集合U上的等价关系对上的等价关系对U的划分作为的划分作为知识，而对知识不确定程度的测量，则是对被分析数据整知识，而对知识不确定程度的测量，则是对被分析数据整体的处理之后自然获得，这样，体的处理之后自然获得，这样，RS理论无需对知识或数据理论无需对知识或数据的局部给予主观评价，也就是说，的局部给予主观评价，也就是说，RS理论对不确定性的描理论对不确定性的描述相对客观述相对客观。2.2基本概念基本概念2.2.1不分明关系不分明关系设设U为为论论域域，R是是U

26、 U上上的的等等价价(equivalence)关关系系（即即满满足足自自反反、对对称称和和传传递递性性质质），则则A=U，R称称为为近近似似(approximation)空空 间间，R为为不不 分分 明明 关关 系系(indiscernibility，也也称称不不可可区区分分关关系系)。如如果果x，y U，（x，y）R，那那么么x，y在在A中中是是不不分分明明的的（不不可可区区分分的）的）。关关系系R的的等等价价类类(equivalenceclasses)称称为为A上上的的基基本本集集合合（elementaryset）或或原原子子(atom)。A上上所所有有基基本本集集合合（原原子子）用用U/

27、R表表示示。A中中基基本本集集合合的的有有限限次次并并操操作作得得到到的的集集合合称称为为A上上的的组组合合(Composed)集集合合。A中中所所有有组组合合集集合合的的族族用用Com(A)表表示示，显显然然，Com(A)是是一一布布尔尔代代数数，也也就是说，组合集合族在交、并、补集合操作下是封闭的。就是说，组合集合族在交、并、补集合操作下是封闭的。2.2.2信息系统信息系统Pawlak在在1981发发表表的的一一篇篇论论文文中中详详细细论论述述了了信信息息系系统统(informationsystem)的的概概念念。经经不不分分明明关关系系定定义义粗粗糙糙集集，这这是是粗粗糙糙集集研研究究者

28、者的的早早期期研研究究，近近期期已已扩扩展展到到在在一一个个信信息息系系统统中中用用属属性性集集来来定定义义Rough集集。信信息息系系统统形形式式定定义义如如下：下：设信息系统设信息系统S=U,Q,V,f，其中其中U：对象的有限集，对象的有限集，Q：属属性性的的有有限限集集，Q=C D，C是是条条件件属属性性子子集集，D是是决策属性子集决策属性子集,Vp是属性是属性P的域。的域。f:UXAV是总函数，使得是总函数，使得f(xi,q)Vq，对于每个对于每个q A,xi U设设P Q，xi,xj U,定定义义二二元元关关系系IND P 称称为为不不分分明明关系如下：关系如下：称称xi和和xj在在

29、S中中关关于于属属性性集集P是是不不分分明明的的，当当且且仅仅当当p(xi)=p(xj)对对所所有有的的p P成成立立。即即xi和和xj不不能能用用P中中的的属属性性加加以以区区别。别。对对所所有有的的p P，可可以以验验证证IND P 是是一一种种U的的等等价价关关系系。关关系系的的等等价价类类称称为为S中中的的P-基基本本集集，Q-基基本本集集称称为为S的的原原子子。信信息息系系统统S是是可可选选择择的的，当当且且仅仅当当S中中的的所所有有原原子子是是单元素集，即单元素集，即Q是一个同一关系。是一个同一关系。重重要要结结论论：一一个个关关系系数数据据库库可可以以看看作作一一个个信信息息系统

30、，它的列是属性，行是对象。系统，它的列是属性，行是对象。2.2.3集合的上、下近似集合的上、下近似在在信信息息系系统统S=U,Q,V,f中中，设设X U是是个个体体全全域域上上的的子集，子集，P Q则则X的下和上近似集及边界区域分别为：的下和上近似集及边界区域分别为：显显然然，PX是是X U上上必必然然被被分分类类的的那那些些元元素素的的集集合合；而而P*X是是U上上可可能能被被分分类类的的那那些些元元素素的的集集合合。Bnd(X)是是既既不不能能在在X U上上被被分分类类，又又不不能能在在U-X上上被被分分类类的的那那些些元元素素的的集集合合。可可见见PX是是被被包包含含在在X内内的的最最大

31、大可可定定义义集集；P*X是包含是包含X的最小可定义集。的最小可定义集。图图3.1集合的上、下近似概念示意集合的上、下近似概念示意Xfactweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno不可区分关系（等价关系）示例：不可区分关系（等价关系）示例：可知，可知，U=1,2,3,4,5,6R=2 weather,road,time,accident 若若P=weather,road，则则x

32、IND(p)=xINDweather xINProad =1,3,6,2,5,4 1,2,4,3,5,6 =1,2,4,3,6,5 上、下近似关系举例：上、下近似关系举例：X1=u|Flu(u)=yes=u2,u3,u6,u7RX1=u2,u3=u2,u3,u6,u7,u8,u5X2=u|Flu(u)=no=u1,u4,u5,u8RX2=u1,u4 =u1,u4,u5,u8,u7,u6TheindiscernibilityclassesdefinedbyR=Headache,Temp.are:u1,u2,u3,u4,u5,u7,u6,u8.上、下近似集的图示：上、下近似集的图示：R=Heada

33、che,Temp.U/R=u1,u2,u3,u4,u5,u7,u6,X1=u|Flu(u)=yes=u2,u3,u6,u7X2=u|Flu(u)=no=u1,u4,u5,u8RX1=u2,u3=u2,u3,u6,u7,u8,u5RX2=u1,u4 =u1,u4,u5,u8,u7,u6u1u4u3X1X2u5u7u2u6u82.2.4集合集合(族族)的近似精度及分类质量的近似精度及分类质量设设S=U,Q,V,f为为一一信信息息系系统统，且且X U，P Q，则则S上上X的的近似精度近似精度为：为：设设S为为一一信信息息系系统统，P Q，且且令令=X1,X2,Xn是是U的的一一个个分分类类（子子集集

34、族族），其其中中Xi U，则则 的的P-下下近近似似和和P-上近似分别表示为上近似分别表示为分类分类 的的近似精度近似精度为为由属性子集PQ确定的分类的分类质量分类质量为分类质量分类质量表示通过属性子集表示通过属性子集P P正确分类的对象数与信息正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集系统中所有对象数的比值。这是评价属性子集P P的重要的重要性的关键指标之一。性的关键指标之一。一个申请信用卡的训练集：一个申请信用卡的训练集：申请申请人人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(70

35、0)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝 原始属性集原始属性集A=c1,c2,c3,c4A=c1,c2,c3,c4的分类质量：的分类质量：令令R=c2,c4R=c2,c4，重新计算分类质量重新计算分类质量，得，得2.2.

36、5属性约简及属性约简及“核核”属属性性约约简简(AttributeReduction，简简称称AR)是是粗粗糙糙集集理理论论的的一一个个重重要要概概念念。在在一一个个信信息息系系统统S中中，设设 是是S上上的的一一个个分分类类，经经约约简简后后的的最最小小属属性性子子集集具具有有同同原原始始属属性性集集 相相 同同 的的 分分 类类 质质 量量，即即 存存 在在 R P Q，使使 得得 R()=P()，称称 之之 为为属属 性性 集集P的的 -约约 简简，记记 作作REDU(P)。所所 有有 -约约 简简 的的 交交 集集 称称 为为-核核，即即CORE(P)=REDU(P)，核核是是信信息息

37、系系统统中中一一系系列列最最重重要的属性要的属性。在在大大多多数数情情况况下下，分分类类是是由由几几个个甚甚至至一一个个属属性性来来决决定定的的，而而不不是是由由关关系系数数据据库库中中的的所所有有属属性性的的微微小小差差异异来来决决定定。属属性性约约简简及及核核的的概概念念为为人人们们提提取取系系统统中中重重要要属属性性及及其其值值提提供供了了有有力力的的数数学学工工具具，而而且且这这种种约约简简是是本本着着不不破破坏坏原原始始数数据据集集的的分分类类质质量量的的，通通俗俗地地说说，它它是是完完全全“保真保真”的。的。关关于于核核的的计计算算，有有人人提提出出了了差差别别矩矩阵阵（disce

38、rnibilitymatrix，也也译译作作可可辨辨识识矩矩阵阵）。在在信信息息系系统统S=(U,C D,V,f)中中，C为为条条件件属属性性，D为为决决策策属属性性，设设为为对对象象全全集集U按按决决策策属属性性D被被分分成成不不相相交交的的类类族族，即即=X1,X2,Xm，则则S中中C的差别矩阵的差别矩阵M(C)=mi,jnxn定义为定义为其中，其中，1 i j n。差别矩阵与信息系统的核有如下关系：对所有的差别矩阵与信息系统的核有如下关系：对所有的c C,c CORE(C,D)的充要条件是，存在的充要条件是，存在i,j(1 i j n)，使使得得mi,j=c。“含糊含糊”是指分别属于两个

39、不同类的对象是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，具有完全相同的条件属性，在差别矩阵中，xi,xj是含糊是含糊的充要条件是存在的充要条件是存在i,j(1 i j n)，使得使得mi,j=-1。申请申请人人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(

40、800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝 因决策因决策d=d=接受，拒绝接受，拒绝，故上表按决策属性，故上表按决策属性d d可分可分为两个等价类：为两个等价类：x1,x4,x6,x7x1,x4,x6,x7和和 x2,x3,x5,x8x2,x3,x5,x8。根据差别矩阵的计算公式可得：根据差别矩阵的计算公式可得：差别矩阵与差别矩阵与“核核”有如下关系：属性有如下关系：属性c c是条件属性是条件属性C C和决策属性和决策属性D D的的“核核”的的充要

41、条件充要条件是，存在是，存在i,i,j(1ijn)j(1ijn)，使得使得m mij ij=c=c。由上述矩阵可知，存在由上述矩阵可知，存在i=4,j=5i=4,j=5，使得使得m4,5=c2m4,5=c2，故表故表1 1的的“核核”为为 c2c2。实例：考虑下面的决策表实例：考虑下面的决策表5 5，条件属性为，条件属性为a,b,c,da,b,c,d，决策属性为决策属性为e e。U/Aabcdeu110210u200121u320210u400222u511210uu1u2u3u4u5u1u2a,c,du3a,c,du4a,dca,du5a,b,c,da,b,d由上述由上述差别矩阵差别矩阵很容

42、易得到很容易得到核核为：为：c c 差别函数差别函数f fM(S)M(S)为：为：c c(a ad d)，即即(a ac c)()(c cd d)得到两个得到两个约简约简 a a,c c 和和 c c,d d 根据得到的两个约简，可得两个约简后的新决策根据得到的两个约简，可得两个约简后的新决策表：表：UAaceu1120u2011u3220u4022u5120UAcdeu1210u2121u3210u4222U5210例如：下表是医学诊断的一个信息系统例如：下表是医学诊断的一个信息系统I=(U,A)。其中，其中，U=e1,e2,.,e7,A=A,T F。为方便表达，用为方便表达，用1表表示示“

43、是是”，0表示表示“否否”；2表示体温表示体温“很高很高”，1表示体表示体温温“高高”，0表示体温表示体温“正常正常”，则表，则表1.1的简化形式如表的简化形式如表2所示。所示。表表医学诊断信息系统的描述医学诊断信息系统的描述实例实例头痛头痛A体温体温T流感流感Fe1是是正常正常否否e2是是高高是是e3是是很高很高是是e4否否正常正常否否e5否否高高否否e6否否很高很高是是表表简化后的决策系统简化后的决策系统UATFe1100e2111e3121e4000e5010e6021e1e4e5e2(T,1)(A,1)(T,1)(A,1)e3(T,2)(A,1)(T,2)(A,1)(T,2)e6(A,

44、0)(T,2)(T,2)(T,2)表表对应决策为对应决策为1的决策矩阵的决策矩阵 将决策矩阵中的每行的元素进行合取，然后进行简化，将决策矩阵中的每行的元素进行合取，然后进行简化，得到相应的必然规则得到相应的必然规则：(T,1)(A,1)(T,1)(A,1)(F,1)得得(T,1)(A,1)(F,1)(1)(T,2)(A,1)(T,2)(A,1)(T,2)(F,1)得得(T,2)(A,1)(F,1)(2)(A,0)(T,2)(T,2)(T,2)(F,1)得得(T,2)(A,0)(F,1)(3)又由（又由（2）和（）和（3）式可知，不管属性）式可知，不管属性A（头痛）是否发生，头痛）是否发生，只要

45、属性只要属性T（体温）体温）“很高很高”（值为（值为2）时，则决策属性）时，则决策属性F（流感）一定为流感）一定为1，即表明一定是得了，即表明一定是得了“流感流感”，故有，故有(T,2)(F,1)(4)2.2.6属性之间的相关程度属性之间的相关程度在在 信信 息息 系系 统统 S=(U,C D,V,f)中中，设设 D*=X1,X2,Xm，属属性性子子集集P C关关于于决决策策属属性性D的的“正正区区域域”定义为定义为P关关于于D的的正正区区域域表表示示那那些些根根据据属属性性子子集集P就就能能正正确确分分入入的所有对象。的所有对象。条条件件属属性性子子集集P C与与决决策策属属性性D的的相相关

46、关程程度度（也也称称依依赖程度赖程度）定义为）定义为显显然然，0 k(P,D)1。k(P,D)为为计计算算条条件件属属性性子子集集P与与决策属性决策属性D之间的相关程度提供了非常有力的手段之间的相关程度提供了非常有力的手段。一个属性一个属性p P C的的有效值有效值(significantvalue)定义为定义为属性属性p的有效值越大，说明其对条件属性与决的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。策属性之间的影响越大，即其重要性也越大。申请申请人人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1

47、 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝1 已知上表的已知上表的“核核”CORE(C,D)=c2CORE(C,D)=c2，设设R=CORE(C,D)=c2R=CORE(C,D)=c2，计算属性计算属

48、性A A的重要性程度：的重要性程度：2.2.6属性值及属性域约简属性值及属性域约简1.属性值约简属性值约简属属性性值值约约简简(AttributeValueReduction，简简称称AVR)也也称称最最小小复复合合(MinimalComplex)。设设B是是一一个个由由决决策策值值对对(d,w)表表示示的的所所有有对对象象（概概念念）的的下下或或上上近近似似，集集合合B依依赖于一个属性值对的集合赖于一个属性值对的集合T，当且仅当当且仅当集合集合T T是是B B的最小复合，当且仅当的最小复合，当且仅当B B依赖于依赖于T T，且无且无S S T T，使得使得B B依赖于依赖于S S。No.No

49、.AgeAgepregnancpregnanciesiesbody-fatbody-fatCholestCholesterolerolBreast-Breast-cancercancer1 129.4129.411.41.418.2818.28188.197188.197nono2 242.5642.561.41.418.2818.28198.320198.320nono3 342.5642.560 029.3729.37198.320198.320yesyes4 429.4129.410 029.3729.37198.320198.320yesyes5 557.6457.641.41.418

50、.2818.28198.320198.320nono6 642.5642.561.41.418.2818.28188.197188.197yesyes7 729.4129.411.41.418.2818.28188.197188.197nono8 842.5642.561.41.429.3729.37198.320198.320yesyes9 957.6457.641.41.429.3729.37198.320198.320yesyes101057.6457.641.41.418.2818.28188.197188.197nono 设设a=Agea=Age，b=pregnanciesb=pre