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

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

　　關鍵詞:組合粒;粒邏輯運算;單一粒;粗糙集;近似 
　　 
　　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。 

證畢。

該定理說明兩個粒度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 結束語 
　　本文討論了單粒運算與多粒運算下粗糙集之間的關系以及不同的多粒運算下粗糙集之間的關系這兩個問題,對于進一步研究動態粒的結構以及基于動態粒的知識獲取奠定了良好的基礎。