覆蓋層次結構的知識距離刻畫方法

宋晶晶, 楊習貝,2,3, 祁云嵩, 宋曉寧

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

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

近年來,國內外關于粒計算的研究取得了重要進展.如文獻[3]中為了體現粒計算思想的深度、廣度及普適性,給出了粒計算三元論的概念,其主要成分是多視角、多層次粒結構和粒計算三角形;文獻[4]中在集合論的框架下對粒計算進行了形式化的研究;文獻[5]中研究了如何對復雜數據進行有效信息粒化以及利用信息?；慕Y果進行高效問題求解;文獻[6]中綜述了粒計算的基本數學模型和方法,并討論了它們之間的相互關系;文獻[7]中探討了基于粒計算的學習方法和應用前景.

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

值得注意的是,以上眾多學者對于粒計算層次結構的研究都是建立在等價關系基礎上的，而在很多實際工程問題中,等價關系并不適用，如不同信息粒之間可能存在著重疊部分,此時所有的信息粒合集就構成了論域上的一個覆蓋[16-17]而非劃分.從這個角度來看,以粒計算的觀點研究覆蓋的層次結構是有實際意義的.文獻[18]利用覆蓋中信息粒之間的包含關系,定義了覆蓋粒空間的層次模型.然而正如文獻[14]中所指出的,在很多的復雜類型數據中,信息粒之間不存在必然的集合包含關系.為了解決這一問題,筆者在文獻[15]的研究基礎上,提出了覆蓋上知識距離的概念,利用覆蓋上知識距離格所誘導出的偏序關系來刻畫覆蓋的層次結構.

1 基本概念

1.1 粒結構

定義1令U≠?為一論域,R為U上的一族等價關系的集合,稱KB=為一個知識基[19].

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

粒計算強調在不同粒度層次上來分析和解決問題,在粒計算理論中,有兩種特殊的粒結構:一種是最粗的粒結構,記為σ={U:x∈U},此時根據二元關系,論域中任意兩個對象都不能被區(qū)分開來,表示擁有的知識量達到最小;另一種是最細的?？臻g,記為ω={{x}:x∈U}, 此時根據二元關系,論域中任意兩個對象都可以被區(qū)分開來,表示擁有的知識量達到最大.

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

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=為一知識基, (K(U),∩,∪)是一個格.

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

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

1.2 粒結構上的知識距離

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

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

(4)

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

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

1) 非負性:D(K(P),K(Q))≥0,D(K(P),K(Q))=0當且僅當K(P)=K(Q);

2) 對稱性: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)是一個距離空間.

2 覆蓋層次結構的距離刻畫方法

2.1 覆蓋與覆蓋距離

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

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

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

(5)

(6)

3)三角不等式:

1)根據定義5, 非負性和對稱性顯然成立.

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

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

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

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

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

(7)

(8)

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

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

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

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

2)對稱性: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的證明結果,定理6易證.

2.2 覆蓋上距離的代數結構

距離從幾何角度刻畫了不同粒結構或覆蓋之間的幾何結構,因而很自然地,可將兩個?？臻g或覆蓋之間的關系通過距離反映出來.為此需選擇一個參照空間,文中采用的是最細的?？臻g,即ω.首先在覆蓋上研究距離的代數結構,進而通過這個代數結構誘導出一個偏序關系,以此來反映覆蓋之間的內在關系.

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

(9)

(10)

根據對象x在兩個覆蓋上的交距離,可定義如下兩種運算形式:

(11)

(12)

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

證明:根據定義7所示的最大最小運算,定理7易證.

2.3 覆蓋上的層次結構

在一個格中, 可以根據“∧”與“∨”運算誘導出一種偏序關系.由定理7所示的格所誘導的偏序關系具體形式如定義8所示.

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

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

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

|∪C2(x) |;

|∩C2(x) |.

證明: 僅證第1個結論,第2個結論的證明類似可得.

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

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

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}}.

根據定義5中式(5)得

根據定義5中式(6)得

3 結論

粒計算中的粒結構是對一個問題的結構化描述,它的形成常常需被模型化為多種層次結構.根據實際問題求解的需要,選擇相應層次的粒結構來解決問題.所以關于層次模型的研究對于粒計算理論的發(fā)展具有重要的現實意義.文中利用新給出的知識距離代數格所誘導出的偏序關系來刻畫不同覆蓋之間的粗細關系,通過實例分析說明這種方法是有效可行的.該方法為以后研究覆蓋之間的層次結構提供了一種新的思路。

在文中工作的基礎上,筆者下一步將對覆蓋上基于知識距離的約簡問題進行進一步的探討.

參考文獻(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]. 計算機學報,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 ] 錢宇華. 復雜數據的?；瘷C理與數據建模[D]. 太原:山西大學,2011:17-56.

[ 6 ] 王國胤,張清華,胡軍. 粒計算研究綜述[J]. 智能系統(tǒng)學報,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 ] 王國胤,李德毅,姚一豫,等. 云模型與粒計算[M]. 北京: 科學出版社,2012: 139-140.

[ 9 ] 王國胤,張清華. 不同知識粒度下粗糙集的不確定性研究[J]. 計算機學報,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] 周君儀,楊習貝,楊靜宇. 鄰域系統(tǒng)分層遞階結構分析[J]. 計算機科學與探索,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] 胡軍,王國胤. 覆蓋粒度空間的層次模型[J]. 南京大學學報:自然科學版,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.