《4粗糙集与数据约简》由会员分享，可在线阅读，更多相关《4粗糙集与数据约简（76页珍藏版）》请在金锄头文库上搜索。
1、智能信息处理技术智能信息处理技术华北电力大学华北电力大学华北电力大学华北电力大学第第4章章 粗糙集与数据约简粗糙集与数据约简 不确定性理论不确定性理论1 粗糙集的基本理论与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 粗糙集的研究现状与展望粗糙集的研究现状与展望64.1、不确定性理论不确定性理论v自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。v确定性现象：在一定条件下必然会出现的现象。v不确定性的分类：随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。用概率来度量。
2、概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律概率规律。模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律隶属规律。粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。4.1、不确定性理论不确定性理论v经典集合、模糊集合、粗糙集的关系经典集合认为一个集合完全有
3、其元素所决定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数X(x)0,1是二值逻辑。模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数X(x)0,1，即在闭区间0,1可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观经验给定。粗糙集合把用于分类的知识引入集合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：x肯定不属于X；x肯定属于X；x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的关于论域的知识。粗糙集的隶属函数为阶梯状，对不确定性信息的描述是粗糙的，但粗糙隶属
4、函数是可计算的。粗糙集主要用于对信息系统进行约简和分类。1.00.80.60.40.20.00.20.40.60.81.0第第4章章 粗糙集与数据约简粗糙集与数据约简 粗糙集的基本理论与方法粗糙集的基本理论与方法2 不确定性理论不确定性理论1 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 粗糙集的研究现状与展望粗糙集的研究现状与展望64.2 粗糙集的基本理论与方法粗糙集的基本理论与方法 粗糙集的基本概念粗糙集的基本概念1 粗糙集的基本思想粗糙集的基本思想2 粗糙集的基本特点粗糙集的基本特点34.2.1、粗糙集的基本概念粗糙集
5、的基本概念v知识与分类在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分辨现实的或抽象的对象的能力。假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其划分开。粗糙集理论的核心是等价关系，通常用等价关系替代分类，根据这个等价关系划分样本集合为等价类。从知识库的观点看，每个等价类被称为一个概念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。4.2.1、粗糙集的基本概念粗糙集的基本概念v知识表达系统
6、一个知识表达系统或信息系统S可以表示为有序四元组S=U,R,V,f其中，U=x1,x2,xn为论域，它是全体样本的集合；RCD 为属性集合，其中子集C是条件属性集，反映对象的特征，D为决策属性集，反映对象的类别； 为属性值的集合，Vr表示属性r的取值范围；f:URV 为一个信息函数，用于确定U中每一个对象x的属性值，即任一xiU，rR，则f(xi,r)=Vr属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是4.2.1、粗糙集的基本概念粗糙集的基本概念v不可分辨关系在粗糙集中，论域U中的对象可用多种信息（知识
7、）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集BR，如果对象xi,xjU，rB，当且仅当f(xi,r)=f(xj,r)时，xi和xj是不可分辨的，简记为Ind(B)。不可分辨关系称为等价关系。例如：只用黑白两种颜色把空间中的一些物体划分成两类：黑色物体、白色物体，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：黑色方物体、黑色圆物体、白色方物体、白色圆物体。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。不可分辨关系这一概念在
8、RS中十分重要，它反映了我们对世界观察的不精确性。另一方面，不可分辨关系反映了论域知识的颗粒性。知识库中的知识越多，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致信息量增大，存储知识库的费用越高。4.2.1、粗糙集的基本概念粗糙集的基本概念v基本集合由论域中相互不可分辨的对象组成的集合称之为基本集合，它是组成论域知识的颗粒。例如：考虑条件属性：头疼和肌肉疼。对于x1,x2,x3这三个对象是不可分辨的。x4,x6在这两个属性上也是不可分辨的。由此构成的不可分辨集x1,x2,x3,x4,x6,x5被称为基本集合。设论域U为
9、有限集，R是U的等价关系簇，则K=U,R称为知识库，知识库的知识粒度由不可分辨关系Ind(R)的等价类反映。属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是4.2.1、粗糙集的基本概念粗糙集的基本概念v下近似集和上近似集下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成的集合，即R-(X)=xU,xR X其中， xR 表示等价关系R下包含元素x的等价类。上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对象所组成的集合，即R(X)=xU,xR X其中， xR 表示等价关系R下包含元
10、素x的等价类。给定知识表达系统S=U,R,V,f，对于每个样本子集X U和等价关系R，所有包含于X的基本集的并（逻辑和）为R-(X)；所有与X的交(逻辑积)不为空集的基本集的并为R(X)。4.2.1、粗糙集的基本概念粗糙集的基本概念v正域、负域和边界域正域：Pos(X)=R-(X)，即根据知识R，U中能完全确定地归入集合X的元素的集合。负域：Neg(X)=U-R-(X)，即根据知识R，U中不能确定一定属于集合X的元素的集，它们是属于X的补集。边界域：Bnd(X)= R-(X) - R-(X) ，边界域是某种意义上论域的不确定域，根据知识R，U中既不是肯定归入集合X，又不能肯定归入集合X，的元素
11、构成的集合。边界域为集合X的上近似与下近似之差，如果Bnd(X)是空集，则称集合X关于R是清晰的；反之，如果Bnd(X)不是空集，则称集合X为关于R的粗糙集。因此，粗糙集中的“粗糙”（不确定性）主要体现在边界域的存在。集合X的边界域越大，其确定性程度就越小。4.2.1、粗糙集的基本概念粗糙集的基本概念v粗糙度（近似精确度）对于知识R（即属性子集），样本子集X的不确定程度可以用粗糙度R(X)来表示为R(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个数）。0R(X)1，如果R(X)1，则称集合X相对于R是确定的，如果R(X)kQ。 当k=1时，称知识Q完全依赖于知识P； 当0k1时
12、，称知识Q部分依赖于知识P； 当k=0时，称知识Q完全独立于知识P。 依赖度k反映了根据知识P将对象分类到Q的基本概念中去的能力。确切的说，当PkQ时，论域中共有kCard(U)个属于Q的P正域的对象，这些对象可以依据知识P分类到知识Q的基本概念中去。例 U=x1,x2,x8，U/P=x1,x2,x3,x4,x5,x6,x7,x8，U/Q= x1,x2,x3,x4,x5,x6,x7,x8，求依赖度k。解：PosP(Q)=x1x2x3,x4x5,x6=x1,x2,x3,x4,x5,x6 k=6/8=0.75 即知识Q相对于知识P的依赖度为0.75第第4章章 粗糙集与数据约简粗糙集与数据约简 决策
13、表的约简决策表的约简4 不确定性理论不确定性理论1 粗糙集的基本理论与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 粗糙集的研究现状与展望粗糙集的研究现状与展望64.4 决策表的约简决策表的约简 决策表决策表1 分辨矩阵与分辨函数分辨矩阵与分辨函数3 属性的重要性属性的重要性2 决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法4 决策规则的生成决策规则的生成54.4.1、决策表决策表v决策表是一类特殊的知识表达系统，它是指当满足某些条件时，决策应该怎样进行。多数决策问题都可以用决策表形式表达，这一工具在决策应用中起
14、着重要作用。v定义：设S=(U,R)为一知识表达系统，若R可划分为条件属性集C和决策属性集D，则CD=R,CD=。具有条件属性和决策属性的知识表达系统可表示为决策表，记作T=(U,R,C,D)或简称CD决策表。Ind(C)的等价类称为条件类，Ind(D)的等价类称为决策类。决策表可分为一致决策表和非一致决策表。 当且仅当D依赖于C，即CD时，称决策表是一致的； 当且仅当CkD(0k1)时，称决策表是不一致的。决策表必须是一致的才能够约简。对于不一致的决策表，首先要将其分解为两个决策表，一个为一致决策表，另一个为非一致决策表，然后再对一致决策表进行约简。4.4.1、决策表决策表例 设论域U=x1
15、,x2,x7，属性集R=CD，条件属性集C=a,b,c,d，决策属性集D=e。决策表如下所示：由决策表可知： U/C=x1,x2,x3,x4,x5,x6,x7 U/D=x1,x2,x7,x3,x5,x6,x4 Posc(D)=x1,x2,x3,x4,x5,x6,x7故该决策表是一致决策表。Uabcdex110211x210201x312002x412210x521002x621102x7212114.4.1、决策表决策表U/(a)=x1,x2,x3,x4,x5,x6,x7 Pos(a)(D)=U/(b)=x1,x2,x3,x4,x5,x6,x7 Pos(b)(D)=x1,x2U/(c)=x1,
16、x2,x4,x7,x3,x5,x6 Pos(c)(D)=x3,x5U/(d)=x1,x4,x7,x2,x3,x5,x6 Pos(d)(D)=U/(a,b)=x1,x2,x3,x4,x5,x6,x7 Pos(a,b)(D)=x1,x2U/(a,c)=x1,x2,x4,x3,x5,x6,x7 Pos(a,c)(D)=x3,x5,x6,x7U/(a,d)=x1,x4,x2,x3,x5,x6,x7 Pos(a,c)(D)=x5,x6,x7U/(b,c)=x1,x2,x3,x4,x5,x6,x7 Pos(b,c)(D)=x1,x2,x3,x4,x5,x6,x7 U/(b,d)=x1,x2,x3,x4,x
17、5,x6,x7 Pos(b,d)(D)=x1,x2,x3,x4,x5,x6,x7U/(c,d)=x1,x4,x7,x2,x3,x5,x6 Pos(c,d)(D)=x2,x3,x5,x6U/(b,c,d)=x1,x2,x3,x4,x5,x6,x7 Pos(b,c,d)(D)=x1,x2,x3,x4,x5,x6,x7U/(a,c,d)=x1,x4,x2,x3,x5,x6,x7 Pos(a,c,d)(D)=x2,x3,x5,x6,x7U/(a,b,d)=x1,x2,x3,x4,x5,x6,x7 Pos(a,b,d)(D)=x1,x2,x3,x4,x5,x6,x7U/(a,b,c)=x1,x2,x3,
18、x4,x5,x6,x7 Pos(a,b,c)(D)=x1,x2,x3,x4,x5,x6,x7所以，b是C中D不可省的,b,c和b,d是两个C的D约简，C的D核为b。4.4.1、决策表决策表例 不一致决策表分解。下表所示为一非一致决策表，其中C=a,b,c,D=d,e,将其分解为两个决策表，一个是一致的，另一个是非一致的。Uabcde132300201131323303401321522032611101701103832310Uabcde323303401321522032611101Uabcde1323002011317011038323104.4 决策表的约简决策表的约简 属性的重要性属性
19、的重要性2 分辨矩阵与分辨函数分辨矩阵与分辨函数3 决策表决策表1 决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法4 决策规则的生成决策规则的生成54.4.2、属性的重要性属性的重要性v 在一个知识系统中，不同的属性具有的重要程度是不同的。在传统的数据分析中，这种重要性需要事先假设，一般有领域专家给出的权重表示，具有一定的主观色彩。在粗糙集方法中，不需要事先假定的信息（先验知识），利用决策表中的数据可以计算其属性的重要性。v 判断属性重要性的方法：从决策表中去掉一些属性，再来考虑没有该属性后分类会怎样变化：若去掉该属性会相应地改变分类，则说明该属性的强度大，而重要性高；反之说明该属性
20、的强度小，即重要性低。v 对于属性的重要性可以利用依赖度rP(Q)来描述。对于属性集D导出的分类属性集BB的重要性，采用两者的依赖度的差来度量，即rB(D)- rB-B(D)。这表示从集合B中去掉某些属性子集B后对对象进行分类时，分类U/D的正域将会受到怎样的影响。4.4.2、属性的重要性属性的重要性例 某一知识表达系统如表所示。计算表中属性a,b,c相对属性d,e的重要性。解：定义C=a,b,c,D=d,e，则可以构成各种分类： U/(b,c)=1,5,2,7,8,3,4,6 U/(a,c)=1,5,2,8,3,6,4,7 U/(a,b)=1,5,2,8,3,4,6,7 U/(a,b,c)=
21、1,5,2,8,3,4,6,7 U/(d,e)=1,2,7,3,6,4,5,8Uabcde1102202011123200114110225102016220117211128011014.4.2、属性的重要性属性的重要性 PosC(D)=3,4,6,7 PosC-a(D)=3,4,6 PosC-b(D)=3,4,6,7 PosC-c(D)=3,4,6,7故 rC(D)=Card(PosC(D)/Card(U)=4/8=0.5 rC-a(D)=Card(PosC-a(D)/Card(U)=3/8=0.375 rC-b(D)=Card(PosC-b(D)/Card(U)=4/8=0.5 rC-c
22、(D)=Card(PosC-c(D)/Card(U)=4/8=0.5因此 rC(D) rC-a(D)0.125 rC(D) rC-b(D)0 rC(D) rC-c(D)0可知，属性a是最重要的，其将U/D的正域改变的最多；属性b和c无关紧要，去掉它们后，分类依赖度未产生变化。4.4 决策表的约简决策表的约简 分辨矩阵与分辨函数分辨矩阵与分辨函数3 决策表决策表1 属性的重要性属性的重要性2 决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法4 决策规则的生成决策规则的生成54.4.3、分辨矩阵与分辨函数分辨矩阵与分辨函数v分辨矩阵 设S(U,R,V,f)为一信息系统，RCD是属性集合，子
23、集C=ai|i=1,2,m和Dd分别为条件属性集和决策属性集，U=x1,x2,xn为论域，ak(xj)是样本xj在属性ak上的取值。定义系统的分别矩阵为M(S)=mijnn，其i行j列处元素为因此，分辨矩阵中元素mij是能够区别对象xi和xj的所有属性的集合；但若xi和xj属于同一决策类时，则分辨矩阵中元素mij的取值为空集。分辨矩阵是一个依主对角线对称的n阶方阵，在进行分辨矩阵运算时，只需考虑其上三角(或下三角)部分。4.4.3、分辨矩阵与分辨函数分辨矩阵与分辨函数v分辨函数 对于每一个分辨矩阵M(S)对应唯一的分辨函数fM(S)，其定义为：信息系统S的分辨函数是一个具有m元变量a1,a2,
24、am(aiC,i=1,2,m)的布尔函数,它是(mij)的和取，而(mij)是矩阵项mij中的各元素的析取，即 fM(S)(a1,a2,am)=mij, 1j in, mij v分辨函数的析取范式中的每一个合取式对应一个约简。而核则是分辨矩阵中所有单个元素组成的集合，即 Core(R)=akR:mij=ak, 1j inv根据分辨函数与约简的对应关系，可以得到计算信息系统S约简Red(S)的方法： 计算信息系统S的分辨矩阵M(S)； 计算分辨矩阵M(S)对应的分辨函数fM(S)； 计算分辨函数fM(S)的最小析取范式，其中每个析取分量对应一个约简。4.4.3、分辨矩阵与分辨函数分辨矩阵与分辨函
25、数例 设有信息系统S=(U,R),U=x1,x2,x6,R=a,b,c,d，其数据表格如右表所示。利用分辨矩阵及分辨函数求约简及核。解：分辨矩阵M(S)如表格所示：分辨函数为：fM(S)(a,b,c,d)=(bcd)(b)(abcd) (ad)(abcd) (bcd)(ad) (abc)(ad) (abcd) (abd) (abcd)(bcd) (bcd) =b(ad)=abbd因此该信息系统有两个约简a,b和b,d，核是babcdx10000x20211x30100x41212x51001x61212x1x2x3x4x5x6x1x2b,c,dx3bb,c,dx4a,b,c,da,da,b,c
26、,dx5a,da,b,c a,b,d b,c,dx6a,b,c,da,da,b,c,d b,c,d4.4 决策表的约简决策表的约简 决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法4 分辨矩阵与分辨函数分辨矩阵与分辨函数3 决策表决策表1 属性的重要性属性的重要性2 决策规则的生成决策规则的生成54.4.4、决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法v 采用分辨矩阵可以方便的求解属性集合的核和约简。v C的D核就是分辨矩阵中所有只有一个元素的矩阵项mij的集合，即 CordD(C)=akC:mij=ak, 1j inv 分辨矩阵fM(S)的极小析取范式中各个合取式分别对应
27、C的D约简，即若属性集合CC是满足以下条件 Cmij 对所有mij 的一个最小属性子集，则称C是C的D约简(相对约简)。4.4.4、决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法例 求下面决策表的属性约简。解：分辨矩阵如下表所示：Uabcdex110211x210201x312002x412210x521002x621102x721211Ux1x2x3x4x5x6x7x1x2x3b,c,db,cx4bb,dc,dx5a,b,c,da,b,ca,b,c,dx6a,b,c,da,b,ca,b,c,dx7a,b,c,da,bc,dc,d4.4.4、决策表属性约简的分辨矩阵方法决策表属性约简
28、的分辨矩阵方法分辨函数为：fM(S)(a,b,c,d)=(bcd)(b)(abcd)(abcd)(bc)(bd) (abc)(abc)(cd)(abcd)(abcd) (ab)(cd)(cd) =b(cd) =bcbd故C的D约简有两个，分别是b,c和b,d,C的D核为b。约简后的决策表如下所示Ubcex1021x2021x3202x4220x5102x6112x7121Ubdex1011x2001x3202x4210x5102x6102x71114.4 决策表的约简决策表的约简 决策规则的生成决策规则的生成5 分辨矩阵与分辨函数分辨矩阵与分辨函数3 决策表决策表1 属性的重要性属性的重要性2
29、 决策表属性约简的分辨矩阵方法决策表属性约简的分辨矩阵方法44.4.5、决策规则的生成决策规则的生成v 决策表是对信息系统中有效事实和规律的描述，根据表中数据能够推导出所有可能的规律。v 从决策表生成决策规则是粗糙集的主要应用之一。v 设T=(U,R,V,f)是决策表，R=CD，C为条件属性集，D为决策属性集。令Xi和Yi分别表示条件类和决策类。 Des(Xi)表示条件类Xi的描述，定义为 Des(Xi)(a,va)|f(x,a)=va,aC Des(Yj)表示决策类Yj的描述，定义为 Des(Yj)(a,va)|f(x,a)=va,aD 决策规则定义为 Tij：Des(Xi)Des(Yj),
30、XiYj 规则Tij的确定因子为 (Xi,Yj)=Card(XiYj)/Card(Xi) 显然，01 当(Xi,Yj)1时，Tij是确定性规则； 当01时，Tij是不确定的规则，此时(Xi,Yj)反映Xi中的对象可分类到Yj中的比例。4.4.5、决策规则的生成决策规则的生成v 决策表中所有决策规则的集合称为决策算法。从决策表中提取决策规则时，如果多个对象的信息（属性值）完全相同，则只保留其中一个（它们反映相同的决策规则），然后求条件属性的相对约简，得到约简的决策表。约简后的决策表具有更少的条件属性，但具有和原决策相同的知识。v从决策表中生成规则需要经过以下步骤： 数据预处理。将知识表达系统中的
31、初始数据信息转换为粗糙集形式，并明确条件属性和决策属性； 数据约简。生成分别矩阵，并在分辨矩阵的基础上生成约简的属性集； 发现规则。在约简的决策表中，根据预先设定的确定性因子发现决策规则。Ubcex1021x2021x3202x4220x5102x6112x7121(b,0)(c,2)(e,1)(b,2)(c,0)(e,2)(b,2)(c,2)(e,0)(b,1)(c,0)(e,2)(b,1)(c,1)(e,2)(b,1)(c,2)(e,1)第第4章章 粗糙集与数据约简粗糙集与数据约简 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 不确定性理论不确定性理论1 粗糙集的基本理论
32、与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集的研究现状与展望粗糙集的研究现状与展望64.5、粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用 属性值的离散归一化属性值的离散归一化1 基于分辨矩阵的启发式属性约简算法基于分辨矩阵的启发式属性约简算法2 基于粗糙集方法的实例基于粗糙集方法的实例34.5.1、属性值的离散归一化属性值的离散归一化v 运用粗糙集处理决策表时，要求决策表中的值用离散数据表达。因此在智能信息处理中，对定性的属性或属性的值域是连续的数据要进行预先处理，将其离散化，转换为粗糙集理论所识别的数据，从而提取有用信息，从中发现
33、知识。v 将属性值的定性和定量描述都叫作连续值，则把粗糙集方法中的数据处理称为离散归一化。v 离散归一化方法应该满足下列条件属性离散归一化后的空间维数尽量小，也就是每一离散归一化后的属性值的种类尽量少；属性值被离散归一化后的信息丢失尽量少。v定性说明型属性值的离散化对每一种定性说明概念，可用一种字母或数字代替，作为属性值的离散归一化值。例如颜色属性，属性值为“红”、“黄”、“蓝”、“白”，可以使用“r”、“y”、“b”、“w”或“1”、“2”、“3”、“4”代表。对每一种层次说明概念，可用一种字母或数字代替，作为属性值的离散归一化值。例如温度属性，属性值为“冷”、“凉”、“暖”、“热”，可以使
34、用“a”、“b”、“c”、“d”或“1”、“2”、“3”、“4”代表。4.5.1、属性值的离散归一化属性值的离散归一化v 连续型属性值的离散化等距离划分在每个属性上，根据给定的参数把属性值简单地划分为距离相等断点段，不考虑每个断点段中属性值个数的多少。假设某个属性的最多属性值是xmax，最小属性值是xmin,给定的参数为k,则断点间隔为=(xmax-xmin)/k,得到此属性上的断点为xmini,i=0,1,k。这些断点间的距离相等。等频率划分根据给定的参数k把m个对象分成段，每段有m/k个对象。假设某个属性的最多属性值为xmax，最小属性值为xmin，给定的参数k，则需将这个属性在所有实例上
35、的取值从大到小排列，然后平均分成k段，即得断点集。Naive Scaler算法对于每一个属性aC,进行如下过程：根据a(x)的值，从小到大排列实例xU从上到下扫描,设xi和xj代表相邻实例：如果a(xi)=a(xj),则继续扫描;如果d(xi)=d(xj),即决策相同，则继续扫描；否则，得到一个断点C，C=(a(xi)+a(xj)/2。4.5、粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用 基于分辨矩阵的启发式属性约简算法基于分辨矩阵的启发式属性约简算法2 属性值的离散归一化属性值的离散归一化1 基于粗糙集方法的实例基于粗糙集方法的实例34.5.2、基于分辨矩阵的启发式属性约简算
36、法基于分辨矩阵的启发式属性约简算法v 基于分辨矩阵的启发式最小约简算法可以解决复杂决策表在进行分辨矩阵约简过程中过大的存储空间的问题。v 如果一个约简和分辨矩阵的某项mij的交为空的话，对象i和对象j对于该约简就是不可分辨的。这和约简是能够区分所有对象的最小属性集合相矛盾。所以，可以得出结论：一个约简和分辨矩阵的非空项的交都不能为空。v 由于原始数据未进行约简，所以其候选约简集合R=。检查分辨矩阵的每一项mij和候选约简集合的交，如果交为空，随机从mij中选择一个属性，加到候选约简集合R中；若不为空，就跳过这一项。重复这一过程，直到分辨矩阵中的每一项都检查过了。此时，在R中得到一个“约简”。但
37、这并不是约简本身。例如，假定分辨矩阵中有这样三项：a1,a3,a2,a3,a3。根据此算法，可能会得到候选约简集合为a1,a2,a3或a1,a3，而不是a3。这是因为这个结论是约简的必要而非充分条件。v 一个简单而有效的方法是根据|mij|来对条件属性进行排序。如果mij中只有一个属性，该属性一定是约简的成员。从分辨矩阵的定义可以看出，分辨矩阵中某项的长度越短，该项就对分类所起的作用越大。而且该项出现的越频繁，该项越重要。因此，对分辨矩阵排序时，除了按长度外，在长度相同的情况下，出现频率高的属性更重要。4.5.2、基于分辨矩阵的启发式属性约简算法基于分辨矩阵的启发式属性约简算法v 由此，提出一
38、种新的基于分辨矩阵的计算属性重要性的方法。在生成分辨矩阵的时候，每个属性出现的频率同时被记录，以供以后使用。这些频率被用来评估属性的重要性，并用于属性的优先选择。这是基于如果一个属性出现的越频繁，它的潜在区分能力就越大的考虑。在计算属性的出现频率时，并不是简单的计数，而是加权，加权的大小根据属性出现的分辨矩阵中的长度。因此，对于一个分辨矩阵M=(mij)nn，相应的属性a的重要性计数公式为：式中，|mij|mij包含属性的个数公式体现了两个重要的启发式思想：属性在分辨矩阵中出现的次数越多，属性的重要性越大。属性出现在分辨矩阵中的项越短，属性的重要性越大。4.5.2、基于分辨矩阵的启发式属性约简
39、算法基于分辨矩阵的启发式属性约简算法v 基于分辨矩阵的启发式约简算法如下： 输入：决策表(U,Ad,其中A=ai,i=1,2,n)。 输出：约简(Reduct)。步骤： 令约简后得到的属性集合等于条件属性集合，即Reduct=R； 计算分辨矩阵M，并找出所有不包含核属性的属性组合S； 将所有不包含核属性的属性组合表示为析取范式的形式，即 P=aik,i=1,2,s,k=1,2,m 将P转化为析取范式的形式，并计算属性的重要性； 选择其中重要性最小的属性a，使得Reduct=Reduct-a； 判断约简操作是否成立，若成立，删除因条件属性约简而引入的冗余样本和不一致样本，i=i+1，转步骤；否则
40、恢复约简该属性前的样本数据，结束约简。步骤步中的判断条件为 p1/p0式中，p0为执行本次约简操作前信息表中样本的数量；p1为执行约简后引入的不一致样本数；为阈值，根据实际需要确定，通常取=5%。4.5、粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用 基于粗糙集方法的实例基于粗糙集方法的实例3 属性值的离散归一化属性值的离散归一化1 基于分辨矩阵的启发式属性约简算法基于分辨矩阵的启发式属性约简算法24.5.3、基于粗糙集方法的实例基于粗糙集方法的实例实例1：以气象状况实例作为决策表，如下表所示，则C=a1,a2,a3,a4,a5,a6,D=dU天气a1温度a2湿度a3风a4沙尘a
41、5污染指数a6决策属性dx1晴热高否是中度Nx2晴温暖高是否中度Nx3晴温暖高否否轻度Nx4雨温暖高是是中度Nx5雨凉正常是是中度Nx6雨凉正常否否轻度Px7多云凉正常是否重度Px8多云热高否是重度Px9晴温暖正常是否轻度Px10雨温暖正常否否轻度Px11晴温暖正常是是中度Px12多云温暖高是否中度Px13多云热高否是中度Px14雨温暖高否是中度P4.5.3、基于粗糙集方法的实例基于粗糙集方法的实例项目离散化结果：U天气a1温度a2湿度a3风a4沙尘a5污染指数a6决策属性dx1332212Nx2322122Nx3322221Nx4122112Nx5111112Nx6111221Px72111
42、23Px8232213Px9321121Px10121221Px11321112Px12222122Px13232212Px14122212P4.5.3、基于粗糙集方法的实例基于粗糙集方法的实例分辨矩阵如下：Ux1x2x3x4x5x6x7x8x9x10x11x12x13x14x1x2x3x4x5x61,2,3,5,61,2,3,4,61,2,32,3,4,5,64,5,6x71,2,3,4,5,61,2,3,61,2,3,4,6 1,2,3,5,61,5,6x81,61,2,4,5,61,2,5,61,2,4,61,2,3,4,6x92,3,4,5,63,63,41,3,5,61,2,5,6x
43、101,2,3,5,61,3,4,61,33,4,5,62,4,5,6x112,3,43,53,4,5,61,31,2x121,2,4,511,4,61,51,2,3,5x1311,2,4,51,2,5,61,2,41,2,3,4x141,21,4,51,5,642,3,44.5.3、基于粗糙集方法的实例基于粗糙集方法的实例由可辨识矩阵求出该决策表的核Core=a1,a4。不含核属性的属性组合为 P=(a3a5)(a3a6)=a3(a5a6)这个析取式的每一项中的元素与核元素就组成了约简后的属性集合，即最终得到的属性集合为：a1,a3,a4和a1,a4,a5,a64.5.3、基于粗糙集方法的实
44、例基于粗糙集方法的实例实例2：某科研基金立项评审系统指标体系的优化。下表是原有的项目评审指标体系，其中可得条件属性15个（0115号），决策属性1个（16号），根据已有的样本对该指标体系进行约简，重建更加科学、合理、简捷的科研项目评审指标体系。项目指标立项依据科学意义(01)；应用前景(02)；创新程度(03)；立项依据(04)；国内外研究现状(05)研究方案研究内容(06)；研究方法和技术路线(07)；实现目标的可信度08；经费预算和落实情况(09)研究基础与项目有关的研究工作积累(10)；已具备的研究条件(11)；研究队伍(12)综合意见评审专家对本项目的熟悉程度(13)；综合评价(14)
45、；是否交叉学科或新兴学科(15)；资助(16)4.5.3、基于粗糙集方法的实例基于粗糙集方法的实例(1)对已有样本进行离散化。随机抽取30个样本，离散化结果如下表所示（部分数据），其中第114指标离散化为3个值：1(优)、2(良)、3(差)，第15指标离散化为2个值：1(是)、2(否)；决策属性(16)值2个：0(不资助)、1(资助)。U1234567891011121314151600392122221322313121004033322121113222200041233332333332322001312111222121213121013232222222223333200133211
46、321211232121001342132323322211210013532333332323233204.5.3、基于粗糙集方法的实例基于粗糙集方法的实例(2)计算分辨矩阵。决策表共30项，15个条件属性，1个决策属性。经计算决策表的核属性为空，不包含核属性的属性组合如下所示：根据分辨矩阵的启发式约简算法，计算15个属性的重要性：f(1)=3.2644； f(2)=3.2973； f(3)=2.8719； f(4)=3.2195； f(5)=3.1049； f(6)=2.1064； f(7)=3.7537； f(8)=2.8656； f(9)=3.0751； f(10)=3.8406；f(
47、11)=3.0957；f(12)=3.3640；f(13)=2.7445；f(14)=3.1699；f(15)=2.5283；由此得出属性的重要性排序为：1071221414511938131564.5.3、基于粗糙集方法的实例基于粗糙集方法的实例(3)属性约简。根据精度要求，取=5%，得属性约简结果如下表所示：根据粗糙集属性约简后的评审指标体系为：约简顺序约简指标拟合精度(%)(%)是否可约简1691.192.56是26，1590.932.82是36，15，1388.145.61否项目指标立项依据科学意义(01)；应用前景(02)；创新程度(03)；立项依据(04)；国内外研究现状(05)研
48、究方案研究方法和技术路线(07)；实现目标的可信度08；经费预算和落实情况(09)研究基础与项目有关的研究工作积累(10)；已具备的研究条件(11)；研究队伍(12)综合意见评审专家对本项目的熟悉程度(13)；综合评价(14)；资助(16)第第4章章 粗糙集与数据约简粗糙集与数据约简 粗糙集的研究现状与展望粗糙集的研究现状与展望6 不确定性理论不确定性理论1 粗糙集的基本理论与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用54.6、粗糙集的研究现状与展望粗糙集的研究现状与展望v粗糙集理论与其他不确定
49、性理论的融合协作粗糙集与概率统计相结合粗糙集主要研究信息系统中知识的不准确、不完善的问题，它的基本方法是确定的。将粗糙集方法与概率统计方法联系，可以为确定性和不确定性知识表达系统提供一个统一模型统计粗集模型。统计粗集模型是确定性粗集模型的一个扩展与补充。粗糙集与模糊集相结合粗糙集理论与模糊集合理论都是研究信息系统中知识的不完整、不确定性问题的理论。可以利用粗糙集的概念考虑模糊集的粗近似，利用模糊划分的相似性关系研究集合的近似问题，将二者有机的结合，取长补短，大大丰富了对信息系统中不完善、不精确知识的描述和处理。粗糙集与神经网络相结合粗糙集方法模拟人类的抽象逻辑思维，神经网络方法模拟人类的形象直
50、觉思维，二者既各有特点，又具有公共之处，将二者有机结合，可望为智能信息处理开拓一个光辉前景。4.6、粗糙集的研究现状与展望粗糙集的研究现状与展望v粗糙集研究的展望粗糙集的理论研究主要包括粗糙逻辑、粗糙函数、模型拓展以及理论融合等方面。粗糙逻辑的研究：建立基于粗糙集的不精确推理逻辑，从而在人工智能的近似或不精确推理中发挥作用。粗糙函数的研究：主要包括粗糙函数的各种近似计算，粗糙函数的基本性质，关于它的存储连续、粗糙可导、粗糙积分和粗糙稳定性、粗糙函数控制及建立由粗糙实函数控制的离散动态系统等问题。模型拓展的研究：在继承原始粗糙集模型的基本属性性质前提下，研究如何扩展模型，以更好地用于数据压缩与信
51、息系统的分析等方面。理论融合的研究：如何将粗糙集理论、模糊集理论、证据理论和概率论等不确定的理论用一个统一的逻辑模型来解释，以及实现多种模型在理论与方法上的融合协作也很值得研究。4.6、粗糙集的研究现状与展望粗糙集的研究现状与展望v粗糙集研究的展望（续）粗糙集理论是一门实用性很强的学科，对它的应用研究一直备受关注，并在实际应用中迅速推广。例如，基于RS的实例学习系统、基于RS的决策支持系统、基于RS的数据挖掘系统、基于RS的数据分析和知识发现系统、基于RS的图像识别系统等等。今后一些可能的应用研究领域： 高效约简算法。高效约简算法是粗糙集应用于知识发现的基础，目前尚不存在一种非常有效的方法。寻求快速的约简算法及其增量版本仍然是主要研究方向之一。 海量数据处理。现实中的数据库已经越来越大，粗糙集理论如何应付这一挑战仍旧是一个问题。探索大数据集分析处理的相应算法具有实际意义。 多方法融合技术。粗糙集方法与其他的处理方法有各自的优点，近年来，粗糙集与其他方法的融合协作技术的研究一直备受关注，尤其是同神经网络、遗传算法、数字图像处理等技术的相互渗透补充，取得了良好的效果，并成为当前应用研究的热点之一。Click to edit company slogan .
