《第七章粗糙集理论PPT课件》由会员分享，可在线阅读，更多相关《第七章粗糙集理论PPT课件（38页珍藏版）》请在金锄头文库上搜索。
1、人人 工工 智智 能能Artificial Intelligence粗糙集理论与应用粗糙集理论与应用董春游董春游(Chunyou Dong) PhD,Professor (Chunyou Dong) PhD,Professor Email:Email:研究生学院研究生学院1第十七讲 粗糙集与数据约简 不确定性理论不确定性理论1 粗糙集的基本理论与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 粗糙集的研究现状与展望粗糙集的研究现状与展望62概论：粗糙集理论的提出及发展概论：粗糙集理论的提出及发展
2、粗糙集（粗糙集（Rough SetsRough Sets）是波兰数学家）是波兰数学家Z. PawlakZ. Pawlak于于19821982年提出年提出的的11（为开发自动规则生成系统及研究软计算问题而引入）。由（为开发自动规则生成系统及研究软计算问题而引入）。由于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视。研究地域也局限在时没有引起国际计算机学界和数学界的重视。研究地域也局限在东欧一些国家，直到东欧一些国家，直到8080年代末才引起各国学者的注意。九十年代年代末才引起各国学者的注意。九十
3、年代初，人们才逐渐认识到它的意义。初，人们才逐渐认识到它的意义。 1992 1992年在波兰年在波兰KiekrzKiekrz召开了第一届国际召开了第一届国际RSRS研讨会。这次会议研讨会。这次会议着重讨论了集合近似定义的基本思想及应用，其中着重讨论了集合近似定义的基本思想及应用，其中RSRS环境下的机环境下的机器学习基础研究是这次会议的四个专题之一。器学习基础研究是这次会议的四个专题之一。3 1993 1993年在加拿大年在加拿大BanffBanff召开第召开第二届国际二届国际RSRS理论与知识发现研讨理论与知识发现研讨会。这次会议积极推动了国际上会。这次会议积极推动了国际上对对RSRS理论与
4、应用的研究。由于当理论与应用的研究。由于当时正值时正值KDDKDD（数据库知识发现）成（数据库知识发现）成为研究的热门话题，一些著名为研究的热门话题，一些著名KDDKDD学习者参加这次会议，并且介绍学习者参加这次会议，并且介绍了许多应用扩展了许多应用扩展RSRS理论的知识发理论的知识发现方法与系统。现方法与系统。 1996 1996年在日本东京召开了第年在日本东京召开了第5 5届国际届国际RSRS研讨会，推动了亚洲地研讨会，推动了亚洲地区对区对RSRS理论与应用的研究。理论与应用的研究。 1995 1995年，年，ACM CommunicationACM Communication将其列为新浮
5、现的将其列为新浮现的计算机科学的计算机科学的研究课题。研究课题。4 19981998年，国际信息科学杂志（年，国际信息科学杂志（Information Information SciencesSciences）为粗糙集理论的研究出了一期专辑）为粗糙集理论的研究出了一期专辑22，33。第一届中国第一届中国RSRS理论与软计算学术研讨会，于理论与软计算学术研讨会，于20012001年年5 5月在月在重庆举行。重庆举行。第二届中国第二届中国RSRS理论与软计算学术研讨会，于理论与软计算学术研讨会，于20022002年年1010月月在苏州大学举行。在苏州大学举行。第三届中国第三届中国RSRS理论与软计
6、算学术研讨会，于理论与软计算学术研讨会，于20032003年年8 8月在月在重庆举行。重庆举行。第四届中国第四届中国RSRS理论与软计算学术研讨会，将于理论与软计算学术研讨会，将于20042004年在年在舟山举行。舟山举行。第八届中国粗糙集与软计算学术会议第八届中国粗糙集与软计算学术会议 , 2008 年 8 月 22 日至 8 月 24日在河南省新乡市召开中国5 粗糙集的理论及应用的文章粗糙集的理论及应用的文章 主要发表在以下杂志主要发表在以下杂志国内：国内： 1模式识别与人工智能模式识别与人工智能 2软件学报软件学报 3科学通报科学通报 4计算机科学计算机科学 5计算机学报计算机学报 6模
7、糊系统与数学模糊系统与数学 7计算机应用与软件计算机应用与软件 8计算机研究与发展计算机研究与发展 9计算技术与自动化计算技术与自动化 国际：国际： 1Information Sciences 2Fuzzy sets and systems 3International Journal of Computer and Information Sciences 4Communication of the ACM 5Computational Intelligence 6Journal of computer and system sciences7 AI Magazine8 AI Communi
8、cations9 European Journal of Operational Research10International Journal of Approximate Reasoning11Theoretical computer sciences12Decision support Systems13International Journal of Man-Machine studies 14Fundamenta Informaticae15Intelligent Automation Sciences 6粗糙集理论粗糙集理论 性质：性质：粗糙集理论是一种粗糙集理论是一种处理不精确、
9、不确定与不完全数据处理不精确、不确定与不完全数据的新的数学方法。的新的数学方法。 应用领域：应用领域：机器学习与知识发现、数据挖掘、决策支持与分析、专家系机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别统、归纳推理、模式识别等方面的广泛应用，现已成为一个热门的研究领域等方面的广泛应用，现已成为一个热门的研究领域2。 RS理论主要兴趣在于它恰好反映了人们用理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性，即集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力。或依据观察，度量到的某些不确定以不完全信息或知识去处理一些不分明
10、现象的能力。或依据观察，度量到的某些不确定的结果而进行分类数据的能力的结果而进行分类数据的能力4。粗糙集理论的优点及局限性主要优点粗糙集理论的优点及局限性主要优点优点：除数据集之外，无需任何先验知识（或信息）优点：除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观对不确定性的描述与处理相对客观【说明】：【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。观性。71、不确定性理论自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。确定性现象：在一定条件下必然会出现的现象。（1）不确定
11、性的分类：随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。用概率来度量。概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律概率规律。模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律隶属规律。粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。8
12、（2）经典集合、模糊集合、粗糙集的关系经典集合认为一个集合完全有其元素所决定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数X(x)0,1是二值逻辑。模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数X(x)0,1，即在闭区间0,1可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观经验给定。粗糙集合把用于分分类类的的知知识识引引入入集集合合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：x肯定不属于X；x肯定属于X；x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的
13、关于论域的知识。粗糙集的隶属函数为阶梯状，对不确定性信息的描述是粗糙的，但粗糙隶属函数是可计算的。粗糙集主要用于对信息系统进行约简和分类行约简和分类。1.00.80.60.40.20.00.20.40.60.81.092、 粗糙集的基本理论与方法 粗糙集的基本概念粗糙集的基本概念1 粗糙集的基本思想粗糙集的基本思想2 粗糙集的基本特点粗糙集的基本特点3101）粗糙集的基本概念（1）知识与分类在在粗粗糙糙集集理理论论中中，知知识识被被认认为为是是一一种种分分类类能能力力。人们的行为基本是分辨现实的或抽象的对象的能力。假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这
14、些知识能够将其划分到不同的类别。若我们对两个对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其划分开。粗糙集理论的核心是等价关系，通常用等等价价关关系系替替代代分分类类，根据这个等价关系划分样本集合为等价类。基本思想：从知识库的观点看，每每个个等等价价类类被被称称为为一一个个概概念念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。11（2）知识表达系统一个知识表达系统或信息系统S可以表示为有序四元组S=U,R,V,f其中，U=x1,x2,xn为论域，它是全体样本的集合；RCD 为属性集合，其中子集C是条件属性集，反映对象的特
15、征，D为决策属性集，反映对象的类别； 为属性值的集合，Vr表示属性r的取值范围；f:URV 为一个信息函数，用于确定U中每一个对象x的属性值，即任一xiU，rR，则f(xi,r)=Vr属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是12（3）不可分辨关系不可分辨关系在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集BR，如果对象xi,xjU，rB，当且仅当f(xf(xi i,r)=f
16、(x,r)=f(xj j,r),r)时，xi和xj是不可分辨的，简记为Ind(B)Ind(B)。不可分辨关系称为等价关系不可分辨关系称为等价关系。例如：只用黑白两种颜色把空间中的一些物体划分成两类：黑色物体、白色物体，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：黑色方物体、黑色圆物体、白色方物体、白色圆物体。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的不精确性。另一方面，不可分辨关系反映了论论域域知知识识的的颗颗粒粒性性。知识库中的知识越多
17、，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致信息量增大，存储知识库的费用越高。13（4）基本集合由论域中相互不可分辨的对象组成的集合称之为基本集合，它是组成论域知识的颗粒。例如：考虑条件属性：头疼和肌肉疼。对于x1,x2,x3这三个对象是不可分辨的。x4,x6在这两个属性上也是不可分辨的。由此构成的不可分辨集x1,x2,x3,x4,x6,x5被称为基本集合。设论域U为有限集，R是U的等价关系簇，则K=U,R称为知识库，知识库的知识粒度由不可分辨关系Ind(R)的等价类反映。属性对象条件属性C决策属性D头疼r1肌肉疼
18、r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是14（5）下近似集和上近似集下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成的集合，即R R- -(X)=x(X)=x U,xU,xR R XX其中，其中， x xR R 表示等价关系表示等价关系R R下包含元素下包含元素x x的等价类。的等价类。上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对象所组成的集合，即R(X)=xU,xR X其中， xR 表示等价关系R下包含元素x的等价类。给定知识表达系统S=U,R,V,f，对于每个样本子集X U和等价关系R，所有包含于X的
19、基本集的并（逻辑和）为R-(X)；所有与X的交(逻辑积)不为空集的基本集的并为R(X)。15（6）正域、负域和边界域正域：Pos(X)=R-(X)，即根据知识R，U中能完全确定地归入集合X的元素的集合。负域：Neg(X)=U-R-(X)，即根据知识R，U中不能确定一定属于集合X的元素的集，它们是属于X的补集。边界域：Bnd(X)= R-(X) - R-(X) ，边界域是某种意义上论域的不确定域，根据知识R，U中既不是肯定归入集合X，又不能肯定归入集合X，的元素构成的集合。边界域为集合X的上近似与下近似之差，如果Bnd(X)是空集，则称集合X关于R是清晰的；反之，如果Bnd(X)不是空集，则称集
20、合X为关于R的粗糙集。因此，粗糙集中的“粗糙”（不确定性）主要体现在边界域的存在。集合X的边界域越大，其确定性程度就越小。16（7）粗糙度（近似精确度）对于知识R（即属性子集），样本子集X的不确定程度可以用粗糙度R(X)来表示为R(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个数）。0R(X)1，如果R(X)1，则称集合X相对于R是确定的，如果R(X)kQ。 当k=1时，称知识Q完全依赖于知识P； 当0k1时，称知识Q部分依赖于知识P； 当k=0时，称知识Q完全独立于知识P。 依赖度k反映了根据知识P将对象分类到Q的基本概念中去的能力。确切的说，当PkQ时，论域中共有kCard(U)个属于Q的P正域的对象，这些对象可以依据知识P分类到知识Q的基本概念中去。例 U=x1,x2,x8，U/P=x1,x2,x3,x4,x5,x6,x7,x8，U/Q= x1,x2,x3,x4,x5,x6,x7,x8，求依赖度k。解：PosP(Q)=x1x2x3,x4x5,x6=x1,x2,x3,x4,x5,x6 k=6/8=0.75 即知识Q相对于知识P的依赖度为0.7535363738
