近似空間的合成及其應用

第19卷第3期工程數學(xué)學(xué)報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工程數學(xué)學(xué)報第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工程數學(xué)學(xué)報第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(fēng) 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。=個(gè)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工程數學(xué)學(xué)報第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))≠φf(shuō)p(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工程數學(xué)學(xué)報第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-西安交通大學(xué)理學(xué)院信息與系統科學(xué)研究所西安710049 ;2.浙江海洋學(xué)院信息學(xué)院舟山316004; 3- 河北師范大學(xué)數學(xué)與信息科學(xué)學(xué)院石家莊050016)摘要:討論了粗糙集理論中近似空間的合成及其在智能信息系統中的應用。證明了隨著(zhù)可利用信息的.不斷增加上下近似對概念的描述也更精確。從而為粗糙集理論的應用提供了更為廣闊的前景。關(guān)鍵詞粗糙集近似空間數據分析信息系統(上接63頁(yè))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