近似空间的合成及其应用

第19卷第3期工程数学学报Vol.19 No.32002年08月JOURNAL OF ENGINEERING MATHEMATICSAug.2002Article ID :1005-3085( 2002 )03-0086-09Combination of Approximation Spacesand Its ApplicationsWU Wei-zhil2 ,MI Ju-sheng13，ZHANG Wen-xiu'( 1-Institute for Information and System Sciences , Faculty of Science ,Xi' an Jiaotong University ,Xi' an 710049 ;2- Information College , Zhejiang Ocean University , Zhoushan , Zhejiang 316004 ;3-College of Mathematics and Information Sciences , Hebei Normal University , Shijazhuang 050016 )Abstract : The combinations of approximation spaces in the rough set theory are studied. Their applications to in-formation systems are discussed. It is proved that with the accumulation of more available information ,the lower and upper approximations will provide a more refine description of the concept.Keyworks : Rough sets ; Approximation spaces ; Data analysis ; Information systemsClassification : AMS 2000 )65L07 65N12CLC number :O235Document code : A1 IntroductionThe rough set theory1~3] ,a new mathematical approach to data analysis and data min-ing , has recently received wider attention on the research areas in both of the real -life applica-tions and the theory itself. In the rough set theory , the approximation space based on a binaryequivalence relation on a universe or a partition of the universe is a primitive notion. A approxi-mation space represents an available information in the rough set data analysis. The lower andupper approximation operators used to describe a given concept are constructed by this notion.The concept of accumulation of information has been studied extensively in different theo-ries of uncertain reasoning such as probability theory and D-S evidence theory4- -6]. Many ap-plications of rough set theory use information o中国煤化工rHence , informa-tion accumulation has received little attention inMYHCNMHGinmanyapcationsof the intelligent information systems , the available information may come from different* Received date 2001-03-12. Biography :WU Weizh( Born 1964 ) ,male , doctoral student , associate pro-fessor , majoring in rough set , random set and set valued stochas-tic process.第3期WU Weizhi et al Combination of Approximation Spaces and Its Applications87sources. Thus combination of information may be necessary to make decisions based on all theavailable information. With the accumulation of more information , the lower and upper ap-proximations will be able intuitively to provide a more refined description of the concept.This paper studies the combination of approximation spaces in the rough set theory. Wewill discuss a simple situation where all the pieces of information use the same universe. Its ap-plication to complete and incomplete information systems will be discussed in detail.2 Generalized Rough Set ModelsLet U denote a finite and nonempty set called the universe ,R∈U X U denote a binaryrelation on U. A binary relation may be more conveniently represented by a set-valued mappingr :U→2U: r(x)= {y∈U | xRy}r( x )consists of all R- related elements of x called the relation neighborhood of x and r is re-ferred to as the relation neighborhood operatorof R. The pairA =( U ,R )is referred to as ageneralized approximation space. If R is reflexive and symmetric , then R is referred to as asimilarity relation.Using the mapping r , we can define two unary set- theoretic operators R and R :RX={x∈UI八(x)∈X};RX={x∈U1r(x)∩X≠φ}The pair( RX ,RX )is referred to as the generalized rough set of X induced by R. R and R arereferred to as the generalized lower and upper approximation operators respectively. With therelation neighborhood operator r , we can define another mappingj 20→2u :j(X)= {x∈U|八(x)= X}.X∈UIt is easy to check that j satisfies the following properies :∪{j(X)1 x∈U}= U :X≠Y→j(X)∩j( Y)= φAny set X satisfyingj( X )≠φ is referred to as a local elementofj . LetJ = {XS U1j(X )≠φ},then{j( X )| X∈J }is a partition of the universe U ,thus we callj the relation parti-tion function of RTheorem 1 If R is a reflexive binary relation , thenJ = {(u)lu∈U};((u))Er(u)， Vu∈UProof It is evidently from the definitionof j thatX∈J if and onlyifX∈{(u)| u∈U}ThereforeJ={r(u)|u∈U}For all u∈Uandx∈j(r( u )) ,it isclear thatr(x )= r( u ). By the reflexivity of R,wehavethatx∈r(x),thenx∈r(u),whichfollowsthatj(r(u))Sr(u).The generalized lower and upper appoximat中国煤化工d by the relation par-tition function j ,and vice versa[ 7]:YHCNMHGRX=∪{j(Y)1Y∈X}RX=∪{j(Y)|Y∩X≠φ}j(X)= RX\∪{RY | YCX}If( U 20 P )is a probability space and r is a reflexive relation on U , define88工程数学学报第19卷m( X)= P(j(X)).B(X)= P(RX ),L( X)= P( RX )Then we know from[ 7 ]that m is a mass function on U ,B and L are belief and plausible func-tions defined on U ,moreover ,any belief function defined on U can be represented by a proba-bility measure of a lower approximation with respect to some approximation space.Based on the lower and upper approximationsof a set X E U , the universe U can be di-vided into three disjoint regions , the positive region POS( X ) , the bounded region or thedoubtful region BN( X ) ,and the negative region NEGA( X ) :POS,( X)= R(X )BN( X)= R(X)- R(X )NEGA( X)= U- R( X)One can say with certainty that any element x∈POSA( X )belongs to X , and that any ele-mentx∈NEGA( X )does not belong to X , but one can not decide with certainty whether ornot an elementx∈BNa( X )belongs toX .3 Approximation of Sets in Information SystemsThe rough set model is useful in the analysis of data presented in terms of an ( complete )information system. An ( complete ) information system can be defined by a quadruple S =(UA,Vp).WhereU is a nonempty finite set of objects called universe ;A is a nonempty finite set of attributes ;V= {Va| a∈A },Va is a nonempty set of values of an attributea∈A ;ρ :U X X→V is an information function.The notion of information systems provides a convenient tool for the representation of ob-jects in terms of their attribute of values. For an information systemS =( U A ,V ρ) ,onecan describe relationships between objects through their attribute values. With respect to an at-tribute subset BS A ,a binary equivalence relation Rp can be defined asxy∈UxRrv→dxa)=dya),Va∈BRA is referred to as the relation derived from the information systemS ,and wecal( U ,RA )the approximation space induced from S. With the relation RA , two objects are considered tobe indiscernible if and only if they have the same value on eacha∈A . Based on the equiv-alence relation RA ,one can derive the lower and upper approximations of an arbitary subset Xof U .The generalized rough set models can be an中国煤化工nation systems in thesituation when the precise values of some of theMYHC N M H Gor are known partial-ly. Such a situation can be described by a set- based information system , in which the informa-tion functiond x ,a )is no longer a single value but a subsetof Va . For example ,if V。= {1，2 3} ,anddx a )is missing , then d x a )can be represented by the set of all possible valuesfor the attributea ,thatis,dx a)= V。,ifdx a )is known partially , for instance ,x，第3期WU Weizhi et al Combination of Approximation Spaces and Its Applications89a )does not take the value2 ,thenp x ,a )can be represented by the rest set of all possible val-ues ,that is,dx ra )= {1 3}. Therefore , an incomplete information system is an informa-tionsystemS=(UA,Vp)inwhichV={2V。1a∈A}With respect to an attribute subset BE A ,a binary relation Rp can be defined asx y∈U xRpy→ζx ,a)∩dy a)≠φ ,Va∈BIt is easy to check that RA is reflexive and symmetric , but is not necessarily transitive ,that is ,RA is a similarity relation on U.Ra is referred to as the relation derived from the informationsystemS ,and we call( U ,RA )the approximation space induced from S . With the relationRA ,two objects are considered to be possibly indiscernible if and only if they have the possiblesame value on eacha∈A . Based on the relation RA ,one can also derive the lower and upperapproximations of an arbitrary subset X of U.An information systemS =( U A ,V ,p )is called a decision tableifA = C∪D and C∩D =φ ,where C is called a conditional attribute set ,and D is a decision attribute set. Thedecision tableS =( U ,C∪D ,V，ρ )is deterministic if and only if Rc∈Rp ;otherwise ,itis non- deterministic. The deterministic decision table uniquely describes the decisions to bemade when some conditions are satisfied. In the case of a non- deterministic table , decisions arenot uniquely determined by the conditions. Instead ,a subset of decisions is defined when couldbe taken under circumstances determined by condition.Any pair(a ,0)a∈A ,r∈V。(or v∈2Va if S is an incomplete information system )iscalled a descriptor inS . With respect to an objectx∈U ,a d. ecision rule can be derived bythe expression des(x )Pdesp(x )if and only if rdx )S rx ) ,or equivalently ,x∈Rcr x ),where des& x ) and des( x )are the descriptors of object x in the decision table S =( U ,C∪D ,V p )with respect to the conditional attribute C and the decision attribute D re-spectively ,rd x )and rd x )are the Rc and Rr( x ) relation neighborhoods of x respectively.With every subset X∈U , one can associate an accuracy of approximation of set by B∈A in S defined asμuB(X)=apr( X )|apr:( X )|Where| Y 1 is the cardinalityofset Y . It is clear that0≤pμ6( X)≤1 ,andpe( X)= 1ifXis definable with respect to the approximation space( U ,RB ).4 Combination of Approximation Spaces with the Same Universe中国煤化工。In Section 2 and Section 3 , the problemseneration of rules arefrom a single source of available information.MYHC N M H Gs in information si-ence , the available information may come from different sources. In order to make meaningfuljudgements , we have to combine all the available information. In this section , we will considerthe combination of two approximation spaces with the same universe.4.1 Methodology90工程数学学报第19卷Definition 1 Let A =( U ,R: )and B =( U ,R2 ) be two approximation spaces. Thecombination of the approximation spaces A and B is defined by A①B =( U ,R ) ,where R =R∩R2.It is easy to see that ,if R1 and R2 are equivalent relations , then R is an equivalent binaryrelation , and if R1 and R2 are generalized relations , then R is a generalized binary relation and(x)= r{(x)∩rfx).Theorem2 LetA =(U ,R1 )andB =( U ,R2 )be two approximation spaces and A田B =(U ,R). Let j be the relation partition function induced byR . If R1 and R2 are similari-ty binary relations , then R is still a similarity relation , and moreover ,J={r.(u)∩rAu)|u∈U}j(X)={u∈U1r(u)∩rtu)=X}.X≤UWhereJ is the focal set of j.Proof Assume that R: and R2 are similarity binary relations. Since R 1 and R2 are reflex-ive,x∈r(x);i = 12. It follows thatx∈(x)= r.(x)∩ r(x) ,that is ,R is reflex-ive. Similarly ,R is symmetric. Consequently ,R is a similarity relation. The rest of the proofis trivial.Theorem 3 LetA =( U ,R1 )andB =( U ,R2 )be two reflexive approximation spaces ,thatis,R;i=12,arereflexive.IfA④B=(UR),then,foranyX∈U:(i)RX∈RX∈X∈RX∈R;X,i= 1 2(ii)POS,(X)∪POSE( X )S POSAB X )( ii)NEG,( X )U NEG;( X )∈NEGA( X)(iv)BNAB( X)S BN.( X)∩BNE( X )Proof (i)Ifx ∈R;X , by the definition of lower approximation , we haver( x )EX ,thenr(x)= r(x)∩rkx)∈X ,thatis,x ∈RX , which follows that RX∈RX i = 1 2.RX∈X C RX can be obtained directly because of the reflexivity of R .Ifx∈RX ,by the definition of upper approximation ,we haver( x )∩X≠φ ,then bythe definitionofR , we have[r(x )∩rfx)]∩X=[r{(x)∩X]∩[r以x )∩X J≠φ ,Therefore ,r(x )∩X≠φ ,that is,x∈R;X , which follows that RX S R;X ;i = 1 2.(ii)~( iv ) can be directly induced by(i).Corollary 1 LetA =( U R: )andB =( U ,R2 )be two approximation spaces and A田B =(U R). Then ,foranyX≤U州A田L X )2 max{pa(X )r( X )}.It is clear from Theorem 3 and its Corollary that both the positive region and the negativeregion with respect to the combined approximation, space A F B = ( U ,R ) are larger thanthose with respect to the approximation spaces中国煤化工u ,R2 )espetively.Thus we have shown that with the accumulatioMHCNMHGation,thelowerandupper approximations will provide a more refined description of the concept.4.2 Application to data analysis4.2.1Combinations of complete information systemsLet us assume thatS; =( U ,C1 ,V1 ,P1 )andS2 =( U ,C2 ,V2 ,pP2 )are two complete第3期WU Weizhi et al Combination of Approximation Spaces and Its Applications91information systems with the same universe U in a certain data analysis issue ,where V;= {Via|a∈C;},p{xa)∈Viaa∈C;i=12.S=s,田S2=(U,C,Vρ)isthecombina-tionof Si and S2 . The binary relation derived from S is denoted by Rc , that is ,x y∈U xRcy→ζx a)= dy a),Va∈C.Where the combined attribute set C and the information function d x ra )are defined by the .following ways. Evidently , there are three possible situations :Case 1 The sets of attributes for the two information systems are the same ,i.e. ,C1 = C2Case 2 The intersection of sets of attributes for the information systems is nonempty set ,i.e,C1∩C2≠φCase3 The intersection of sets of attributes for the two information systems is emptyset,i.e,C1∩C2= φWe will combine two information systems for the above three situations as follows :ForCase1letC=C1=C2,defineV= V1X V2= {V1aX V2ala∈C}dx a)=(ρ(x a)p$x a))∈V1aX V2a x∈Ua∈CFor Case2 C = C1∪C2 ,defineVIa，a∈Ci\C2V={V。1a∈C},whereV。=个V2a，a∈C2\C1V1aX V2a，a∈C∩C2(ρ{x a),a∈C1\C2dx a)=〈ρζx xa),a∈C2\Cil(ρ(x ,a )p4x a))，a∈C∩C2For Case3 letC = C∪C2 ,defineV={V。1a∈C},whereVa=(V1a，a∈C1V2a，a∈C2(ρ(x ra ),a∈C1,dxa)=.lpAx a)， a∈C2.Theorem4 LetSi=(U ,C ,V1 rP1 )andS2=(U ,C2 ,V2 ρ2 )be two( complete )in-formation systems , the combination of S1 and S2 is denoted byS= s田S2=(U ,C,V p) ,andlet R1 ,R2 and R be the binary relations derived fromSi S2 ,and S , respectively. Then R =R∩R2.Proof IfC1 = C2 ,then(x y)∈Rθζx a)=(ρ{x a)中国煤化工ρ(y a)pAya))Jρ{x a)= ρ(y a:[YHCNMHGy)∈R∩R2(p6x a)= py xa) (x v)∈R2which fllows that R = R∩R2.The proofs for the rest situations are similar to the proof of case 1.We can see from Theorem 4 that the combined information systemS = S1田S2 =( U，92工程数学学报第19卷C ,V p )is still a complete information system and the combined approximation space( U ,R ) .is a Pawlak approximation space.4.2.2 Combinations of incomplete information systemsLet us assume thatS; =( U ,C1 ,V1 P1 )andS2 =( U ,C2 ,V2 ,pP2 )are two incompleteinformation systems with the same universe U in a certain data analysis issue ,where V;= {Via|a∈C;}np(xa)SViaa∈C;i=12.S=S1田S2=(U,C,Vρ)isthecombina-tionof S1 and S2. The binary relation derived from S is denoted by Rc , that is ,x v∈U xRcy→dx a)∩dy a)≠φ ,Va∈CWhere the combined attribute set C and the information function d x ,a )are defined by thefollowing ways. Similar to the combination of complete information systems , there are threepossible situations :ForCase1letC=C1=C2,defineV= V1x V2= {V1aX V2ala∈C}dx a)=(ρ(x a ),o4x ra))∈ V1aX V2ax∈Ua∈CFor Case2 letC = C∪C2 ,defineVia ，a∈C1\C2V={Va1a∈C},whereVa=?V2a，a∈C2\CiV1aX V2a， a∈C∩C2(ρ{x a),dx ra)=\pfx a ),l(ρ(x a)6x a))，a∈C∩C2For Case3 letC= C1 U C2 ,defineV={Va1a∈C},whereV。=fV1a，a∈C1[Vza ,a∈C2dxa)=[ρ1(x ra),a∈Cilρ4xa)，a∈C2Theorem5 LetSi=( U ,C1 ,V1 ρ1 )andSz=( U ,C2 ,V2 ,P2 )be two incomplete in-formation systems , the combination of S and S2 is denoted byS= s,田S2=(U ,C,V p),and let R ,R2and R be the binary relations derived fromS1 ,S2 ,and S ,respectively. Then .R=R1∩R2.Proof IfC1 = C2 ,then(x v)∈R=(ρ(x a ),p4x a))∩(ρy a )pAy a))≠φfp(x a)∩p{y a中国煤化工(p6x a)∩p6y aYHCNMHGxv)∈R∩R2which fllows that R = R1∩R2. .The proofs for the rest situations are similar to the proof of case 1.We can see from Theorem 5 that the combined information systemS = s,田S2 =( U ,C ,V ρ )is an incomplete information system and the combined approximation space( U ,R )is第3期WU Weizhi et al Combination of Approximation Spaces and Its Applications93still a similarity approximation space.Theorem6 LetS|=(U ,C∪D ,V1 ρ1 )andS2=( U ,C2∪D ,V2 ,pP2 )be two deci-sion tables with the same decision attribute set D andp( x ra )= pSx a )forallx∈U a∈D ,( S1 and S2 may be incomplete ) the combination of Si and S2 is denotedbyS = si田S2=(U,C∪D,Vρ)whereC,V,andρaredefinedasinthesubsection4.2.Ifdesc(x )>desr(x) ,ordesc,(x )>desp( x ) , thendes( x )>desr( x ).Proof It is immediately from Theorem4 , Theorem 5 , and Theorem 3.We can see from Theorem 6 that the set of the decision rules obtained from the combineddecision tableS = S,田S2 =( U ,C∪D ,V ρ )contains all the rules obtained form S1 and .S2 , and furthermore , new rules may be derived from the combined decision table. These newrules will provide us a more refined rule base and reduce the size of the bounded or the doubtfulregion. From which we know that with the accumulation of more information , the lower andupper approximations can provide a more refined description of the concept.5 ConclusionsThis paper studied the combination of two approximation spaces in the rough set theory.This approach is very useful in the applications to intelligent information systems. In this pa-per , we only considered the situation which both the universes in different sources are thesame. However there may exist more general cases in real-life applications , that is , both the u-niverses may have nonempty intersection or the intersection of the two universes may be empty.The combinations of such approximation spaces are more complex in terms of different applica-tions. We give only one approach with the situation U1∩U2≠φ as follows :LetA =( U1 ,Rr )andB =( U2 ,R2 )be two approximation spaces withRi∩R2≠φ .The combination of the approximation spaces A and B is defined byA①B =( U ,R ) ,whereU = Ui∪U2 ,and R is the combined relation on U defined as{r(x)∩( U1\ U2)，x∈U1\ U2(x)= rfx)∩( U2\ U1)，x∈U2\ U1(r{(x)∩rfx)， x∈U∩U2It can be check that if bothA =( U1 ,R1 )andB =( U2 ,R2 )are Pawlak approximation spaceA田B=( U ,R )is also a Pawlak one ,and if bothA =( U1 ,R: )andB=( U2 R2 )are sim-ilarity , then the combined approximation spaceA田B =( U ,R )is also similarity.The approach proposed here will provide a furtber researh nn hnw complete and incom-plete information system can provide flexibility中国煤化工，management process.YHCNMHGReferences :[ 1] Pawlak Z. Rough set[J] Inter J of Inform and Comput Sci ,1982 ;11 145 - 172[2] Pawlak Zet al。Rough sets Theoretical aspects to reasoning about dats[ M ] Boston : Kluwer Academic94工程数学学报第19卷Publisher ,1991:3] Zhang W X ,Wu W Z ,LiangJ Y ,LiD Y. Rough set Theory and ApproacH[ M] Beijing Science Press ,2000[4] Shafer G. A Mathematical theory of EvidencE M ] New Jersey( USA ): Princeton University Press ,1976[5] Chen Y ,Xu P ,Zhang W X. Evidence generation and combination in relational database[ J] ChineseJ ofComput 1994 ;17 10 )729 - 735[6] Zhang W X , Leung Y. The uncertainty reasoning principles[ M] Xi an: Xi' an Jjiaotong UniversityPress ,1996[7] Zhang W X ,Wu W Z. Rough set models based on randomsets(IIJ] J of Xi an Jjiaotong Univ 2000 34(12 )75 -79[8] LingrasPS, Yao Y Y. Data mining using extensions of the rough set model[J] J of the Amer Soc forInform Sci ,1998 49( 5 )415- 422[9] Yao Y Y. Relational interpretations of neighborhood operators and rough set approximation operator{[J ]Inform Sci ,1998 ;11 239 - 259[ 10 ] Krysxkiewicz M. Rouhg set approech to inoomplete information system{J ] Inform Sci .1998 ;112 39 - 49近似空间的合成及其应用吴伟志12，米据生'3，张文修1( 1-西安交通大学理学院信息与系统科学研究所西安710049 ;2.浙江海洋学院信息学院舟山316004; 3- 河北师范大学数学与信息科学学院石家庄050016)摘要:讨论了粗糙集理论中近似空间的合成及其在智能信息系统中的应用。证明了随着可利用信息的.不断增加上下近似对概念的描述也更精确。从而为粗糙集理论的应用提供了更为广阔的前景。关键词粗糙集近似空间数据分析信息系统(上接63页)Nonparametric Approach of Accelerated Life Testingwith Competing Causes of FailureZHANG Zhi-hua .( Naval University of Engineering , Wuhan 430033 )中国煤化工Abstract : Two nonparametric Approache( Linear estima.MYHc N M H Gmator )of aceleaed lifetesting with competing causes of failure are presented by deretuing tne requrement tnat the common parametricfamily of life distributions under all the stresses be specifiesd in advance. the requirement that the time transfor-mation function be speified is relained.Keywords : competing causes of failure ; accelerated life test ; nonparametric estimation ; least square estimation ;least distance estimation