高级人工智能 第十一章 粗糙集

2020/2/12高级人工智能史忠植1高级人工智能第十一章粗糙集RoughSet史忠植中科院计算所2020/2/12高级人工智能史忠植2内容提要一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统七、粒度计算简介2020/2/12高级人工智能史忠植3一、概述现实生活中有许多含糊现象并不能简单地用真、假值来表示﹐如何表示和处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词，他把它归结到边界线上，也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类。2020/2/12高级人工智能史忠植4模糊集1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。2020/2/12高级人工智能史忠植5粗糙集的提出20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集（RoughSet）﹐他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完全由数据决定，所以更有客观性。2020/2/12高级人工智能史忠植6粗糙集的研究粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。2020/2/12高级人工智能史忠植7粗糙集的研究1991年波兰Pawlak教授的第一本关于粗糙集的专著《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。2020/2/12高级人工智能史忠植8研究现状分析2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”，邀请了创始人Z.Pawlak教授做大会报告；2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005年8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会（CRSSC2005）2006第六届中国粗糙集与软计算学术研讨会在浙江师范大学2020/2/12高级人工智能史忠植9研究现状分析2007年粗糙集与软计算、Web智能、粒计算联合学术会议,山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议（CRSSC-CWI-CGrC2008）,河南师范大学中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学、上海大学2020/2/12高级人工智能史忠植10研究现状分析曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社,1998刘清.RoughSet及Rough推理.北京:科学出版社,2001张文修等.RoughSet理论与方法.北京:科学出版社,2001王国胤.RoughSet理论与知识获取.西安:西安交通大学出版社,2001史忠植.知识发现.北京:清华大学出版社,2002苗夺谦//王国胤//刘清//林早阳//姚一豫.粒计算--过去现在与展望.科学出版社,20072020/2/12高级人工智能史忠植11二、知识分类基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。例如，在现实世界中关于环境的知识主要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式，就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此，粗糙集理论假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域或论域(universe)。对于全域及知识的特性并没有任何特别假设。事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集(family)，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。2020/2/12高级人工智能史忠植12二、知识分类为数学处理方便起见，在下面的定义中用等价关系来代替分类。一个近似空间(approximatespace)（或知识库）定义为一个关系系统（或二元组）K=(U,R)其中U（为空集）是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R是U上等价关系的一个族集。2020/2/12高级人工智能史忠植13二、知识分类设PR，且P，P中所有等价关系的交集称为P上的一种不可区分关系(indiscernbilityrelation)（或称难区分关系），记作IND(P)，即[x]IND(p)=∩[x]RRP注意，IND(P)也是等价关系且是唯一的。2020/2/12高级人工智能史忠植14二、知识分类给定近似空间K=(U,R)，子集XU称为U上的一个概念(concept)，形式上，空集也视为一个概念；非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识(basicknowledge)，相应的等价类称为基本概念(basicconcept)；特别地，若关系QR，则关系Q就称为初等知识(elementaryknowledge)，相应的等价类就称为初等概念(elementaryconcept)。一般用大写字母P,Q,R等表示一个关系，用大写黑体字母P,Q,R等表示关系的族集；[x]R或R(x)表示关系R中包含元素xU的概念或等价类。为了简便起见，有时用P代替IND(P)。根据上述定义可知，概念即对象的集合，概念的族集（分类）就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。2020/2/12高级人工智能史忠植15二、知识分类粗糙集理论与传统的集合理论有着相似之处，但是它们的出发点完全不同。传统集合论认为，一个集合完全是由其元素所决定，一个元素要么属于这个集合，要么不属于这个集合，即它的隶属函数X(x){0,1}。模糊集合对此做了拓广，它给成员赋予一个隶属度，即X(x)[0,1]，使得模糊集合能够处理一定的模糊和不确定数据，但是其模糊隶属度的确定往往具有人为因素，这给其应用带来了一定的不便。而且，传统集合论和模糊集合论都是把隶属关系作为原始概念来处理，集合的并和交就建立在其元素的隶属度max和min操作上，因此其隶属度必须事先给定（传统集合默认隶属度为1或0）。在粗糙集中，隶属关系不再是一个原始概念，因此无需人为给元素指定一个隶属度，从而避免了主观因素的影响。2020/2/12高级人工智能史忠植16InformationSystems/Tables•ISisapair(U,A)•Uisanon-emptyfinitesetofobjects.•Aisanon-emptyfinitesetofattributessuchthatforevery•iscalledthevaluesetofa.aVUa:.AaaVAgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-492020/2/12高级人工智能史忠植17DecisionSystems/Tables•DS:•isthedecisionattribute(insteadofonewecanconsidermoredecisionattributes).•TheelementsofAarecalledtheconditionattributes.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no}){,(dAUTAd2020/2/12高级人工智能史忠植18IssuesintheDecisionTable•相同或不可区分的对象可能被表示多次Thesameorindiscernibleobjectsmayberepresentedseveraltimes.•有些属性可能是多余的Someoftheattributesmaybesuperfluous.2020/2/12高级人工智能史忠植19不可区分性Indiscernibility•TheequivalencerelationAbinaryrelationwhichisreflexive(xRxforanyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRzthenxRz).•TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.XXRXxXyRx][2020/2/12高级人工智能史忠植20不可区分性Indiscernibility(2)•LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.•Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.•TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedbyAB)}'()(,|)',{()(2xaxaBaUxxBINDIS)(BINDIS),()',(BINDxxIS.][Bx2020/2/12高级人工智能史忠植21不可区分性实例Indiscernibility•Thenon-emptysubsetsoftheconditionattributesare{Age},{LEMS},and{Age,LEMS}.•IND({Age})={{x1,x2,x6},{x3,x4},{x5,x7}}•IND({LEMS})={{x1},{x2},{x3,x4},{x5,x6,x7}}•IND({Age,LEMS})={{x1},{x2},{x3,x4},{x5,x7},{x6}}.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no2020/2/12高级人工智能史忠植22概念的边界知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓的关于不精确的“边界”思想。著名哲学家Frege认为“概念必须有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域”。粗糙集理论中的模糊性就是一种基于边界的概念，即一个不精确的概念具有模糊的不可被明确划分的边界。为刻画模糊性，每个不精确概念由一对称为上近似与下近似的精确概