基于粗糙集理论的数据挖掘方法(2006.10.16)

基于粗糙集理论的数据挖掘方法2006.10.16粗糙集理论的历史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问题启发式算法－属性重要性作为启发信息(X.HU)－条件信息熵作为启发式信息(王国胤)－充分利用区分矩阵的信息作为启发－基于进化计算方法(GA,PSO)的方法粗糙集约简的代数观和信息观代数观和信息观：由王国胤提出。代数观(algebraview)：基于正域的方法信息观(informationview)：基于条件信息熵的方法。两者关系：①代数观和信息观对于粗糙集属性约简不一定是相等价的，它们仅仅在一致性决策系统中才是相同的。②信息观包含了代数观③代数观约简可能会严重打乱属性空间中不一致样本的分布，因而会丢失更多信息规则生成方法区分矩阵也可用来生成决策规则区分矩阵的每一列的和化简的结果就是把该对象和其它类对象区分开来的最小属性(值)集。所有同类的对象积化简后就是该类对象的决策规则。LEM2算法是一个粗糙集规则提取(ruleinduction)算法:规则集覆盖所有的学习样例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类最小决策规则粗糙集和其他理论方法结合和模糊集(Fuzzyset)►模糊粗糙集(Fuzzy-Roughset)►应用：特征选择聚类►RoughK-means►应用：Web挖掘粗糙集的问题粗糙集理论应用于实际数据分析时,会遇到－离散化：－噪音:过拟合－数据缺失:如何“不可区分”?－大数据量:计算复杂度太高.研究对策快速算法的研究:约简，规则生成基本模型的扩展:－可变精度粗糙集模型：增加上下近似容错度－相似模型：改变基本块构造方式粗糙集的扩展模型粗糙集理论应用于数据分析时,会遇到噪音,数据缺失,大数据量等一系列经典理论解决不够理想的问题.因此在近几年的研究中,出现了许多粗糙集的扩展模型.其中典型的有可变精度粗糙集模型,相似模型等.可变精度模型(VPRS)在数据集中存在噪音等干扰情况下,经典理论会由于对数据的过拟合而使其对新对象的预测能力大为降低.VPRS允许一定的误分类率.上下近似可以包括一定的错误对象.在误分类率为零的时候,就退化为经典模型.相似模型不可区分关系太强,要求完全等价.应用受到限制.相似模型使用相似关系代替不可区分关系.相似关系一般不再具有传递性.相似类不再形成对原集合的划分,因而具有较强的容错性.在模式识别问题中的已有应用特征选择：基于约简Web挖掘：基于约简图像分割：利用粗糙熵和图像粒度字符识别：利用近似关系研究方向1.粗糙集在数学理论中的拓宽.2.基于粗糙集理论的粗糙逻辑以及不确定性推理的研究。3.寻求快速、高效的约简算法将是一个主要研究方向。4.结合粗糙集性质的数据离散化预处理5.粗糙集Web知识发现问题。6.粗糙集方法与其它方法的融合7.粗糙集理论的应用研究：用于图像处理、模式识别实际应用中存在的问题经过实践研究发现粗糙集在应用中需要进一步研究解决的问题：1数据的离散化2约简算法的速度3和其它数据挖掘、机器学习、模式识别方法的有效融合4基于决策规则的方法的可行性？5粗糙集在模式识别中的应用价值？？参考文献Pawlak,Z.Roughsets:TheoreticalAspectsofReasoningaboutData.KluwerAcademicPublishers,1991JanKomorowski,LechPolkowski,AndrzejSkowron，1999：RoughSets:ATutorial王国胤.Rough集理论与知识获取.西安：西安交通大学出版社,2001.工具软件-RSES(网络资源)Skowron,A.,Bazan,J.,Son,N.H.,Wroblewski,J.,etal.RSES2.2User’sGuide.~rses.InstituteofMathematics,WarsawUniversity,Warsaw,Poland.January19,2005RSES2.2是粗糙集理论发源地—波兰华沙大学数学研究所20年研究成果，是一个粗糙集工具软件，其中包括绝大多数粗糙集算法。用于学习、研究。谢谢大家