高级人工智能

高级人工智能

第十一章

史忠植

中国科学院计算技术研究所粗糙集RoughSet

1/17/20231内容提要一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统七、粒度计算简介1/17/20232一、概述现实生活中有许多含糊现象并不能简单地用真、假值来表示﹐如何表示和处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词，他把它归结到边界线上，也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类。

1/17/20233模糊集1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。1/17/20234粗糙集的提出20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集（RoughSet）﹐他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完全由数据决定，所以更有客观性。1/17/20235粗糙集的研究粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。1/17/20236粗糙集的研究1991年波兰Pawlak教授的第一本关于粗糙集的专著《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。1/17/20237研究现状分析2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”，邀请了创始人Z.Pawlak教授做大会报告；2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005年8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会（CRSSC2005）2006第六届中国粗糙集与软计算学术研讨会在浙江师范大学1/17/20238研究现状分析2007年粗糙集与软计算、Web智能、粒计算联合学术会议,山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议（CRSSC-CWI-CGrC2008）,河南师范大学中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学、上海大学

1/17/20239研究现状分析曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社,1998刘清.RoughSet及Rough推理.北京:科学出版社,2001张文修等.RoughSet理论与方法.北京:科学出版社,2001王国胤.RoughSet理论与知识获取.西安:西安交通大学出版社,2001史忠植.知识发现.北京:清华大学出版社,2002苗夺谦//王国胤//刘清//林早阳//姚一豫.粒计算--过去现在与展望.科学出版社,2007

1/17/202310二、知知识识分类类基本粗粗糙集集理论论认为为知识识就是是人类类和其其他物物种所所固有有的分分类能能力。。例如，，在现现实世世界中中关于于环境境的知知识主主要表表明了了生物物根据据其生生存观观来对对各种种各样样的情情形进进行分分类区区别的的能力力。每每种生生物根根据其其传感感器信信号形形成复复杂的的分类类模式式，就就是这这种生生物的的基本本机制制。分类是是推理理、学学习与与决策策中的的关键键问题题。因因此，，粗糙糙集理理论假假定知知识是是一种种对对对象进进行分分类的的能力力。这这里的的“对对象””是指指我们们所能能言及及的任任何事事物，，比如如实物物、状状态、、抽象象概念念、过过程和和时刻刻等等等。即即知识识必须须与具具体或或抽象象世界界的特特定部部分相相关的的各种种分类类模式式联系系在一一起，，这种种特定定部分分称之之为所所讨论论的全域或论域(universe)。对对于全全域及及知识识的特特性并并没有有任何何特别别假设设。事实上，知知识构成了了某一感兴兴趣领域中中各种分类类模式的一一个族集(family)，，这个族集集提供了关关于现实的的显事实，，以及能够够从这些显显事实中推推导出隐事事实的推理理能力。12/31/202211二、知识识分类为数学处理理方便起见见，在下面面的定义中中用等价关关系来代替替分类。一个近似空间(approximatespace)（或知识库）定义为一一个关系系系统（或二二元组）K=(U,R)其中U（为空集集）是一个个被称为全全域或论域域(universe)的所所有要讨论论的个体的的集合，R是U上等价价关系的一一个族集。。12/31/202212二、知识识分类设PR，且P，P中所有等价价关系的交交集称为P上的一种不不可区分关关系(indiscernbilityrelation)（或称难区区分关系）），记作IND(P)，即[x]IND(p)=∩[x]RRP注意，IND(P)也是等价价关系且是是唯一的。。12/31/202213二、知知识分类类给定近似似空间K=(U,R)，子集XU称为U上的一个个概念(concept)，形式上上，空集集也视为为一个概概念；非非空子族族集PR所产生的的不分明明关系IND(P)的所有等等价类关关系的集集合即U/IND(P)，称为基本知识识(basicknowledge)，相应的的等价类类称为基本概念念(basicconcept)；特别地地，若关关系QR，则关系系Q就称为初等知识识(elementaryknowledge)，相应的的等价类类就称为为初等概念念(elementaryconcept)。一般用大大写字母母P,Q,R等表示一一个关系系，用大大写黑体体字母P,Q,R等表示关关系的族族集；[x]R或R(x)表示关系系R中包含元元素xU的概念或或等价类类。为了了简便起起见，有有时用P代替IND(P)。根据上述述定义可可知，概概念即对对象的集集合，概概念的族族集（分分类）就就是U上上的知识识，U上上分类的的族集可可以认为为是U上上的一个个知识库库，或说说知识库库即是分分类方法法的集合合。12/31/202214二、知识分分类粗糙集理论与与传统的集合合理论有着相相似之处，但但是它们的出出发点完全不不同。传统集集合论认为，，一个集合完完全是由其元元素所决定，，一个元素要要么属于这个个集合，要么么不属于这个个集合，即它它的隶属函数数X(x){0,1}。。模糊集合对对此做了拓广广，它给成员员赋予一个隶隶属度，即X(x)[0,1]，，使得模糊集集合能够处理理一定的模糊糊和不确定数数据，但是其其模糊隶属度度的确定往往往具有人为因因素，这给其其应用带来了了一定的不便便。而且，传传统集合论和和模糊集合论论都是把隶属属关系作为原原始概念来处处理，集合的的并和交就建建立在其元素素的隶属度max和min操作上，，因此其隶属属度必须事先先给定（传统统集合默认隶隶属度为1或或0）。在粗粗糙集中，隶隶属关系不再再是一个原始始概念，因此此无需人为给给元素指定一一个隶属度，，从而避免了了主观因素的的影响。12/31/202215InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-4912/31/202216DecisionSystems/TablesDS:isthedecisionattribute(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/31/202217IssuesintheDecisionTable相同同或或不不可可区区分分的的对对象象可可能能被被表表示示多多次次Thesameorindiscernibleobjectsmayberepresentedseveraltimes.有些属性性可能是是多余的的Someoftheattributesmaybesuperfluous.12/31/202218不可区分分性IndiscernibilityTheequivalencerelationAbinaryrelationwhichisreflexive(xRxforanyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRzthenxRz).TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.12/31/202219不可区分分性Indiscernibility(2)LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby12/31/202220不可区区分性性实例例IndiscernibilityThenon-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-49no12/31/202221概念的边界界知识的粒度度性是造成成使用已有有知识不能能精确地表表示某些概概念的原因因。这就产产生了所谓谓的关于不不精确的““边界”思思想。著名名哲学家Frege认为“概概念必须有有明确的边边界。没有有明确边界界的概念，，将对应于于一个在周周围没有明明确界线的的区域”。。粗糙集理理论中的模模糊性就是是一种基于于边界的概概念，即一一个不精确确的概念具具有模糊的的不可被明明确划分的的边界。为刻画模糊糊性，每个个不精确概概念由一对对称为上近近似与下近近似的精确确概念来表表示，它们们可用隶属属函数定义义12/31/202222粗糙集的基本本定义知识的分类观观点粗糙集理论假假定知识是一一种对对象进进行分类的能能力。而知识识必须与具体体或抽象世界界的特定部分分相关的各种种分类模式联联系在一起，，这种特定部部分称之为所所讨论的全域或论域(universe)。为数学处理方方便起见，在在下面的定义义中用等价关关系来代替分分类。12/31/202223粗糙集的基本本定义定义1一个近似空间(approximatespace)(或知识库)定义为一个个关系系统(或二元组)K=(U,R)，其中U(为空集)是一一个被称为全全域或论域(universe)的所有要讨论论的个体的集集合，R是U上等价关系的的一个族集。。定义2设PR，且P，P中所有等价关关系的交集称称为P上的一种不分分明关系(indiscernbilityrelation)（或称不可区区分关系），，记作IND(P)12/31/202224粗糙集的基本本定义定义3给定近似空间间K=(U,R)，子集XU称为U上的一个概念(concept)，形式上，空空集也视为一一个概念；非非空子族集PR所产生的不分分明关系IND(P)的所有等价类类关系的集合合即U/IND(P)，称为基本知识(basicknowledge)，相应的等价价类称为基本概念(basicconcept)；特别地，若若关系QR，则关系Q就称为初等知识(elementaryknowledge)，相应的等价价类就称为初等概念(elementaryconcept)。12/31/202225上近近似似、、下下近近似似和和边边界界区区域域定义义5:X的的下下近近似似：：R*(X)={x:(xU)([x]RX)}X的的上上近近似似：：R*(X)={x:(xU)([x]RX)}X的的边边界界区区域域：：BNR(X)=R*(X)––R*(X)若BNR(X)，，则集集合合X就就是是一一个个粗粗糙糙概概念念。。下下近近似似包包含含了了所所有有使使用用知知识识R可可确确切切分分类类到到X的的元元素素，，上上近近似似则则包包含含了了所所有有那那些些可可能能是是属属于于X的的元元素素。。概概念念的的边边界界区区域域由由不不能能肯肯定定分分类类到到这这个个概概念念或或其其补补集集中中的的所所有有元元素素组组成成。。POSR(X)=R*(X)称称为为集集合合X的的R-正区区域域，NEGR(X)=U––R*(X)称称为为集集合合X的的R-反区区域域。12/31/202226Lower&UpperApproximations(2)LowerApproximation:UpperApproximation:上近近似似、、下下近近似似和和边边界界区区域域12/31/202227新型的的隶属属关系系传统集集合论论中，，一个个元素素的隶隶属函函数X(x){0,1}。而而粗糙糙集理理论中中，X(x)[0,1]定义4设XU且xU,集合X的粗糙隶隶属函函数(roughmembershipfunction)定义为为其中R是不不分明明关系系，R(x)=[x]R={y:(yU)(yRx)}=1当当且仅仅当[x]RX>0当当且仅仅当[x]RX=0当当且仅仅当[x]RX=12/31/202228隶属关系显然有[0,1]。。我们可以以看到，这这里的隶属属关系是根根据已有的的分类知识识客观计算算出来的，，可以被解解释为一种种条件概率率，能够从从全域上的的个体加以以计算，而而不是主观观给定的。。12/31/202229集近似实实例SetApproximationLetW={x|Walk(x)=yes}.Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/31/202230集近似实实例SetApproximation(2)yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AW12/31/202231UsetＸU/RR:subsetofattributes粗糙集近似图图示12/31/202232Lower&Upper近似(3)X1={u|Flu(u)=yes}={u2,u3,u6,u7}RX1={u2,u3}={u2,u3,u6,u7,u8,u5}X2={u|Flu(u)=no}={u1,u4,u5,u8}RX2={u1,u4}={u1,u4,u5,u8,u7,u6}TheindiscernibilityclassesdefinedbyR={Headache,Temp.}are{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.12/31/202233Lower&Upper近似(4)R={Headache,Temp.}U/R={{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}}X1={u|Flu(u)=yes}={u2,u3,u6,u7}X2={u|Flu(u)=no}={u1,u4,u5,u8}RX1={u2,u3}={u2,u3,u6,u7,u8,u5}RX2={u1,u4}={u1,u4,u5,u8,u7,u6}u1u4u3X1X2u5u7u2u6u812/31/202234例1：设有一一知识识库K={U,{p,q,r}}﹐其其中U={x1,x2,x3,x4,x5,x6,x7,x8}﹐且U/p={{x1,x4,x5},{x2,x8},{x3},{x6,x7}}U/q={{x1,x3,x5},{x6},{x2,x4,x7,x8}}U/r={{x1,x5},{x6},{x2,x7,x8},{x3,x4}}则[x1]p={x1,x4,x5}﹐[x1]q={x1,x3,x5}。。若P={p,q,r}﹐﹐则IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}对于U上的的子集集X1={x1,x4,x7}﹐可可得到到P*X1={x4}∪{x7}={x4,x7}P*X1={x1,x5}∪{x4}∪{x7}={x1,x4,x5,x7}Lower&Upper近似似(5)12/31/202235近似似度度AccuracyofApproximationwhere|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.12/31/202236近似性质质PropertiesofApproximationsimpliesand12/31/202237近似性质质PropertiesofApproximations(2)where-XdenotesU-X.12/31/202238三、知知识的约约简一般约简简定义6设R是等价价关系系的一一个族族集，，且设设RR。若IND(R)=IND(R–R)，则称称关系系R在族集集R之中是是可省的(dispensable)﹐否则则就是是不可省省的。若若族集集R中的每每个关关系R都是不不可省省的﹐﹐则称称族集集R是独立的的(independent)﹐否则则就是是依赖的的或非独立立的。定义7若QP是独立立的﹐﹐并且且IND(Q)=IND(P)﹐则称称Q是关系系族集集P的一个个约简(reduct)。在族族集P中所有有不可可省的的关系系的集集合称称为P的核(core)﹐以CORE(P)来表示示。显然，，族集集P有多个个约简简（约约简的的不唯唯一性性）。。定理1族集P的核等等于P的所有有约简简的交交集。。即CORE(P)=∩RED(P)12/31/202239例2：取前面的例1﹐若若P={p,q,r}﹐则IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}﹐IND(P-p})={{x1,x5},{x2,x7,x8},{x3},{x4},{x6}}IND(P)所以p是不不可省的﹐﹐同理可得得q、r是是可省的。。这样﹐由由{p,q,r}三三个等价关关系组成的的集合和{p,q}、{p,r}定义义了相同的的不分明关关系。又IND({p,q})IND({p})﹐IND({p﹐q})IND({q})﹐则{p,q}和和{p,r}就是是P的约简﹐而且{p}是P的的核﹐也就就是说p是是绝对不能能省的三、知识识的约简12/31/202240相对约简定义8设P和Q是全域U上的等价关关系的族集集，所谓族族集Q的P-正区域(P-positiveregionofQ)，记作POSP(Q)=P*(X)族集Q的P-正区域域是全域U的的所有那些些使用分类类U/P所表达的知知识，能够够正确地分分类于U/Q的等价类之之中的对象象的集合。。定义9设P和Q是全域U上的等价关关系的族集集，RP。若POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))则称称关系R在在族集P中是Q-可省的的﹐否则称为为Q-不可省省的﹔如果在族族集P中的每个关关系R都是是Q-不可省的的﹐则称P关于Q是独立的﹐否则就称称为是依赖的。12/31/202241相对对约约简简定义义10SP称为为P的Q-约约简简(Q-reduct)﹐﹐当当且且仅仅当当S是P的Q-独立的子族族集﹐且POSS(Q)=POSP(Q)；族集P中的所有Q-不可省的初初等关系的集集合﹐称为族族集P的Q-核(Q-core)﹐记作COREQ(P)。下面的定理是是定理1的拓广。定理2族集P的Q-核等于族集集P的所有Q-约简的交集集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集P的所有Q-约简的族集集。12/31/202242知识的依赖性性知识的依赖性性可形式定义义如下：定义11设K=(U,R)是一个近似似空间，P,QR。1)知识Q依赖于知识P或知识P可推导出知识Q，当且仅当IND(P)IND(Q)﹐记作PQ；2)知识P和知识Q是等价的﹐当且仅当PQ且QP﹐即IND(P)=IND(Q)﹐记作P=Q，明显地，P=Q当且仅当IND(P)=IND(Q)；3)知识P和知识Q是独立的，当且仅当PQ且QP均不成立，记记作PQ。12/31/202243知识的的依赖赖性依赖性性也可可以是是部分分成立立的﹐﹐也就就是从从知识识P能推导导出知知识Q的一部部分知知识，，或者者说知知识Q只有一一部分分依赖赖于知知识P的。部部分依依赖性性（部部分可可推导导性））可以以由知知识的的正区区域来来定义义。现现在我我们形形式地地定义义部分分依赖赖性。。定义12设K=(U,R)是一一个知知识库库﹐P,QR﹐我们们称知识Q以依依赖度度k(0k1)依赖于于知识识P﹐记作作PkQ﹐当且且仅当当k=P(Q)=card(POSP(Q))/card(U)(6.8)(1)若k=1﹐﹐则称称知识识Q完全全依赖赖于知识P，P1Q也记成成PQ；(2)若0k1﹐则则称知知识Q部分分依赖赖于知识P；(3)若k=0﹐﹐则称称知识识Q完全全独立立于与知识识P。12/31/202244四、决决策策表的的约简简决策表表决策表表是一一类特特殊而而重要要的知知识表表达系系统，，它指指当满满足某某些条条件时时，决决策（（行为为）应应当怎怎样进进行。。多数数决策策问题题都可可以用用决策策表形形式来来表示示，这这一工工具在在决策策应用用中起起着重重要的的作用用。决策表表可以以定义义如下下：S=(U,A)为一一信息息系统统，且且C,DA是两个个属性性子集集，分分别称称为条条件属属性和和决策策属性性，且且CD=A，CD=，，则该该信息息系统统称为为决策表表，记记作T=(U,A,C,D)或简简称CD决策表表。关关系IND(C)和关关系IND(D)的等价价类分别别称为条条件类和和决策类类。12/31/202245

身高性别视力录取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一一决策表表身高、性性别、视视力为条条件属性性，录取取为决策策属性四、决决策表的的约简12/31/202246决策规则则决策表中中的每一一行对应应诸如形式的决决策规则则，和分别称为为决策规规则的前前驱和后后继。当决策表表S中决决策规则则为真时，，我们说说该决策策规则是是S中一一致的，，否则说说该决策策规则是是S中不不一致的的。若决决策规则则是S中中一致的的，相同同的前驱驱必导致致相同的的后继；；但同一一种后继继不一定定必需是是同一前前驱产生生的。如表1第第一行对对应决策策规则：：身高(高高)性别(男男)视力(差差)录取取(否)12/31/202247决策表的的一致性性命题1当且仅当当CD，决策表T=(U,A,C,D)是一致的。。由命题1，很容易通通过计算条条件属性和和决策属性性间的依赖赖程度来检检查一致性性。当依赖赖程度等于于1时，我们说说决策表是是一致的，，否则不一一致。12/31/202248决策表的分分解命题2每个决策表表T=(U,A,C,D)都可以唯一一分解为两两个决策表表T1=(U1,A,C,D)和T2=(U2,A,C,D)，这样使得得表T1中C1D和T2中C0D。这里U1=POSC(D)，U2=BNC(X)，XU|IND(D)。由命题2可可见，假设设我们已计计算出条件件属性的依依赖度，若若表的结果果不一致，，即依赖度度小于1，，则由命题题2可以将将表分解成成两个子表表：其中一一个表完全全不一致，，依赖度为为0；另一一个表则完完全一致，，依赖度为为1。当然然，只有依依赖度大于于0且不等等于1时，，这一分解解才能进行行。12/31/202249表2不不一致决决策表a、b、c为条件属属性，d、、e为决策策属性1、5产生生不一致Uabcde123456781022001112200111102210201220112111201101决策表的分分解12/31/202250表3完全全一致的决决策表Uabcde346720011110222201121112表4完完全不一致致的决策表表Uabcde125810220011121020101101决策表的分分解12/31/202251一致决策表的的约简在我们制定决决策时是否需需要全部的条条件属性，能能否进行决策策表的约简。。约简后的决决策表具有与与约简前的决决策表相同的的功能，但是是约简后的决决策表具有更更少的条件属属性。一致决策表的的约简步骤如如下：(1)对决策表进行行条件属性的的约简，即从从决策表中消消去某一列；；(主要研究究点)(2)消去重复的行行；(3)消去去每一决策规规则中属性的的冗余值。12/31/202252条件属性的约约简A.Skowron提出出了分明矩阵，，使核核与约约简等等概念念的计计算较较为简简单，，主要要思想想：设S=(U,A)为一个个知识识表示示系统统，其其中U={x1,x2,…,xn}，xi为所讨讨论的的个体体，i=1,2,…,n，A={a1,a2,…,am}，aj为个体体所具具有的的属性性，j=1,2,…,m。知识表表达系系统S的分明矩阵M(S)=[cij]n×n，其中中矩阵阵项定定义如如下：：cij={a∈A：a(xi)≠a(xj)，i,j=1,2,…,n}因此cij是个体体xi与xj有区别别的所所有属属性的的集合合12/31/202253分明矩矩阵对对应的的核与与约简简核就可可以定定义为为分明明矩阵阵中所所有只只有一一个元元素的的矩阵阵项的的集合合，即即CORE(A)={a∈∈A：：cij=(a)，，对一一些i,j}相对于于集合合包含含关系系运算算而言言，若若属性性集合合BA是满足足下列列条件件B∩cij≠，对于于M(S)中的任任一非非空项项cij≠的一个个最小小属性性子集集，则则称属属性集集合BA是A的一一个约约简。。换言之之，约约简是是这样样的最最小属属性子子集，，它能能够区区分用用整个个属性性集合合A可可区分分的所所有对对象。。12/31/202254Skowron的约约简方方法对于每每一个个分明明矩阵阵M(S)对应唯唯一的的分明明函数数fM(S)﹙DiscernibilityFunction﹚，它它的定定义如如下：：信息系系统S的分明明函数数fM(S)是一个个有m-元变量量a1,…,am(ai∈A，i=1,…,m)的布尔尔函数数，它它是∨∨cij的合取取，∨∨cij是矩阵阵项cij中的各各元素素的析析取，，1≤j<i≤n且cij≠Φ。。根据分分明函函数与与约简简的对对应关关系，，A.Skowron提出了了计算算信息息系统统S的约简简RED(S)的方法法：1）计算信信息系系统S的分明明矩阵阵M(S)2）计算与与分明明矩阵阵M(S)对应的的分明明函数数fM(S)3））计计算算分明明函数数fM(S)的最最小小析析取取范范式式，，其其中中每每个个析析取取分分量量对对应应一一个个约约简简12/31/202255为了了对对决决策策表表进进行行约约简简，，可可以以采采用用分明明矩阵阵的的方方法法对对条条件件属属性性进进行行约约简简，，对对决决策策属属性性相相同同的的个个体体不不予予比比较较。。考考虑虑下下面面的的决决策策表表5，，条条件件属属性性为为a,b,c,d，，决决策策属属性性为为eU/Aabcdeu110210u200121u320210u400222u511210表5决策策表表约约简简12/31/202256表5对应应的分明矩阵uu1u2u3u4u5u1

u2a,c,d

u3

a,c,d

u4a,dca,d

u5

a,b,c,d

a,b,d

由下面的的分明矩阵很容容易得到到核为{c}，分明函数fM(S)为c∧(a∨d)，即(a∧c)∨(c∧d)，得到到两个约约简{a,c}和{c,d}决策表约约简12/31/202257表6根据得到的两两个约简，表表5可以简化化为表6和表表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210表7决策表约简12/31/202258求最优或次优优约简所有约简的计计算是NP-hard问题，因此运运用启发信息息来简化计算算以找出最优优或次优约简简是必要的。。现在在求最优优或次优约简简的算法一般般都使用核作作为计算约简简的出发点，，计算一个最最好的或者用用户指定的最最小约简。算算法将属性的的重要性作为为启发规则，，按照属性的的重要度从大大到小逐个加加入属性，直直到该集合是是一个约简为为止。12/31/202259行的约简对决策表中中的重复的的行要删除除，因为它它们的条件件属性和决决策属性都都相同，都都表示同一一条决策规规则。另外外，决策规规则的列表表顺序不是是本质性的的，所以表表6、表7都可进行行约简，如如表6可简简化为下表表：U\Aaceu1120u2011u3220u4022表812/31/202260属性值的约约简对于决策表表而言，属属性值的约约简就是决决策规则的的约简。决决策规则的的约简是利利用决策逻逻辑消去每每个决策规规则的不必必要条件，它不是整整体上约简简属性，而而是针对每每个决策规规则，去掉掉表达该规规则时的冗冗余属性值值，即要计计算每条决决策规则的的核与约简简。12/31/202261非一一致致决决策策表表的的约约简简对于于一一致致的的决决策策表表比比较较容容易易处处理理，，在在进进行行约约简简时时，，只只要要判判断断去去掉掉某某个个属属性性或或某某个个属属性性值值时时是是否否会会导导致致不不一一致致规规则则的的产产生生。。而对对不不一一致致表表进进行行约约简简时时就就不不能能再再使使用用这这种种方方法法了了，，一一般般采采用用下下面面的的方方法法：：一一种种是是考考虑虑正正域域的的变变化化，，另另外外一一种种是是将将不不一一致致表表分分成成完完全全一一致致表表和和完完全全不不一一致致表表两两个个子子表表。非一一致致决决策策表表的的约约简简步步骤骤与与一一致致决决策策表表的的约约简简步步骤骤类类似似。。12/31/202262五、粗糙集集的扩展模型型基本粗糙集理理论的主要存存在的问题是是：1)对原始数据本本身的模糊性性缺乏相应的的处理能力；；2)对于粗糙集的的边界区域的的刻画过于简简单；3)粗粗糙集理论的的方法在可用用信息不完全全的情况下将将对象们归类类于某一具体体的类，通常常分类是确定定的，但并未未提供数理统统计中所常用用的在一个给给定错误率的的条件下将尽尽可能多的对对象进行分类类的方法，而而实际中常常常遇到这类问问题。12/31/202263可变精度粗糙糙集模型W.Ziarko提出了了一种称之为为可变精度粗粗糙集模型，，该模型给出出了错误率低低于预先给定定值的分类策策略，定义了了该精度下的的正区域、边边界区域和负负区域。下面面扼要地介绍绍其思想：一般地，集合合X包含于Y并未反映出集集合X的元素属于集集合Y的“多少”。。为此，VPRS定义了它的量量度：C(X,Y)=1–card(XY)/card(X)当card(x)>0，C(X,Y)=0当card(x)=0。C(X,Y)表示把集集合X归类于于集合Y的误误分类度，即即有C(X,Y)100%的元元素归类错误误。显然，C(X,Y)=0时有有XY。如此，可可事先给定一一错误分类率率(0<0.5)，，基于上述定定义，我们有有XY，当且仅当当C(X,Y)。12/31/202264可变精精度粗粗糙集集模型型在此基基础上上，设设U为论域域且R为U上的等等价关关系，，U/R=A={X1,X2,…,Xk}，这样，可可定义集合合X的-下近似为RX=Xi(XiX,i=1,2,…,k)或RX=Xi(C(Xi,X),i=1,2,…,k)，并且RX称为集合X的-正区域，集合X的-上近似为RX=Xi(C(Xi,X)<1–,i=1,2,…,k)，这样，-边界区域就定义为：：BNRX=Xi(<C(Xi,X)<1–)；-负区域为：NEGRX=Xi(C(Xi,X)1–)。以此类推，，我们还可可以定义-依赖、-约简等与传统粗粗糙集模型型相对应的的概念。12/31/202265相似模型型在数据中中存在缺缺失的属属性值的的时候（（在数据据库中很很普遍）），不分分明关系系或等价价关系无无法处理理这种情情形。为为扩展粗粗糙集的的能力，，有许多多作者提提出了用用相似关关系来代代替不分分明关系系作为粗粗糙集的的基础。。在使用相相似关系系代替粗粗糙集的的不分明明关系后后，最重重要的变变化就是是相似类类不再形形成对集集合的划划分了，，它们之之间是相相互重叠叠的。类类似于等等价类，，可以定定义相似似集，即即所有和和某各元元素x在在属性集集合B上上相似的的集合SIMb(x)。。值得注注意的是是SIMb(x)中中的元素素不一定定属于同同一决策策类，因因此还还需要定定义相似似决策类类，即相相似集对对应的决决策类集集合。12/31/202266基于粗糙集的的非单调逻辑辑自粗糙集理论论提出以来，，粗糙集理论论的研究者都都很重视它的的逻辑研究，，试图通过粗粗糙集建立粗粗糙逻辑，也也相应地发表表了一系列的的粗糙逻辑方方面的论文。12/31/202267与其其它它数数学学工工具具的的结结合合D.Dudios和H.Prade由此此提提出出了了RoughFuzzySet和FuzzyRoughSet的概概念念A.Skowron和J.Grazymala-Buss认为为，，粗粗糙糙集集理理论论可可以以看看作作证证据据理理论论的的基基础础。。并并在在粗粗糙糙集集理理论论的的框框架架上上重重新新解解释释了了证证据据理理论论的的基基本本概概念念，，特特别别是是用用上上近近似似和和下下近近似似的的术术语语解解释释了了信信念念(belief)和似似然然(plausibility)函数数，，进进而而讨讨论论了了两两者者之之间间的的互互补补问问题题。。12/31/202268六、、粗粗糙糙集集的的实实验验系系统统在过过去去几几年年中中，，建建立立了了不不少少基基于于粗粗糙糙集集的的KDD系系统统，，其其中中最最有有代代表表性性的的有有LERS、、ROSE、、KDD-R等等。。1．．LERSLERS(LearningfromexamplesbasedonRoughSet)系系统统是是美美国国Kansas大大学学开开发发的的基基于于粗粗糙糙集集的的实实例例学学习习系系统统。。它它是是用用CommonLisp在在VAX9000上上实实现现的的。。LERS已已经经为为NASA的的Johnson空空间间中中心心应应用用了了两两年年。。此此外外，，LERS还还被被广广泛泛地地用用于于环环境境保保护护、、气气候候研研究究和和医医疗疗研研究究12/31/202269六、、粗粗糙糙集集的的实实验验系系统统2．．ROSE波兰兰Poznan科科技技大大学学基基于于粗粗糙糙集集开开发发了了ROSE(RoughSetdataExplorer),用用于于决决策策分分析析。。它它是是RoughDas&RoughClass系系统统的的新新版版，，其其中中RoughDas执执行行信信息息系系统统数数据据分分析析任任务务，，RoughClass支支持持新新对对象象的的分分类类，，这这两两个个系系统统已已经经在在许许多多实实际际领领域域中中得得到到应应用用。。3．KDD—RKDD-R是由由加拿拿大的的Regina大学学开发发的基基于可可变精精度粗粗糙集集模型型，采采用知知识发发现的的决策策矩阵阵方法法开发发了KDD-R系统统，这这个系系统被被用来来对医医学数数据分分析，，以此此产生生症状状与病病证之之间新新的联联系，，另外外它还还支持持电信信工业业的市市场研研究。。12/31/202270七、粒粒度计计算粒度计计算从从广义义上来来说是是一种种看待待客观观世界界的世世界观观和方方法论论。粒度计计算的的基本本思想想就是使使用粒而不是是对象为计算算单元元，使使用粒粒、粒粒集以以及粒粒间关关系进进行计计算或或问题题求解解。12/31/202271粒度计计算1997年年LotfiA.Zadeh提提出了了粒度度的概概念，，他认认为在在人类类认知知中存存在三三种概概念：：粒度度，组组织与与因果果关系系。从从直观观的来来讲，，粒化化涉及及到从从整体体到部部分的的分解解，而而组织织却是是从部部分到到整体体的集集成，，而因因果关关系涉涉及原原因与与结果果之间间的联联系。。对一一个事事物的的粒化化就是是以可可分辨辨性、、相似似性、、邻近近性与与功能能性集集聚有有关的的事物物。粒度计计算是是信息息处理理的一一种新新的概概念和和计算算范式式，覆覆盖了了所有有有关关粒度度的理理论、、方法法、技技术和和工具具的研研究，，主要要用于于处理理不确确定的的、模模糊的的、不不完整整的和和海量量的信信息。。粗略略地讲讲，一一方面面它是是模糊糊信息息粒度度理论论、粗粗糙集集理论论、商商空间间理论论、区区间计计算等等的超超集，，另一一方面面是粒粒度数数学的的子集集。具具体地地讲，，凡是是在分分析问问题和和求解解问题题中，，应用用了分分组、、分类类、聚聚类以以及层层次化化手段段的一一切理理论与与方法法均属属于粒粒度计计算的的范畴畴。信信息粒粒度在在粒度度计算算，词词计算算，感感知计计算理理论和和精化化自然然语言言中都都有反反映12/31/202272粒度计算算的必要要性从哲学的的角度看看Yager和Filev指出出“人类类已经形形成了世世界就是是一个粒粒度的观观点”以以及““人们观观察、度度量、定定义和推推理的实实体都是是粒度””。信息粒粒是一种种抽象，，它如同同数学中中的“点点”、““线”、、“面””一样，，在人类类的思维维和活动动中占有有重要地地位。从人工智智能的角角度看张钹院士士指出““人类智智能的公公认特点点，就是是人们能能从极不不相同的的粒度上上观察和和分析同同一问题题。人们们不仅能能在不同同粒度的的世界上上进行问问题求解解，而且且能够很很快地从从一个粒粒度世界界跳到另另一个粒粒度的世世界，往往返自如如，毫无无困难。。这种处处理不同同世界的的能力，，正是人人类问题题求解的的强有力力的表现现”。12/31/202273粒度计算算的必要要性从优化论论的角度度来看粒度计算算的理论论与方法法在观念念上突破破了传统统优化思思想的束束缚，不不再以数数学上的的精确解解为目标标，即：：需要的的是很好好地理解解和刻画画一个问问题，而而不是沉沉溺于那那些用处处不大的的细节信信息上。。粒度计计算的方方法不要要求目标标函数和和约束函函数的连连续性与与凸性，，甚至有有时连解解析表达达式都不不要求，，而且对对计算中中数据的的不确定定性也有有很强地地适应能能力，计计算速度度也快，，这些优优点使粒粒度计算算具有更更广泛地地应用前前景，所所以，粒粒度计算算理论的的研究对对推动优优化领域域的发展展极其重重要。12/31/202274粒度计算的必必要性从问题求解的的角度看用粒度计算的的观点来分析析解决问题显显得尤为重要要，这样就不不用局限于具具体对象的细细节。除此之之外，将复杂杂问题划分为为一系列更容容易管理和更更小的子任务务，可以降低低全局计算代代价。从应用技术的的角度看图像处理、语语音与字符识识别等，是计计算机多媒体体的核心技术术。这些信息息处理质量的的好坏直接依依赖于分割的的方法和技术术，而粒度计算算的研究或许许能够解决这这一问题。12/31/202275粒度计算的基基本问题两大问题粒的构造：处理粒的形成成、表