高级人工智能十一章.ppt

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

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

3、数据决定，所以更有客观性。7/11/20255高级人工智能 史忠植粗糙集的研究粗糙集的研究 粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。7/11/20256高级人工智能 史忠植粗糙集的研究粗糙集的研究 1991年波兰Pawlak教授的第一本关于粗糙集的专著Rough Sets：Theoretical Aspects of Reasoning about Data 和1992

4、年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。7/11/20257高级人工智能 史忠植研究现状分析研究现状分析2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”，邀请了创始人Z.Pawlak教授做大会报告；2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005年

5、8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会（CRSSC2005）2006第六届中国粗糙集与软计算学术研讨会在浙江师范大学7/11/20258高级人工智能 史忠植研究现状分析研究现状分析2007年粗糙集与软计算、Web智能、粒计算联合学术会议,山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议（CRSSC-CWI-CGrC2008）,河南师范大学 中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学、上海大学7/11/20259高级人工智能 史

6、忠植研究现状分析研究现状分析曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社,1998刘清.RoughSet及Rough推理.北京:科学出版社,2001张文修等.RoughSet理论与方法.北京:科学出版社,2001王国胤.RoughSet理论与知识获取.西安:西安交通大学出版社,2001史忠植.知识发现.北京:清华大学出版社,2002苗夺谦苗夺谦/王国胤王国胤/刘清刘清/林早阳林早阳/姚一姚一豫.粒计算-过去现在与展望.科学出版社,20077/11/202510高级人工智能 史忠植二、二、知识分类知识分类基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。基本粗糙集理论认为知识

7、就是人类和其他物种所固有的分类能力。例如，在现实世界中关于环境的知识主要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式，就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此，粗糙集理论假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域全域或论域论域(universeuniverse)。对于全域及知识的特性并没有任何特别假设。事实上，知识构成了某一感兴趣领域中各种分

8、类模式的一个族集(family)，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。7/11/202511高级人工智能 史忠植二、二、知识分类知识分类 为数学处理方便起见，在下面的定义中用等价关系来代替分类。一个近近似似空空间间(approximate space)（或知知识识库库）定义为一个关系系统（或二元组）K K=(U,R R)其中U（为空集）是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R R是U上等价关系的一个族集。7/11/202512高级人工智能 史忠植二、二、知识分类知识分类 设P PR R，且P P，P P中所有等价关系的交集

9、称为P P上的一种不可区分关系(indiscernbility relation)（或称难区分关系），记作IND(P P)，即 xIND(p)=xR RP 注意，IND(P P)也是等价关系且是唯一的。7/11/202513高级人工智能 史忠植二、二、知识分类知识分类 给定近似空间K K=(U,R R)，子集XU称为U上的一个概念概念(concept)，形式上，空集也视为一个概念；非空子族集P PR R所产生的不分明关系IND(P P)的所有等价类关系的集合即U/IND(P P)，称为基本知识基本知识(basic knowledge)，相应的等价类称为基本概念基本概念(basic concep

10、t)；特别地，若关系QR R，则关系Q就称为初等知识初等知识(elementary knowledge)，相应的等价类就称为初等概念初等概念(elementary concept)。一般用大写字母P,Q,R等表示一个关系，用大写黑体字母P P,Q Q,R R等表示关系的族集；xR或R(x)表示关系R中包含元素xU的概念或等价类。为了简便起见，有时用P P代替IND(P P)。根据上述定义可知，概念即对象的集合，概念的族集（分类）就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。7/11/202514高级人工智能 史忠植二、二、知识分类知识分类 粗糙集理论与

11、传统的集合理论有着相似之处，但是它们的粗糙集理论与传统的集合理论有着相似之处，但是它们的出发点完全不同。传统集合论认为，一个集合完全是由其元出发点完全不同。传统集合论认为，一个集合完全是由其元素所决定，一个元素要么属于这个集合，要么不属于这个集素所决定，一个元素要么属于这个集合，要么不属于这个集合，即它的隶属函数合，即它的隶属函数 X X(x x)0,10,1。模糊集合对此做了拓广，模糊集合对此做了拓广，它给成员赋予一个隶属度，即它给成员赋予一个隶属度，即 X X(x x)0,10,1，使得模糊集合使得模糊集合能够处理一定的模糊和不确定数据，但是其模糊隶属度的确能够处理一定的模糊和不确定数据，

12、但是其模糊隶属度的确定往往具有人为因素，这给其应用带来了一定的不便。而且，定往往具有人为因素，这给其应用带来了一定的不便。而且，传统集合论和模糊集合论都是把隶属关系作为原始概念来处传统集合论和模糊集合论都是把隶属关系作为原始概念来处理，集合的并和交就建立在其元素的隶属度理，集合的并和交就建立在其元素的隶属度maxmax和和minmin操作上，操作上，因此其隶属度必须事先给定（传统集合默认隶属度为因此其隶属度必须事先给定（传统集合默认隶属度为1 1或或0 0）。）。在粗糙集中，隶属关系不再是一个原始概念，因此无需人为在粗糙集中，隶属关系不再是一个原始概念，因此无需人为给元素指定一个隶属度，从而避

13、免了主观因素的影响。给元素指定一个隶属度，从而避免了主观因素的影响。7/11/202515高级人工智能 史忠植Information Systems/TableslIS is a pair(U,A)lU is a non-empty finite set of objects.lA is a non-empty finite set of attributes such that for every l is called the value set of a.AgeLEMSx16-3050 x216-300 x331-451-25x431-451-25x546-6026-49x616-302

14、6-49x746-6026-497/11/202516高级人工智能 史忠植Decision Systems/TableslDS:l is the decision attribute(instead of one we can consider more decision attributes).lThe elements of A are called the condition attributes.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-602

15、6-49no7/11/202517高级人工智能 史忠植Issues in the Decision Tablel相同或不可区分的对象可能被表示多次相同或不可区分的对象可能被表示多次The same or indiscernible objects may be represented several times.l有些属性可能是多余的 Some of the attributes may be superfluous.7/11/202518高级人工智能 史忠植不可区分性不可区分性IndiscernibilitylThe equivalence relation A binary relatio

16、n which is reflexive(xRx for any object x),symmetric(if xRy then yRx),and transitive(if xRy and yRz then xRz).lThe equivalence class of an element consists of all objects such that xRy.7/11/202519高级人工智能 史忠植不可区分性不可区分性Indiscernibility(2)lLet IS=(U,A)be an information system,then with any there is an a

17、ssociated equivalence relation:where is called the B-indiscernibility relation.lIf then objects x and x are indiscernible from each other by attributes from B.lThe equivalence classes of the B-indiscernibility relation are denoted by 7/11/202520高级人工智能 史忠植不可区分性实例不可区分性实例 IndiscernibilitylThe non-empty

18、 subsets of the condition attributes are Age,LEMS,and Age,LEMS.lIND(Age)=x1,x2,x6,x3,x4,x5,x7lIND(LEMS)=x1,x2,x3,x4,x5,x6,x7lIND(Age,LEMS)=x1,x2,x3,x4,x5,x7,x6.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no7/11/202521高级人工智能 史忠植概念的边界概念的边界 知识的粒度性

19、是造成使用已有知识不能精确地表示知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓的关于不精确的某些概念的原因。这就产生了所谓的关于不精确的“边界边界”思想。著名哲学家思想。著名哲学家FregeFrege认为认为“概念必须概念必须有明确的边界。没有明确边界的概念，将对应于一有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域个在周围没有明确界线的区域”。粗糙集理论中的。粗糙集理论中的模糊性就是一种基于边界的概念，即一个不精确的模糊性就是一种基于边界的概念，即一个不精确的概念具有模糊的不可被明确划分的边界。概念具有模糊的不可被明确划分的边界。为刻画模为刻

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

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

22、cept)，形式上，空集也视为一个概念；非空子族集P PR R所产生的不分明关系IND(P P)的所有等价类关系的集合即U/IND(P P)，称为基基本本知知识识(basic knowledge)，相应的等价类称为基基本本概概念念(basic concept)；特别地，若关系QR R，则 关 系 Q就 称 为 初初 等等 知知 识识(elementary knowledge)，相应的等价类就称为初初等等概概念念(elementary concept)。7/11/202525高级人工智能 史忠植上近似、下近似和边界区域上近似、下近似和边界区域定义定义5:X的下近似：R*(X)=x:(xU)(xR

23、X)X的上近似：R*(X)=x:(xU)(xRX)X的边界区域：BNR(X)=R*(X)R*(X)若BNR(X)，则集合X就是一个粗糙概念。下近似包含了所有使用知识R可确切分类到X的元素，上近似则包含了所有那些可能是属于X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。POSR(X)=R*(X)称为集合X的R-正区域正区域，NEGR(X)=UR*(X)称为集合X的R-反区域反区域。7/11/202526高级人工智能 史忠植Lower&UpperApproximations(2)Lower Approximation:Upper Approximation:上近似、下近似

24、和边界区域上近似、下近似和边界区域7/11/202527高级人工智能 史忠植新型的隶属关系新型的隶属关系 传统集合论中，一个元素的隶属函数X(x)0,1。而粗糙集理论中，X(x)0,1 定定义义4 4 设XU且xU,集合X的粗粗糙糙隶隶属属函函数数(rough membership function)定义为 其中R是不分明关系，R(x)=xR=y:(yU)(yRx)=1当且仅当xRX 0当且仅当xRX=0当且仅当xRX=7/11/202528高级人工智能 史忠植隶属关系隶属关系显然有显然有 0,10,1。我们可以看到，这里的隶属关系我们可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的

25、可以被解是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率，能够从全域上的个体加以计算，释为一种条件概率，能够从全域上的个体加以计算，而不是主观给定的。而不是主观给定的。7/11/202529高级人工智能 史忠植集近似实例集近似实例 Set ApproximationlLet W=x|Walk(x)=yes.lThe decision class,Walk,is rough since the boundary region is not empty.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-60

26、26-49nox616-3026-49yesx746-6026-49no7/11/202530高级人工智能 史忠植集近似实例集近似实例 Set Approximation(2)yesyes/nonox1,x6x3,x4x2,x5,x7AW7/11/202531高级人工智能 史忠植UsetU/RR:subset of attributes粗糙粗糙集近似图示集近似图示7/11/202532高级人工智能 史忠植Lower&Upper 近似近似 (3)X1=u|Flu(u)=yes=u2,u3,u6,u7RX1=u2,u3=u2,u3,u6,u7,u8,u5X2=u|Flu(u)=no=u1,u4,u

27、5,u8RX2=u1,u4 =u1,u4,u5,u8,u7,u6TheindiscernibilityclassesdefinedbyR=Headache,Temp.areu1,u2,u3,u4,u5,u7,u6,u8.7/11/202533高级人工智能 史忠植Lower&Upper 近似近似(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,u

28、6u1u4u3X1X2u5u7u2u6u87/11/202534高级人工智能 史忠植例例1 1：设有一知识库K=U,p,q,r其中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,x8,x3,x6,x7U/q=x1,x3,x5,x6,x2,x4,x7,x8 U/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,

29、x7Lower&Upper 近似近似(5)7/11/202535高级人工智能 史忠植近似度近似度Accuracy of Approximation where|X|denotes the cardinality of Obviously If X is crisp with respect to B.If X is rough with respect to B.7/11/202536高级人工智能 史忠植近似性质近似性质Properties of Approximationsimpliesand7/11/202537高级人工智能 史忠植近似性质近似性质Properties of Approxi

30、mations(2)where-XdenotesU-X.7/11/202538高级人工智能 史忠植三、三、知识的约简知识的约简一般约简 定义定义6 6 设R R是等价关系的一个族集，且设RR R。若IND(R R)=IND(R RR)，则称关系R在族集R R之中是可省可省的(dispensable)否则就是不可省不可省的。若族集R R中的每个关系R都是不可省的则称族集R R是独立的独立的(independent)否则就是依赖的依赖的或非独立非独立的。定义定义7 7 若Q QP P是独立的并且IND(Q Q)=IND(P P)则称Q Q是关系族集P P的一个约简约简(reduct)。在族集P P

31、中所有不可省的关系的集合称为P P的核核(core)以CORE(P P)来表示。显然，族集P P有多个约简（约简的不唯一性）。定理定理1 1 族集P P的核等于P P的所有约简的交集。即CORE(P P)=RED(P P)7/11/202539高级人工智能 史忠植例例2 2：取前面的例1若P=p,q,r则IND(P)=x1,x5,x2,x8,x3,x4,x6,x7IND(P-p)=x1,x5,x2,x7,x8,x3,x4,x6IND(P)所以p是不可省的同理可得q、r是可省的。这样由p,q,r三个等价关系组成的集合和p,q、p,r定义了相同的不分明关系。又IND(p,q)IND(p)IND(p

32、q)IND(q)则p,q和p,r就是P的约简而且p是P的核也就是说p是绝对不能省的 三、三、知识的约简知识的约简7/11/202540高级人工智能 史忠植相对约简相对约简定义定义8 8 设P P和Q Q是全域U上的等价关系的族集，所谓族集Q Q的P-P-正区域正区域(P-positive region of Q Q)，记作POSP P(Q Q)=P P*(X)族集Q Q的P-P-正区域正区域是全域U的所有那些使用分类U/P P所表达的知识，能够正确地分类于U/Q Q的等价类之中的对象的集合。定义定义9 9 设P P和Q Q是全域U上的等价关系的族集，RP P。若POSIND(P P)(IND(

33、Q Q)=POSIND(P P-R)(IND(Q Q)则称关系R在族集P P中是Q-Q-可可省省的的否则称为Q-Q-不不可可省省的的如果在族集P P中的每个关系R都是Q Q-不可省的则称P P关于Q Q是独独立立的的否则就称为是依赖的依赖的。7/11/202541高级人工智能 史忠植相对约简相对约简定义定义10 SP称为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-约

34、简的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集P的所有Q-约简的族集。7/11/202542高级人工智能 史忠植知识的依赖性知识的依赖性知识的依赖性可形式定义如下：定义定义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。7/11/202543高级人工智能 史忠植知

35、识的依赖性知识的依赖性依赖性也可以是部分成立的也就是从知识P能推导出知识Q的一部分知识，或者说知识Q只有一部分依赖于知识P的。部分依赖性（部分可推导性）可以由知识的正区域来定义。现在我们形式地定义部分依赖性。定义定义12 设K=(U,R)是一个知识库P,QR我们称知识知识Q以以依赖度依赖度k(0 k1)依赖于知识依赖于知识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。7/11/202

36、544高级人工智能 史忠植四、四、决策表的约简决策表的约简 决策表 决策表是一类特殊而重要的知识表达系统，它指当满足某些条件时，决策（行为）应当怎样进行。多数决策问题都可以用决策表形式来表示，这一工具在决策应用中起着重要的作用。决策表可以定义如下：S=(U,A)为一信息系统，且C,DA是两个属性子集，分别称为条件属性和决策属性，且CD=A，CD=，则该信息系统称为决策表，记作T=(U,A,C,D)或简称CD决策表。关系IND(C)和关系IND(D)的等价类分别称为条件类和决策类。7/11/202545高级人工智能 史忠植身高性别视力录取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女

37、一般是e6矮男好是表1一决策表身高、性别、视力为条件属性，录取为决策属性四、四、决策表的约简决策表的约简7/11/202546高级人工智能 史忠植决策规则决策规则决策表中的每一行对应诸如形式的决策规则，和分别称为决策规则的前驱和后继。当决策表S中决策规则为真时，我们说该决策规则是S中一致的，否则说该决策规则是S中不一致的。若决策规则是S中一致的，相同的前驱必导致相同的后继；但同一种后继不一定必需是同一前驱产生的。如表1第一行对应决策规则：身高(高)性别(男)视力(差)录取(否)7/11/202547高级人工智能 史忠植决策表的一致性决策表的一致性命题命题1 1当且仅当 CD，决策表T=(U,A

38、C,D)是一致的。由命题1，很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于1时，我们说决策表是一致的，否则不一致。7/11/202548高级人工智能 史忠植决策表的分解决策表的分解 命题命题2 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；另一个

39、表则完全一致，依赖度为1。当然，只有依赖度大于0且不等于1时，这一分解才能进行。7/11/202549高级人工智能 史忠植表2不一致决策表 a、b、c为条件属性，d、e为决策属性 1、5产生不一致Ua b c d e123456781022001112200111102210201220112111201101决策表的分解决策表的分解7/11/202550高级人工智能 史忠植表3完全一致的决策表Ua b c d e346720011110222201121112表4完全不一致的决策表Ua b c d e125810220011121020101101决策表的分解决策表的分解7/11/20255

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

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

42、最小属性子集，它能够区分用整个属性集合A可区分的所有对象。7/11/202554高级人工智能 史忠植SkowronSkowron的约简方法的约简方法对于每一个分明矩阵M(S)对应唯一的分明函数fM(S)Discernibility Function，它的定义如下：信息系统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。如此，可事先给定一错

43、误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X,Y)。7/11/202564高级人工智能 史忠植可变精度粗糙集模型可变精度粗糙集模型在 此 基 础 上，设 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 (

44、C(Xi,X)1)。以此类推，我们还可以定义-依依赖赖、-约约简简等与传统粗糙集模型相对应的概念。7/11/202565高级人工智能 史忠植相似模型相似模型在数据中存在缺失的属性值的时候（在数据库中很普遍），不分明关系或等价关系无法处理这种情形。为扩展粗糙集的能力，有许多作者提出了用相似关系来代替不分明关系作为粗糙集的基础。在使用相似关系代替粗糙集的不分明关系后，最重要的变化就是相似类不再形成对集合的划分了，它们之间是相互重叠的。类似于等价类，可以定义相似集，即所有和某各元素x在属性集合B上相似的集合SIMb(x)。值得注意的是SIMb(x)中的元素不一定属于同一决策类，因此还需要定义相似决策

45、类，即相似集对应的决策类集合。7/11/202566高级人工智能 史忠植基于粗糙集的非单调逻辑基于粗糙集的非单调逻辑 自粗糙集理论提出以来，粗糙集理论的研究者都很重视它的逻辑研究，试图通过粗糙集建立粗糙逻辑，也相应地发表了一系列的粗糙逻辑方面的论文。7/11/202567高级人工智能 史忠植与其它数学工具的结合与其它数学工具的结合 D.Dudios和H.Prade由此提出了RoughFuzzySet和FuzzyRoughSet的概念A.Skowron和J.Grazymala-Buss认为，粗糙集理论可以看作证据理论的基础。并在粗糙集理论的框架上重新解释了证据理论的基本概念，特别是用上近似和下近

46、似的术语解释了信念(belief)和似然(plausibility)函数，进而讨论了两者之间的互补问题。7/11/202568高级人工智能 史忠植六、粗糙集的实验系统六、粗糙集的实验系统在过去几年中，建立了不少基于粗糙集的KDD系统，其中最有代表性的有LERS、ROSE、KDD-R等。1 1LERSLERSLERS(Learning from examples based on Rough Set)系统是美国Kansas大学开发的基于粗糙集的实例学习系统。它是用Common Lisp在VAX9000上实现的。LERS已经为NASA的Johnson空间中心应用了两年。此外，LERS还被广泛地用于

47、环境保护、气候研究和医疗研究 7/11/202569高级人工智能 史忠植六、粗糙集的实验系统六、粗糙集的实验系统2 2ROSEROSE波兰Poznan科技大学基于粗糙集开发了ROSE(Rough Set data Explorer),用于决策分析。它是Rough Das&Rough Class系统的新版，其中RoughDas执行信息系统数据分析任务，RoughClass支持新对象的分类，这两个系统已经在许多实际领域中得到应用。3 3KDDRKDDRKDD-R是由加拿大的Regina大学开发的基于可变精度粗糙集模型，采用知识发现的决策矩阵方法开发了KDD-R系统，这个系统被用来对医学数据分析，以

48、此产生症状与病证之间新的联系，另外它还支持电信工业的市场研究。7/11/202570高级人工智能 史忠植七、粒度计算七、粒度计算l粒度计算从广义上来说是一种看待客观世界的世界观和方法论。l粒度计算的基本思想就是使用粒而不是对象为计算单元，使用粒、粒集以及粒间关系进行计算或问题求解。7/11/202571高级人工智能 史忠植粒度计算粒度计算l1997年年Lotfi A.Zadeh 提出了粒度的概念，他认为在人类认知中存提出了粒度的概念，他认为在人类认知中存在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到从在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到从整体到部分的分解，而组

49、织却是从部分到整体的集成，而因果关系涉整体到部分的分解，而组织却是从部分到整体的集成，而因果关系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、相似及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、相似性、邻近性与功能性集聚有关的事物。性、邻近性与功能性集聚有关的事物。l粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，主要用于处理不确定的、模糊度的理论、方法、技术和工具的研究，主要用于处理不确定的、模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息粒度理的、不完整的

50、和海量的信息。粗略地讲，一方面它是模糊信息粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方面是粒度论、粗糙集理论、商空间理论、区间计算等的超集，另一方面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，应用了分组、数学的子集。具体地讲，凡是在分析问题和求解问题中，应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于粒度计算的范畴。分类、聚类以及层次化手段的一切理论与方法均属于粒度计算的范畴。信息粒度在粒度计算，词计算，感知计算理论和精化自然语言中都有信息粒度在粒度计算，词计算，感知计算理论和精化自然语言中都有反映反映 7/11/202572高级人工智能 史忠植粒度计算的必