粒計算下的粗糙集模型對比

論文類別:計算機論文 > 計算機理論論文
論文作者: 張小峰 鄒海林 賈世
上傳時間:2013/2/1 8:34:00

  摘 要:提出了幾種組合粒下的粗糙集模型,並將其與單一粒下的粗糙集進行了對比,同時又與粒邏輯運算下的粗糙集模型進行比對,創造性地得到了組合粒、單一粒以及粒邏輯運算下的粗糙集模型之間的關系。結果表明,組合粒與粒邏輯運算構成了一個鏈結構,這為探討基於信息粒的知識獲取以及動態粒的推理奠定了基礎。

  關鍵詞:組合粒;粒邏輯運算;單一粒;粗糙集;近似
  
  Comparison of rough set model under granular computing
  
  ZHANG Xiao-feng, ZOU Hai-lin, JIA Shi-xiang
  (School of Information Science & Engineering, Ludong University, Yantai Shandong 264025, China)
  Abstract:This paper proposed the rough set model under combination granule, and compared it with that under single granular, also with rough set model under logical computing of granule, which contributed to the relationship between rough set models under combination granule, singular granules and logical computing of granules. Results show that combination granule and logical computing of granule construct a chain, which will lay a foundation for knowledge acquisition based on information granule and induction based on dynamic granule.
  Key words:combination granule; logical computing of granule; single granular; rough set; approximation
  0 引言
  粒度計算是由Zadeh[1]於1996年提出,他認為,人類認識主要基於三個主要概念,即粒度、組織和因果。其中粒度計算是一把傘,涵蓋了有關粒度計算的理論、方法論、技術和工具的研究,在粗糙集理論、概念格、知識工程、數據挖掘、人工智能、機器學習等領域有潛在的應用,已成為信息科學的研究熱點之一[2]職稱論文。
  粗糙集[3]定義為給定關系上集合的上近似與下近似構成的有序對,已被成功地應用於機器學習、決策分析、過程控制、模式識別和數據挖掘等領域[4]。傳統的粗糙集理論是基於單一粒定義的,即靜態粒。文獻[5~7]提出了多粒運算下的粗糙集理論模型,即MGRS(multi-granulations rough set,MGRS),並討論了相關的數學性質。考慮到文獻[5~7]中主要討論了集合在粒度P和Q的P+Q、P∩Q運算下的上下近似集合,本文對多粒運算下的粗糙集模型進行了進一步的討論,並將其與單一粒度下的粗糙集模型進行了比較;同時,將多粒運算下的粗糙集模型與組合粒度下的粗糙集模型進行了?比較。
  1 相關概念
  本章給出的相關概念對於後續部分給出的討論是必要的。
  定義1 命題邏輯中,命題P和Q的合取記為P∧Q。P∧Q為真當且僅當P和Q同時為真;命題P和Q的析取記為P∨Q,P∨Q為假當且僅當P和Q同時為假。
  定義2 信息系統是一個四元組(U,A,V,f)。其中,U是對象的集合,稱為域(universe);A是用來描述對象的屬性的集合;V是屬性集A的值域; f:U×A→V反映的是某個對象在某個屬性上的取值,信息系統通常略寫為(U,A)。
  定義3 給定一個非空的域U,U×U的子集EU×U表示域U上的一個關系。有序對(U,E)稱為一個近似空間[8](approximation space)。
  如果關系E滿足自反性、對稱性和傳遞性,則E稱為一個等價關系[9]。等價關系E對域U可以形成一個劃分,記為U/E。可以證明,等價關系和劃分是等價的,即給定一個等價關系,可以構造域的劃分;同樣,給定域的一個劃分,可以構造域上的一個等價關系。
  信息系統(U,A)中,如果兩個體x,y∈U在屬性a∈A上取值相同,則稱兩者在屬性a上是不可分辨的。如果x,y在集合BA中的每一個屬性b∈B都是不可分辨的,則稱兩者在集合B上是不可分辨的。與x在集合B上不可分辨的所有個體的集合稱為x在集合B上生成的等價類,記為[x]?B,它可以看成是由與x不可分辨的元素構成的信息粒[8](information granule)。
  定理1 域U上所有元素在集合A上生成的等價類滿足以下三個條件[9]:
  
  a)?x∈U,有[x]?A≠?;
  b)?x,y∈U,或者[x]?A=[y]?A成立,或者[x]?A∩[y]?A=?成立;
  c)∪x∈U[x]?A=U。
  該定理表明,在集合A上生成的所有等價類構成了域的一個劃分,這些等價類稱為基本等價類。
  定義4 對域U的任一子集XU而言,如果它可以表示成某些等價類的並集,稱x是精確的(或者稱為可定義的),否則稱為粗糙的。如果一個概念XU是粗糙的,則可以用兩個精確定義的集合來近似,分別稱為X的下近似或上近似,記為PX和X,定義如下:
  PX=∪[x]?PX[x]?P
  X=∪[x]?P∩X≠?[x]?P
  
  其中:[x]?P={y|f(x,P)=f(x,P)}是由x在屬性集P上生成的等價類。顯然有下式成立:
  PXXX
  定義5 如果集合X是粗糙的,有序對〈PX,X〉稱為它的粗糙集。該粗糙集的近似質量α?P(X)定義如下:
  α?P(X)=|PX|/|X|
  2 幾種基於粒運算的粗糙集模型
  定義6 給定信息系統(U,A),P,QA。假設由P,Q對域可以構造相應的劃分為
  
  U/IND(P)={[x?1]?P,[x?2]?P,…,[x|U|]?P}
  U/IND(Q)={[x?1]?Q,[x?2]?Q,…,[x|U|]?Q}
  則由P和Q構成的兩個組合粒定義為
  U/IND(P∩Q)={[x?1]?P∩[x?1]?Q,…,[x|U|]?P∩
  [x|U|]?Q}(1)
  
  U/IND(P∪Q)={[x?1]?P∪[x?1]?Q,…,[x|U|]?P∪
  [x|U|]?Q}(2)
  
  例如信息系統(U,A)中,XU且P,QA。其中U={e?1,e?2,e?3,e?4,e?5,e?6,e?7,e?8},X={e?1,e?2,e?5,e?7,e?8}。由P,Q對域形成的劃分分別為
  
  U/IND(P)={{e?1,e?7},{e?2,e?3,e?4,e?5,e?6},{e?8}}

  U/IND(Q)={{e?1,e?2},{e?3,e?4,e?5},{e?6,e?7,e?8}}
  因此有
  U/IND(P∩Q)={{e?1},{e?2},{e?3,e?4,e?5},{e?6},{e?7},{e?8}}
  U/IND(P∪Q)={e?1,e?2,e?7},{e?1,e?2,e?3,e?4,e?5,e?6},{e?2,e?3,e?4,e?5,e?6},?{e?2,e?3,e?4,e?5,e?6,e?7,e?8},{e?1,e?6,e?7,e?8},{e?8}
  
  定理2 U/IND(P∩Q)形成域的劃分,而U/IND(P∪Q)形成域的覆蓋。
  
  證明 由於等價關系滿足自反性,對由P,Q構造的等價類[x?i]?P和[x?i]?Q,有x?i∈[x?i]?P且x?i∈[x?i]?Q。因此有?∪x?i([x?i]?P∩[x?i]?Q)=∪x?i[x?i]?P∪[x?i]?Q)=U成立,同時有?[x?i]?P∩[x?i]?Q≠?,[x?i]?P∪[x?i]?Q≠?,即U/IND(P∩Q)和U/IND(P∪Q)形成了域的覆蓋。
  進一步考慮,如果x?j∈[x?i]?P∩[x?i]?Q,如果x?j≠x?i,則有x?j∈[x?i]?P,x?j∈[x?i]?Q。由於[x?i]?P和[x?i]?Q均是等價類,根據定理1可得x?i∈[x?j]?P,x?i∈[x?j]?Q成立,即x?i∈[x?i]?P∩[x?i]?Q成立。
  如果x?j?[x?i]?P∩[x?i]?Q,則可能有以下三種情況:a)x?j?[x?i]?P,x?j?[x?i]?Q;b)x?j?[x?i]?P,x?j∈[x?i]?Q;c)x?j∈[x?i]?P,x?j?[x?i]?Q。相應地,根據等價類的性質可得:a)x?i?[x?j]?P,x?i?[x?j]?Q;b)x?i?[x?j]?P,x?i∈[x?j]?Q;c)x?i∈[x?j]?P,x?j?[x?i]?Q,因此有x?i?[x?j]?P∩[x?j]?Q。
  通過上述兩種情況可得,或者[x?i]?P∩[x?i]?Q=[x?j]?P∩[x?j]?Q成立,或者([x?i]?P∩[x?i]?Q)∩([x?j]?P∩[x?j]?Q)=?成立,因此U/IND(P∩Q)構成了域的一個劃分。
  證畢。
  定義7 給定信息系統(U,A),P,QA,XU,定義組合粒下的粗糙集如下:
  P∩QX=∪([x]??P∩[x]??Q)X
  ([x]?P∩[x]?Q)
  P∩QX=∪([x]??P∩[x]??Q)∩X≠?
  ([x]?P∩[x]?Q)
  P∪QX=∪([x]??P∩[x]??Q)X
  ([x]?P∪[x]?Q)
  P∪QX=∪([x]??P∩[x]??Q)∩X≠?
  ([x]?P∪[x]?Q)
  
  文獻[10]中曾經定義了粒邏輯運算下的粗糙集模型,如定義8。
  
  定義8 給定信息系統(U,A),P和Q是信息系統的兩個信息粒,則粒邏輯運算下的粗糙集模型定義為
  P∧QX=∪{x|([x]?PX)∧([x]?QX)}
  P∧QX=∪{x|([x]?P∩X≠?)∧([x]?Q∩X≠?)}
  P∨QX=∪{x|([x]?PX)∨([x]?QX)}
  P∨QX=∪{x|([x]?P∩X≠?)∨([x]?Q∩X≠?)}
  
  下面將討論組合粒下的粗糙集與單粒下的粗糙集模型之間的關系以及組合粒下的粗糙集與粒邏輯運算下的粗糙集之間的關系。
  3 單一粒與多粒運算下粗糙集的關系
  筆者已經證明了下面的定理。
  定理3 給定信息系統(U,A),P,QA,XU,則有
  P∧QX=PX∩QX
  P∧QX=X∩X
  P∨QX=PX∪QX
  P∨QX=X∪X
  
  運用本文提出的組合粒,並將其與粒邏輯運算下的粗糙集模型進行進一步比對,可以得到下面的定理。
  定理4 給定信息系統(U,A),P,QA,XU則有
  PX∩QX?P∩QX
  P∩QXX∩X
  證明
  
  a)?x∈PX∩QX,根據定義有[x]?PX且[x]?PX成立,因此有[x]?P∩[x]?QX,即x∈?P∩QX成立。因此有PX∩?QX?P∩QX。
  
  b)?x∈?P∩QX,有([x]?P∩[x]?Q)∩X≠?。由於[x]?P∩[x]?Q[x]?P,[x]?P∩[x]?Q[x]?Q,有[x]?P∩X≠?並且[x]?Q∩X≠?,因此有x∈X∩X,即P∩QXX∩X。
  證畢。

免費論文下載中心 http://www.hi138.com   該定理說明兩個粒度P,Q組合產生的商空間U/IND(P∩Q)比組合粒度P∧Q構造的知識更細,因而對集合X的逼近更為準確。
  定理5 給定信息系統(U,A),P,QA,XU,則有
  P∪QX=PX∩QX
  P∪QX=X∪X
  證明
  
  a)?x∈?P∪QX,有[x]?P∪[x]?QX成立。由於[x]?P[x]??P∪[x]?Q,[x?Q][x]?P∪[x]?Q,有[x]?PX和[x]?QX成立,即
  x∈PX且x∈QX。因此有x∈PX∩QX,即
  P∪QXPX∩QX成立。
  ?x∈PX∩QX,根據定義有x∈PX且x∈QX,因此有[x]?PX和[x]?QX成立。由於[x]?PX和[x]?QX成立,有[x]?P∪[x]?QX成立。因此有x∈?P∪QX,即PX∩QX?P∪QX。
  綜合上述兩點可得 ?P∪QX=PX∩QX。
  
  b)?x∈?P∪QX,有([x]?P∪[x]?Q)∩X≠?,因此有[x]?P∩X≠?或
  
  [x]?Q∩X≠?,即x∈X或x∈X
  成立,x∈X∪X。因而可得?P∪QXX∪X成立。
  
  ?x∈X∪X,有x∈X或x∈X成立,即[x]?P∩X≠?或[x]?Q∩X≠?。由於[x]?P[x]?P∪[x]?Q,[x]?Q[x]?P∪[x]?Q,可得([x]?P∪[x]?Q)∩X≠?成立。因此有x∈?P∪QX,即X∪X?P∪QX。
  根據上述兩點可得P∪QX=X∪X。
  證畢。
  該定理表明組合粒P∪Q下的粗糙集模型可以由單一粒下的粗糙集模型構造出。
  4 不同粒運算下的粗糙集模型的關系
  既然可以在組合粒、粒邏輯運算等不同的粒運算下都可形式化相應的粗糙集,那麽產生一個問題:不同粒運算下的粗糙集之間有什麽關系?
  定理6 給定信息系統(U,A),P,QA,XU,則有
  P∪QX?P∩QX
  P∩QX?P∪QX
  αP∪Q≤αP∩Q
 證明
  a)?x∈?P∪QX,有[x]?P∪[x]?QX,因此可得[x]?PX且[x]?QX。由此可以推斷出[x]?P∩[x]?QX,即x∈?P∩QX。因此有P∪QX?P∩QX。
  
  b)?x∈?P∩QX,根據定義有([x]?P∩[x]?Q)∩X≠?;又由於[x]?P∩[x]?Q[x]?P∪[x]?Q,有([x]?P∪[x]?Q)∩X≠?,可得?x∈?P∪QX,因此有?P∩QX?P∪QX。
  
  c)由於
  
  P∪QX?P∩QX,
  
  有|?P∪QX|≤|?P∩QX|;由於
  P∩QX?P∪QX,有|?P∩QX|≤|?P∪QX|。因此,?αP∪Q≤αP∩Q。
  證畢。
  定理7 給定信息系統(U,A),P,QA,XU,則有
  P∧QX?P∩QX
  P∩QX?P∧QX
  αP∧Q≤αP∩Q
  證明
  a)?x∈?P∧QX,有[x]?PX且[x]?QX成立,因此可得([x]?P∩[x]?Q)X成立。因此有P∨QX?P∩QX。
  b)P∩QX=∪{x|([x]?P∩[x]?Q)∩X≠?},?P∧QX=?∪{x|([x]?P∩X≠?)∧([x]?Q∩X≠?)}。
  ?x∈?P∩QX,有([x]?P∩[x]?Q)∩X≠?。由於[x]?P∩[x]?Q[x]?P
  且[x]?P∩[x]?Q[x]?Q,可得[x]?P∩X≠?且?
  [x]?Q∩X≠?,有x∈?P∧QX。因此有P∩QX?P∧QX。
  c)由於P∨QX?P∩QX,有|?P∨QX|≤|?P∩QX|;同時,由於P∩QX?P∧QX,有
  |?P∩QX|≤|?P∧QX|。因此αP∧Q≤αP∩Q成立。
  證畢。
  
  定理8 給定信息系統(U,A),P,QA,XU,則有
  
  P∨QX?P∩QX
  P∩QX?P∨QX
  αP∨Q≤αP∩Q
  證明
  
  a)?x∈?P∨QX,有[x]?PX或[x]?QX成立。由於?[x]?P∩[x]?Q[x]?P且[x]?P∩[x]?Q[x]?Q,有[x]?P∩[x]?QX成立,則有x∈?P∩QX成立。因此有P∨QX?P∩QX。
  
  b)?x∈?P∩QX,有([x]?P∩[x]?Q)∩X≠?。由於[x]?P∩[x]?Q[x]?P且[x]?P∩[x]?Q[x]?Q。有[x]?P∩X≠?和[x]?Q∩X≠?成立,則有x∈?P∨QX。因此有P∩QX?P∨QX。
  
  c)由於P∨QX?P∩QX,有|?P∨QX|≤|?P∩QX|;由於P∩QX?P∨QX,有|?P∩QX|≤|?P∨QX|。因此αP∨Q≤αP∩Q。
  證畢。
  定理9 給定信息系統(U,A),P,QA,XU,則有
  P∧QX=?P∪QX
  P∧QX?P∪QX
  
  αP∪Q≤αP∧Q
  證明
  
  a)?x∈?P∪QX,根據定義可得([x]?P∪[x]?Q)X成立,
  
  根據集合之間的關系可得
  [x]?PX和[x]?QX成立。因此有x∈P∧QX成立,即
  P∪QX?P∧QX。
  
  ?x∈?P∧QX,有([x]?PX和[x]?QX成立,因此有([x]?P∪[x]?Q)X,即x∈?P∪QX,因此P∧QX?P∪QX。
  綜合這兩種情況有P∧QX=?P∪QX。
  
  b)?x∈?P∧QX,有[x]?P∩X≠?且
  [x]?Q∩X≠?成立。由於[x]?P[x]?P∪[x]?Q,必然有
  ([x]?P∪[x]?P)∩X≠?,即x∈?P∪QX 。因此有P∧QX?P∪QX成立。
  
  c)由於P∧QX=?P∪QX,有|?P∧QX|=|?P∪QX|;由於P∧QX?P∪QX,有|?P∧QX|≤|?P∪QX|。因此可得αP∪Q≤αP∧Q。
  
  證畢。
  定理10 給定信息系統(U,A),P,QA,XU,則有
  
  P∪QX?P∨QX
  P∨QX?P∪QX
  αP∨Q≤αP∪Q
  證明
  
  a)?x∈?P∪QX,有[x]?P∪[x]?QX成立;
  由於[x]?P[x]?P∪[x]?Q,可得[x]?PX,即x∈?P∨QX。
  因此有P∪QX?P∨QX。
  
  b)?x∈?P∨QX,有[x]?P∩X≠?或
  [x]?Q∩X≠?成立。由於[x]?P[x]?P∪[x]?Q,
  
  [x]?Q[x]?P∪[x]?Q,上述兩種情況中的任何一種均可推導出
  ([x]?P∪[x]?Q)∩X≠?。因此有P∨QX?P∪QX。
  
  c)由於P∪QX?P∨QX,有|?P∪QX|≤|?P∨QX|;由於P∨QX?P∪QX,有
  |?P∨QX||?P∪QX|。因此可得αP∨Q≤αP∪Q。
  證畢。
  通過上述各定理可以得到組合粒下的粗糙集模型與粒邏輯運算下的粗糙集模型之間的關系,並且發現在相關粒下的知識粗糙度具有如下關系:
  αP∨Q≤αP∪Q≤αP∧Q≤αP∩Q
  
  基於此,從另一個角度給出知識粗細的形式化定義。
  定義9 給定信息系統(U,A),P,Q是兩個信息粒構造的商空間,稱P?Q,如果對任意集合XU,均有α?Q≤α?P成立。
  實際上,如果P?Q,則由粒集合P提供的知識比由Q提供的知識更細。基於上述相關定理,可以得到下面的結論。
  定理11 〈{P∨Q,P∪Q,P∧Q,P∩Q},?〉是一個鏈。
  證明略。
  5 結束語
  本文討論了單粒運算與多粒運算下粗糙集之間的關系以及不同的多粒運算下粗糙集之間的關系這兩個問題,對於進一步研究動態粒的結構以及基於動態粒的知識獲取奠定了良好的基礎。
  

參考文獻


  [1]ZADEH L A.Fuzzy logic=computing with words[J].IEEE Trans on Fuzzy System, 1996,4(1):103-111.
  [2]梁吉業,錢宇華.信息系統中的信息粒與熵理論[J].中國科學E輯,2008,38(12):2048-2065.
  [3]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
  [4]張文修,吳偉誌,梁吉業,等.粗糙集理論與方法[M].北京:科學出版社,2001.
  [5]QIAN Yu-hua,LIANG Ji-ye.Rough set method based on multi-granulations[C]//Proc of the 5th IEEE Conference on Cognitive Informa-?tics.New York:IEEE Press,2006:297-304.
  [6]QIAN Yu-hua,LIANG Ji-ye,DANG Chang-yin.MGRS in incomplete information systems[C]//Proc of IEEE International Conference on Granular Computing.New York:IEEE Press,2007:163-168.
  [7]QIAN Yu-hua,LIANG Ji-ye,YAO Yi-yu,et al.MGRS:a multi-granulation rough set[J].Information Sciences,2009,180(6):949-970.
  [8]YAO Yi-yu.Stratified rough sets and granular computing[C]//Proc of the 18th International Conference of the North American Fuzzy Information Processing Society.New York:IEEE Press,1999:800-804.
  [9]傅彥,顧小豐,劉啟和,等.離散數學[M].北京:高等教育出版社,2008. 免費論文下載中心 http://www.hi138.com
下载论文

論文《粒計算下的粗糙集模型對比》其它版本

計算機理論論文服務

網站聲明 | 聯系我們 | 網站地圖 | 論文下載地址 | 代寫論文 | 作者搜索 | 英文版 | 手機版 CopyRight@2008 - 2017 免費論文下載中心 京ICP备17062730号