粗糙集理论介绍解析ppt课件.ppt

《粗糙集理论介绍解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论介绍解析ppt课件.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、粗糙集理论介绍问题的提出：知识的含糊性术语的模糊性，如高矮 数据的不确定性，如噪声知识自身的不确定性，如规则的前后件间的依赖关系不完全可靠不完备性，数据缺失由此，提出了包括概率与统计、证据理论：理论上还难以令人信服，不能处理模糊和不完整的数据模糊集合理论：能处理模糊类数据，但要提供隶属函数（先验知识）粗糙集理论：能处理具有不精确性和不确定性的知识等各种理论和方法模糊集和基于概率方法，有时需要一些数据的附加信息或先验知识,如模糊隶属函数,基本概率指派函数和有关统计概率分布等,而这些信息有时并不容易得到粗糙集无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是

2、比较客观的 粗糙集理论的历史20世纪70 年代,波兰数学家Z.Pawlak 和一些波兰科学院,波兰华沙大学的逻辑学家们,一起从事关于信息系统逻辑特性的研究.1982.Z.Pawlak发表论文“Rough Set”.宣告RS的诞生1991.Z.Pawlak出版著作“Rough Sets:Theoretical Aspects of Reasoning about Data”1992.召开首次国际研讨会,应用专集.之后得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论

3、将知识理解为对数据的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画。粗糙集理论的基本观点Outline：粗糙集理论的基本概念粗糙集理论的应用（规则挖掘和属性约简）其他基本概念1 信息系统，决策表2 知识3 等价关系，不可分辨关系与基本集4 下、上近似 正区域，负区域，边界域5 粗糙度6 粗糙隶属函数基本概念（1）信息系统信息系统是四元组(U,Q,V,f).其中U是对象集合Q是属性集合（包括条件属性C和决策属性D)，V是属性的值域f是一种映射，反应对象集合之间的值返回U A1 A2 A3 A41 0 0 1 02

4、 1 0 2 13 1 1 1 04 0 2 1 15 1 2 1 0信息系统实例：其中U1，2，3，4，5；QA1,A2,A3,A4;V=VA1 VA2VA3VA40,1,2 f，将对象属性映射到它的值域基本概念（2）：知识RS中，知识被认为是一种分类能力。人们的行为是基于分辨现实的或抽象的对象的能力。那些根据事务的特征差别将其分门别类的能力都可以看作是某种“知识”。论域中相互间不可分辨的对象组成的集合。是组成知识的颗粒（granule）。知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:不可分辨关系/等价类.粒度是知识的最小单位。返回基本概念（3）不可分辨关系与基本集不可分辨

5、关系IND(P)/等价关系：分类过程中，相差不大的个体被归于同一类，他们的关系就是不可区分关系。对于任何一个属性集合P，不可分辨关系用IND表示，定义如下：IND(P)(x,y)UU:f(x,a)=f(y,a),a P 不可分辨关系就是U上的等价关系基本集：由论域中相互间不可区分的对象组成的集合，是组成论域知识的颗粒。例1 一玩具积木的集合如下表描述（表1）取不同的属性组合,可得不同的等价关系（粒度)为：IND（R1）x1,x3,x7,x2,x4,x5,x6,x8IND（R1,R2）x1,x2,x3,x7,x4,x5,x6,x8R1(颜色)R2(形状)R3(体积)X1红 圆形 小X2蓝 方形

6、大X3红 三角形 小X4蓝 三角形 小X5黄 圆形 小X6黄 方形 小X7红 三角形 大X8黄 三角形 大返回基本概念（4）集合的上近似、下近似和边界区 一个对象a是否属于集合X根据现有知识来判断，可分为三种情况：1）a肯定属于集合X2)a可能属于也可能不属于集合X 3)a肯定不属于集合X返回Let U为论域（非空对象集合），I为U中的一组等价关系，Then集合X关于I的下近似（Lower approximation）是由那些根据现有知识判断肯定属于X的对象所组成的最大集合，有时也称为X的正区（positive region），记做POS（X）集合X关于I的上近似（Upper approxim

7、ation）是由所有与X相交非空的等效类I（x）的并集，是那些可能属于X的对象组成的最小集合。如果上下近似是相等的,则这是一个精确集合,否则它是一个粗糙集,其中下近似称为该概念的正区域,上下近似的差称为边界。上近似以外的区域称为负区域（Negative region），记为NEG（x）。soR1(颜色)R2(形状)R3(体积)classX1红 圆形 小1X2蓝 方形 大1X3红 三角形 小1X4蓝 三角形 小1X5黄 圆形 小2X6黄 方形 小2X7红 三角形 大2X8黄 三角形 大2等价类IND(R1)=x1,x3,x7,x2,x4,x5,x6,x8X=X1,X2,X3,X4例2：（表2）T

8、hen，there are:I*(x)=x2，x4 I*(x)=x1，x3，x7，x2，x4回 回回 回回24近似的示意图假定有一个信息系统,有两个属性.属性一有5个值,属性二有6个值.现在有一个要近似的集合(X),在图中用红色的圆表示.仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.使用两个属性进行划分的情况加入第二个属性 负区域正区域(下近似)边界区域 上近似 综合表示返回基本概念（5）粗糙度下近似、上近似及边界区等概念称为可分辨区，刻化了一个边界含糊(vague)集合的逼近特性。粗糙程度按右边公式计算。式中|表示集合的基数或势，对有限集合表示集合中所包含的元素个数。例2的粗

9、糙度2/5返回基本概念（6）粗糙隶属函数（Rough membership function)含糊集合没有清晰的边界，即，根据论域中现有知识无法判定某些元素是否属于该集合。在RS中，不确定（uncertainty）这个概念是针对元素隶属于集合的程度而言。例2中，I为属性R1上构成的等价关系时，x1对集合的粗糙隶属函数为：2/3粗糙度与粗糙隶属函数vague（粗糙度）：用来描述集合，指集合的边界不清楚uncertainty（粗糙隶属函数）：描述元素，指某个元素是否属于某集合是不确定的。返回粗糙集理论的基本概念粗糙集理论的应用（规则挖掘和属性约简）其他粗糙集的应用粗糙集在数据挖掘中的应用基于粗糙集

10、的数据约简返回 是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确，不一致，不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律 1.粗糙集在数据挖掘中的应用 粗糙集理论的的数学基础：假定所研究的每一个对象都涉及到一些信息（数据、知识），如果对象由相同的信息描述，那么它们就是相似的或不可区分的。粗糙集对不精确概念的描述是通过上、下近似这两个精确概念来表示的。Example 例3 含6个流感病例的表（表43）病例头疼肌肉疼体温流感P1否 是 高 是P2是 否 高 是P3是 是很高是P4否 是正常否P5是 否 高 否p6否 是很高是Step1.寻找不可分

11、辨关系：“头疼”：p2,p3,p5,p1,p4,p6“肌肉痛”：p1,p3,p4,p6,p2,p5“体温”：p1,p2,p5,p3,p6,p4“头疼肌肉痛”：p1,p4,p6,p2,p5,p3“头疼体温”：p1,p2,p5,p3,p4,p6“肌肉痛体温”：p1,p2,p5,p3,p6,p4“头疼肌肉痛体温”：p1,p2,p5,p3,p4,p6Step2.针对各个属性下的初等集合寻找下近似和上近似。以“头疼肌肉痛体温”为例，设集合X 为患流感的人的集合，I 为3个属性构成的一个等效关系：p1,p2,p5,p3,p4,p6，则 X=P1,P2,P3,P6 I=p1,p2,p5,p3,p4,p6集合

12、X的下近似为 I*(X)=POS(X)=p1,p3,p6集合X的上近似为 I*(X)p1,p2,p3,p5,p6集合X的负区为 NEG(X)=p4集合X的边界区为 BND(X)=p2,p5Step3.获取规则根据上面的分析可得出关于属性“头疼肌肉痛体温”的规则：下近似得到的：RULE1：IF（头疼否）and（肌肉痛是)and(体温高）THEN 患有流感RULE2：IF（头疼是）and（肌肉痛是)and(体温很高）THEN 患有流感RULE3：IF（头疼否）and（肌肉痛是)and(体温很高）THEN 患有流感负区得到的：RULE4：IF（头疼否）and（肌肉痛是)and(体温正常）THEN 没

13、患流感边界区得到的：RULE5：IF（头疼是）and（肌肉痛否)and(体温高）THEN 可能以“肌肉痛体温”为例：X=P1,P2,P3,P6 I=p1,p2,p5,p3,p6,p4可以处理不完整的数据的体现RULE1：IF（肌肉痛是)and(体温高）THEN 患有流感RULE2：IF（肌肉痛是)and(体温很高）THEN 患有流感RULE3：IF（肌肉痛是)and(体温正常）THEN 没患流感RULE4：IF（肌肉痛否)and(体温高）THEN 可能返回2.基于粗糙集的数据约简不可分辨关系近似集（下近似和上近似）属性的依赖度属性的重要性冗余属性属性约简返回属性的依赖度利用两个属性集合D、C之

14、间的相互依赖程度，确定在决策属性D之下的条件属性集合C的重要性即，决策属性集合D 对条件属性集合C的依赖程度用如下定义来表示：POSc(D)是属性集C在U/IND(D)中的正区域。example例4.属性依赖度的计算U A1 A2 A3 A4 A51 0 0 1 0 02 1 0 2 1 13 1 1 1 0 04 0 2 1 1 15 1 2 1 0 16 1 0 1 0 07 1 2 2 1 18 0 0 2 1 1令CA1,A2,D=A5依据属性A1、A2，可得到U/IND（D）：1,8,2,6,3,4,5,7正区域为：4,5,7So，POSC(D)POSA1,A2(A5)4,5,7 Q

15、(P)=3/8=0.375返回属性的重要性不同属性对于决定条件属性和决策属性之间的依赖关系起着不同的作用属性a加入C，对于分类U/IND(D)的重要程度定义为：SGF(a,C,D)=C(D)-C-a(D)有属性a的依赖度没有属性a的依赖度例5.属性的重要性计算U A1 A2 A3 A4 A51 0 0 1 0 02 1 0 2 1 13 1 1 1 0 04 0 2 1 1 15 1 2 1 0 16 1 0 1 0 07 1 2 2 1 18 0 0 2 1 1表4令CA1,A2,D=A5有POSC(D)4,5,7 C(D)=3/8=0.375if aA1，thenC-a(D)A2(D)=3

16、/8if aA2，thenC-a(D)A1(D)=0SO,SGF(A1,C,D)=0SGF(A2,C,D)=3/8说明属性A2比属性A1更重要返回冗余属性 对于属性集D和R，属性a属于R，如果 POSR(D)=POSR-a(D)，OR SGF(a,R,P)=0 则a在属性集R中是冗余的(如例5中的A1），否则a在R中对于D是不可缺少的。实际应用中存在的问题不可分辨关系对问题的限制太过于严格，对问题的描述过于单调离散化问题难以优化 对于规模小，且属性本身具有明确的逻辑意义的数据会有较好的数据分析效果。对于大规模，特征又是连续值的数据，一定要离散化之后用粗糙集方法，很难得到十分满意的结果。粗糙集知

17、识发现系统http:/www.cs.uregina.ca/roughset RSES系统:基于粗糙集理论的方法分析数据的工具集，波兰华沙大学 LERS系统:基于粗糙集的实例学习系统,美国Kansas大学开发 ROSE系统:实现了Pawlak的基本粗糙集模型和可变精度粗糙集模型,波兰Poznan工业大学计算机科学研究所智能决策支持系统实验室研制KDD-R系统:基于可变精度粗糙集模型，采用知识发现的决策矩阵方法。加拿大Regina大学研制 Rough Enough系统:包括数据输入、预处理、编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析。挪威Troll Data Inc.公司开发重要文献Pawlak,Z.Rough sets:Theoretical Aspects of Reasoning about Data.Kluwer Academic Publishers,1991L.Polkowski,A.Skowron(eds.).Rough sets in knowledge discovery,Physica-Verlag,1998(I,II)前几年理论扩展和应用总结网络资源International Rough set Society http:/www.roughsets.org/相关会议，粗糙集资源链接，公告KDDNuggets http:/http:/