粗糙集理论介绍PPT课件.ppt

《粗糙集理论介绍PPT课件.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论介绍PPT课件.ppt（42页珍藏版）》请在三一文库上搜索。

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

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

3、的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。 粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似) 刻画。,粗糙集理论的基本观点,7,Outline：,粗糙集理论的基本概念 粗糙集理论的应用（规则挖掘和属性约简） 其他,8,基本概念,1 信息系统，决策表 2 知识 3 等价关系，不可分辨关系与基本集 4 下、上近似 正区域，负区域，边界域 5 粗糙度 6 粗糙隶属函数,9,基本概念（1） 信息系统,信息系统是四元组(U,Q,V,f). 其中 U是对象集合 Q是属

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

5、的最小单位。,返回,12,基本概念（3）不可分辨关系与基本集,不可分辨关系IND(P)/等价关系：分类过程中，相差不大的个体被归于同一类，他们的关系就是不可区分关系。 对于任何一个属性集合P，不可分辨关系用IND表示，定义如下： IND(P)(x,y) UU:f(x,a)=f(y,a), aP 不可分辨关系就是U上的等价关系 基本集：由论域中相互间不可区分的对象组成的集合，是组成论域知识的颗粒。,13,例1 一玩具积木的集合如下表描述（表1） 取不同的属性组合,可得不同的等价关系（粒度)为： IND（R1）x1,x3,x7, x2,x4, x5,x6,x8 IND（R1,R2）x1, x2,

6、x3,x7, x4, x5, x6, x8,返回,14,基本概念（4） 集合的上近似、下近似和边界区,一个对象a是否属于集合X根据现有知识来判断，可分为三种情况： 1）a肯定属于集合X a可能属于也可能不属于集合X a肯定不属于集合X,返回,15,Let U为论域（非空对象集合 ），I为U中的一组等价关系， Then 集合X关于I的下近似（Lower approximation）是由那些根据现有知识判断肯定属于X的对象所组成的最大集合，有时也称为X的正区（positive region），记做POS（X） 集合X关于I的上近似（Upper approximation）是由所有与X相交非空的等效

7、类I（x）的并集，是那些可能属于X的对象组成的最小集合。,16,如果上下近似是相等的, 则这是一个精确集合, 否则它是一个粗糙集, 其中下近似称为该概念的正区域, 上下近似的差称为边界。上近似以外的区域称为负区域（Negative region），记为NEG（x）。 so,17,等价类IND(R1)=x1,x3,x7, x2,x4, x5,x6,x8 X=X1,X2,X3,X4,例2： （表2）,Then，there are: I*(x)=x2，x4 I*(x)=x1，x3，x7，x2，x4,回,回,回24,18,近似的示意图,假定有一个信息系统, 有两个属性. 属性一有5个值, 属性二有6个

8、值. 现在有一个要近似的集合(X), 在图中用红色的圆表示.,19,仅使用第一个属性进行划分的情形. 正区域为空. 蓝色区域为负区域.,20,使用两个属性进行划分的情况,加入第二个属性,负区域,正区域(下近似),21,边界区域,上近似,综合表示,返回,22,基本概念（5）粗糙度,下近似、上近似及边界区等概念称为可分辨区，刻化了一个边界含糊(vague)集合的逼近特性。粗糙程度按右边公式计算。 式中|表示集合的基数或势，对有限集合表示集合中所包含的元素个数。,例2的粗糙度 2/5,返回,23,基本概念（6）粗糙隶属函数 （Rough membership function),含糊集合没有清晰的边

9、界，即，根据论域中现有知识无法判定某些元素是否属于该集合。在RS中，不确定（uncertainty）这个概念是针对元素隶属于集合的程度而言。,例2中，I为属性R1上构成的等价关系时，x1对集合的粗糙隶属函数为：2/3,24,粗糙度与粗糙隶属函数,vague（粗糙度）：用来描述集合，指集合的边界不清楚 uncertainty（粗糙隶属函数）：描述元素，指某个元素是否属于某集合是不确定的。,返回,25,粗糙集理论的基本概念 粗糙集理论的应用（规则挖掘和属性约简） 其他,26,粗糙集的应用,粗糙集在数据挖掘中的应用 基于粗糙集的数据约简,返回,是一种刻划不完整性和不确定性的数学工具， 能有效地分析不

10、精确，不一致，不完整等各种不完备的信息， 还可以对数据进行分析和推理， 从中发现隐含的知识， 揭示潜在的规律,27,1. 粗糙集在数据挖掘中的应用,粗糙集理论的的数学基础：假定所研究的每一个对象都涉及到一些信息（数据、知识），如果对象由相同的信息描述，那么它们就是相似的或不可区分的。,粗糙集对不精确概念的描述是通过上、下近似这两个精确概念来表示的。,28,Example 例3 含6个流感病例的表 （表43）,Step1. 寻找不可分辨关系： “头疼”：p2,p3,p5,p1,p4,p6 “肌肉痛”：p1,p3,p4,p6,p2,p5 “体温”：p1,p2,p5,p3,p6,p4 “头疼肌肉痛”

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

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

13、温高） THEN 可能,31,以“肌肉痛体温”为例： 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 可能,返回,32,2. 基于粗糙集的数据约简,不可分辨关系 近似集（下近似和上近似） 属性的依赖度 属性的重要性 冗余属性 属性约简,返回,33,属性的依赖度,利用两个属性集合D、C之

14、间的相互依赖程度，确定在决策属性D之下的条件属性集合C的重要性,即，决策属性集合D 对条件属性集合C的依赖程度用如下定义来表示：,POSc(D)是属性集C在U/IND(D)中的正区域。 example,34,例4. 属性依赖度的计算,令CA1,A2, D=A5 依据属性A1、A2，可得到U/IND（D）： 1,8,2,6,3,4,5,7 正区域为：4,5,7 So， POSC(D)POSA1,A2(A5)4,5,7 Q(P)=3/8=0.375,返回,35,属性的重要性,不同属性对于决定条件属性和决策属性之间的依赖关系起着不同的作用,属性a加入C，对于分类U/IND(D)的重要程度定义为： S

15、GF(a, C, D)=C(D)-C-a(D),有属性a的依赖度,没有属性a的依赖度,36,例5. 属性的重要性计算,表4,令CA1,A2,D=A5 有POSC(D)4,5,7 C(D)=3/8=0.375 if aA1，then C-a(D) A2(D)=3/8 if aA2，then C-a(D) A1(D)=0 SO, SGF(A1, C, D)=0 SGF(A2, C, D)=3/8 说明属性A2比属性A1更重要,返回,37,冗余属性,对于属性集D和R，属性a属于R，如果 POSR(D)= POSR-a(D)， OR SGF(a,R,P)=0 则a在属性集R中是冗余的(如例5中的A1）

16、，否则a在R中对于D是不可缺少的。,38,实际应用中存在的问题,不可分辨关系对问题的限制太过于严格，对问题的描述过于单调 离散化问题难以优化,对于规模小 ，且属性本身具有明确的逻辑意义的数据会有较好的数据分析效果。 对于大规模，特征又是连续值的数据，一定要离散化之后用粗糙集方法，很难得到十分满意的结果。,39,粗糙集知识发现系统http:/www.cs.uregina.ca/roughset, RSES系统: 基于粗糙集理论的方法分析数据的工具集，波兰华沙大学 LERS系统: 基于粗糙集的实例学习系统,美国Kansas大学开发 ROSE系统: 实现了Pawlak的基本粗糙集模型和可变精度粗糙集

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