您好,欢迎来到飒榕旅游知识分享网。
搜索
您的当前位置:首页不完备信息系统一种新的粗糙集的性质

不完备信息系统一种新的粗糙集的性质

来源:飒榕旅游知识分享网
计算机科学2004Vo1. 31N2. 10A不完备信息系统一种新的粗糙集的性质”杨晓平                (浙江海洋学院信息学院舟山316004)Abstract  In this paper, a new approximation set is proposed, the properties of lower and upper approximations arediscussed. They are more accurate in partition of the universe of discourse than previous definition.Keywords  Rough fuzzy sets,Incomplete information systems, Description    自从波兰数学家Pawlak提出粗糙集的概念与方法以来,粗糙集理论迅速发展,不完备信息系统作为粗糙集理论的一r要研究方向,近年来取得了AT U(d})且d(}- AT,决策属性d是完备的。如果(U,AT)是完备的信息系统,则S称为完备决策表。如果(U,AT)是不完备的,则S称为不完备决策表。    例1表1是一个不完备决策表S=(U,ATU(d}),其中U= (XI ,xz,...,X7) .AT= (a,b)是条件属性集,d是决策属性。a,b和d分别表示收缩压,舒张压和血压。V,= (H, N, L) ,V6= {H,N,L} ,V,很多成果[[1-61,特别随着计算机科学的发展,不完备信息系统更是成了信息恢复、模糊关系数据库、医疗诊断、知识发现、机器学习、粗糙数据分析等人工智能领域的基础概念。Kryszkiewiczc,一‘〕提出T近似集的概念,替代完备信息系统中的等价类,得到了相应的粗糙集。本文提出了具有相同描述的支持集类构成的基本模块(称之为描述集类)以代替粗糙集中的相似类。所有的描述类构成了论域的覆盖,与相似=(H,N,L},H,N和L分别表示各种压力的指标是高的,正常的和低的。在以下的讨论中,    记号n表示逻辑“与”。若vEV󰀀aEA,属性对((a,v)称为是A的基本元。所有的A基本元或者它的逻辑“与”n连接称为A描述,设t为描述,若基本元((a,v)存在于t中,我们简单地称(a, v) Et,若b' aEA,(a,v)Et,则称t为A的全描述。II t 11 =(xEU;vEa(x);(a,v)Et}称为t的支持集。如果t和:是两个描述且A(t)门A(s)=必,可以很容易地得到}}tAs}}=}}tII门II‘II。如果ACAT,    定义:FDES     (A) = (t,t是A的描述;}!t II 7}=O)对任意t     E DES (A),如果A(t) =A,则t是完全的A描述,定义为:FDES     (A) = (t,t是A的完全描述}集类相比有其更好的性质。)1基本概念设S=(    U,AT)是一个信息系统,其中U为非空有限论域,U中的元素称为对象。AT是有限非空属性集。对于每一个aEA,a:U-V。且V xEU,a(x) E Va,称V,为属性a的值域。如果信息系统中的某些属性值缺省或部分知道,这样的系统称为不完备信息系统,属性值函数a (x)可以定义为从U到V,的幂集的一个集值映射。如果a (x)部分已知,比如说,如果知道a (x)不是V。中b,‘值,则a (x)可表示为V。一{b,c),表1不完备决策表N一HNLHHL三翔劝为介瓜为集理论。。64。设S=(    U,AT)是一个不完备信息系统,对于任意的aEAT和v E V,,如果vEa(x) na(y),也就是{{x,y}C}}(a, v)}},x和y被称为关于属性a类似,同样,若ACAT,tEFDES(A),x,yEU则x和  {H}  (N,H)(N,H)     {H}丈L,N)     (N)y被称为关于A类似当且仅当{x,y)C 11 t 11,这些类似关系就把有限论域U分成了几个子集并作为基本模块(称为描述集),这些描述集类构成了U的一个覆盖,我们把它记成U/A,即U/A= (II  t II,tE FDES (A) ),包含x的描述集类记为A(x),即A(x)={II t II:xE II t II ,tEFDES(A)}一个决策表(D,T)是一个信息系统S= (U,。)本课题获得国家自然科学基金项目(No. 60373078)和浙江省教育厅科研计划项目(No. 20020940)资助。杨晓平副教授.研究方向为粗糙    例2在例1中,既然x2, Xs和x。的关于属性值都具有“H",则关于属性a它们都应属于同一个描述类!I (a,H) II,即II (a,H) 11二{x2,xs,x6)。用a,b,AT= (a,必的描述集类可表示以下各种分类:U/     (a}={11 (a,N) II,11 (a,H) 11,11 (a,L)              }})=((XI,x2,          x3,x6,x小(x2,XS,x6},{ x4,x,}}              U/(    b}={11 (b,N) 11,11 (b,H) 11,11 (b,L) 11}          =((xI,x2,x3,xs,x,},(x3,x5,x6},(x4}}U/AT={I    I (a,N) A (b,N) 11,II (a,N) A (b,H)             11,}            }(a, H) A (b, N)}】,}}(a,H) A (b,H)             11,}            }(a,L) A (b, L)}},{}(a,L) A (b,              N) II}={(            x1,x2rx3,xy},(x3,x6),(x2,x5},(              X5 ,X6},(x,},(x,}}。同时也容易看到:    (    a}(x2)={(xi,x2,x3,xs,x小(x2,xs,x6}}定义1设XCU和ACAT,    X关于A下近似和上近似分别记为AT (X)和不(X),其中AT(    x)={Il1t1}!:II t II CX,tEFDES(A)},AT     (X)=( II t II:}}川!nX:A 0,tEFDES(A)},不(    X)-AT(X)称为X关于A的边界,记为BNAT(X)    注:这里所定的下近似和上近似集合,其中的元素是描述集类,而不是U的一个子集。例3在例1中,    设X=(x2,xs,x6),经计算可得:(a}二(X)二((x2.xs.x6}}(a}二(X)={(x󰀀 x2,x3IX6IX7},(x2,xs.x6}}(b}二(X)二必(b. }T (X)=((x1,x2,x3,x5,x7},(x3.xs,x6}}ATT(X)=((xs+x6),(xz,xs}}ATT(X)={(xl,xz,x3,x小(x3,x6},(Xs,x6},(x2,xs))B凡二(    X)={(XI 9XZ,x3,x7),(X3 ,X6)}Kr    yszkiewic:在文[2〕中给出T相似关系,简介如下:设ACAT    SIM     (A)=((x,y)EUXU}V aEA,a (x)门a(              Y) =A必}SA(    X)=(YEUI (x, y)ESIM(A)}称为x的A相似集。记:U/SIM(A)={    WAS l xEU)UISIM(A)中的任何元素称为相容类,UISIM(A)中的相容类一般不构成U的划分,它们构成U的覆当台n们  0    定义2令X(-u和ACAT,X关于A的下近似,上近似和边界分别:As    X=(xEU}SA(x)gX)=(XEX}SA(x)CX}            不X=(    xEU!SA(x) n X--,必)=U(SA(x)!xEX)            BNA    S(X)=A,(X)一鱼(X)2两种粗糙集的性质及比较    若A是一个集类,即其中元素均为集合,则记UA为A中集类的并,即若A=(B󰀀B2,-,B.),则UA=B,UB2U…U B.性质1记    SA=U/SIM(A)=(    SA(x) I xC-U)TA=U/A={I    I t II:t E FDES (A)}则对于TA中的每一个}It11,总有SA中的SA(x),使}}t II CSA(x),我们把这个性质记为TAGSA,由此可见以TA作为U的分类,基本模块更细小一些。证:    e II t}}ETA,因}}t}}非空,存在xE}}t}},下面只需证}}t II CSA(x),    事实上,d yE II t II }x,y具有相同的A完全描述,则(x, y) E SIM(A),所以yESA(x),于是}It11CSA(x)。性质2        元(X)=U{II t II:II t II门X =A必,t E FDES(            A))二U不(x),即不(    X)=U不(X)。证:    d xE不(X),则SA(x)门x}必,于是3 xoESA (x)和XOEX,则xo, x具有相同的A完全描述,故3 tE FDES (A),使xo,XE}】t11,则xo E}}tii n x,于是xE     U{}}t!】:}}t}}nx=A必,t E FDES (A)}。反之HxEU(}】t 1I:ii tii nx=A必,t E FDES(A)},有}!to}}门X并必,to E FDES (A)},xE}}to】}。因}}to}}门X=A必,则3 x, E}}to}】nx,于是xo,x E lit (1,且xoEX,即(x,, x) E SIM(A),从而xo ESA (x)门XO(15,即fl xEAs(X)综上,性质2由此得证。性质3        SA(x)=U(}卜}},xE}}t}},tEFDE,S(A)}即SA中的x的相似类恰为TA中所有包含x的类的并,即SA(X)= UA(x),证:    b yESA(x),则x,y具有相同的A的完全描述。即有to E FDES (A),使x,yE 11 to!},所以(下转第94页)           。65。           DU)) = Lo?,可知成立,转6);6)输出最小约简REDU:    输出最小约简为(a,b,c}。法不需要分明矩阵;并且Rough集中数据约简的方法没有考虑到各等价关系之间的拓扑结构,而我们的方法使用一个反映各等价关系之间拓扑结构的率度幂图;综上所述,可见其效率较高。使用算法2:        1)计算最小率度,构造率度幂图第。层:Lo    = Rate(IND(A))=}IND(A) I/IIND(U) I“二(1+1+1+1+1)/(5二5) = 5/25;结论(本文以Ro    ugh集发展的粒计算理论为基础建立了知识的率度概念,考虑到等价关系的空间拓扑结构而定义了率度幂图,并给出了在率度幂图中实现数据约简的两种算法。对算法的实现过程作了应用举例,得到和使用分明矩阵法数据约简相    2)按宽度扩展分枝构成率度幂图下一层,图2显示了扩展过程,括号内为率度值,星号表示不能再扩展。    3)从图2可知{a,b,e),(a,b,c}为最小约简。同的结果。最后和分明矩阵法作了简单比较。夕参考文献                 这个结果和文〔4」中的分明矩阵法求所有最小    约简的结果相同。分明矩阵法的时间和空间复杂度1  Pawlak Z. Rough Sets [J]- International Journal of Computer and是关于信息系统S的大小成指数变化;文【5]中给出Inf    ormation Science, 1982,11(5):341-3562  Zadeh L A. Fuzzy logic=computing with words [J].IEEE,求所有最小约简的时间复杂度为0(21AIIIAIJUJI'),3  PawlTr    ansactak Z. ions Rough on FuzSetzy s SystTheorems, etic1996,al Aspe4:c103-111ts of Reasoning about虽然率度幂图中所有结点数为2 JAI,搜索率度幂图空Dat    a [M]. Kluwer Academic Publishers, Dordrecht,Boston,Lon-间也是成指数增长,但是不必搜索全部结点,可以根4刘清Rough集及Rough推理[don,    1991M].北京:科学出版社,2001.51据率度进行剪枝,正如图2所示;分明矩阵法需要一^-53    5刘业政.杨善林,马溪骏.粗糙集数据分析的计算方法[J].合肥工个}AIIUI'数量级的矩阵,随着属性A和论域U的业大学学报(自然科学版),  增加,其空间和时间复杂度急剧增加[[61,而我们的算刘清,刘少辉,郑非.Rough逻辑及其在数据约简中的应用〔2002,25(2)J].软件学报,2001,12(3)(上接第65页)3,可以得到    yE U{Iltll:xEIltll,tEFESE(A)}A,(X)CUAT(X)CXCAT(X)=As(X)反之,V xE lltll,tEFDES(A),欲证SA(x);Qll tll。只从中我们可以清楚地看到用 ̄坠鱼(X)作为X的下需证V YE Iltll,tEFDES(A),xE Iltll,一定有YESA近似比As (X)要好一些。(x)即可。因为V yEIItil,tEFDES(A),xEIltll,显结论    本文提出了以类似关系构成描述集类作然有x,yE Iltll且t E FDES (A)。这说明x,y具有相为论域的分类的方法,定义了下上近似,构造了相应同的A的完全描述,所以YES从x),的粗糙集,对其性质作了研究,与已有的相似类方法综上,性质3得证。    相比较,可以看出相似类的构造:即每一个相似集都性质4    是若干描述集的并,相似类作为论域的覆盖,有较多U{I    ltil:IItllg;X,tEFDES(A)}重叠部分,因此用描述集作为论域的分类的基本模cxc     U(Iltll:Iltll flx=A必,tEFDES(A) }块,精度更高,所定义的下、上近似使边界更小,因此即以A袱X)CXC     UAT(X)。也可以更精确地近似刻画论域的子集。证:    V xEIItil,Iltll=X,tEFDES(A),显然xEX,参考文献                    V xEX,包含x的A完全描述记为t,则xE llt1  Wu Wei-Zhi,Mi Ju-Sheng,Zhang Wen-Xiu. New Rough Set Ap-II。于是xE IItii (1 X:AO,tEFDES(A),pr    oach to Knowledge Discovery in Incomplete Information Sys-t    ems. In: IEEE proc. of the Second Intl. Cord. on Machine Learn-所以xE U{ Ilt ll : Iltl旧X00,tEFDES(A)},i  ng and Cybernetics, 2003. 1713^-1718性质52  Kryszkiewicz M. Rough Set Approach to Incomplete InformationSyst    ems. Information Sciences, 1998,(112)39-49As (X)C U{Iltll:lltllCX,tEFDES(A),3  Kryszkiewicz M.  Incompleteness Aspects in Rough Set Ap-As (X)C UAT(X)。pr  oach. In: Proc. of JCIS'98. Raleigh, NC. USA, 1998, 2: 371 ̄374    证:    V xEAs(X),则有S抓x)CX,由性质3,至4  Kryszkiewicz  M. Rules  in  Incomplete  Information  Sys-t    erns. Information Sciences, 1999,113:271-292少有一个!It. 11,使xEIItoII,t.EFDES(A)且}It. 11 9;s."5  Mi Ju-Sheng. Wu Wei-Zhi, Zhang Wen-Xiu. Approaches to Ap-(x)CX,因此pr    oximation Reducts in Inconsistent Decision Tables. LectureNotes in Artificial Intelligence 2639,2003. 283^-286xE U(IIrII:II tII CX,tEFDES(A) }6张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法.北京:科学从而As (X)CUAT(X),从而结合上面性质2,性质出版社,    2001・94・

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- sarr.cn 版权所有 赣ICP备2024042794号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务