粗糙集理论介绍

粗糙集理论简介胡可云2002.11.29粗糙集理论的历史1982.波兰数学家Z.Pawlak首次提出.1991.Z.Pawlak出版著作“RoughSets:TheoreticalAspectsofReasoningaboutData”1992.召开首次国际研讨会.近几年来得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.粗糙集理论的基本观点粒度的观点.知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:不可区分关系/等价类.粒度是知识的最小单位。近似的观点.利用两个在当前粒度下能精确表达的概念逼近不精确概念(粗糙集)—上近似和下近似.粗糙集理论的特点将知识定义为不可区分关系的一个族集,使得知识具有了清晰的数学意义，便于用集合运算处理。不需要关于数据的附加信息基本概念(一)信息系统是三元组(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个值.现在有一个要近似的集合,在图中用红色的圆表示.仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.使用两个属性进行划分的情况加入第二个属性负区域正区域(下近似)边界区域上近似综合表示近似的应用:约简对于任意概念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类最小决策规则粗糙集的当前问题粗糙集理论应用于实际数据分析时,会遇到－噪音:过拟合－数据缺失:如何“不可区分”?－大数据量:计算复杂度.研究对策快速算法的研究:约简，规则生成基本模型的扩展:－可变精度粗糙集模型：增加上下近似容错度－相似模型：改变基本块构造方式粗糙集的扩展模型粗糙集理论应用于数据分析时,会遇到噪音,数据缺失,大数据量等一系列经典理论解决不够理想的问题.因此在近几年的研究中,出现了许多粗糙集的扩展模型.其中典型的有可变精度粗糙集模型,相似模型等.可变精度模型(VPRS)在数据集中存在噪音等干扰情况下,经典理论会由于对数据的过拟合而使其对新对象的预测能力大为降低.VPRS允许一定的误分类率.上下近似可以包括一定的错误对象.在误分类率为零的时候,就退化为经典模型.相似模型不可区分关系太强,要求完全等价.应用受到限制.相似模型使用相似关系代替不可区分关系.相似关系一般不再具有传递性.相似类不再形成对原集合的划分,因而具有较强的容错性.重要文献Pawlak,Z.Roughsets:TheoreticalAspectsofReasoningaboutData.KluwerAcademicPublishers,1991入门必读L.Polkowski,A.Skowron(eds.).Roughsetsinknowledgediscovery,Physica-Verlag,1998(I,II)前几年理论扩展和应用总结网络资源InternationalRoughsetSociety相关会议，粗糙集资源链接，公告KDDNuggets动态，资源。包括粗糙集方面的资源链接Citeseer论文资源当然还有Google谢谢大家