1、2018/9/25,高级人工智能 史忠植,1,知识发现（数据挖掘) 第七章,史忠植 中国科学院计算技术研究所,粗 糙 集 Rough Set,2018/9/25,高级人工智能 史忠植,2,内容提要,一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统七、粒度计算简介,2018/9/25,高级人工智能 史忠植,3,一、 概述,现实生活中有许多含糊现象并不能简单地用真、假值来表示如何表示和处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词，他把它归结到边界线上，也就是说在全域上存在一些个体既不能在其某个子
2、集上分类，也不能在该子集的补集上分类。,2018/9/25,高级人工智能 史忠植,4,模糊集,1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。,2018/9/25,高级人工智能 史忠植,5,粗糙集的提出,20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集（Rough Set）他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完
3、全由数据决定，所以更有客观性 。,2018/9/25,高级人工智能 史忠植,6,粗糙集的研究,粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。,2018/9/25,高级人工智能 史忠植,7,粗糙集的研究,1991年波兰Pawlak教授的第一本关于粗糙集的专著Rough Sets：Theoretical Aspects of Reasoning about Data 和1992年
4、R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。,2018/9/25,高级人工智能 史忠植,8,研究现状分析,2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”，邀请了创始人Z. Pawlak教授做大会报告；2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆 第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005年
5、8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会（CRSSC2005）2006第六届中国粗糙集与软计算学术研讨会在 浙江师范大学,2018/9/25,高级人工智能 史忠植,9,研究现状分析,2007年粗糙集与软计算、Web智能、粒计算联合学术会议, 山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议（CRSSC-CWI-CGrC2008）, 河南师范大学 中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学 、上海大学,2018/9/25,高级人工
6、智能 史忠植,10,研究现状分析,曾黄麟. 粗集理论及其应用(修订版). 重庆: 重庆大学出版社, 1998刘清. Rough Set及Rough推理. 北京: 科学出版社, 2001张文修等. Rough Set理论与方法. 北京: 科学出版社, 2001王国胤. Rough Set理论与知识获取. 西安: 西安交通大学出版社, 2001史忠植. 知识发现. 北京: 清华大学出版社, 2002苗夺谦/王国胤/刘清/林早阳/姚一 豫. 粒计算-过去现在与展望. 科学出版社, 2007,2018/9/25,高级人工智能 史忠植,11,二、 知识分类,基本粗糙集理论认为知识就是人类和其他物种所固有
7、的分类能力。例如，在现实世界中关于环境的知识主要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式，就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此，粗糙集理论假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域或论域(universe)。对于全域及知识的特性并没有任何特别假设。事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集(family)，这个族集提供了
8、关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。,2018/9/25,高级人工智能 史忠植,12,二、 知识分类,为数学处理方便起见，在下面的定义中用等价关系来代替分类。一个近似空间(approximate space)（或知识库）定义为一个关系系统（或二元组） K=(U,R) 其中U（ 为空集）是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R是U上等价关系的一个族集。,2018/9/25,高级人工智能 史忠植,13,二、 知识分类,设PR，且P ，P中所有等价关系的交集称为P上的一种不可区分关系(indiscernbility relation)（或称难
9、区分关系），记作IND(P)，即 xIND(p)= xR RP 注意，IND(P)也是等价关系且是唯一的。,2018/9/25,高级人工智能 史忠植,14,二、 知识分类,给定近似空间K=(U, R)，子集XU称为U上的一个概念(concept)，形式上，空集也视为一个概念；非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识(basic knowledge)，相应的等价类称为基本概念(basic concept)；特别地，若关系QR，则关系Q就称为初等知识(elementary knowledge)，相应的等价类就称为初等概念(elementar
10、y concept)。 一般用大写字母P,Q,R等表示一个关系，用大写黑体字母P,Q,R等表示关系的族集；xR或R(x)表示关系R中包含元素xU的概念或等价类。为了简便起见，有时用P代替IND(P)。 根据上述定义可知，概念即对象的集合，概念的族集（分类）就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。,2018/9/25,高级人工智能 史忠植,15,二、 知识分类,粗糙集理论与传统的集合理论有着相似之处，但是它们的出发点完全不同。传统集合论认为，一个集合完全是由其元素所决定，一个元素要么属于这个集合，要么不属于这个集合，即它的隶属函数X(x)0,1。模
11、糊集合对此做了拓广，它给成员赋予一个隶属度，即X(x)0,1，使得模糊集合能够处理一定的模糊和不确定数据，但是其模糊隶属度的确定往往具有人为因素，这给其应用带来了一定的不便。而且，传统集合论和模糊集合论都是把隶属关系作为原始概念来处理，集合的并和交就建立在其元素的隶属度max和min操作上，因此其隶属度必须事先给定（传统集合默认隶属度为1或0）。在粗糙集中，隶属关系不再是一个原始概念，因此无需人为给元素指定一个隶属度，从而避免了主观因素的影响。,2018/9/25,高级人工智能 史忠植,16,Information Systems/Tables,IS is a pair (U, A)U is
12、a non-empty finite set of objects.A is a non-empty finite set of attributes such that for every is called the value set of a.,Age LEMS,x 16-30 50x2 16-30 0x3 31-45 1-25x4 31-45 1-25x5 46-60 26-49x6 16-30 26-49x7 46-60 26-49,2018/9/25,高级人工智能 史忠植,17,Decision Systems/Tables,DS: is the decision attribut
13、e (instead of one we can consider more decision attributes).The elements of A are called the condition attributes.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2018/9/25,高级人工智能 史忠植,18,Issues in the Decision Table,相同或
14、不可区分的对象可能被表示多次The same or indiscernible objects may be represented several times.有些属性可能是多余的 Some of the attributes may be superfluous.,2018/9/25,高级人工智能 史忠植,19,不可区分性Indiscernibility,The equivalence relation A binary relation which is reflexive (xRx for any object x) , symmetric (if xRy then yRx), and
15、 transitive (if xRy and yRz then xRz). The equivalence class of an element consists of all objects such that xRy.,2018/9/25,高级人工智能 史忠植,20,不可区分性Indiscernibility (2),Let IS = (U, A) be an information system, then with any there is an associated equivalence relation: where is called the B-indiscernibil
16、ity relation.If then objects x and x are indiscernible from each other by attributes from B.The equivalence classes of the B-indiscernibility relation are denoted by,2018/9/25,高级人工智能 史忠植,21,不可区分性实例 Indiscernibility,The non-empty subsets of the condition attributes are Age, LEMS, and Age, LEMS.IND(Ag
17、e) = x1,x2,x6, x3,x4, x5,x7IND(LEMS) = x1, x2, x3,x4, x5,x6,x7IND(Age,LEMS) = x1, x2, x3,x4, x5,x7, x6.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2018/9/25,高级人工智能 史忠植,22,概念的边界,知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓
18、的关于不精确的“边界”思想。著名哲学家Frege认为“概念必须有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域”。粗糙集理论中的模糊性就是一种基于边界的概念，即一个不精确的概念具有模糊的不可被明确划分的边界。为刻画模糊性，每个不精确概念由一对称为上近似与下近似的精确概念来表示，它们可用隶属函数定义,2018/9/25,高级人工智能 史忠植,23,粗糙集的基本定义,知识的分类观点 粗糙集理论假定知识是一种对对象进行分类的能力。而知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域或论域(universe)。为数学处理方便起见，在下面
19、的定义中用等价关系来代替分类。,2018/9/25,高级人工智能 史忠植,24,粗糙集的基本定义,定义1 一个近似空间(approximate space)(或知识库)定义为一个关系系统(或二元组)K=(U, R)，其中U(为空集)是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R是U上等价关系的一个族集。定义2 设PR，且P ，P中所有等价关系的交集称为P上的一种不分明关系(indiscernbility relation)（或称不可区分关系），记作IND(P),2018/9/25,高级人工智能 史忠植,25,粗糙集的基本定义,定义3 给定近似空间K=(U, R)，子集X
20、U称为U上的一个概念(concept)，形式上，空集也视为一个概念；非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识(basic knowledge)，相应的等价类称为基本概念(basic concept)；特别地，若关系QR，则关系Q就称为初等知识(elementary knowledge)，相应的等价类就称为初等概念(elementary concept)。,2018/9/25,高级人工智能 史忠植,26,上近似、下近似和边界区域,定义5:X的下近似：R*(X)=x:(xU) (xRX ) X的上近似：R*(X)=x:(xU) (xRX )
21、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-反区域。,2018/9/25,高级人工智能 史忠植,27,Lower & Upper Approximations (2),Lower Approximation:,Upper Approximation:,上近似、下近似和边界区域,2018/9/25,高级
22、人工智能 史忠植,28,新型的隶属关系,传统集合论中，一个元素的隶属函数X(x)0,1。而粗糙集理论中，X(x)0,1 定义4 设XU且xU,集合X的粗糙隶属函数(rough membership function) 定义为,其中R是不分明关系，R(x)=xR=y:(yU)(yRx),=1当且仅当xRX,0当且仅当xRX,=0当且仅当xRX=,2018/9/25,高级人工智能 史忠植,29,隶属关系,显然有 0,1。我们可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率，能够从全域上的个体加以计算，而不是主观给定的。,2018/9/25,高级人工智能 史忠植,
23、30,集近似实例 Set Approximation,Let W = x | Walk(x) = yes. The decision class, Walk, is rough since the boundary region is not empty.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2018/9/25,高级人工智能 史忠植,31,集近似实例 Set Approxim
24、ation (2),yes,yes/no,no,x1,x6,x3,x4,x2, x5,x7,AW,2018/9/25,高级人工智能 史忠植,32,U,set,U/RR : subset of attributes,粗糙集近似图示,2018/9/25,高级人工智能 史忠植,33,Lower & 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
25、, u8, u7, u6,The indiscernibility classes defined by R = Headache, Temp. are u1, u2, u3, u4, u5, u7, u6, u8.,2018/9/25,高级人工智能 史忠植,34,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,u8,RX1 = u2, u3 = u2, u3,
26、 u6, u7, u8, u5,RX2 = u1, u4 = u1, u4, u5, u8, u7, u6,u1,u4,u3,X1,X2,u5,u7,u2,u6,u8,2018/9/25,高级人工智能 史忠植,35,例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,
27、x3,x4,x6,x7 对于U上的子集X1=x1,x4,x7可得到P* X1=x4x7=x4 ,x7P* X1=x1 ,x5x4x7=x1 ,x4 ,x5 ,x7,Lower & Upper 近似(5),2018/9/25,高级人工智能 史忠植,36,近似度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.,2018/9/25,高级人工智能 史忠植,37,近似性质Prop
28、erties of Approximations,implies,and,2018/9/25,高级人工智能 史忠植,38,近似性质Properties of Approximations (2),where -X denotes U - X.,2018/9/25,高级人工智能 史忠植,39,三、 知识的约简,一般约简 定义6 设R是等价关系的一个族集，且设RR。若IND(R)=IND(RR)，则称关系R在族集R之中是可省的(dispensable)否则就是不可省的。若族集R中的每个关系R都是不可省的则称族集R是独立的(independent)否则就是依赖的或非独立的。 定义7 若QP是独立的并
29、且IND(Q)=IND(P)则称Q是关系族集P的一个约简(reduct) 。在族集P中所有不可省的关系的集合称为P的核(core) 以CORE(P)来表示。 显然，族集P有多个约简（约简的不唯一性）。 定理1 族集P的核等于P的所有约简的交集。即CORE(P)=RED(P),2018/9/25,高级人工智能 史忠植,40,例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
30、定义了相同的不分明关系。又IND(p,q)IND(p) IND(pq)IND(q)则p,q和p, r就是P的约简而且p是P的核也就是说p是绝对不能省的,三、 知识的约简,2018/9/25,高级人工智能 史忠植,41,相对约简,定义8 设P和Q是全域U上的等价关系的族集，所谓族集Q的P-正区域(P-positive region of Q)，记作,POSP(Q)=,P*(X),族集Q的P-正区域是全域U的所有那些使用分类U/P所表达的知识，能够正确地分类于U/Q的等价类之中的对象的集合。定义9 设P和Q是全域U上的等价关系的族集，RP。若POSIND(P)(IND(Q)=POSIND(P-R)
31、(IND(Q) 则称关系R在族集P中是Q-可省的否则称为Q-不可省的如果在族集P中的每个关系R都是Q-不可省的则称P关于Q是独立的否则就称为是依赖的。,2018/9/25,高级人工智能 史忠植,42,相对约简,定义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-约简的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集P的所有Q-约简的族集。,2018/9
32、/25,高级人工智能 史忠植,43,知识的依赖性,知识的依赖性可形式定义如下：定义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。,2018/9/25,高级人工智能 史忠植,44,知识的依赖性,依赖性也可以是部分成立的也就是从知识P能推导出知识Q的一部分知识，或者说知识Q只有一部分依赖于知识P的。部
33、分依赖性（部分可推导性）可以由知识的正区域来定义。现在我们形式地定义部分依赖性。定义12 设K=(U, R)是一个知识库P, QR我们称知识Q以依赖度k(0 k 1)依赖于知识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。,2018/9/25,高级人工智能 史忠植,45,四、 决策表的约简,决策表 决策表是一类特殊而重要的知识表达系统，它指当满足某些条件时，决策（行为）应当怎样进行。多数决策问题都可以用决
34、策表形式来表示，这一工具在决策应用中起着重要的作用。 决策表可以定义如下： S=(U, A)为一信息系统，且C, DA是两个属性子集，分别称为条件属性和决策属性，且CD=A，CD=，则该信息系统称为决策表，记作T=(U, A, C, D)或简称CD决策表。关系IND(C)和关系IND(D)的等价类分别称为条件类和决策类。,2018/9/25,高级人工智能 史忠植,46,表1 一决策表 身高、性别、视力为条件属性，录取为决策属性,四、 决策表的约简,2018/9/25,高级人工智能 史忠植,47,决策规则,决策表中的每一行对应诸如 形式的决策规则，和分别称为决策规则的前驱和后继 。当决策表S中决
35、策规则为真时，我们说该决策规则是S中一致的，否则说该决策规则是S中不一致的。若决策规则是S中一致的，相同的前驱必导致相同的后继；但同一种后继不一定必需是同一前驱产生的。 如表1第一行对应决策规则： 身高(高)性别(男)视力(差) 录取(否),2018/9/25,高级人工智能 史忠植,48,决策表的一致性,命题1当且仅当 CD，决策表T=(U, A, C, D)是一致的。由命题1，很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于1时，我们说决策表是一致的，否则不一致。,2018/9/25,高级人工智能 史忠植,49,决策表的分解,命题2 每个决策表T=(U, A, C,
36、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时，这一分解才能进行。,2018/9/25,高级人工智能 史忠植,50,表2 不一致决策表 a、b、c为条件属性，d、e为决策属性 1、5产生不一致,决策表的分解,2018/9/25
37、,高级人工智能 史忠植,51,表3 完全一致的决策表,表4 完全不一致的决策表,决策表的分解,2018/9/25,高级人工智能 史忠植,52,一致决策表的约简,在我们制定决策时是否需要全部的条件属性，能否进行决策表的约简。约简后的决策表具有与约简前的决策表相同的功能，但是约简后的决策表具有更少的条件属性。一致决策表的约简步骤如下：(1) 对决策表进行条件属性的约简，即从决策表中消去某一列；(主要研究点)(2) 消去重复的行；(3) 消去每一决策规则中属性的冗余值。,2018/9/25,高级人工智能 史忠植,53,条件属性的约简,A.Skowron提出了分明矩阵，使核与约简等概念的计算较为简单，
38、主要思想：设S=(U,A)为一个知识表示系统，其中U =x1,x2,xn，xi为所讨论的个体，i=1,2,n，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有区别的所有属性的集合,2018/9/25,高级人工智能 史忠植,54,分明矩阵对应的核与约简,核就可以定义为分明矩阵中所有只有一个元素的矩阵项的集合，即 CORE(A)=aA：cij=(a)，对一些i,j 相对于集合包含关系运算而言，若属性集合BA是满足下列条件 Bcij，对
39、于M(S)中的任一非空项cij的一个最小属性子集，则称属性集合BA是A的一个约简。换言之，约简是这样的最小属性子集，它能够区分用整个属性集合A可区分的所有对象。,2018/9/25,高级人工智能 史忠植,55,Skowron的约简方法,对于每一个分明矩阵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。如此，可事先给定一错误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X, Y)。,
