基于粗糙集理论的知识发现(XCF,2002).ppt

《基于粗糙集理论的知识发现(XCF,2002).ppt》由会员分享，可在线阅读，更多相关《基于粗糙集理论的知识发现(XCF,2002).ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于粗糙集理论的知识发现浙江大学计算机学院浙江大学计算机学院2002004 4年年1 10 0月月1010日日人工智能第三讲人工智能第三讲第一章第一章 粗糙集理论的发展概述粗糙集理论的发展概述1.1 粗糙集理论概况粗糙集理论概况 在经典逻辑中，只有在经典逻辑中，只有“真真”（TRUE）、）、“假假”(FALSE)二值之分，其含义是二值之分，其含义是“非此即彼非此即彼”、“不容含糊不容含糊”。然而，。然而，自然界中大部分事物所呈自然界中大部分事物所呈现的信息都是现的信息都是不完整的、不确定的、模糊的和含不完整的、不确定的、模糊的和含糊的糊的，因而经典逻辑无法对此类问题进行准确的、，因而经典逻辑无

2、法对此类问题进行准确的、较为圆满的描述和解决较为圆满的描述和解决。长期以来，许多逻辑学。长期以来，许多逻辑学家和哲学家都致力于研究家和哲学家都致力于研究“含糊含糊”概念。早在概念。早在1904年，谓词逻辑创始人年，谓词逻辑创始人G.Frege就提出了就提出了“含含糊糊”（Vague）一词，他将含糊性归结到一词，他将含糊性归结到“边界边界线区域线区域”(Boundary region)上，即在全域上存在上，即在全域上存在一些个体，它既不能被分类到某一个子集上，也一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上。不能被分类到该子集的补集上。1965年，美国数学家年，美国数学家L

3、.A.Zadeh提出了提出了“模模糊集糊集”（Fuzzy sets），），许多计算机科学家和逻辑许多计算机科学家和逻辑学家试图通过这一理论解决学家试图通过这一理论解决G.Frege提出的提出的“含糊含糊”问题，但模糊集没有给出数学公式描述这一含问题，但模糊集没有给出数学公式描述这一含糊概念，无法计算出它的具体的含糊元素数目。糊概念，无法计算出它的具体的含糊元素数目。1982年，波兰数学家年，波兰数学家Z.Pawlak针对针对G.Frege的的“边界线区域边界线区域”思想，提出了思想，提出了“粗糙集粗糙集”（Rough Sets）。Pawlak把那些无法确认的个把那些无法确认的个体都归属于边界线

4、区域，而这种边界线区域被定体都归属于边界线区域，而这种边界线区域被定义为：义为：“上近似集上近似集”与与“下近似集下近似集”的差集的差集。由。由于它有确定的数学公式描述，故含糊元素的数目于它有确定的数学公式描述，故含糊元素的数目是可以计算的，即是可以计算的，即在在“真真”、“假假”二值之间的二值之间的“含糊度含糊度”是可以计算的是可以计算的。粗糙集理论自诞生以来，经过许多数学家和计粗糙集理论自诞生以来，经过许多数学家和计算机科学家的努力，其理论上日趋成熟，特别是算机科学家的努力，其理论上日趋成熟，特别是在在20世纪世纪80年代末和年代末和90年代初，由于粗糙集理论年代初，由于粗糙集理论在数据挖

5、掘、知识发现等领域得到了成功的应用，在数据挖掘、知识发现等领域得到了成功的应用，它受到了国际上的广泛关注。它受到了国际上的广泛关注。相对于其它处理不确定和模糊性的理论工具相对于其它处理不确定和模糊性的理论工具（如模糊集理论、（如模糊集理论、Dempster-Shafer证据理论等）证据理论等）而言，而言，粗糙集理论有许多不可替代的优越性粗糙集理论有许多不可替代的优越性。目。目前，它在信息科学、医药科学、工程技术、金融前，它在信息科学、医药科学、工程技术、金融商业、环境科学、社会科学等领域中得到了广泛商业、环境科学、社会科学等领域中得到了广泛的、较为成功的应用，并且越来越受到其它更多的、较为成功

6、的应用，并且越来越受到其它更多领域的重视。领域的重视。在计算机科学（特别是人工智能）领域，粗在计算机科学（特别是人工智能）领域，粗糙集理论在专家系统、决策支持系统、机器学习、糙集理论在专家系统、决策支持系统、机器学习、机器发现、归纳推理、模式识别、决策表等方面机器发现、归纳推理、模式识别、决策表等方面都有非常成功的应用实例。其中，在都有非常成功的应用实例。其中，在AI中的应用中的应用可分为两大类：可分为两大类：有决策的分析有决策的分析和和无决策的分析无决策的分析。（1）有决策的分析，主要包括：）有决策的分析，主要包括：监督学习监督学习与与决策决策分析分析；（；（2）对无决策的分析，主要是）对无

7、决策的分析，主要是数据压缩、数据压缩、化简、聚类、模式发现、机器发现化简、聚类、模式发现、机器发现等。等。Jelonek等人成功地应用粗糙集理论对神经网等人成功地应用粗糙集理论对神经网络的输入属性及属性域进行约简络的输入属性及属性域进行约简。用粗糙集理论用粗糙集理论获取知识和进行机器学习的有代表性的应用实例获取知识和进行机器学习的有代表性的应用实例是，是，Kansas大学开发的大学开发的“基于粗糙集方法的学习基于粗糙集方法的学习系统系统”（LERS）。）。这个系统的规则发现能力能帮这个系统的规则发现能力能帮助那些用不完全知识进行工作的专家系统建立知助那些用不完全知识进行工作的专家系统建立知识库

8、识库。粗糙集理论认为，粗糙集理论认为，“概念概念”就是对象的集合，就是对象的集合，“知识知识”就是将对象进行分类的能力就是将对象进行分类的能力。将概念看将概念看成是成是“对象的集合对象的集合”的思想，实质上是一种强调的思想，实质上是一种强调概念的概念的“外延外延”的表达方式。假设我们对全域中的表达方式。假设我们对全域中的对象具有必要的的对象具有必要的“信息信息”或或“知识知识”，这些，这些“知识知识”可以被认为是关于对象的内涵（如属性、可以被认为是关于对象的内涵（如属性、特征或描述）的某种刻划特征或描述）的某种刻划。通过这些知识就能够。通过这些知识就能够将全域中的所有对象划分到不同的类别中。将

9、全域中的所有对象划分到不同的类别中。如果存在两个对象具有相同的信息，即下面如果存在两个对象具有相同的信息，即下面将要论述的将要论述的“不可区分关系不可区分关系”，则根据这些已知，则根据这些已知的信息无法将它们区分开来，显然这是一种等价的信息无法将它们区分开来，显然这是一种等价关系。这样的等价关系可以认为是对概念的内涵关系。这样的等价关系可以认为是对概念的内涵的描述。不可区分关系是粗糙集理论中最基本的的描述。不可区分关系是粗糙集理论中最基本的概念之一，在此基础上引入成员关系、上近似、概念之一，在此基础上引入成员关系、上近似、下近似、分类质量等来刻划知识的处理方法。下近似、分类质量等来刻划知识的处

10、理方法。粗糙集理论在知识发现中的主要应用为：粗糙集理论在知识发现中的主要应用为：（1）数据之间（精确的或近似的）依赖关系数据之间（精确的或近似的）依赖关系发现。发现。（2）评价某一分类（属性）的重要性。评价某一分类（属性）的重要性。（3）数据模式发现。数据模式发现。（4）决策规则发现。决策规则发现。（5）剔除冗余属性。剔除冗余属性。（6）数据集的降维，等等。数据集的降维，等等。粗糙集理论的局限性主要有：粗糙集理论的局限性主要有：（1）缺乏处理不精确或不确定原始数据的机缺乏处理不精确或不确定原始数据的机制。制。（2）对含糊概念的刻划过于简单。对含糊概念的刻划过于简单。（3）粗糙集理论不是万能的，

11、它不可能解决粗糙集理论不是万能的，它不可能解决一切含糊的、模糊的不确定性问题。一切含糊的、模糊的不确定性问题。（4）在一个实际的数据挖掘系统或知识发现在一个实际的数据挖掘系统或知识发现系统，单纯地使用粗糙集理论方法不一定能有效系统，单纯地使用粗糙集理论方法不一定能有效地描述不精确或不确定的实际问题，这意味着需地描述不精确或不确定的实际问题，这意味着需要其它方法的补充。一般地，将粗糙集理论与模要其它方法的补充。一般地，将粗糙集理论与模糊集理论、证据理论等其它相关的不确定性处理糊集理论、证据理论等其它相关的不确定性处理方法构成互补，是一种非常自然而又可行的方法。方法构成互补，是一种非常自然而又可行

12、的方法。1.2 粗糙集理论的发展简况粗糙集理论的发展简况 （1）20世纪世纪70年代，年代，Pawlak和一些波兰科学院、华和一些波兰科学院、华沙大学的逻辑学家，在研究信息系统逻辑特性的基础上，沙大学的逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。提出了粗糙集理论的思想。（2）1982年，年，Pawlak发表了经典论文发表了经典论文“Rough sets”，标志着粗糙集理论的正式诞生。标志着粗糙集理论的正式诞生。（3）在最初的几年里，由于大多数研究论文是用波）在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域兰文发表的，所以未引起国际

13、计算机界的重视，研究地域仅限于东欧各国。仅限于东欧各国。（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”的出版，奠定了粗糙集理论的基础，有力地推动了国际粗的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入

14、研究。糙集理论与应用的深入研究。（5）1992年，在波兰召开了第一届国际粗糙集理论年，在波兰召开了第一届国际粗糙集理论研讨会，有研讨会，有15篇论文发表在篇论文发表在1993年第年第18卷的卷的“Foundation of computing and decision sciences”上。上。（6）1993和和1994年，分别在加拿大、美国召开第二、年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。三届国际粗糙集与知识发现（或软计算）研讨会。（7）1995年，年，Pawlak等人在美国等人在美国ACM通讯上发表通讯上发表“Rough sets”，极大地扩大了该理论的

15、国际影响极大地扩大了该理论的国际影响。（8）19961999年，分别在日本、美国、美国、日年，分别在日本、美国、美国、日本召开了第四七届粗糙集理论国际研讨会。本召开了第四七届粗糙集理论国际研讨会。（9）2000年，在加拿大召开了第二届粗糙集与计算年，在加拿大召开了第二届粗糙集与计算趋势国际会议。趋势国际会议。（10）20012002，中国分别在重庆、苏州召开第一、，中国分别在重庆、苏州召开第一、二届粗糙集与软件学术会议。二届粗糙集与软件学术会议。（11）2003年将在重庆召开粗糙集与软计算国际研讨年将在重庆召开粗糙集与软计算国际研讨会。会。1.3 粗糙集理论的研究现状粗糙集理论的研究现状 对粗

16、糙集理论的研究主要分为对粗糙集理论的研究主要分为理论理论和和应用应用两两个部分。个部分。（1）在理论研究方面）在理论研究方面，主要集中在如下方面：，主要集中在如下方面：数学性质数学性质：研究其代数与拓扑结构、收敛：研究其代数与拓扑结构、收敛性等。性等。粗糙集拓广粗糙集拓广：广义粗糙集模型、连续属性：广义粗糙集模型、连续属性离散化。离散化。与其它不确定方法的关系和互补与其它不确定方法的关系和互补：与模糊：与模糊集理论、集理论、Dempster-Shafer证据理论的关系和互补。证据理论的关系和互补。多多Agent系统系统(MAS)中的粗糙集中的粗糙集：MAS中基中基于粗糙集理论的推理和规则合成策

17、略。于粗糙集理论的推理和规则合成策略。粒度（粒度（Granules）计算计算：这是一种新的研：这是一种新的研究方向。究方向。有效算法有效算法：导出规则的增量式算法、简约：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进。的启发式算法、并行算法、现有算法的改进。（2）在应用研究方面）在应用研究方面，主要集中研究，主要集中研究粗糙集粗糙集理论在数据挖掘或知识发现过程中的使用方法和理论在数据挖掘或知识发现过程中的使用方法和应用效果。应用效果。1.4 粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用 （1）在数据准备过程中，在数据进行进一步）在数据准备过程中，在数据进行进一步的

18、分析之前，必须的分析之前，必须对数据进行预处理，粗糙集分对数据进行预处理，粗糙集分析方法可以用于对遗失数据的填补析方法可以用于对遗失数据的填补。（2）在数据准备过程中，利用粗糙集理论的）在数据准备过程中，利用粗糙集理论的数据约简特性，数据约简特性，对数据集进行降维操作对数据集进行降维操作。（3）在数据挖掘阶段，可将粗糙集分析方法）在数据挖掘阶段，可将粗糙集分析方法用于分类规则的发现用于分类规则的发现。（4）在数据挖掘阶段，选择数据挖掘算法时，）在数据挖掘阶段，选择数据挖掘算法时，粗糙集分析方法主要有三个方面：粗糙集分析方法主要有三个方面：a)通过布尔推理通过布尔推理挖掘出约简和简洁的规则来解挖

19、掘出约简和简洁的规则来解释决策释决策。b)通过熵理论通过熵理论将规则的复杂性和预测的误差将规则的复杂性和预测的误差分析溶入到无条件的度量中分析溶入到无条件的度量中。c)与模糊集理论、证据理论与模糊集理论、证据理论构成复合分析方构成复合分析方法法。（5）在数据挖掘阶段，粗糙集分析方法可以）在数据挖掘阶段，粗糙集分析方法可以搜寻隐含在数据中的确定的或非确定的规则搜寻隐含在数据中的确定的或非确定的规则。（6）在解释与评估过程中，粗糙集分析方法）在解释与评估过程中，粗糙集分析方法用于用于对所得到的结果进行统计评估对所得到的结果进行统计评估。第二章第二章 粗糙集理论粗糙集理论2.1 概概 述述 Roug

20、h set(以下简称以下简称RS)理论的理论的要点要点是将是将“分类分类”与与“知识知识”联系在一起，而作为一种数学理论，它使用联系在一起，而作为一种数学理论，它使用“等等价关系价关系”来形式化地表示分类，这样，来形式化地表示分类，这样，“知识知识”就可以理就可以理解为：解为：使用等价关系集使用等价关系集R对离散表示的空间对离散表示的空间U进行划分，进行划分，知识就是知识就是R对对U划分的结果划分的结果。由此，在。由此，在U与与R的意义下，的意义下，“知识库知识库”可以定义为：属于可以定义为：属于R中的所有可能的关系对中的所有可能的关系对U的的划分，记为划分，记为K=(U,R)为了描述知识的为

21、了描述知识的“确定程度确定程度”，RS理论引入理论引入“上近似上近似”与与“下近似下近似”的概念，并以这些概念来定义的概念，并以这些概念来定义U中的一个中的一个子集合子集合B与被关系与被关系R划分之后的划分之后的U的相合程度，称为的相合程度，称为“粗糙粗糙度度”。“粗糙集粗糙集”之名由此而来。之名由此而来。RS理论还包含了求取大量数据中最小不变集合（称为理论还包含了求取大量数据中最小不变集合（称为“核核”）与求解最小规则集（称为）与求解最小规则集（称为“约简约简”）的理论，事）的理论，事实上，这就是实上，这就是KDD中所需完成的主要任务。中所需完成的主要任务。RS理论的理论的特点特点是，是，除

22、问题所需的数据集之外，无需任除问题所需的数据集之外，无需任何先验知识（或信息）何先验知识（或信息）。这是。这是RS理论与模糊理论、证据理理论与模糊理论、证据理论的论的最主要的区别最主要的区别，也是其，也是其最重要的优点最重要的优点。证据理论证据理论需要预先设定需要预先设定先验概率分配（先验概率分配（mass函数）函数）模糊集理论模糊集理论需要预先设定需要预先设定隶属度、隶属度函数隶属度、隶属度函数 证据理论证据理论则无需任何先验知识则无需任何先验知识 RS理论的理论的基本思想基本思想是：是：利用定义在数据集合利用定义在数据集合U上的等价关系对上的等价关系对U的划分作为的划分作为知识，而对知识不

23、确定程度的测量，则是对被分析数据整知识，而对知识不确定程度的测量，则是对被分析数据整体的处理之后自然获得，这样，体的处理之后自然获得，这样，RS理论无需对知识或数据理论无需对知识或数据的局部给予主观评价，也就是说，的局部给予主观评价，也就是说，RS理论对不确定性的描理论对不确定性的描述相对客观述相对客观。2.2 基本概念基本概念2.2.1 不分明关系不分明关系 设设U为为论论域域，R是是U U上上的的等等价价(equivalence)关关系系（即即满满足足自自反反、对对称称和和传传递递性性质质），则则A=U，R称称为为近近似似(approximation)空空 间间，R为为不不 分分 明明 关

24、关 系系(indiscernibility，也也称称不不可可区区分分关关系系)。如如果果x，y U，（x，y）R，那那么么x，y在在A中中是是不不分分明明的的（不不可可区区分分的）的）。关关系系R的的等等价价类类(equivalence classes)称称为为A上上的的基基本本集集合合（elementary set）或或原原子子(atom)。A上上所所有有基基本本集集合合（原原子子）用用U/R表表示示。A中中基基本本集集合合的的有有限限次次并并操操作作得得到到的的集集合合称称为为A上上的的组组合合(Composed)集集合合。A中中所所有有组组合合集集合合的的族族用用Com(A)表表示示，显

25、显然然，Com(A)是是一一布布尔尔代代数数，也也就是说，组合集合族在交、并、补集合操作下是封闭的。就是说，组合集合族在交、并、补集合操作下是封闭的。2.2.2 信息系统信息系统 Pawlak在在1981发发表表的的一一篇篇论论文文中中详详细细论论述述了了信信息息系系统统(information system)的的概概念念。经经不不分分明明关关系系定定义义粗粗糙糙集集，这这是是粗粗糙糙集集研研究究者者的的早早期期研研究究，近近期期已已扩扩展展到到在在一一个个信信息息系系统统中中用用属属性性集集来来定定义义Rough集集。信信息息系系统统形形式式定定义义如如下：下：设信息系统设信息系统S=U,Q

26、,V,f，其中其中 U：对象的有限集，对象的有限集，Q：属属性性的的有有限限集集，Q=C D，C是是条条件件属属性性子子集集，D是是决策属性子集决策属性子集 ,Vp是属性是属性P的域。的域。f:U X A V是总函数，使得是总函数，使得 f(xi,q)Vq，对于每个对于每个q A,xi U 设设P Q，xi,xj U,定定义义二二元元关关系系IND P 称称为为不不分分明明关系如下：关系如下：称称xi和和xj在在S中中关关于于属属性性集集P是是不不分分明明的的，当当且且仅仅当当p(xi)=p(xj)对对所所有有的的p P成成立立。即即xi和和xj不不能能用用P中中的的属属性性加以区别。加以区别

27、。对对所所有有的的p P，可可以以验验证证IND P 是是一一种种U的的等等价价关关系系。关关系系的的等等价价类类称称为为S中中的的P-基基本本集集，Q-基基本本集集称称为为S的的原原子子。信信息息系系统统S是是可可选选择择的的，当当且且仅仅当当S中中的的所所有有原原子子是是单元素集，即单元素集，即Q是一个同一关系。是一个同一关系。重重要要结结论论：一一个个关关系系数数据据库库可可以以看看作作一一个个信信息息系统，它的列是属性，行是对象。系统，它的列是属性，行是对象。2.2.3 集合的上、下近似集合的上、下近似 在在信信息息系系统统S=U,Q,V,f中中，设设X U是是个个体体全全域域上上的的

28、子集，子集，P Q则则X的下和上近似集及边界区域分别为：的下和上近似集及边界区域分别为：显显然然，PX是是X U上上必必然然被被分分类类的的那那些些元元素素的的集集合合；而而P*X是是U上上可可能能被被分分类类的的那那些些元元素素的的集集合合。Bnd(X)是是既既不不能能在在X U上上被被分分类类，又又不不能能在在U-X上上被被分分类类的的那那些些元元素素的的集集合合。可可见见PX是是被被包包含含在在X内内的的最最大大可可定定义义集集；P*X是包含是包含X的最小可定义集。的最小可定义集。图3.1集合的上、下近似概念示意图X2.2.4 集合集合(族族)的近似精度及分类质量的近似精度及分类质量 设

29、设S=U,Q,V,f为为一一信信息息系系统统，且且X U，P Q，则则S上上X的的近似精度近似精度为：为：设设S为为一一信信息息系系统统，P Q，且且令令=X1,X2,Xn是是U的的一一个个分分类类（子子集集族族），其其中中Xi U，则则 的的P-下下近近似似和和P-上近似分别表示为上近似分别表示为上下集近集计算实例（1）LetW=x|Walk(x)=yes.A=Age,LEMSandweget:W=x1,x4,x6U/A=x1,x2,x3,x4,x5,x7,x6Sowehave:AgeLEMSWalkx16-3050yesx216-300nox3 31-45 1-25 nox4 31-45

30、1-25 yesx546-6026-49nox616-3026-49yesx746-6026-49no上下集近集计算实例(2)yesyes/nonox1,x6x3,x4x2,x5,x7AWX1=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.上下集近集计算实例(3)上下集近集计算

31、实例上下集近集计算实例(4)R=Headache,Temp.U/R=u1,u2,u3,u4,u5,u7,u6,u8X1=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,u6u1u4u3X1X2u5u7u2u6u8近似集性质（1）近似集性质(2)where-XdenotesU-X.分类分类 的的近似精度近似精度为为由属性子集PQ确定的分类的分类质量分类质量为分类质量分类质量表示通过属性子集表示通过属性子集P P正确分类的对象数与信息正确分类

32、的对象数与信息系统中所有对象数的比值。这是评价属性子集系统中所有对象数的比值。这是评价属性子集P P的重要的重要性的关键指标之一。性的关键指标之一。2.2.5 属性约简及属性约简及“核核”属属性性约约简简(Attribute Reduction，简简称称AR)是是粗粗糙糙集集理理论论的的一一个个重重要要概概念念。在在一一个个信信息息系系统统S中中，设设 是是S上上的的一一个个分分类类，经经约约简简后后的的最最小小属属性性子子集集具具有有同同原原始始属属性性集集 相相 同同 的的 分分 类类 质质 量量，即即 存存 在在 R P Q，使使 得得 R()=P()，称称 之之 为为属属 性性 集集P

33、的的 -约约 简简，记记 作作REDU(P)。所所 有有 -约约 简简 的的 交交 集集 称称 为为-核核，即即CORE(P)=REDU(P)，核核是是信信息息系系统统中中一一系系列列最最重重要的属性要的属性。在在大大多多数数情情况况下下，分分类类是是由由几几个个甚甚至至一一个个属属性性来来决决定定的的，而而不不是是由由关关系系数数据据库库中中的的所所有有属属性性的的微微小小差差异异来来决决定定。属属性性约约简简及及核核的的概概念念为为人人们们提提取取系系统统中中重重要要属属性性及及其其值值提提供供了了有有力力的的数数学学工工具具，而而且且这这种种约约简简是是本本着着不不破破坏坏原原始始数数据

34、据集集的的分分类类质质量量的的，通通俗俗地地说说，它它是是完完全全“保真保真”的。的。关关于于核核的的计计算算，有有人人提提出出了了差差别别矩矩阵阵（discernibility matrix，也也译译作作可可辨辨识识矩矩阵阵）。在在信信息息系系统统S=(U,C D,V,f)中中，C为为条条件件属属性性，D为为决决策策属属性性，设设为为对对象象全全集集U按按决决策策属属性性D被被分分成成不不相相交交的的类类族族，即即=X1,X2,Xm，则则S中中C的差别矩阵的差别矩阵M(C)=mi,jnxn定义为定义为其中，其中，1 i j n。差别矩阵与信息系统的核有如下关系：对所有的差别矩阵与信息系统的核

35、有如下关系：对所有的c C,c CORE(C,D)的充要条件是，存在的充要条件是，存在i,j(1 i j n)，使使得得mi,j=c。“含糊含糊”是指分别属于两个不同类的对象是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，具有完全相同的条件属性，在差别矩阵中，xi,xj是含糊是含糊的充要条件是存在的充要条件是存在i,j(1 i j n)，使得使得mi,j=-1。2.2.6 属性之间的相关程度属性之间的相关程度 在在 信信 息息 系系 统统 S=(U,C D,V,f)中中，设设 D*=X1,X2,Xm，属属性性子子集集P C关关于于决决策策属属性性D的的“正正区区域域”定义为定

36、义为 P关关于于D的的正正区区域域表表示示那那些些根根据据属属性性子子集集P就就能能正正确确分分入入的所有对象。的所有对象。条条件件属属性性子子集集P C与与决决策策属属性性D的的相相关关程程度度（也也称称依依赖程度赖程度）定义为）定义为显显然然，0 k(P,D)1。k(P,D)为为计计算算条条件件属属性性子子集集P与与决策属性决策属性D之间的相关程度提供了非常有力的手段之间的相关程度提供了非常有力的手段。一个属性一个属性p P C的的有效值有效值(significant value)定义为定义为属性属性p的有效值越大，说明其对条件属性与决的有效值越大，说明其对条件属性与决策属性之间的影响越大

37、，即其重要性也越大。策属性之间的影响越大，即其重要性也越大。2.2.6 属性值及属性域约简属性值及属性域约简 1.属性值约简属性值约简 属属性性值值约约简简(Attribute Value Reduction，简简称称AVR)也也称称最最小小复复合合(Minimal Complex)。设设B是是一一个个由由决决策策值值对对(d,w)表表示示的的所所有有对对象象（概概念念）的的下下或或上上近近似似，集集合合B依依赖于一个属性值对的集合赖于一个属性值对的集合T，当且仅当当且仅当集合集合T T是是B B的最小复合，当且仅当的最小复合，当且仅当B B依赖于依赖于T T，且无且无S S T T，使得使得

38、B B依赖于依赖于S S。2.属性域约简属性域约简 属属性性可可分分为为定定量量属属性性(Quantitative attributes)和和定定性性属属性性(Qualitative attributes)，其其中中定定性性属属性性又又被被分分成成有有序序定定性性属属性性(Ordered qualitative attributes)和和无无序序定定性属性性属性(Unordered qualitative attributes)。如如“年年龄龄”为为有有序序定定性性属属性性，它它可可分分为为年年轻轻、中中年年及及老老年年等等；而而“性性别别”为为无无序序定定性性属属性性，它它包包含含男男、女女

39、两两种种类类型型，但但并并无无一一定定的的顺顺序序。针针对对无无序序定定性性属属性性，有有人人提提出出了了属属性性域域约约简简(Attribute Domain Reduction，简简称称ADR)的概念。的概念。属属性性域域约约简简的的基基本本思思想想是是，设设某某个个需需要要约约简简的的无无序序定定性性属属性性p的的属属性性域域基基数数card(Vp)为为N，构构造造一一个个具具有有N个个二二进进制制属属性性(binary attribute)的的表表，原原表表中中属属性性p的的每每个个值值就就相相应应地地转转化化为为新新表表的的一一个个二二进进制制属属性性，然然后后对对新新表表按按照照属

40、属性性约约简简的的方方法法进进行行约约简简，即即得得属属性性域域约约简简的的结结果。果。2.3 Drawing conclusions from data2.3.1 An ExamplefactDriving conditionsconsequencesupportweatherroadtimeaccident1mistyicydayyes62foggyicynightyes83mistynot icynightyes54sunnyicydayno555foggynot icyduskyes116mistynot icynightno15Thetablecontainsdataaboutdri

41、vingcarsinvariousdrivingconditions-weather,read and time are condition attributes-accident is the decision attribute2.3.2 The ProblemWe want to explain accidents in terms of the driving conditions,i.e.,to describe the set of facts 1,2,3,5 in terms of the attributes weather,road and timeNote that the

42、 data are inconsistent because the facts number 3 and 6 are inconsistent,i.e.,they have the same driving conditions but different consequencesThe set of all accidents can not be described in terms of attributes weather,road and time due to the inconsistency of the data2.3.3 What are the data telling

43、 us?1,2,5 is the set of all facts that can be certainly classified as accidents in terms of the driving conditions 1,2,3,5,6 is the set of all facts that can be possibly classified as accidents in terms of the driving conditions3,6 are inconsistent factsNote:the set 3,6 is the difference between set

44、s 1,2,3,5,6 and 1,2,52.3.4 The indiscernibility relationAny subset B of A determines an indiscernibility relation I(B)on U,defined as follows:(x,y)I(B)if and only if a(x)=a(y)for every a A,where a(x)denotes the value of attribute a for element x.I(B)is an equivalence relation,i.e.,each subset B of A

45、 determines a partition(classification)of all objects into classes having the same description in terms of attributes from B.2.3.5 ResultsDecision algorithm(eff.=0.95)certainty1.(weather,misty)(road,icy)(accident,yes)1.002.(weather,foggy)(accident,yes)1.003.(weather,misty)(road,not icy)(accident,yes

46、)1.004.(weather,sunny)(accident,no)1.005.(weather,misty)(road,not icy)(accident,no)1.00Inverse decision algorithm(eff.=0.74)certainty1.(accident,yes)(weather,misty)(road,icy)0.202.(accident,yes)(weather,foggy)0.633.(accident,yes)(weather,misty)(road,not icy)0.174.(accident,no)(weather,sunny)0.795.(a

47、ccident,no)(weather,misty)(road,not icy)0.212.3.6 Final effectsConclusions certainty1.misty weather and icy road or foggy weather for certain cause accidents 1.002.misty weather and not icy road most probably do not cause accidents 0.753.sunny weather for certain does not cause accidents 1.00Explana

48、tions1.if there are no accidents the weather is most probably sunny 0.632.if there are accidents the weather is most probably foggy3.0.792.3.6 Approximations and decision rules Certain rules describing accidents(the lower approximation of the set 1,2,3,5)1.(weather,misty)(road,icy)(accident,yes)2.(w

49、eather,foggy)(accident,yes)Uncertain rule describing accidents(the boundary region of the set 1,2,3,5)3.(weather,misty)(road,not icy)(accident,yes)Certain rule describing lack of accidents(the lower approximation of the set 4,6)4.(weather,sunny)(accident,no)Uncertain rule describing lack of accidents(the boundary region of the set 4,6)5.(weather,misty)(road,not icy)(accident,no)