論文題目：粒計算下的粗糙集模型對比
摘 要:提出了幾種組合粒下的粗糙集模型,并將其與單一粒下的粗糙集進行了對比,同時又與粒邏輯運算下的粗糙集模型進行比對,創(chuàng)造性地得到了組合粒、單一粒以及粒邏輯運算下的粗糙集模型之間的關(guān)系。結(jié)果表明,組合粒與粒邏輯運算構(gòu)成了一個鏈結(jié)構(gòu),這為探討基于信息粒的知識獲取以及動態(tài)粒的推理奠定了基礎(chǔ)。
關(guān)鍵詞:組合粒;粒邏輯運算;單一粒;粗糙集;近似
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年提出,他認為,人類認識主要基于三個主要概念,即粒度、組織和因果。其中粒度計算是一把傘,涵蓋了有關(guān)粒度計算的理論、方法論、技術(shù)和工具的研究,在粗糙集理論、概念格、知識工程、數(shù)據(jù)挖掘、人工智能、機器學(xué)習(xí)等領(lǐng)域有潛在的應(yīng)用,已成為信息科學(xué)的研究熱點之一[2]職稱論文。
粗糙集[3]定義為給定關(guān)系上集合的上近似與下近似構(gòu)成的有序?qū)?已被成功地應(yīng)用于機器學(xué)習(xí)、決策分析、過程控制、模式識別和數(shù)據(jù)挖掘等領(lǐng)域[4]。傳統(tǒng)的粗糙集理論是基于單一粒定義的,即靜態(tài)粒。文獻[5~7] 提出了多粒運算下的粗糙集理論模型,即MGRS(multi-granulations rough set,MGRS),并討論了相關(guān)的數(shù)學(xué)性質(zhì)�？紤]到文獻[5~7]中主要討論了集合在粒度P和Q的P+Q、P∩Q運算下的上下近似集合,本文對多粒運算下的粗糙集模型進行了進一步的討論,并將其與單一粒度下的粗糙集模型進行了比較;同時,將多粒運算下的粗糙集模型與組合粒度下的粗糙集模型進行了?比較。
1 相關(guān)概念
本章給出的相關(guān)概念對于后續(xù)部分給出的討論是必要的。
定義1 命題邏輯中,命題P和Q的合取記為P∧Q。P∧Q為真當且僅當P和Q同時為真;命題P和Q的析取記為P∨Q,P∨Q為假當且僅當P和Q同時為假。
定義2 信息系統(tǒng)是一個四元組(U,A,V,f)。其中,U是對象的集合,稱為域(universe);A是用來描述對象的屬性的集合;V是屬性集A的值域; f:U×A→V反映的是某個對象在某個屬性上的取值,信息系統(tǒng)通常略寫為(U,A)。
定義3 給定一個非空的域U,U×U的子集EU×U表示域U上的一個關(guān)系。有序?qū)?U,E)稱為一個近似空間[8](approximation space)。
如果關(guān)系E滿足自反性、對稱性和傳遞性,則E稱為一個等價關(guān)系[9]。等價關(guān)系E對域U可以形成一個劃分,記為U/E�？梢宰C明,等價關(guān)系和劃分是等價的,即給定一個等價關(guān)系,可以構(gòu)造域的劃分;同樣,給定域的一個劃分,可以構(gòu)造域上的一個等價關(guān)系。
信息系統(tǒng)(U,A)中,如果兩個體x,y∈U在屬性a∈A上取值相同,則稱兩者在屬性a上是不可分辨的。如果x,y在集合BA中的每一個屬性b∈B都是不可分辨的,則稱兩者在集合B上是不可分辨的。與x在集合B上不可分辨的所有個體的集合稱為x在集合B上生成的等價類,記為[x]?B,它可以看成是由與 x不可分辨的元素構(gòu)成的信息粒[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上生成的所有等價類構(gòu)成了域的一個劃分,這些等價類稱為基本等價類。
定義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是粗糙的,有序?qū)Α碢X,X〉稱為它的粗糙集。該粗糙集的近似質(zhì)量α?P(X)定義如下:
α?P(X)=|PX|/|X|
2 幾種基于粒運算的粗糙集模型
定義6 給定信息系統(tǒng)(U,A),P,QA。假設(shè)由P,Q對域可以構(gòu)造相應(yīng)的劃分為
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構(gòu)成的兩個組合粒定義為
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)
例如信息系統(tǒng)(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)形成域的覆蓋。
證明 由于等價關(guān)系滿足自反性,對由P,Q構(gòu)造的等價類[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均是等價類,根據(jù)定理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。相應(yīng)地,根據(jù)等價類的性質(zhì)可得: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)構(gòu)成了域的一個劃分。
證畢。
定義7 給定信息系統(tǒng)(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]中曾經(jīng)定義了粒邏輯運算下的粗糙集模型,如定義8。
定義8 給定信息系統(tǒng)(U,A),P和Q是信息系統(tǒng)的兩個信息粒,則粒邏輯運算下的粗糙集模型定義為
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≠?)}
下面將討論組合粒下的粗糙集與單粒下的粗糙集模型之間的關(guān)系以及組合粒下的粗糙集與粒邏輯運算下的粗糙集之間的關(guān)系。
3 單一粒與多粒運算下粗糙集的關(guān)系
筆者已經(jīng)證明了下面的定理。
定理3 給定信息系統(tǒng)(U,A),P,QA,XU,則有
P∧QX=PX∩QX
P∧QX=X∩X
P∨QX=PX∪QX
P∨QX=X∪X
運用本文提出的組合粒,并將其與粒邏輯運算下的粗糙集模型進行進一步比對,可以得到下面的定理。
定理4 給定信息系統(tǒng)(U,A),P,QA,XU則有
PX∩QX?P∩QX
P∩QXX∩X
證明
a)?x∈PX∩QX,根據(jù)定義有[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組合產(chǎn)生的商空間U/IND(P∩Q)比組合粒度P∧Q構(gòu)造的知識更細,因而對集合X的逼近更為準確。
定理5 給定信息系統(tǒng)(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,根據(jù)定義有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。
根據(jù)上述兩點可得P∪QX=X∪X。
證畢。
該定理表明組合粒P∪Q下的粗糙集模型可以由單一粒下的粗糙集模型構(gòu)造出。
4 不同粒運算下的粗糙集模型的關(guān)系
既然可以在組合粒、粒邏輯運算等不同的粒運算下都可形式化相應(yīng)的粗糙集,那么產(chǎn)生一個問題:不同粒運算下的粗糙集之間有什么關(guān)系?
定理6 給定信息系統(tǒng)(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,根據(jù)定義有([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 給定信息系統(tǒng)(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 給定信息系統(tǒng)(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 給定信息系統(tǒng)(U,A),P,QA,XU,則有
P∧QX=?P∪QX
P∧QX?P∪QX
αP∪Q≤αP∧Q
證明
a)?x∈?P∪QX,根據(jù)定義可得([x]?P∪[x]?Q)X成立,
根據(jù)集合之間的關(guān)系可得
[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 給定信息系統(tǒng)(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,上述兩種情況中的任何一種均可推導(dǎo)出
([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。
證畢。
通過上述各定理可以得到組合粒下的粗糙集模型與粒邏輯運算下的粗糙集模型之間的關(guān)系,并且發(fā)現(xiàn)在相關(guān)粒下的知識粗糙度具有如下關(guān)系:
αP∨Q≤αP∪Q≤αP∧Q≤αP∩Q
基于此,從另一個角度給出知識粗細的形式化定義。
定義9 給定信息系統(tǒng)(U,A),P,Q是兩個信息粒構(gòu)造的商空間,稱P?Q,如果對任意集合XU,均有α?Q≤α?P成立。
實際上,如果P?Q,則由粒集合P提供的知識比由Q提供的知識更細。基于上述相關(guān)定理,可以得到下面的結(jié)論。
定理11 〈{P∨Q,P∪Q,P∧Q,P∩Q},?〉是一個鏈。
證明略。
5 結(jié)束語
本文討論了單粒運算與多粒運算下粗糙集之間的關(guān)系以及不同的多粒運算下粗糙集之間的關(guān)系這兩個問題,對于進一步研究動態(tài)粒的結(jié)構(gòu)以及基于動態(tài)粒的知識獲取奠定了良好的基礎(chǔ)。
參考文獻:
[1]ZADEH L A.Fuzzy logic=computing with words[J].IEEE Trans on Fuzzy System, 1996,4(1):103-111.
[2]梁吉業(yè),錢宇華.信息系統(tǒng)中的信息粒與熵理論[J].中國科學(xué)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]張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京:科學(xué)出版社,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]傅彥,顧小豐,劉啟和,等.離散數(shù)學(xué)[M].北京:高等教育出版社,2008.