2-粗糙集理论介绍

合肥工业大学计算机与信息学院图像信息处理研究室Tel:2901393Email:[e-mail]粗糙集理论简介图像研究室2006.2粗糙集产生背景边界问题的提出•经典逻辑：只有真、假二值之分。•现实生活：存在许多含糊的现象，并不能简单地用真、假值来表示。•在1904年，谓词逻辑的创始人G.frege提出了含糊(vague)一词，他把含糊现象归结到边界线上。•全域上存在一些个体不能在其某个子集上分类，也不能在该子集的补集上分类。粗糙集产生背景应运而生的理论(模糊集)•1965年，L.A.Zadeh提出FuzzySets的概念，试图通过这一理论解决G.frege的含糊概念。•FS方法：利用隶属函数描述边界上的不确定对象。•1982年，波兰华沙理工大学Z.Pawlak教授针对G.frege的边界线区域思想提出了RoughSets理论。•RS方法：把无法确认的个体都归属于边界区域，把边界区域定义为上近似集和下近似集的差集。粗糙集产生背景经典集合A={apples,oranges,cherries,mangoes}A={a1,a2,a3}A={2,4,6,8,…}A={x|xisanevennaturalnumber}AxAxxAif0if1)(成员函数粗糙集产生背景(模糊集)模糊集合粗糙集产生背景(模糊集)粗糙集产生背景(模糊集)粗糙集产生背景(模糊集)zzzzzzz粗糙集产生背景(模糊集)粗糙集产生背景(模糊集)粗糙集理论历史1982.波兰数学家Z.Pawlak首次提出.1991.Z.Pawlak出版著作“RoughSets:TheoreticalAspectsofReasoningaboutData”1992.召开首次国际研讨会.近几年来得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.粗糙集理论相关的学科人工智能(ArtificialIntelligence)离散数学(DisperseMathematics)概率论(ProbabilityTheory)模糊集理论(FuzzySetsTheory)神经网络(NeuralNetworks)计算机控制(ComputerControl)专家系统(ExpertSystem)其它(Others)粗糙集理论的基本观点粒度的观点.知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:不可区分关系/等价类.粒度是知识的最小单位.近似的观点.利用两个在当前粒度下能精确表达的概念逼近不精确概念(粗糙集)—上近似和下近似.粗糙集理论的特点将知识定义为不可区分关系的一个族集,使得知识具有了清晰的数学意义,便于用集合运算处理.不需要关于数据的附加信息.粗糙集仅仅从数据本身进行分析,通过建立新型的成员关系,计算成员归属程度的不确定性,无需任何先验知识.粗糙集和模糊集错误认识：两者是相互竞争的.正确观点：是描述知识不精确性与不确定性的两个不同的概念，二者相互补充，有望显示出更强的功能.相同点：都是处理不确定信息的理论.不同点粗糙集和模糊集研究对象：FS研究人类语言产生的集合边界的病态定义，即边界的不分明性；RS研究认知能力产生的集合对象之间的不可分辨性。研究方法：FS通过隶属函数描述对象关于集合的不确定性；RS引入一对上下近似集合，用它们的差集来描述不确定的对象。需指出的一点：FS的隶属函数带有很强的主观意志；RS通过客观存在的结构（上下近似的差集）来处理边界上的不确定性，即知识的含糊度是可以用公式来计算的。基本概念(一)信息系统是三元组(U,A,D).其中U是对象集合,A是属性集合,D是属性的值域.不可区分关系是定义在A的子集B上的二元关系.xyiffx(a)=y(a),x,yU,aB不可区分关系是一个等价关系,它的等价类构成了信息系统表示的知识的最小粒度.这个粒度内的对象不可区分.例一玩具积木的集合如下表描述取B为各种属性组合,则得到不同粒度.如B={R1},则等价类(粒度)为：{{x1,x3,x7},{x2,x4},{x5,x6,x8}}R1(颜色)R2(形状)R3(体积)x1红圆形小x2蓝方形大x3红三角形小x4蓝三角形小x5黄圆形小x6黄方形小x7红三角形大x8黄三角形大基本概念(二)对象集合PU成为信息系统的一个概念.此概念在属性集合BA下的下近似是包含在该概念下的最小粒度之和.此概念在属性集合BA下的上近似是和该概念交不为空的最小粒度之和.如果上下近似是相等的,则这是一个精确集合,否则它是一个粗糙集,其中下近似称为该概念的正区域,上下近似的差称为边界.上近似以外的区域称为负区域.近似的示意图假定有一个信息系统,有两个属性.属性一有5个值,属性二有6个值.现在有一个要近似的集合,在图中用红色的圆表示.仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.使用两个属性进行划分的情况加入第二个属性负区域正区域(下近似)边界区域上近似综合表示粗糙集信息处理过程原始信息表数据预处理决策表约简决策表推理新知识获取数据预处理对于不同获取途径的原始数据不一定能获取有效信息,所以数据预处理非常必要.方法:1、获取信息数据空缺或遗漏时,进行决策表补齐,尽可能恢复真实信息.2、获取信息数据复杂多变,进行数据离散化,对数据进行适当的划分.数据预处理要求信息表缺失项补齐,不能引入相关冲突.缺失项的填补应使完整化后的信息系统的分类规则有尽可能高的支持度.数据离散化的分隔断点应尽可能少.相关算法的时间和空间复杂度尽可能低.预处理相关算法(一)决策表补齐1、MeanCompleter算法2、CombinatorialCompleter算法3、ROUSTIDA算法预处理相关算法(二)决策表离散化1、等距离、等频率划分算法2、NaïveScaler算法3、SemiNaïveScaler算法4、布尔逻辑算法5、启发式算法6、基于断点、属性重要性的离散化算法例不完备信息表补齐过程Ua1a2a3a4X14*12X231**X3*11*X42143X5*134Ua1a2a3a4X14112X23134X34112X42143X53134原始信息表补齐后的信息表例信息表离散化UabdX10.821X210.50X31.330X41.411X51.420X61.631X71.311属性域Va=[0,2)，Vb=[0,4)属性a和b的值分别为a(U)={0.8,1,1.3,1.4,1.6}b(U)={0.5,1,2,3}0.511.524321布尔逻辑算法启发式算法近似的应用:约简对于任意概念PU,下近似是原信息系统中属性集合BA能确定表达出该概念的部分.有可能只需要部分属性就能表达出同样的东西.如果这部分属性是最小的,即它的子集不再具有这个性质,那么该属性集称为约简.求约简是属性选择问题.约简是保持系统近似能力不变的最小属性子集.等价地说,就是保持原属性集合分类能力不变的最小属性子集.约简不唯一.最小约简问题.关于属性选择许多学习算法处理高维数据有困难,并且大量无关属性的存在,也使得数据分析受到干扰.目的是找到满足特定标准的最小的属性子集.搜索算法起着重要的作用.搜索算法可以用搜索方向(前向,后向,双向),搜索方式(穷尽搜索,启发式,非确定式)及评价方式(精确度,一致性,依赖度,信息熵等)等三个方面来分类.约简的特点是可以保持分类/近似能力不变.求约简的方法:区分矩阵直观地,可以通过增减属性集合中的属性,并观察正区域的变化来找到约简.(指数复杂度).区分矩阵将此问题巧妙地转化成了布尔推理问题.区分矩阵D是|U|*|U|矩阵,每一项Dij表示能把对象i,j区分开来的属性集合.在存在类属性时,同类对象不做区分.区分函数是区分矩阵每一项的和,代表了能区分开所有对象的属性组合.化简后就得到了所有可能的约简.DiplomaExperienceFrenchReferenceDecisionx1MBAMediumYesExcellentAcceptx2MScHighYesNeutralAcceptx3MScHighYesExcellentAcceptx4MBAHighNoGoodAcceptx5MBALowYesNeutralRejectx6MCELowYesGoodRejectx7MScMediumYesNeutralRejectx8MCELowNoExcellentRejectx1x2x3x4x5x6x7x8x1x2x3x4x5erdederefrx6derderderdefx7dreerdefrx8defdefrdefder左边是一个信息系统及区分矩阵的例子.可由此构造区分函数:f(S)=(er)(de)(der)(efr)(def)(dr)e(defr)简化后,f(S)=(er)(de).所以该信息系统的约简是{e,r}或{d,e}快速约简算法的考虑区分函数的化简仍旧是NP-hard问题启发式算法－属性重要性作为启发信息－充分利用区分矩阵的信息作为启发规则生成方法区分矩阵也可用来生成决策规则.区分矩阵的每一列的和化简的结果就是把该对象和其它类对象区分开来的最小属性(值)集.所有同类的对象积化简后就是该类对象的决策规则.DiplomaExperienceFrenchReferenceDecisionx1MBAMediumYesExcellentAcceptx2MScHighYesNeutralAcceptx3MScHighYesExcellentAcceptx4MBAHighNoGoodAcceptx5MBALowYesNeutralRejectx6MCELowYesGoodRejectx7MScMediumYesNeutralRejectx8MCELowNoExcellentRejectx1x2x3x4x5x6x7x8x1x2x3x4x5erdederefrx6derderderdefx7dreerdefrx8defdefrdefder例如，x1的决策函数为f(x1)=(er)(der)(dr)(def)整个Accept类的决策函数为f(Accept)=f(x1)f(x2)f(x3)f(x4)化成析取范式后，各项就是Accept类最小决策规则例1粗糙集合进行数字模式识别计算器中的数字显示由7个元素组成0—9十个数码afgbecd构建信息表表示数字结构Uabcdefg0******1**2*****3*****4****5*****6******7***8*******9******产生式规则a1b1c1d1e1f1g00a0b1c1d0e0f0g01a1b1c0d1e1f0g12a1b1c1d1e0f0g13a0b1c1d0e0f1g14a1b0c1d1e0f1g15a1b0c1d1e1f1g16a1b1c1d0e0f0g07a1b1c1d1e1f1g18a1b1c1d1e0f1g19Rough集方法对表进行属性约简,由产生式规则可知属性的核集为{a,b,e,f,g}Uabefg011110101000211101311001401011510011610111711000811111911011计算上表中每条规则的核值,将规则中的某个属性值去掉,若使原表出现不一致性,则意味着该属性值为当前规则中的核值,按此方法得到所有规则的核值表.*表示可以省略的属性取值Uabefg0****010****2**10*3**00140****5*00**6*01**71***08*111191101*从上表中求得每条决策——规则的约简,共有16个最小决策算法，得到全体约简规则表：e1g00a0f01e1f02e0f0g13a0f14b0e05b0e16a1e0g07b1e1f1g18a1b1e0f19上述算法可以用软硬件实现,经Rough集理论处理后,比原始图案要简单的多,所以Rough集合可是模式识别的问题简化.例2