aai09粗糙集高级人工智能史忠植

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

2、类。3/1/20203高级人工工智能史史忠植植模糊集1965年，Zadeh提出出了模糊糊集，不不少理论论计算机机科学家家和逻辑辑学家试试图通过过这一理理论解决决G.Frege的含含糊概念念，但模模糊集理理论采用用隶属度度函数来来处理模模糊性，而基本本的隶属属度是凭凭经验或或者由领领域专家家给出，所以具具有相当当的主观观性。3/1/20204高级人工工智能史史忠植植粗糙集的的提出20世纪纪80年年代初，波兰的的Pawlak针对G.Frege的边界界线区域域思想提提出了粗粗糙集（RoughSet）他他把那些些无法确确认的个个体都归归属于边边界线区区域，而而这种边边界线区区域被定定义为上上近似集集和

3、下近近似集之之差集。由于它它有确定定的数学学公式描描述，完完全由数数据决定定，所所以更有有客观性性 。3/1/20205高级人工工智能史史忠植植粗糙集的的研究粗糙集理理论的主主要优势势之一是是它不需需要任何何预备的的或额外外的有关关数据信信息。自自提出以以来，许许多计算算机科学学家和数数学家对对粗糙集集理论及及其应用用进行了了坚持不不懈的研研究，使使之在理理论上日日趋完善善，特别别是由于于20世世纪80年代末末和90年代初初在知识识发现等等领域得得到了成成功的应应用而越越来越受受到国际际上的广广泛关注注。3/1/20206高级人工工智能史史忠植植粗糙集的的研究1991年波兰兰Pawlak教授的

4、的第一本本关于粗粗糙集的的专著RoughSets：Theoretical AspectsofReasoning about Data和1992年年R.Slowinski主主编的关关于粗糙糙集应用用及其与与相关方方法比较较研究的的论文集集的出版版，推动动了国际际上对粗粗糙集理理论与应应用的深深入研究究。1992年年在波兰兰Kiekrz召开了了第1届届国际粗粗糙集讨讨论会。从此每每年召开开一次与与粗糙集集理论为为主题的的国际研研讨会。3/1/20207高级人工工智能史史忠植植研究现状状分析史忠植. 知识识发现. 北京京:清清华大学学出版社社,2002刘清.RoughSet及Rough推理. 北京京

5、:科科学出版版社,2001张文修等等.RoughSet理理论与方方法.北北京: 科学学出版社社,2001王国胤, Rough Set理论论与知识识获取. 西安安:西西安交通通大学出出版社, 2001曾黄麟. 粗集集理论及及其应用用(修订订版). 重庆庆:重重庆大学学出版社社,19983/1/20208高级人工工智能史史忠植植研究现状状分析2001年5月月在重庆庆召开了了“第1届中国国Rough集集与软计计算学术术研讨会会”，邀邀请了创创始人Z.Pawlak教教授做大大会报告告；2002年10月在苏苏州第第2届2003年5月月在重庆庆第第3届届，同时时举办“第9届届粗糙集集、模糊糊集、数数据挖掘

6、掘和粒度度-软计计算的国国际会议议”因因非非典推迟迟到10月中科院计计算所、中科院院自动化化所、北北京工业业大学、西安交交通大学学、重庆庆邮电学学院、山山西大学学、合肥肥工业大大学、上上海大学学、南昌昌大学3/1/20209高级人工工智能史史忠植植二、知知识分类类基本粗糙糙集理论论认为知知识就是是人类和和其他物物种所固固有的分分类能力力。例如如，在现现实世界界中关于于环境的的知识主主要表明明了生物物根据其其生存观观来对各各种各样样的情形形进行分分类区别别的能力力。每种种生物根根据其传传感器信信号形成成复杂的的分类模模式，就就是这种种生物的的基本机机制。分分类是推推理、学学习与决决策中的的关键问

7、问题。因因此，粗粗糙集理理论假定定知识是是一种对对对象进进行分类类的能力力。这里里的“对对象”是是指我们们所能言言及的任任何事物物，比如如实物、状态、抽象概概念、过过程和时时刻等等等。即知知识必须须与具体体或抽象象世界的的特定部部分相关关的各种种分类模模式联系系在一起起，这种种特定部部分称之之为所讨讨论的全域或论域(universe)。对于于全域及及知识的的特性并并没有任任何特别别假设。事实上上，知识识构成了了某一感感兴趣领领域中各各种分类类模式的的一个族族集(family)，这个个族集提提供了关关于现实实的显事事实，以以及能够够从这些些显事实实中推导导出隐事事实的推推理能力力。3/1/202

8、010高级人工工智能史史忠植植二、知知识分类类为数学处处理方便便起见，在下面面的定义义中用等等价关系系来代替替分类。一个近似空间间(approximatespace)（或知识库）定义为为一个关关系系统统（或二二元组）K=(U,R)其中U（为空集集）是一一个被称称为全域域或论域域(universe)的所所有要讨讨论的个个体的集集合，R是U上等等价关系系的一个个族集。3/1/202011高级人工工智能史史忠植植二、知知识分类类设PR，且P ，P中所有等等价关系系的交集集称为P上的一种种难区分分关系(indiscernbility relation)（或称难难区分关关系），记作IND(P)，即xIN

9、D(p)= IxRRP注意，IND(P)也是等等价关系系且是唯唯一的。3/1/202012高级人工工智能史史忠植植二、知知识分类类给定近似似空间K=(U,R)，子集XU称为U上的一个个概念(concept)，形式上上，空集集也视为为一个概概念；非非空子族族集PR所产生的的不分明明关系IND(P)的所有等等价类关关系的集集合即U/IND(P)，称为基本知识识(basicknowledge)，相应的的等价类类称为基本概念念(basicconcept)；特别地地，若关关系QR，则关系系Q就称为初等知识识(elementaryknowledge)，相应的的等价类类就称为为初等概念念(elementar

10、yconcept)。一般用大大写字母母P,Q,R等表示一一个关系系，用大大写黑体体字母P,Q,R等表示关关系的族族集；xR或R(x)表示关系系R中包含元元素xU的概念或或等价类类。为了了简便起起见，有有时用P代替IND(P)。根据上述述定义可可知，概概念即对对象的集集合，概概念的族族集（分分类）就就是U上上的知识识，U上上分类的的族集可可以认为为是U上上的一个个知识库库，或说说知识库库即是分分类方法法的集合合。3/1/202013高级人工工智能史史忠植植二、知知识分类类粗糙集理理论与传传统的集集合理论论有着相相似之处处，但是是它们的的出发点点完全不不同。传传统集合合论认为为，一个个集合完完全是

11、由由其元素素所决定定，一个个元素要要么属于于这个集集合，要要么不属属于这个个集合，即它的的隶属函函数X(x)0,1。模模糊集合合对此做做了拓广广，它给给成员赋赋予一个个隶属度度，即X(x)0,1，使使得模糊糊集合能能够处理理一定的的模糊和和不确定定数据，但是其其模糊隶隶属度的的确定往往往具有有人为因因素，这这给其应应用带来来了一定定的不便便。而且且，传统统集合论论和模糊糊集合论论都是把把隶属关关系作为为原始概概念来处处理，集集合的并并和交就就建立在在其元素素的隶属属度max和min操操作上，因此其其隶属度度必须事事先给定定（传统统集合默默认隶属属度为1或0）。在粗粗糙集中中，隶属属关系不不再是

12、一一个原始始概念，因此无无需人为为给元素素指定一一个隶属属度，从从而避免免了主观观因素的的影响。3/1/202014高级人工工智能史史忠植植InformationSystems/TablesISisa pair(U,A)Uisa non-emptyfiniteset of objects.Aisa non-emptyfiniteset of attributessuchthatforeveryiscalledthe value setofa.AgeLEMSx16-3050 x216-300 x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6

13、026-493/1/202015高级人工工智能史史忠植植DecisionSystems/TablesDS:isthedecisionattribute(insteadofonewecan consider moredecisionattributes).TheelementsofAarecalled theconditionattributes.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202016高级人工工智能史史忠植植Is

14、suesinthe Decision TableThesameorindiscernible objectsmay be represented severaltimes.Some of theattributes maybesuperfluous.3/1/202017高级人工工智能史史忠植植难区分性性IndiscernibilityTheequivalencerelationA binaryrelationwhichisreflexive(xRxforany objectx) ,symmetric(ifxRythenyRx),andtransitive (ifxRyandyRzthenxRz

15、).Theequivalenceclassof an elementconsistsofallobjectssuch thatxRy.3/1/202018高级人工工智能史史忠植植难区分性性Indiscernibility(2)LetIS= (U,A)beaninformationsystem, thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandxareindiscerniblefrom eachotherbyattribute

16、sfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby3/1/202019高级人工工智能史史忠植植难区分性性实例IndiscernibilityThenon-empty subsetsofthe conditionattributes areAge,LEMS,andAge,LEMS.IND(Age) =x1,x2,x6, x3,x4, x5,x7IND(LEMS)= x1,x2,x3,x4,x5,x6,x7IND(Age,LEMS)=x1,x2,x3,x4,x5,x7,x6.AgeLEMSWalkx16-3

17、050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202020高级人工工智能史史忠植植概念的边边界知识的粒粒度性是是造成使使用已有有知识不不能精确确地表示示某些概概念的原原因。这这就产生生了所谓谓的关于于不精确确的“边边界”思思想。著著名哲学学家Frege认为“概念必必须有明明确的边边界。没没有明确确边界的的概念，将对应应于一个个在周围围没有明明确界线线的区域域”。粗粗糙集理理论中的的模糊性性就是一一种基于于边界的的概念，即一个个不精确确的概念念具有模模糊的不不可被

18、明明确划分分的边界界。为刻刻画模糊糊性，每每个不精精确概念念由一对对称为上上近似与与下近似似的精确确概念来来表示，它们可可用隶属属函数定定义3/1/202021高级人工工智能史史忠植植粗糙集的的基本定定义知识的分分类观点点粗糙集理理论假定定知识是是一种对对对象进进行分类类的能力力。而知知识必须须与具体体或抽象象世界的的特定部部分相关关的各种种分类模模式联系系在一起起，这种种特定部部分称之之为所讨讨论的全域或论域(universe)。为数学处处理方便便起见，在下面面的定义义中用等等价关系系来代替替分类。3/1/202022高级人工工智能史史忠植植粗糙集的的基本定定义定义1一个近似空间间(appr

19、oximatespace)(或知识库)定义为为一个关关系系统统(或二二元组)K=(U,R)，其中U(为空集)是一个个被称为为全域或或论域(universe)的所有要要讨论的的个体的的集合，R是U上等价关关系的一一个族集集。定义2设PR，且P，P中所有等等价关系系的交集集称为P上的一种种不分明明关系(indiscernbility relation)（或称不不可区分分关系），记作作IND(P)3/1/202023高级人工工智能史史忠植植粗糙集的的基本定定义定义3给定近似似空间K=(U,R)，子集XU称为U上的一个个概念(concept)，形式上上，空集集也视为为一个概概念；非非空子族族集PR所产

20、生的的不分明明关系IND(P)的所有等等价类关关系的集集合即U/IND(P)，称为基本知识识(basicknowledge)，相应的的等价类类称为基本概念念(basicconcept)；特别地地，若关关系QR，则关系系Q就称为初等知识识(elementaryknowledge)，相应的的等价类类就称为为初等概念念(elementaryconcept)。3/1/202024高级人工工智能史史忠植植上近似、下近似似和边界界区域定义5:X的下近近似：R*(X)=x:(xU) (xRX )X的上近近似：R*(X)=x:(xU) (xRX)X的边界界区域：BNR(X)=R*(X)R*(X)若BNR(X)

21、 ，则集合X就是一一个粗糙糙概念。下近似似包含了了所有使使用知识识R可确确切分类类到X的的元素，上近似似则包含含了所有有那些可可能是属属于X的的元素。概念的的边界区区域由不不能肯定定分类到到这个概概念或其其补集中中的所有有元素组组成。POSR(X)=R*(X)称称为集合合X的R-正区域，NEGR(X)=UR*(X)称称为集合合X的R-反区域。3/1/202025高级人工工智能史史忠植植Lower& Upper Approximations (2)LowerApproximation:UpperApproximation:3/1/202026高级人工工智能史史忠植植新型的隶隶属关系系传统集合合论

22、中，一个元元素的隶隶属函数数X(x)0,1。而而粗糙集集理论中中，X(x)0,1定义4设XU且xU,集合X的粗糙隶属属函数(roughmembershipfunction)定义为其中R是是不分明明关系，R(x)=xR=y:(yU)(yRx)=1当且且仅当xRX0当且且仅当xRX=0当且且仅当xRX=3/1/202027高级人工工智能史史忠植植隶属关系系根据上面面的定义义，可以以得到以以下性质质(1）(x)=1当且仅当当xRX；(2）(x)0当且仅当当xRX；(3）(x)=0当且仅当当xRX=。显然有(x)0,1。我们们可以看看到，这这里的隶隶属关系系是根据据已有的的分类知知识客观观计算出出来的

23、，可以被被解释为为一种条条件概率率，能够够从全域域上的个个体加以以计算，而不是是主观给给定的。3/1/202028高级人工工智能史史忠植植集近似SetApproximationLetT =(U, A)andletandWecan approximateXusingonly theinformationcontainedinBbyconstructingtheB-lowerandB-upperapproximationsofX,denotedandrespectively,where3/1/202029高级人工工智能史史忠植植集近似SetApproximation(2)B-boundary re

24、gionofX,consistsofthoseobjects thatwecannot decisivelyclassifyintoXinB.B-outsideregionofX,consistsofthoseobjects thatcan be withcertainty classifiedasnot belongingtoX.A setissaid to beroughifitsboundaryregion is non-empty,otherwise thesetiscrisp. 3/1/202030高级人工工智能史史忠植植集近似实实例SetApproximationLetW= x |

25、Walk(x)= yes.Thedecisionclass,Walk,isroughsincetheboundaryregion is notempty.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202031高级人工工智能史史忠植植集近似实实例SetApproximation (2)yesyes/nonox1,x6x3,x4x2, x5,x7AW3/1/202032高级人工工智能史史忠植植UsetU/RR :subsetofa

26、ttributesLower&集近似图图示ns3/1/202033高级人工工智能史史忠植植Lower& Upper Approximations(3)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,u6Theindiscernibilityclasses definedbyR=Headache, Temp.areu1,u2,u3,u4,u5, u7,u6,u8.3/1/202034高级人工工智能史史忠植植Lo

27、wer& Upper Approximations(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,u6u1u4u3X1X2u5u7u2u6u83/1/202035高级人工工智能史史忠植植例1：设有一知知识库K=U,p,q,r其中中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,

28、x8,x3,x6,x7U/q=x1,x3,x5,x6,x2,x4,x7,x8U/r=x1,x5,x6,x2,x7,x8,x3,x4则x1p=x1,x4,x5x1q= x1,x3,x5 。若P=p,q,r则IND(P)= x1,x5,x2,x8,x3,x4,x6,x7对于U上上的子集集X1=x1,x4,x7可得得到P*X1=x4x7=x4,x7P*X1=x1,x5x4x7=x1,x4,x5,x73/1/202036高级人工工智能史史忠植植近似度AccuracyofApproximationwhere|X|denotesthecardinalityofObviouslyIfXiscrispwith

29、 respecttoB.IfXisroughwith respecttoB.3/1/202037高级人工工智能史史忠植植近似性质质PropertiesofApproximationsimpliesand3/1/202038高级人工工智能史史忠植植近似性质质PropertiesofApproximations(2)where-XdenotesU -X.3/1/202039高级人工工智能史史忠植植三、知知识的约约简一般约简简定义6设R是等价关关系的一一个族集集，且设设RR。若IND(R)=IND(RR)，则称关关系R在族集R之中是可省的(dispensable)否则就就是不可省的。若族族集R中的每

30、个个关系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)3/1/202040高级人工工智能史史忠植植例2：取前面的例1若P=p,q,r则则IND(P)=x1,x5,x2,x8,x3,x4,x6,x7IND(P-p)=x1,x5,x2,x7

31、,x8,x3,x4,x6IND(P)所以p是是不可省省的同同理可得得q、r是可省省的。这这样由由p,q,r三个个等价关关系组成成的集合合和p,q、p,r定义了了相同的的不分明明关系。又IND(p,q)IND(p)IND(pq)IND(q)则则p,q和和p, r就是P的约简而且p是是P的核核也就就是说p是绝对对不能省省的3/1/202041高级人工工智能史史忠植植相对约简简定义8设P和Q是全域U上的等价价关系的的族集，所谓族族集Q的P-正区域(P-positiveregionofQ)，记作POSP(Q)=P*(X)族集Q的P-正区区域是全域U的所有有那些使使用分类类U/P所表达的的知识，能够正正

32、确地分分类于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是独立的否则就就称为是是依赖的。3/1/202042高级人工工智能史史忠植植相对约简简定义10 SP称为P的Q-约简简(Q-reduct)当当且仅当当S是P的Q-独立的的子族集集且POSS(Q)=POSP(Q)；族集集P中的所有有Q-不可省省的初等等关系的的集合称为族族集P的Q-核(Q-core)记

33、作COREQ(P) 。下面的定定理是定理1的拓广。定理2族集P的Q-核等于于族集P的所有Q-约简的的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集集P的所有Q-约简的的族集。3/1/202043高级人工工智能史史忠植植知识的依依赖性知识的依依赖性可可形式定定义如下下：定义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和知识

34、Q是独立的，当且仅仅当PQ且QP均不成立立，记作作PQ。3/1/202044高级人工工智能史史忠植植知识的依依赖性依赖性也也可以是是部分成成立的也就是是从知识识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

35、)若0k1则称称知识Q部分依依赖于知识P；(3)若k=0则则称知识识Q完全独独立于与知识P。3/1/202045高级人工工智能史史忠植植四、决决策表的的约简决策表决策表是是一类特特殊而重重要的知知识表达达系统，它指当当满足某某些条件件时，决决策（行行为）应应当怎样样进行。多数决决策问题题都可以以用决策策表形式式来表示示，这一一工具在在决策应应用中起起着重要要的作用用。决策表可可以定义义如下：S=(U,A)为一信信息系统统，且C,DA是两个属属性子集集，分别别称为条条件属性性和决策策属性，且CD=A，CD=，则则该信息息系统称称为决策表，记作T=(U,A,C,D)或简称称CD决策表。关系IND(

36、C)和关系系IND(D)的等价价类分别别称为条条件类和和决策类类。3/1/202046高级人工工智能史史忠植植身高性别视力录取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一一决策表表身高、性性别、视视力为条条件属性性，录取取为决策策属性3/1/202047高级人工工智能史史忠植植决策规则则决策表中中的每一一行对应应诸如形式的决决策规则则，和分别称为为决策规规则的前前驱和后后继。当决策表表S中决决策规则则为真时，我们说说该决策策规则是是S中一一致的，否则说说该决策策规则是是S中不不一致的的。若决决策规则则是S中中一致的的，相同同的前驱驱必导致致相同的的后继；但

37、同一一种后继继不一定定必需是是同一前前驱产生生的。 如表1第第一行对对应决策策规则：身高(高高)性别(男男)视力(差差) 录取取(否) 3/1/202048高级人工工智能史史忠植植决策表的的一致性性命题1当且仅当当CD，决策表表T=(U,A,C,D)是一致的的。由命题1，很容易易通过计计算条件件属性和和决策属属性间的的依赖程程度来检检查一致致性。当当依赖程程度等于于1时，我们们说决策策表是一一致的，否则不不一致。3/1/202049高级人工工智能史史忠植植决策表的的分解命题2每个决策策表T=(U,A,C,D)都可以唯唯一分解解为两个个决策表表T1=(U1,A,C,D)和T2=(U2,A,C,D

38、)，这样使使得表T1中C1D和T2中C0D。这里U1=POSC(D)，U2=BNC(X)，XU|IND(D)。由命题2可见，假设我我们已计计算出条条件属性性的依赖赖度，若若表的结结果不一一致，即即依赖度度小于1，则由由命题2可以将将表分解解成两个个子表：其中一一个表完完全不一一致，依依赖度为为0；另另一个表表则完全全一致，依赖度度为1。当然，只有依依赖度大大于0且且不等于于1时，这一分分解才能能进行。3/1/202050高级人工工智能史史忠植植表2不不一一致决策策表a、b、c为条条件属性性，d、e为决决策属性性1、5产产生不一一致Ua b c d e123456781 0 2 2 00 1 1

39、 1 22 0 0 1 11 1 0 2 21 0 2 0 12 2 0 1 12 1 1 1 20 1 1 0 13/1/202051高级人工工智能史史忠植植表3完完全一致致的决策策表Ua b c d e34672 0 0 1 11 1 0 2 22 2 0 1 12 1 1 1 2表4完完全不不一致的的决策表表Ua b c d e12581 0 2 2 00 1 1 1 21 0 2 0 10 1 1 0 13/1/202052高级人工工智能史史忠植植一致决策策表的约约简在我们制制定决策策时是否否需要全全部的条条件属性性，能否否进行决决策表的的约简。约简后后的决策策表具有有与约简简前的决决

40、策表相相同的功功能，但但是约简简后的决决策表具具有更少少的条件件属性。一致决策策表的约约简步骤骤如下：(1)对决策表表进行条条件属性性的约简简，即从从决策表表中消去去某一列列；(主主要研究究点)(2)消去重复复的行；(3)消消去每每一决策策规则中中属性的的冗余值值。 3/1/202053高级人工工智能史史忠植植条件属性性的约简简A.Skowron提提出了差差别矩阵阵，使核核与约简简等概念念的计算算较为简简单，主主要思想想：设S=(U,A)为一个知知识表示示系统，其中U=x1,x2,xn，xi为所讨论论的个体体，i=1,2,n，A=a1,a2,am，aj为个体所所具有的的属性，j=1,2,m。知

41、识表达达系统S的差别矩矩阵M(S)=cijnn，其中矩矩阵项定定义如下下：cij=aA：a(xi)a(xj)，i,j=1,2,n因此cij是个体xi与xj有区别的的所有属属性的集集合3/1/202054高级人工工智能史史忠植植差别矩阵阵对应的的核与约约简核就可以以定义为为差别矩矩阵中所所有只有有一个元元素的矩矩阵项的的集合，即CORE(A)=aA：cij=(a)，对一一些i,j相对于集集合包含含关系运运算而言言，若属属性集合合BA是满足下下列条件件Bcij，对于M(S)中的任一一非空项项cij的一个最最小属性性子集，则称属属性集合合BA是A的的一个约约简。换言之，约简是是这样的的最小属属性子集

42、集，它能能够区分分用整个个属性集集合A可可区分的的所有对对象。3/1/202055高级人工工智能史史忠植植Skowron的约简简方法对于每一一个差别别矩阵M(S)对应唯一一的差别别函数fM(S)DiscernibilityFunction，它的的定义如如下：信息系统统S的差别函函数fM(S)是一个有有m-元变量a1, am(aiA，i=1,m)的布尔函函数，它它是cij的合取，cij是矩阵项项cij中的各元元素的析析取，1j0，C(X, Y)=0当card(x)=0。C(X, Y)表示把把集合X归类于于集合Y的误分分类度，即有C(X, Y)100%的元素素归类错错误。显显然，C(X, Y)=0时时有XY。如此此，可事事先给定定一错误误分类率率(00.5)，基基于上述述定义，我们有有XY，当且且仅当C(X, Y)。3/1/202065高级人工工智能史史忠植植可变精度度粗糙集集模型在此基础础上，设设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)；-负