宋晶晶, 楊習(xí)貝,2,3, 祁云嵩, 宋曉寧

(1. 江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 江蘇 鎮(zhèn)江 212003) (2.南京理工大學(xué) 高維信息智能感知與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室, 江蘇 南京 210094) (3.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所智能信息處理重點(diǎn)實(shí)驗(yàn)室, 北京 100190)

粒計(jì)算最早是由美國(guó)控制論專家Zadeh提出的[1].粒計(jì)算是當(dāng)前計(jì)算智能研究領(lǐng)域中模擬人類思維和解決復(fù)雜問(wèn)題的新方法,它亦是復(fù)雜問(wèn)題求解、海量數(shù)據(jù)挖掘、模糊信息處理的有效工具.文獻(xiàn)[2]中首次提出了粒度的概念,立即引起了眾多學(xué)者的廣泛關(guān)注.

近年來(lái),國(guó)內(nèi)外關(guān)于粒計(jì)算的研究取得了重要進(jìn)展.如文獻(xiàn)[3]中為了體現(xiàn)粒計(jì)算思想的深度、廣度及普適性,給出了粒計(jì)算三元論的概念,其主要成分是多視角、多層次粒結(jié)構(gòu)和粒計(jì)算三角形;文獻(xiàn)[4]中在集合論的框架下對(duì)粒計(jì)算進(jìn)行了形式化的研究;文獻(xiàn)[5]中研究了如何對(duì)復(fù)雜數(shù)據(jù)進(jìn)行有效信息?；约袄眯畔⒘；慕Y(jié)果進(jìn)行高效問(wèn)題求解;文獻(xiàn)[6]中綜述了粒計(jì)算的基本數(shù)學(xué)模型和方法,并討論了它們之間的相互關(guān)系;文獻(xiàn)[7]中探討了基于粒計(jì)算的學(xué)習(xí)方法和應(yīng)用前景.

就目前的研究成果來(lái)看,眾多學(xué)者普遍認(rèn)同這樣一個(gè)觀點(diǎn):粒計(jì)算中的粒結(jié)構(gòu)概念給出了一個(gè)系統(tǒng)或者問(wèn)題的結(jié)構(gòu)化描述.然而在實(shí)際工程應(yīng)用中,對(duì)于同一個(gè)系統(tǒng)或者同一個(gè)問(wèn)題,許多解釋和描述可能是同時(shí)存在的[8],所以粒結(jié)構(gòu)的形成常常需被模型化為多種層次結(jié)構(gòu).由此可以看出,層次性在粒計(jì)算中占據(jù)著重要作用.一般來(lái)說(shuō),粒結(jié)構(gòu)層次化方法可以用于比較不同粒結(jié)構(gòu)之間的粗細(xì)關(guān)系，如文獻(xiàn)[9]中在不同知識(shí)粒度下,從屬性變化的角度,給出了分層遞階的知識(shí)空間鏈.文獻(xiàn)[10]中給出了鄰域系統(tǒng)分層遞階結(jié)構(gòu)的5條公理,提出了一種序關(guān)系來(lái)描述不同鄰域系統(tǒng)之間的粗細(xì)關(guān)系.文獻(xiàn)[11]中研究了兩種多粒度空間下的分層遞階結(jié)構(gòu).文獻(xiàn)[12]中從知識(shí)距離[13]的角度出發(fā),研究了不同粒結(jié)構(gòu)之間的差異.文獻(xiàn)[14]中考慮了當(dāng)信息粒之間不存在集合包含關(guān)系時(shí),利用集合的基數(shù)大小關(guān)系來(lái)描述粒結(jié)構(gòu)的層次性問(wèn)題;文獻(xiàn)[15]利用集合距離和知識(shí)距離構(gòu)建了代數(shù)格結(jié)構(gòu),以此刻畫基于等價(jià)關(guān)系信息粒的層次模型.

值得注意的是,以上眾多學(xué)者對(duì)于粒計(jì)算層次結(jié)構(gòu)的研究都是建立在等價(jià)關(guān)系基礎(chǔ)上的，而在很多實(shí)際工程問(wèn)題中,等價(jià)關(guān)系并不適用，如不同信息粒之間可能存在著重疊部分,此時(shí)所有的信息粒合集就構(gòu)成了論域上的一個(gè)覆蓋[16-17]而非劃分.從這個(gè)角度來(lái)看,以粒計(jì)算的觀點(diǎn)研究覆蓋的層次結(jié)構(gòu)是有實(shí)際意義的.文獻(xiàn)[18]利用覆蓋中信息粒之間的包含關(guān)系,定義了覆蓋?？臻g的層次模型.然而正如文獻(xiàn)[14]中所指出的,在很多的復(fù)雜類型數(shù)據(jù)中,信息粒之間不存在必然的集合包含關(guān)系.為了解決這一問(wèn)題,筆者在文獻(xiàn)[15]的研究基礎(chǔ)上,提出了覆蓋上知識(shí)距離的概念,利用覆蓋上知識(shí)距離格所誘導(dǎo)出的偏序關(guān)系來(lái)刻畫覆蓋的層次結(jié)構(gòu).

1 基本概念

1.1 粒結(jié)構(gòu)

定義1令U≠?為一論域,R為U上的一族等價(jià)關(guān)系的集合,稱KB=為一個(gè)知識(shí)基[19].

給定一個(gè)知識(shí)基KB=,若P?R,則P中所有等價(jià)關(guān)系的交集依然是一個(gè)等價(jià)關(guān)系,Pawlak稱其為不可分辨關(guān)系,記為IND(P)[19].以粒計(jì)算的觀點(diǎn)來(lái)看,劃分U/IND(P)中的每一個(gè)等價(jià)類就是一個(gè)信息粒,所有這些等價(jià)類的合集,也就是劃分U/IND(P),就構(gòu)成了一個(gè)粒結(jié)構(gòu).為后續(xù)討論方便起見,不妨將由等價(jià)關(guān)系IND(P)生成的粒結(jié)構(gòu)記為K(P)={[x]P:x∈U}[13],其中[x]P={y∈U: (x,y)∈IND(P)}表示U中所有與x具有等價(jià)關(guān)系IND(P)的對(duì)象的集合,即包含x的等價(jià)類.在論域U上, 將所有粒結(jié)構(gòu)的合集記為K(U).

粒計(jì)算強(qiáng)調(diào)在不同粒度層次上來(lái)分析和解決問(wèn)題,在粒計(jì)算理論中,有兩種特殊的粒結(jié)構(gòu):一種是最粗的粒結(jié)構(gòu),記為σ={U:x∈U},此時(shí)根據(jù)二元關(guān)系,論域中任意兩個(gè)對(duì)象都不能被區(qū)分開來(lái),表示擁有的知識(shí)量達(dá)到最小;另一種是最細(xì)的粒空間,記為ω={{x}:x∈U}, 此時(shí)根據(jù)二元關(guān)系,論域中任意兩個(gè)對(duì)象都可以被區(qū)分開來(lái),表示擁有的知識(shí)量達(dá)到最大.

定義2[13]令U為論域,?K(P),K(Q)∈K(U), 可定義如下所示的3種運(yùn)算:

K(P)∩K(Q)={[x]P∩Q: [x]P∩Q=

[x]P∩[x]Q}

(1)

K(P)∪K(Q)={[x]P∪Q: [x]P∪Q=

[x]P∪[x]Q}

(2)

～K(P)={～[x]P: ～[x]P=

{x}∪(U-[x]P) }

(3)

定理1[13]令KB=為一知識(shí)基, (K(U),∩,∪)是一個(gè)格.

定理2[13]令KB=為一知識(shí)基,(K(U),∩,∪)是一個(gè)分配格.

定理3[13]令KB=為一知識(shí)基,(K(U),∩,∪,～)是一個(gè)有補(bǔ)格.

1.2 粒結(jié)構(gòu)上的知識(shí)距離

定義3[12-13]令KB=為一知識(shí)基,?K(P),K(Q)∈K(U),粒結(jié)構(gòu)K(P)與K(Q)之間的距離稱為知識(shí)距離,記為D(K(P),K(Q))且

D(K(P),K(Q))=

(4)

在定義3中, [x]P?[x]Q表示集合[x]P和[x]Q的對(duì)稱差,即[x]P?[x]Q=([x]P-[x]Q)∪([x]Q-[x]P).D(K(P),K(Q))是用來(lái)度量?jī)蓚€(gè)不同單粒度空間所擁有知識(shí)含量差距的.顯然, 0≤D(K(P),K(Q))≤1-1/|U|成立.當(dāng)K(P)=K(Q), 即兩個(gè)單粒度空間完全相同時(shí),知識(shí)距離D(K(P),K(Q))達(dá)到最小值0; 當(dāng)K(P)=～K(Q)時(shí),知識(shí)距離D(K(P),K(Q))達(dá)到最大值1-1/|U|.

定理4[13]令KB=為一知識(shí)基,?K(P),K(Q),K(R)∈K(U), 知識(shí)距離具有如下性質(zhì):

1) 非負(fù)性:D(K(P),K(Q))≥0,D(K(P),K(Q))=0當(dāng)且僅當(dāng)K(P)=K(Q);

2) 對(duì)稱性:D(K(P),K(Q))=D(K(Q),K(P));

3) 三角不等式:

①D(K(P),K(Q))+D(K(P),K(R))≥D(K(Q),K(R))；

②D(K(R),K(Q))+D(K(P),K(R))≥D(K(Q),K(P))；

③D(K(R),K(Q))+D(K(P),K(Q))≥D(K(R),K(P)).

由定理4可知(K(U),D)是一個(gè)距離空間.

2 覆蓋層次結(jié)構(gòu)的距離刻畫方法

2.1 覆蓋與覆蓋距離

在此,稱二元組(U,C)為一個(gè)覆蓋近似空間.類似于粒結(jié)構(gòu)的合集K(U), 由U上所有的覆蓋構(gòu)成的合集記為C(U).

從粒計(jì)算的角度看,覆蓋的每個(gè)元素就是一個(gè)信息粒.在傳統(tǒng)的粒結(jié)構(gòu)討論方法中,論域中的每一個(gè)對(duì)象僅僅屬于一個(gè)信息粒的范疇,因而在考慮兩個(gè)粒結(jié)構(gòu)之間的知識(shí)距離時(shí),只需求得對(duì)象在兩個(gè)粒結(jié)構(gòu)中信息粒的對(duì)稱差即可.然而在覆蓋中,?x∈U,包含x的信息?？赡懿恢挂粋€(gè),簡(jiǎn)便起見,記覆蓋C中包含x的信息粒的合集為C(x)={ci∈C:x∈ci}.此時(shí)要討論兩個(gè)不同覆蓋之間的距離,首先需給出一個(gè)對(duì)象在兩個(gè)不同覆蓋之間的距離.

定義5令U≠?為一論域, ?x∈U,?C1,C2∈C(U),x在覆蓋C1與C2之間的距離有如下兩種定義:

(5)

(6)

3)三角不等式:

1)根據(jù)定義5, 非負(fù)性和對(duì)稱性顯然成立.

2)若覆蓋C1,C2和C3中有兩個(gè)覆蓋相同,此時(shí)不妨假設(shè)C1=C2,根據(jù)定義5,3個(gè)三角不等式顯然成立.

若C1,C2和C3兩兩都不相同,根據(jù)定義5,

由集合論的基本知識(shí)可知，對(duì)于任意有限集合X,Y和Z, 有(Y?Z)?(X?Y)∪(X?Z), 于是

類似地,不難證得其他三角不等式.

定義6令U≠?為一論域, ?x∈U,?C1,C2∈C(U),覆蓋C1和C2之間的距離有如下兩種定義:

(7)

(8)

不難看出,D∪(C1,C2)是論域中所有對(duì)象在兩個(gè)覆蓋上并距離的平均值，而D∩(C1,C2)則是論域中所有對(duì)象在兩個(gè)覆蓋上交距離的平均值.

在定理5的基礎(chǔ)上,同樣可以得到如下所示的定理6.

定理6令U≠?為一論域,?C1,C2,C3∈C(U),覆蓋之間的距離具有如下性質(zhì):

1)非負(fù)性:D∪(C1,C2)≥0,D∩(C1,C2)≥0;

2)對(duì)稱性:D∪(C1,C2)=D∪(C2,C1),

D∩(C1,C2)=D∩(C2,C1);

3)三角不等式:

①D∪(C1,C2)+D∪(C1,C3)≥D∪(C2,C3),D∩(C1,C2)+D∩(C1,C3)≥D∩(C2,C3);

②D∪(C1,C2)+D∪(C2,C3)≥D∪(C1,C3),D∩(C1,C2)+D∩(C2,C3)≥D∩(C1,C3);

③D∪(C1,C3)+D∪(C2,C3)≥D∪(C1,C2),D∩(C1,C3)+D∩(C2,C3)≥D∩(C2,C3).

證明: 由定理5的證明結(jié)果,定理6易證.

2.2 覆蓋上距離的代數(shù)結(jié)構(gòu)

距離從幾何角度刻畫了不同粒結(jié)構(gòu)或覆蓋之間的幾何結(jié)構(gòu),因而很自然地,可將兩個(gè)粒空間或覆蓋之間的關(guān)系通過(guò)距離反映出來(lái).為此需選擇一個(gè)參照空間,文中采用的是最細(xì)的?？臻g,即ω.首先在覆蓋上研究距離的代數(shù)結(jié)構(gòu),進(jìn)而通過(guò)這個(gè)代數(shù)結(jié)構(gòu)誘導(dǎo)出一個(gè)偏序關(guān)系,以此來(lái)反映覆蓋之間的內(nèi)在關(guān)系.

定義7令U≠?為一論域,?x∈U,?C1,C2∈C(U),根據(jù)對(duì)象x在兩個(gè)覆蓋上的并距離,可定義如下兩種運(yùn)算形式:

(9)

(10)

根據(jù)對(duì)象x在兩個(gè)覆蓋上的交距離,可定義如下兩種運(yùn)算形式:

(11)

(12)

定理7令U≠?為一論域,?x∈U,

證明:根據(jù)定義7所示的最大最小運(yùn)算,定理7易證.

2.3 覆蓋上的層次結(jié)構(gòu)

在一個(gè)格中, 可以根據(jù)“∧”與“∨”運(yùn)算誘導(dǎo)出一種偏序關(guān)系.由定理7所示的格所誘導(dǎo)的偏序關(guān)系具體形式如定義8所示.

定義8令U≠?為一論域,?x∈U,?C1,C2∈C(U),

定義8所示的兩種偏序關(guān)系可用于刻畫覆蓋上的層次結(jié)構(gòu),即?C1,C2∈C(U).

定理8令U≠?為一論域,?x∈U,?C1,C2∈C(U),

|∪C2(x) |;

|∩C2(x) |.

證明: 僅證第1個(gè)結(jié)論,第2個(gè)結(jié)論的證明類似可得.

?x∈U,|∪C1(x) |≤|∪C2(x) |.

例1:設(shè)論域U={x1,x2,x3,x4,x5,x6},C1,C2為論域U上的兩個(gè)覆蓋,其中

C1={{x1,x2,x4},{x2,x3,x5},{x4,x6},{x1,x2,x5}},

C2={{x1,x2,x3,x5},{x2,x5,x6},{x2,x3,x4,x5,x6}}.

根據(jù)定義5中式(5)得

根據(jù)定義5中式(6)得

3 結(jié)論

粒計(jì)算中的粒結(jié)構(gòu)是對(duì)一個(gè)問(wèn)題的結(jié)構(gòu)化描述,它的形成常常需被模型化為多種層次結(jié)構(gòu).根據(jù)實(shí)際問(wèn)題求解的需要,選擇相應(yīng)層次的粒結(jié)構(gòu)來(lái)解決問(wèn)題.所以關(guān)于層次模型的研究對(duì)于粒計(jì)算理論的發(fā)展具有重要的現(xiàn)實(shí)意義.文中利用新給出的知識(shí)距離代數(shù)格所誘導(dǎo)出的偏序關(guān)系來(lái)刻畫不同覆蓋之間的粗細(xì)關(guān)系,通過(guò)實(shí)例分析說(shuō)明這種方法是有效可行的.該方法為以后研究覆蓋之間的層次結(jié)構(gòu)提供了一種新的思路。

在文中工作的基礎(chǔ)上,筆者下一步將對(duì)覆蓋上基于知識(shí)距離的約簡(jiǎn)問(wèn)題進(jìn)行進(jìn)一步的探討.

參考文獻(xiàn)(References)

[ 1 ] Zadeh L A. Fuzzy sets and information granulation[M].Amsterdam: North-Holland Publishing Company,1979: 111-127.

[ 2 ] Hobbs J R. Granularity[C]∥ProceedingsoftheNinthInternationalJointConferenceonArtificialIntelligence.California,Los Angeles：[s.n.],1985: 432-435.

[ 3 ] Yao Y Y. Granular computing: past,present and future[C]∥IEEEInternationalConferenceonGranularComputing.[S.l.]:Springer,2008: 80-85.

[ 4 ] 苗奪謙,徐菲菲,姚一豫,等. 粒計(jì)算的集合論描述[J]. 計(jì)算機(jī)學(xué)報(bào),2012,35(2): 351-363.

Miao Duoqian,Xu Feifei,Yao Yiyu,et al. Set-theoretic formulation of granular computing[J].ChineseJournalofComputers,2012,35(2): 351-363. (in Chinese)

[ 5 ] 錢宇華. 復(fù)雜數(shù)據(jù)的?；瘷C(jī)理與數(shù)據(jù)建模[D]. 太原:山西大學(xué),2011:17-56.

[ 6 ] 王國(guó)胤,張清華,胡軍. 粒計(jì)算研究綜述[J]. 智能系統(tǒng)學(xué)報(bào),2007,2(6): 8-26.

Wang Guoyin,Zhang Qinghua,Hu Jun. An overview of granular computing[J].CAAITransactionsonIntelligentSystems,2007,2(6): 8-26. (in Chinese)

[ 7 ] Yager R R. Some learning paradigms for granular computing[C]∥IEEEInternationalConferenceonGranularComputing,[S.l.].IEEE,2006: 25-29.

[ 8 ] 王國(guó)胤,李德毅,姚一豫,等. 云模型與粒計(jì)算[M]. 北京: 科學(xué)出版社,2012: 139-140.

[ 9 ] 王國(guó)胤,張清華. 不同知識(shí)粒度下粗糙集的不確定性研究[J]. 計(jì)算機(jī)學(xué)報(bào),2008,31(9): 1588-1598.

Wang Guoyin,Zhang Qinghua. Uncertainty of rough sets in different knowledge granularities[J].ChineseJournalofComputers,2008,31(9): 1588-1598. (in Chinese)

[10] 周君儀,楊習(xí)貝,楊靜宇. 鄰域系統(tǒng)分層遞階結(jié)構(gòu)分析[J]. 計(jì)算機(jī)科學(xué)與探索,2012,6(3): 275-280.

Zhou Junyi,Yang Xibei,Yang Jingyu. Analysis of hierarchical structure of neighborhood systems[J].JournalofFrontiersofComputerScienceandTechnology,2012,6(3): 275-280. (in Chinese)

[11] Yang Xibei,Qian Yuhua,Yang Jingyu. Hierarchical structures on multigranulation spaces[J].JournalofComputerScienceandTechnology,2012,27(6): 1169-1183.

[12] Liang Jiye,Li Ru,Qian Yuhua. Distance: a more comprehensible perspective for measures in rough set theory[J].Knowledge-BasedSystems,2012,27: 126-136.

[13] Qian Yuhua,Liang Jiye,Dang Chuangyin. Knowledge structure,knowledge granulation and knowledge distance in a knowledge base[J].InternationalJournalofApproximateReasoning,2009,50(1): 174-188.

[14] Qian Yuhua,Dang Chuangyin,Liang Jiye. Partial ordering of information granulations: a further investigation[J].ExpertSystems,2012,29(1): 3-24.

[15] Yang Xibei,Qian Yuhua,Yang Jingyu. On characterizing hierarchies of granulation structures via distances[J].FundamentaInformaticae,2013,123(3): 365-380.

[16] Zhu William,Wang Feiyue. The fourth type of covering-based rough sets[J].InformationSciences,2012,201:80-92.

[17] Wang Lijuan,Yang Xibei,Yang Jingyu,et al. Relationships among generalized rough sets in six coverings and pure reflexive neighborhood system[J].InformationSciences,2012,207: 66-78.

[18] 胡軍,王國(guó)胤. 覆蓋粒度空間的層次模型[J]. 南京大學(xué)學(xué)報(bào):自然科學(xué)版,2008,44(5): 551-558.

Hu Jun,Wang Guoyin. Hierarchical model of covering granular space[J].JournalofNanjingUniversity:NaturalSciencesEdition,2008,44(5): 551-558. (in Chinese)

[19] Pawlak Z. Rough sets: theoretical aspects of reasoning about data[M].Netherland:Kluwer Academic Publishers,1991:9.