第七章粗糙集理论

1人工智能ArtificialIntelligence粗糙集理论与应用董春游(ChunyouDong)PhD,ProfessorEmail:[e-mail]研究生学院2第十七讲粗糙集与数据约简不确定性理论1粗糙集的基本理论与方法2知识的约简3决策表的约简4粗糙集数据约简的具体实现与应用5粗糙集的研究现状与展望63概论：粗糙集理论的提出及发展粗糙集（RoughSets）是波兰数学家Z.Pawlak于1982年提出的[1]（为开发自动规则生成系统及研究软计算问题而引入）。由于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视。研究地域也局限在东欧一些国家，直到80年代末才引起各国学者的注意。九十年代初，人们才逐渐认识到它的意义。1992年在波兰Kiekrz召开了第一届国际RS研讨会。这次会议着重讨论了集合近似定义的基本思想及应用，其中RS环境下的机器学习基础研究是这次会议的四个专题之一。41993年在加拿大Banff召开第二届国际RS理论与知识发现研讨会。这次会议积极推动了国际上对RS理论与应用的研究。由于当时正值KDD（数据库知识发现）成为研究的热门话题，一些著名KDD学习者参加这次会议，并且介绍了许多应用扩展RS理论的知识发现方法与系统。1996年在日本东京召开了第5届国际RS研讨会，推动了亚洲地区对RS理论与应用的研究。1995年，ACMCommunication将其列为新浮现的计算机科学的研究课题。51998年，国际信息科学杂志（InformationSciences）为粗糙集理论的研究出了一期专辑[2，3]。第一届中国RS理论与软计算学术研讨会，于2001年5月在重庆举行。第二届中国RS理论与软计算学术研讨会，于2002年10月在苏州大学举行。第三届中国RS理论与软计算学术研讨会，于2003年8月在重庆举行。第四届中国RS理论与软计算学术研讨会，将于2004年在舟山举行。第八届中国粗糙集与软计算学术会议,2008年8月22日至8月24日在河南省新乡市召开中国6粗糙集的理论及应用的文章主要发表在以下杂志国内：1．模式识别与人工智能2．软件学报3．科学通报4．计算机科学5．计算机学报6．模糊系统与数学7．计算机应用与软件8．计算机研究与发展9．计算技术与自动化国际：1．InformationSciences2．Fuzzysetsandsystems3．InternationalJournalofComputerandInformationSciences4．CommunicationoftheACM5．ComputationalIntelligence6．Journalofcomputerandsystemsciences7．AIMagazine8．AICommunications9．EuropeanJournalofOperationalResearch10．InternationalJournalofApproximateReasoning11．Theoreticalcomputersciences12．DecisionsupportSystems13．InternationalJournalofMan-Machinestudies14．FundamentaInformaticae15．IntelligentAutomationSciences7粗糙集理论性质：粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法。应用领域：机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别等方面的广泛应用，现已成为一个热门的研究领域[2]。RS理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力。或依据观察，度量到的某些不确定的结果而进行分类数据的能力[4]。粗糙集理论的优点及局限性主要优点优点：除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观……【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。81、不确定性理论•自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。•确定性现象：在一定条件下必然会出现的现象。（1）不确定性的分类：–随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。用概率来度量。概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律——概率规律。–模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律——隶属规律。–粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。9（2）经典集合、模糊集合、粗糙集的关系–经典集合认为一个集合完全有其元素所决定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数μX(x)∊{0,1}是二值逻辑。–模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数μX(x)∊[0,1]，即在闭区间[0,1]可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观经验给定。–粗糙集合把用于分类的知识引入集合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：①x肯定不属于X；②x肯定属于X；③x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的关于论域的知识。粗糙集的隶属函数为阶梯状，对不确定性信息的描述是粗糙的，但粗糙隶属函数是可计算的。粗糙集主要用于对信息系统进行约简和分类。1.00.80.60.40.20.00.20.40.60.81.0102、粗糙集的基本理论与方法粗糙集的基本概念1粗糙集的基本思想2粗糙集的基本特点3111）粗糙集的基本概念（1）知识与分类–在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分辨现实的或抽象的对象的能力。–假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其划分开。–粗糙集理论的核心是等价关系，通常用等价关系替代分类，根据这个等价关系划分样本集合为等价类。基本思想：从知识库的观点看，每个等价类被称为一个概念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。12（2）知识表达系统–一个知识表达系统或信息系统S可以表示为有序四元组S={U,R,V,f}其中，U={x1,x2,…,xn}为论域，它是全体样本的集合；R＝C∪D为属性集合，其中子集C是条件属性集，反映对象的特征，D为决策属性集，反映对象的类别；为属性值的集合，Vr表示属性r的取值范围；f:U×R→V为一个信息函数，用于确定U中每一个对象x的属性值，即任一xi∊U，r∊R，则f(xi,r)=VrRrrVV属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是13•（3）不可分辨关系–在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集B⊆R，如果对象xi,xj∊U，∀r∊B，当且仅当f(xi,r)=f(xj,r)时，xi和xj是不可分辨的，简记为Ind(B)。不可分辨关系称为等价关系。–例如：只用黑白两种颜色把空间中的一些物体划分成两类：{黑色物体}、{白色物体}，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：{黑色方物体}、{黑色圆物体}、{白色方物体}、{白色圆物体}。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。–不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的不精确性。–另一方面，不可分辨关系反映了论域知识的颗粒性。知识库中的知识越多，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致信息量增大，存储知识库的费用越高。14（4）基本集合–由论域中相互不可分辨的对象组成的集合称之为基本集合，它是组成论域知识的颗粒。–例如：考虑条件属性：头疼和肌肉疼。对于x1,x2,x3这三个对象是不可分辨的。x4,x6在这两个属性上也是不可分辨的。由此构成的不可分辨集{x1,x2,x3},{x4,x6},{x5}被称为基本集合。–设论域U为有限集，R是U的等价关系簇，则K={U,R}称为知识库，知识库的知识粒度由不可分辨关系Ind(R)的等价类反映。属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是15（5）下近似集和上近似集–下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成的集合，即R-(X)={x∊U,[x]R⊆X}其中，[x]R表示等价关系R下包含元素x的等价类。–上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对象所组成的集合，即R－(X)={x∊U,[x]R∩X≠φ}其中，[x]R表示等价关系R下包含元素x的等价类。–给定知识表达系统S={U,R,V,f}，对于每个样本子集X⊆U和等价关系R，所有包含于X的基本集的并（逻辑和）为R-(X)；所有与X的交(逻辑积)不为空集的基本集的并为R－(X)。16（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)不是空集，则称集合X为关于R的粗糙集。因此，粗糙集中的“粗糙”（不确定性）主要体现在边界域的存在。集合X的边界域越大，其确定性程度就越小。BUN（X))(XHNEG(X)X的边界线图6.1粗糙集概念示意图其中，)(XH=)(XH+BUN(X)；U为整个方框区域。17•（7）粗糙度（近似精确度）–对于知识R（即属性子集），样本子集X的不确定程度可以用粗糙度αR(X)来表示为–αR(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个数）。–0≤αR(X)≤1，如果αR(X)＝1，则称集合X相对于R是确定的，如果αR(X)1则称集合X相对于R是粗糙的，αR(X)可认为是在等价关系R下逼近集合X的精度。–定义：由属性集B定义X的近似质量为–表示通过B中属性被正确分类的对象的相对频率，0《《1)(XBXRCardXRCardXRXXBXB)()(；，（X）BB00时当且仅当；，（X）BB11时当且仅当)(XB18例1：以医疗信息表为例，对于属性子集R={头疼,肌肉疼}={r1,r2},计算样本子集X={x1,x2,x5}的上近似集、下近似集、正域、边界域。解：①计算论域U的所有R基本集：U|Ind(R)={{x1,x2,x3},{x4,x6},{x5}}令R1={x1,x2,x3}R2={x4,