粗糙集理论介绍.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,粗糙集理论介绍,问题的提出：知识的含糊性,术语的模糊性，如高矮,数据的不确定性，如噪声,知识自身的不确定性，如规则的前后件间的依赖关系不完全可靠,不完备性，数据缺失,由此，提出了包括,概率与统计、证据理论：,理论上还难以令人信服，不能处理模糊和不完整的数据,模糊集合理论：,能处理模糊类数据，但要提供隶属函数（先验知识）,粗糙集理论：,能处理具有不精确性和不确定性的知识,等各种理论和方法,模糊集和基于概率方法，有时需要一些数据的附加信息或先验知识,如模糊隶属函数,基本概率指派函数和有关统计概率分布等,而这些信息有时并不容易得到,粗糙集无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的,粗糙集理论的历史,20世纪70 年代,波兰数学家Z.Pawlak 和一些波兰科学院,波兰华沙大学的逻辑学家们,一起从事关于,信息系统逻辑特性,的研究.,1982.Z.Pawlak发表论文“Rough Set”.宣告RS的诞生,1991.Z.Pawlak出版著作“Rough Sets:Theoretical Aspects of Reasoning about Data”,1992.召开首次国际研讨会,应用专集.,之后得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.,粗糙集理论是建立在,分类机制,的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。

粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画粗糙集理论的基本观点,Outline：,粗糙集理论的基本概念,粗糙集理论的应用,（规则挖掘和属性约简）,其他,基本概念,1,信息系统,，决策表,2,知识,3,等价关系,，不可分辨关系与基本集,4,下、上,近似,正区域，负区域，边界域,5,粗糙度,6,粗糙隶属函数,基本概念（1）,信息系统,信息系统,是四元组(U,Q,V,f).其中,U是对象集合,Q是属性集合（包括条件属性C和决策属性D)，,V是属性的值域,f是一种映射，反应对象集合之间的值,返回,U,A1,A2,A3,A4,1,0,0,1,0,2,1,0,2,1,3,1,1,1,0,4,0,2,1,1,5,1,2,1,0,信息系统实例：其中U1，2，3，4，5；,QA1,A2,A3,A4;,V=V,A1,V,A2,V,A3,V,A4,0,1,2,f，将对象属性映射到它的值域,基本概念（2）：,知识,RS中，知识被认为是一种分类能力人们的行为是基于分辨现实的或抽象的对象的能力那些根据事务的特征差别将其分门别类的能力都可以看作是某种“知识”。

论域中相互间不可分辨的对象组成的集合是组成知识的颗粒（granule）知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:,不可分辨关系,/,等价类,.粒度是知识的最小单位返回,基本概念（3）,不可分辨关系与基本集,不可分辨关系IND(P)/等价关系,：,分类过程中，相差不大的个体被归于同一类，他们的关系就是不可区分关系对于任何一个属性集合P，不可分辨关系用IND表示，定义如下：,IND(P)(x,y),UU:f(x,a)=f(y,a),aP,不可分辨关系就是U上的等价关系,基本集：由论域中相互间不可区分的对象组成的集合，是组成论域知识的颗粒例1,一玩具积木的集合如下表描述（表1）,取不同的属性组合,可得不同的等价关系（粒度)为：,IND（R1）x1,x3,x7,x2,x4,x5,x6,x8,IND（R1,R2）,x1,x2,x3,x7,x4,x5,x6,x8,R1(颜色),R2(形状),R3(体积),X1,红,圆形,小,X2,蓝,方形,大,X3,红,三角形,小,X4,蓝,三角形,小,X5,黄,圆形,小,X6,黄,方形,小,X7,红,三角形,大,X8,黄,三角形,大,返回,基本概念（4）,集合的上近似、下近似和边界区,一个对象a是否属于集合X根据现有知识来判断，可分为三种情况：,1）a肯定属于集合X,a,可能属于也可能不属于集合,X,a,肯定不属于集合,X,返回,Let,U为论域（非空对象集合），I为U中的一组等价关系，,Then,集合,X,关于,I,的,下近似,（,Lower approximation,）,是由那些根据现有知识判断肯定属于,X,的对象所组成的最大集合，有时也称为,X,的正区（,positive region,），,记做,POS,（,X,）,集合,X,关于,I,的,上近似,（,Upper approximation,）,是由所有与,X,相交非空的等效类,I,（,x,）的并集，是那些可能属于,X,的对象组成的最小集合。

如果上下近似是相等的,则这是一个,精确集合,否则它是一个,粗糙集,其中下近似称为该概念的,正区域,上下近似的差称为,边界,上近似以外的区域称为,负区域,（Negative region），记为NEG（x）so,R1(颜色),R2(形状),R3(体积),class,X1,红,圆形,小,1,X2,蓝,方形,大,1,X3,红,三角形,小,1,X4,蓝,三角形,小,1,X5,黄,圆形,小,2,X6,黄,方形,小,2,X7,红,三角形,大,2,X8,黄,三角形,大,2,等价类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,近似的示意图,假定有一个信息系统,有两个属性.属性一有5个值,属性二有6个值.现在有一个要近似的集合(X),在图中用红色的圆表示.,仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.,使用两个属性进行划分的情况,加入第二个属性,负区域,正区域(下近似),边界区域,上近似,综合表示,返回,基本概念（5）,粗糙度,下近似、上近似及边界区等概念称为可分辨区，刻化了一个边界含糊(vague)集合的逼近特性。

粗糙程度,按右边公式计算式中|表示集合的基数或势，对有限集合表示集合中所包含的元素个数例2,的粗糙度,2/5,返回,基本概念（6）粗糙隶属函数 （,Rough membership function,),含糊集合没有清晰的边界，即，根据论域中现有知识无法判定某些元素是否属于该集合在RS中，不确定（uncertainty）这个概念是针对元素隶属于集合的程度而言例2,中，I为属性R1上构成的等价关系时，x1对集合的粗糙隶属函数为：2/3,粗糙度与粗糙隶属函数,vague（粗糙度）：用来描述集合，指集合的边界不清楚,uncertainty（粗糙隶属函数）：描述元素，指某个元素是否属于某集合是不确定的返回,粗糙集理论的基本概念,粗糙集理论的应用,（规则挖掘和属性约简）,其他,粗糙集的应用,粗糙集在数据挖掘中的应用,基于粗糙集的数据约简,返回,是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确，不一致，不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律,1.粗糙集在数据挖掘中的应用,粗糙集理论的的数学基础：假定所研究的每一个对象都涉及到一些信息（数据、知识），如果对象由相同的信息描述，那么它们就是相似的或不可区分的。

粗糙集对不精确概念的描述是通过上、下近似这两个精确概念来表示的Example 例3 含6个流感病例的表,（表43）,病例,头疼,肌肉疼,体温,流感,P1,否,是,高,是,P2,是,否,高,是,P3,是,是,很高,是,P4,否,是,正常,否,P5,是,否,高,否,p6,否,是,很高,是,Step1.寻找不可分辨关系：,“头疼”：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,p6,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的负区为 NEG(X)=p4,集合X的边界区为 BND(X)=p2,p5,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(体温高）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之间的相互依赖程度，确定在决策属性D之下的条件属性集合C的重要性,即，决策属性集合D 对条件属性集合C的依赖程度用如下定义来表示：,POSc(D)是属性集C在U/IND(D)中的正区域。

example,例4.属性依赖度的计算,U,A1,A2,A3,A4,A5,1,0,0,1,0,0,2,1,0,2,1,1,3,1,1,1,0,0,4,0,2,1,1,1,5,1,2,1,0,1,6,1,0,1,0,0,7,1,2,2,1,1,8,0,0,2,1,1,令CA1,A2,D=A5,依据属性A1、A2，可得到U/IND（D）：,1,8,2,6,3,4,5,7,正区域为：4,5,7,So，POS,C,(D)POS,A1,A2,(A5)4,5,7,Q,(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,A5,1,0,0,1,0,0,2,1,0,2,1,1,3,1,1,1,0,0,4,0,2,1,1,1,5,1,2,1,0,1,6,1,0,1,0,0,7,1,2,2,1,1,8,0,0,2,1,1,表4,令CA1,A2,D=A5,有POS,C,(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。