粗糙集理论

2020/5/20陕西师范大学计算机科学学院xjy1粗糙集理论[e-mail]2020/5/20陕西师范大学计算机科学学院xjy2•粗糙集理论（RoughSetsTheory，RST）由波兰华沙理工大学的Pawlak教授于20世纪80年代提出，是用于处理含糊性和不确定性的一种数学工具。该理论主要用于从不完整的数据集中发现模式和规律，因此是机器学习、知识获取，以及进行不确定信息形式推理的基础。当前粗糙集理论主要用来处理从现实世界中获得的不完整的数据，并从其中发现模式规律。在短短二十多年时间里，粗糙集理论已经在诸如医疗诊断、过程控制、信息恢复、工业制造、卫星信号分类分析、商业经济等领域得到了广泛的应用。2020/5/20陕西师范大学计算机科学学院xjy3信息系统的定义•信息系统（InformationSystem，IS）是粗糙集理论所研究的对象。如果要应用粗糙集理论，则必须事先将所研究的对象表示为信息系统。信息系统是一个数据集，经常表示为一张数据表。该数据表的一行代表一个对象（样本），这些对象可以是事例、事件等。而数据表的每一列是对象的属性，这些属性可以是对象的特征、度量等。2020/5/20陕西师范大学计算机科学学院xjy4信息系统的定义•一个信息系统（或一个近似空间）—可以形式化地用一个四元组表示为：。其中，是全域（对象构成的集合，）；是属性（特征，变量）集；是属性值的集合，是属性a的值集，也称为属性a的值域；是一个信息函数，对每一个，和定义了一个信息函数，即信息函数指定中每一个对象的属性值。IS),,,(fVAUISU},,{2,1mxxxUAaAaVVaVVAUf:AaUxaVaxf),(fUx2020/5/20陕西师范大学计算机科学学院xjy5信息系统的定义。4}，3，2，{1V，2}，{1V，3}，2，{1V属性的值性，}x,x,x,x,x,x,x,x,x,{x=U全域，}a,a,{a=A属性集中就是一个信息系统是1下面的表:1例系统统也可称为决策表，这这种信DC且DC即A两部分，和决策属性集合D属性集合C可分为分为的属性集合如果信息系统321aaa10987654321321其如果信息系统IS的属性集合A可分为分为条件属性集合C和决策属性集合D两部分，即DCA且DC，这种信息系统也可称为决策表。例1：下面的表1就是一个信息系统，其中属性集},,{321aaaA，全域},,,,,,,,,{10987654321xxxxxxxxxxU，属性的值域}3,2,1{1aV，}2,1{2aV，}4,3,2,1{3aV。2020/5/20陕西师范大学计算机科学学院xjy6信息系统IS举例U1a2a3a1x2132x3213x2134x2235x1146x1127x3218x1149x21310x3212020/5/20陕西师范大学计算机科学学院xjy7不可辨识关系不可辨识关系（Indiscernibilityrelation）是用来表达由于缺乏一定的知识而不能将已知信息系统中的某些对象区别开。其实质是一个等价关系。设),,,(fVAUIS为一个信息系统，则AB，所对应的不可辨识关系)(BInd={(jixx,)(jixx,)∈2U，Bb()()(jixbxb)}，表示对象ix和jx关于属性集A的子集B是不可辨识的。2020/5/20陕西师范大学计算机科学学院xjy8不可辨识关系不可辨识关系)(BInd，通常也简称为不可辨识关系B，是一个等价关系，它与属性子集B一一对应。如果)(),(BIndyx，则对象yx,将是不可辨识的，即它们在属性集合B上是不可区分的。根据不可辨识关系)(BInd可导出一个等价划分)(/BIndU，该划分中包含对象x的等价类记为)(][BIndx。关于)(BInd的等价类称为B的基本集。对,Uxi关于)(BInd的等价类记为)(][BIndix。2020/5/20陕西师范大学计算机科学学院xjy9不可辨识关系例2∶以表1的信息系统为例，则属性集A对应的不可辨识关系)(AInd导出的划分)(/AIndU见表2。表2中的每一行表示一全域U在空间A上基本集，简称为A基本集。表2：关于属性全集A的基本集AU1a2a3a{931,,xxx}213{1072,,xxx}321{4x}223{85,xx}114{6x}1122020/5/20陕西师范大学计算机科学学院xjy10例3：如果仅考虑表1所示信息系统的属性子集},,{21aaB则B所对应的不可辨识关系)(BInd导出的等价类)(/BIndU如表3所示。其中的每一行是一个B的基本集。表3：关于属性子集},{21aaB的基本集BU1a2a{931,,xxx}21{1072,,xxx}32{4x}22{865,,xxx}112020/5/20陕西师范大学计算机科学学院xjy11下近似和上近似上、下近似（LowerandUpperapproximations）是用粗糙集理论进行数据分析的两个关键概念。设信息系统),,,(fVAUIS，则根据属性集合AB所对应的不可辨识关系)(BInd，可以导出全域U上的一个等价划分)(/BIndU，划分中的等价类构成信息系统基本集的集合。通过这些基本集，可以构造集合的近似。2020/5/20陕西师范大学计算机科学学院xjy12下近似和上近似设任意对象集合UX，属性集合AB，则X关于B的下近似BX，是所有真包含于X的B基本集的并。即：BX={XxUxBIndii)(][|}；X关于B的上近似BX，定义为所有与X的交不为空的B基本集的并。即：}][|{)(XxUxBXBIndii。2020/5/20陕西师范大学计算机科学学院xjy13集合XX的上近似集X的下近似集集合X2020/5/20陕西师范大学计算机科学学院xjy14集合X的B下近似内的所有对象是根据属性子集B的知识可判断必然属于X的对象，而集合X的B上近似内的对象是根据属性子集B的知识推断可能属于X的对象。如果BXBX，则集合X是可定义集；否则，集合X在U中是不可定义集，即Rough集。显然，一个集合X是否粗糙与具体的属性集合B上的知识相关。集合X可视为一个概念，如果集合X在属性集合B上是粗糙集，则说明B不足以描述X所对应的概念。2020/5/20陕西师范大学计算机科学学院xjy15上、下近似集粗糙集的核心思想是用上、下近似来描述事物的不确定性。经典粗糙集中，集合可以精确定义，当且仅当它可表示为基本等价类的并集，否则需通过下近似和上近似来表示该集合。后者表示集合是不可精确定义的粗糙集。2020/5/20陕西师范大学计算机科学学院xjy16粗糙集理论给出了以下四类不可定义集（粗糙集）：①如果BX且UBX，则称X在U中B可Rough（粗糙）定义。②如果BX且UBX，则称X在U中B外不可定义。③如果BX且UBX，则称X在U中B内不可定义。④如果BX且UBX，则称X在U中B全不可定义。如果X为B可粗糙定义，则说明U中某些对象是可以确定是属于X或X。如果X为B外不可定义，则说明可以确定U中某些对象是否属于X，但是不能确定U中的任一对象是否属于X。如果X为B内不可定义，则说明虽然不能确定U中的任一对象是属于X的，但是可以确定U中的某些对象是否属于X。如果X为B全不可定义，则说明无法确定U中的任一对象是否属于X或X。2020/5/20陕西师范大学计算机科学学院xjy17Roughsetsview---集合X在U中B可粗糙定义2020/5/20陕西师范大学计算机科学学院xjy18Roughsetsview---集合X在U中B外不可定义2020/5/20陕西师范大学计算机科学学院xjy19Roughsetsview---集合X在U中B内不可定义2020/5/20陕西师范大学计算机科学学院xjy20Roughsetsview---集合X在U中B全不可定义2020/5/20陕西师范大学计算机科学学院xjy21粗集中还有如下概念：集合X的B边界)(XBNB定义为：BXBXXBNB)(。它是所有根据知识B不能确定地划入集合X，也不能确定地划入集合X的U中对象的集合。也就是B上近似BX内无法确定属于X的对象。X的B正域)(XPOSB定义为：)(XPOSB=BX。它是所有根据知识B能确定地划入集合X的U中对象的集合。X的B负域)(XNEGB定义为：)(XNEGB=BXU。它是所有根据知识B确定地不能划入集合X的U中对象的集合。2020/5/20陕西师范大学计算机科学学院xjy22集合XX的上近似集X的下近似集集合X2020/5/20陕西师范大学计算机科学学院xjy23例4：以表1的信息系统为例，令},,,,{95431xxxxxX，属性子集},,{321aaaB。则根据表2，可计算X的下近似},,,{9431xxxxBX；上近似},,,,,{985431xxxxxxBX；)(XBNB=BXBX={985431,,,,,xxxxxx}－{9431,,,xxxx}＝{85,xx}。因为BXBX，即)(XBNB，所以X是B可粗糙定义的。2020/5/20陕西师范大学计算机科学学院xjy24近似精度粗糙集理论引入集合的近似概念后，同样也给出了近似的度量。集合的不确定性主要是由于边界域的存在，边界域越大，那么该集合就越不精确。粗糙集理论通过近似度（Accuracyofapproximation）这一概念来衡量集合的精确程度。令ABUX,，则X在空间B的精度（由不可辨识关系B所定义的集合X的近似精度）)(XB定义为：)()()(BXcardBXcardXB。近似精度用以刻划某一集合（或概念）的精确程度。显然，1)(0XB。如果1)(XB，那么意味着相对于属性集合B，对象集合X是粗糙的；反之，如果1)(XB，那么X的边界域为空集，所以对象集合X相对于属性集合B是精确的。2020/5/20陕西师范大学计算机科学学院xjy25例5：例4已经计算得到集合X的上下近似，则X的近似精度是：3264}),,,,,({}),,,({)()()(9854319431xxxxxxcardxxxxcardBXcardBXcardXB2020/5/20陕西师范大学计算机科学学院xjy26属性独立性（Independenceofattributes）如果}){()(iaAIndAInd，则属性ia相对于属性集A是冗余的。否则属性ia在空间A中是独立的（必要的）。如果)(}){(,AIndaAIndAaii，则A是独立的。为了判断一个属性集独立与否，需要对该属性集的每一个属性进行独立性判断。这需要计算去掉属性集的任一个属性是否会带来原始信息系统关于该属性集的基本集是否有增减变化。2020/5/20陕西师范大学计算机科学学院xjy27例6：分析表1，当三个属性321,,aaa都考虑时，分析可得5个基本集见表2。下表4给出当去掉其中任一属性时，基本集的变化情况。表4RemovedattributeNone1a2a3aNumberofelementarysets5544从表4可见，当去掉属性2a或3a时，基本集个数减少，而去掉属性1a时，基本集数目不变。说明属性1a是冗余的，而属性2a和3a则是独立的。所以，仅仅使用属性2a和3a，便可以区分出5个基本集，可获得于原始信息系统相同的信息系统。2020/5/20陕西师范大学计算机科学学院xjy28U/Aa1a2a3{x1,x3,x9}{x2,x7,x10}{x4}{x5,x8}{x6}232111221131342表2：关于属性全集A的基本集2020/5/20陕西师范大学计算机科学学院xjy29•一个信息系统，去掉冗余属性可得到与原信息系统具有相同特性的简化了的信息系统，因此，属性集之间是依赖的。在分类规则挖掘中为了挖掘出简明的规则需要进行属性的约简。2020/5/2