基于粗糙集理论的数据挖掘方法ppt课件

《基于粗糙集理论的数据挖掘方法ppt课件》由会员分享，可在线阅读，更多相关《基于粗糙集理论的数据挖掘方法ppt课件（31页珍藏版）》请在装配图网上搜索。

1、基于粗糙集理论的数据挖掘方法2006.10.16资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值粗糙集理论的历史1982.波兰数学家Z.Pawlak首次提出.1991.Z.Pawlak出版著作“Rough Sets:Theoretical Aspects of Reasoning about Data”1992.召开首次国际研讨会.近几年来得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时

2、间价值粗糙集理论的基本观点粒度的观点.知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:不可区分关系/等价类.粒度是知识的最小单位。近似的观点.利用两个在当前粒度下能精确表达的概念逼近不精确概念(粗糙集)上近似和下近似.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值粗糙集理论的特点将知识定义为不可区分关系的一个族集,使得知识具有了清晰的数学意义，便于用集合运算处理。不需要关于数据的附加信息 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金

3、的时间价值基本概念(一)信息系统是三元组(U,A,D).其中U是对象集合,A是属性集合,D是属性的值域.不可区分关系是定义在A的子集B上的二元关系.xy iff x(a)=y(a),x,yU,aB不可区分关系是一个等价关系,它的等价类构成了信息系统表示的知识的最小粒度.这个粒度内的对象不可区分.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例 一玩具积木的集合如下表描述 取B为各种属性组合,则得到不同粒度.如B=R1,则等价类(粒度)为：x1,x3,x7,x2,x4,x5,x6,x8R1(颜色)R2(形状)R3(体积

4、)X1红圆形小x2蓝方形大x3红三角形小x4蓝三角形小x5黄圆形小x6黄方形小x7红三角形大x8黄三角形大资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值基本概念(二)对象集合PU 成为信息系统的一个概念.此概念在属性集合B A下的下近似是包含在该概念下的最小粒度之和.此概念在属性集合B A下的上近似是和该概念交不为空的最小粒度之和.如果上下近似是相等的,则这是一个精确集合,否则它是一个粗糙集,其中下近似称为该概念的正区域,上下近似的差称为边界.上近似以外的区域称为负区域.资金是运动的价值，资金的价值是随时间变化而变化

5、的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值近似的示意图假定有一个信息系统,有两个属性.属性一有5个值,属性二有6个值.现在有一个要近似的集合,在图中用红色的圆表示.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值使用两个属性进行划分的情况加入第二个属性负区域正区域(下近似)资金是运动的价值，资金的价值

6、是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值边界区域上近似综合表示资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值近似的应用:约简对于任意概念PU,下近似是原信息系统中属性集合B A能确定表达出该概念的部分.有可能只需要部分属性就能表达出同样的东西.如果这部分属性是最小的,即它的子集不再具有这个性质,那么该属性集称为约简.求约简是属性选择问题.约简是保持系统近似能力不变的最小属性子集.等价地说,就是保持原属性集合分类能力不变的最小属性子集约简不唯一.最小约简问题.资金

7、是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值关于属性选择许多学习算法处理高维数据有困难,并且大量无关属性的存在,也使得数据分析受到干扰.目的是找到满足特定标准的最小的属性子集.搜索算法起着重要的作用.搜索算法可以用搜索方向(前向,后向,双向),搜索方式(穷尽搜索,启发式,非确定式)及评价方式(精确度,一致性,依赖度,信息熵等)等三个方面来分类.约简的特点是可以保持分类/近似能力不变。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值求约简的方法:

8、区分矩阵直观地,可以通过增减属性集合中的属性,并观察正区域的变化来找到约简.(指数复杂度).区分矩阵将此问题巧妙地转化成了布尔推理问题.区分矩阵D是|U|*|U|矩阵,每一项Dij表示能把对象i,j区分开来的属性集合.在存在类属性时,同类对象不做区分.区分函数是区分矩阵每一项的和,代表了能区分开所有对象的属性组合.化简后就得到了所有可能的约简.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值Diploma Experience French Reference Decision x1MBA Medium Yes Exc

9、ellent Acceptx2MSc High Yes Neutral Acceptx3MSc High Yes Excellent Acceptx4MBA High No Good Acceptx5MBA Low Yes Neutral Reject x6MCELow Yes Good Reject x7MSc Medium Yes Neutral Reject x8MCELow No Excellent Reject x1x2x3x4x5x6x7x8x1x2x3x4x5erdederefrx6derderderdefx7dreerdefrx8defdefrdefder左边是一个信息系统及区

10、分矩阵的例子.可由此构造区分函数:f(S)=(er)(de)(der)(efr)(def)(dr)e(defr)简化后,f(S)=(er)(d e).所以该信息系统的约简是e,r 或d,e资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值快速约简算法的考虑区分函数的化简仍旧是NP-hard问题启发式算法 属性重要性作为启发信息(X.HU)条件信息熵作为启发式信息(王国胤)充分利用区分矩阵的信息作为启发 基于进化计算方法(GA,PSO)的方法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值

11、，其增值的这部分资金就是原有资金的时间价值粗糙集约简的代数观和信息观代数观和信息观：由王国胤提出。代数观(algebra view)：基于正域的方法信息观(information view)：基于条件信息熵的方法。两者关系：代数观和信息观对于粗糙集属性约简不一定是相等价的，它们仅仅在一致性决策系统中才是相同的。信息观包含了代数观 代数观约简可能会严重打乱属性空间中不一致样本的分布，因而会丢失更多信息 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值规则生成方法区分矩阵也可用来生成决策规则区分矩阵的每一列的和化简的结果就

12、是把该对象和其它类对象区分开来的最小属性(值)集。所有同类的对象积化简后就是该类对象的决策规则。LEM2算法是一个粗糙集规则提取(rule induction)算法:规则集覆盖所有的学习样例 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值Diploma Experience French Reference Decision x1MBA Medium Yes Excellent Acceptx2MSc High Yes Neutral Acceptx3MSc High Yes Excellent Acceptx4MB

13、A High No Good Acceptx5MBA Low Yes Neutral Reject x6MCELow Yes Good Reject x7MSc Medium Yes Neutral Reject x8MCELow No Excellent Reject x1x2x3x4x5x6x7x8x1x2x3x4x5erdederefrx6derderderdefx7dreerdefrx8defdefrdefder例如，x1的决策函数为f(x1)=(e r)(d e r)(d r)(d e f)整个Accept类的决策函数为f(Accept)=f(x1)f(x2)f(x3)f(x4)化成

14、析取范式后，各项就是Accept类最小决策规则资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值粗糙集和其他理论方法结合和模糊集(Fuzzy set)模糊粗糙集(Fuzzy-Rough set)应用：特征选择聚类 Rough K-means 应用：Web挖掘资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值粗糙集的问题粗糙集理论应用于实际数据分析时,会遇到 离散化：噪音:过拟合 数据缺失:如何“不可区分”?大数据量:计算复杂度太高.资金是运动的价值

15、，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值研究对策快速算法的研究:约简，规则生成基本模型的扩展:可变精度粗糙集模型：增加上下近似容错度 相似模型：改变基本块构造方式资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值粗糙集的扩展模型粗糙集理论应用于数据分析时,会遇到噪音,数据缺失,大数据量等一系列经典理论解决不够理想的问题.因此在近几年的研究中,出现了许多粗糙集的扩展模型.其中典型的有可变精度粗糙集模型,相似模型等.资金是运动的价值，资金的价值是随时间变化而

16、变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值可变精度模型(VPRS)在数据集中存在噪音等干扰情况下,经典理论会由于对数据的过拟合而使其对新对象的预测能力大为降低.VPRS允许一定的误分类率.上下近似可以包括一定的错误对象.在误分类率为零的时候,就退化为经典模型.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值相似模型不可区分关系太强,要求完全等价.应用受到限制.相似模型使用相似关系代替不可区分关系.相似关系一般不再具有传递性.相似类不再形成对原集合的划分,因而具有较强的容错性.资金

17、是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值在模式识别问题中的已有应用特征选择：基于约简Web挖掘：基于约简图像分割：利用粗糙熵和图像粒度 字符识别：利用近似关系资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值研究方向1.粗糙集在数学理论中的拓宽.2.基于粗糙集理论的粗糙逻辑以及不确定性推理的研究。3.寻求快速、高效的约简算法将是一个主要研究方向。4.结合粗糙集性质的数据离散化预处理5.粗糙集Web知识发现问题。6.粗糙集方法与其它方法的融合7

18、.粗糙集理论的应用研究：用于图像处理、模式识别资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值实际应用中存在的问题经过实践研究发现粗糙集在应用中需要进一步研究解决的问题：1 数据的离散化数据的离散化 2 约简算法的速度 3 和其它数据挖掘、机器学习、模式识别方法的有效融合 4 基于决策规则的方法的可行性？5 粗糙集在模式识别中的应用价值？资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值参考文献Pawlak,Z.Rough sets:Theore

19、tical Aspects of Reasoning about Data.Kluwer Academic Publishers,1991Jan Komorowski,Lech Polkowski,Andrzej Skowron，1999：Rough Sets:A Tutorial王国胤.Rough集理论与知识获取.西安：西安交通大学出版社,2001.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值工具软件-RSES(网络资源)Skowron,A.,Bazan,J.,Son,N.H.,Wroblewski,J.,et al.RSES 2.2 Users Guide.http:/logic.mimuw.edu.pl/rses.Institute of Mathematics,Warsaw University,Warsaw,Poland.January 19,2005 RSES2.2是粗糙集理论发源地波兰华沙大学数学研究所20年研究成果，是一个粗糙集工具软件，其中包括绝大多数粗糙集算法。用于学习、研究。谢谢大家