基于圖的粒結構及其轉換

1粒結構的基本組成和運算符粒計算是解決人類問題所提出的一種思維方式和計算策略。粒度計算的形成和發(fā)展，結合了不同的思想、模型、模型、方法論、技術和工具[1.2.4、7、9、11、13、14、15、16、17和18]。粒計算三元論模型將現(xiàn)有粒計算研究成果的共性抽象出來,為問題求解提供了統(tǒng)一的方法論。以粒結構為基礎的三元論模型包括3個部分,即結構化思維、結構化問題求解、結構化信息處理。結構化思維強調了對粒計算的哲學思想的研究。結構化問題求解致力于將粒計算哲學思想具體到問題求解的方法、技術和工具的研究和開發(fā)中。結構化信息處理強調以計算機為主體的信息處理與以人為主體的信息處理的差別。粒結構體現(xiàn)了粒計算所倡導的多粒度、多層次、多視角的結構化方法。一個實際問題或系統(tǒng)總是由眾多關聯(lián)的部分組成。這種結構反映了兩個主要特征:一個整體可以看成是由部分組成的網狀結構,任何一個部分都可能同其他部分相連;一個部分也可能是由更小部分組成的網狀結構。粒結構能將復雜的網絡轉化為一個較為簡單的多層次結構,這就自然引入了粒度與層次的概念。粒結構的基本組成主要包括粒、層次、不同層次組成的分層結構,而粒結構又是從不同視角出發(fā)的多個分層結構的組合。粒計算正是基于這種簡化的粒結構的問題求解。第2節(jié)將詳細介紹粒結構的構成。圖論是描述和分析許多現(xiàn)實世界問題很好的工具?；趫D建立粒結構的模型既是對粒結構很好的表示,又能方便地對粒結構的建立、轉換進行操作。在圖中,用節(jié)點表示粒,節(jié)點與節(jié)點之間的邊來表示粒之間的關系是非常形象和直觀的。由于圖的節(jié)點和邊都是通過集合的方式來定義,因此基于圖的粒結構可以通過集合理論和圖論兩種方式對粒結構中的節(jié)點和層次進行計算和操作。本文基于圖構建圖上多層次多粒度的粒結構,并通過粒度轉換的運算符實現(xiàn)層次與層次之間、不同層次的粒之間的轉換。第3節(jié)將詳細介紹基于圖的粒結構。在粒結構中,不同粒度的層次與層次之間、不同層次的粒之間的聯(lián)系和轉換,可以通過粒度轉換的運算符來實現(xiàn)。粒度轉換運算符至少有兩類,一類運算符處理從細粒度到粗粒度的轉換,這類運算符將細粒度的層次轉換為粗粒度的層次,將細粒度層次中的粒轉換為粗粒度層次中的粒,隱藏具體細節(jié),體現(xiàn)共性。許多研究涉及了包含類似功能的操作,例如:抽象、簡化、一般化、粗化、縮小等。另一類運算符處理從粗粒度到細粒度的轉換,這類運算符將粗粒度層次中的粒轉換為細粒度層次中的粒,將粗粒度層次轉換為細粒度層次。以往研究中,涉及到類似功能的定義有:擴張、特定化、細分、放大等。此外,粒結構上還可以定義一些具有其他功能的運算符。例如,對于在細粒度層次上某些粒的集合,在粗粒度層次上可能找不到一個確定的粒來表示它們,這就需要對它們進行類似于粗糙集中上下近似的運算。第4節(jié)將詳細介紹粒度轉換的幾種運算符。2粒的層次與粒度粒計算研究的對象所具有的多層次、多視角的結構稱為粒結構,其組成元素包括粒、層次及分層結構。在粒計算中,粒是一個最基本的抽象概念,我們在處理問題時將可以看作一個整體的對象作為一個粒。粒具有雙重身份,可以是其他粒的一部分,也可以是多個更小粒組成的整體。粒存在著不同的粒度,相同粒度的粒結合在一起,構成對問題特定粒度層次的描述。我們可以基于特定的視角用較小的粒來觀察研究較大的粒。層次是粒計算的另一個重要概念,一個層由同樣粒度或同樣性質的粒組成。粒給出局部描述,由一簇粒形成的層給出一個給定粒度的全局描述。人們在不同層次中研究不同粒度的粒,同一層次的粒之間可以是不相交的關系,也可以是交疊的關系。同一層次上所有的粒共同體現(xiàn)了本層次的特性,它們互相補充,互相呼應,完整地表達了在這個層次、這個粒度上對一個問題的描述。不同的層次可以組織起來形成一個多層次結構。分層結構由若干層次組成,不同層次體現(xiàn)了不同的粒度。層次間的遞進反映了由表及里、由抽象到具體、由粗糙到細致、由籠統(tǒng)到具體的變化。通過細化運算,一個高層次的粒可以分解為若干個低層次的粒,從而對問題提供更詳細的描述或者更多的信息。通過粗化運算,若干個低層次的?？梢越M合成一個高層次的粒,從而將隱藏不相關的細節(jié),體現(xiàn)問題的共性。一個分層結構只可能給出一個局限性的視角,要達到全面的理解必須采用多個分層結構。對于現(xiàn)實世界的描述,多個分層結構可以給出特定問題的不同視角。一個分層結構中,不同的粒度使我們對問題有多層次的理解,多視角方法將若干個分層結構組合成粒結構。多層次、多視角的粒結構反映了對同一問題理解的多個角度和視點。多層次和多視角是粒結構的核心內容。3基于圖的粒度結構3.1v的嚴格區(qū)別—圖中的粒定義1一個圖G定義為一個偶對(V,E),記作G=(V,E),其中,V是頂點的集合,E是邊的集合。在一個無向圖中,一條邊是一個無序對(v,w),在一個有向圖中,一條邊是一個有序對。頂點v,w稱為邊的頂點。在有權圖中,每條邊都有一個由賦權函數賦給的權值。圖1是一個無向圖的例子。定義2設集合V為圖G上所有頂點的集合,V的冪集2V中的一個元素g稱為圖G上的一個粒。一個粒g是圖上所有頂點的集合V的一個子集,它是這個子集中所有頂點的整體。在處理問題時,如果一些頂點可以看作是不可區(qū)分的,那它們就被作為一個粒,這個粒可以看作是這些頂點的概括和抽象。頂點集V的冪集2V包含了圖G上所有可能的粒,其中,最大的粒是頂點的全集V,空集可以看作是圖上最小的粒。定義3如果一個粒g1中的任意一個元素同時也是粒g2中的元素,也就是,g1∈g2,則稱g1是g2的子粒,g2是g1的父粒。粒具有雙重身份,其既可以是某個整體的相對獨立的一個部分,又可以被看作是由其他的一些粒組成的整體。集合上的包含關系?定義了集合2V上的部分序,通過包含關系,可以得到粒之間的父粒-子粒關系?？紤]頂點集合V的一系列子集H和H上的半序關系,可以構建圖上的粒結構。一般地,可以根據圖中節(jié)點的度、邊的權值、圖的連通性、圖的密度來建立圖的?；瘶藴屎途唧w?；惴?關于將圖?；木唧w標準和算法在文獻中有詳細討論。3.2粒度結構的構建定義4當圖G上的頂點按照給定的?；瘶藴史謩e歸納為粒,也就是圖G按照給定的?；瘶藴释瓿闪艘淮瘟；?我們稱一次?；蟮玫剿辛５募蠟閳DG的一個層次。根據不同的?；瘶藴?可以對圖進行不同程度的粒化,得到不同的層次。每個層次對應一個特定的粒度,它可以被看作問題的一個特定的理解。定義5考慮圖G的兩個層次l1和l2,對于l1中的任意一個粒g1,如果存在一個l2中的粒g2,使得g1∈g2,也就是說,對于l1中的任意一個粒g1,都能夠在l2中找到它的父粒g2,則稱層次l1的粒度比層次l2更精細,層次l2的粒度比l1更粗糙。較細粒度的層次相對較粗粒度的層次是對問題的一個更具體的理解、觀點和描述;較粗粒度的層次是對問題比較抽象的理解和描述。通過在不同粒度的層次之間轉換,可以得到對問題的由具體到抽象,由精細到粗糙的理解。例1圖2和圖3分別是將圖1中的圖G經過不同程度的?；蟮玫降膶哟巍D2所示的層次將圖G?；癁閮蓚€粒,圖3所示的層次將圖G?；癁?個粒,圖2所示層次的粒度比圖3所示的層次更加粗糙,圖3所示層次的粒度更為精細。定義6設H是圖G的一個層次上的所有粒的集合,偏序集(H,?)稱為一個粒結構,其中?是包含關系。通過半序關系,各個不同的層次可以結合成一個多層次的粒結構,不同層次中的粒也被關聯(lián)到一起。在粒結構中,不同層次是對圖的不同粒度的描述,整個粒結構提供了對問題的多粒度的理解。包含關系?是半序關系的一個特例,更一般地,我們可以考慮用任意其他的半序關系來構建對應的粒結構。例2圖4所示為對圖G建立的粒結構,粒結構中包含兩個層次,分別為圖2所示較粗糙的層次和圖3所示較精細的層次,包含關系將這兩個層次聯(lián)系在一起,形成一個偏序集,即為圖G的粒結構。4同層次的運算符在基于圖的粒結構中,不同粒度的層次與層次之間、不同層次的粒之間的聯(lián)系和轉換,可以通過“細化”和“粗化”運算符來實現(xiàn)。細化運算符處理從粗粒度到細粒度的轉換,粗化運算符處理從細粒度到粗粒度的轉換。4.1細化運算符的定義細化運算符實現(xiàn)從粗粒度層次到細粒度層次的轉換,這種轉換反映了由抽象到具體、由粗糙到細致的變化。細化運算將一個高層次的粒分解為若干個低層次的粒,當高層次的所有粒全部被分解為低層次中的粒后,就完成了從粗粒度層次到細粒度層次的轉換。細化運算符可以根據需要為問題求解提供更詳細的描述或者更多的細節(jié)。下面在基于圖的粒結構基礎上,給出“細化”運算符的定義。定義7設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,g1為l1中的粒,對g1的運算:ω(g1)l1→l2={g|g1?g,g∈l2}稱為將g1細化到l2層次,ω稱為細化運算符。定義8設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,對l1的運算:ω(l1)l1→l2=∪ω(g)l1→l2,g∈l1稱為將l1層次細化為l2層次,ω為細化運算符。例3如圖5所示,對圖4的粒結構的層次Level1中的粒g1={a,b,c,d}進行細化運算,有:ω(g1)={g3,g4,g5}={{a},{b,c},umywooc}圖6所示為對圖4的粒結構中的層次Level1的細化運算:ω(l1)=ω{g1,g2}={g3,g4,g5,g6,g7}=l2下面的定理反映了細化運算的性質。定理1ω(?)=?ω(Xc)=(ω(X))cω(X∩Y)=ω(X)∩ω(Y)ω(X∪Y)=ω(X)∪ω(Y)X?Y?ω(X)?ω(Y)4.2粗化運算的編碼粗化運算符實現(xiàn)從細粒度層次到粗粒度層次的轉換,這種轉換反映了由細致到抽象,由具體到籠統(tǒng)的變化。粗化運算將在處理問題時區(qū)別不大的對象合成為一個整體,將細粒度層次中的粒轉換為粗粒度層次中的粒,將細粒度的層次轉換為粗粒度的層次。粗化運算符在問題求解時忽略掉不相關的細節(jié),提供抽象的描述。定義9設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,g為l1中的粒,對g的細化運算將g細化為l2中的粒g1..gn,即ω(g)l1→l2=g1..gn則對g1..gn的運算:σ(g1..gn)l2→l1=g稱為將g1..gn粗化到l1層次,σ稱為粗化運算符。定義10設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,且有:ω(l1)l1→l2=l2則對l2的運算:σ(l2)l2→l1=l1稱為對l2層次的粗化運算,σ為粗化運算符。例4對圖4的粒結構中層次Level2的粒g4,g5進行粗化運算,有:σ(g3,g4,g5)=g1對圖4的粒結構中的層次Level2的粗化運算:σ(l2)=σ{g3,g4,g5,g6,g7}={g1,g2}=l1下面的定理反映了粗化運算的性質。定理2σ(V)=Vσ(Xc)=(σ(X))c4.3粒結構的生成當對l2層次中的一些粒做粗化到l1層次的運算時,如果這些粒不能正好粗化為l1層次中的粒,也就是說這些粒并不正好是l1中某些粒經過細化得到的粒的集合,就需要粗化運算的近似運算。類似于粗糙集中的上下近似概念,我們給出粗化運算符的兩個近似運算。定義11設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,H為l2的一個子集,對H的運算:σˉ(H)l2→l1={g|g∈l1,ω(g)l1→l2?H}σˉ(Η)l2→l1={g|g∈l1,ω(g)l1→l2?Η}稱為對H的內粗化運算。定義12設l1,l2為圖G的兩個層次,l1的粒度比l2粗糙,H為l2的一個子集,對H的運算:σˉ(H)l2→l1={g|g∈l1,ω(g)l1→l2∩H≠?}σˉ(Η)l2→l1={g|g∈l1,ω(g)l1→l2∩Η≠?}稱為對H的外粗化運算。例5對圖4的粒結構中層次Level2中的粒g5,g6,g7無法直接進行粗化運算,對它們進行內粗化和外粗化運算有:σˉ({g5,g6,g7})=g2σˉ({g5,g6,g7})={g1,g2}σˉ({g5,g6,g7})=g2σˉ({g5,g6,g7})={g1,g2}下面的定理反映了內外粗化運算的性質。定理3設l1,l2為兩個層次,l1的粒度比l2粗糙,A?l1,B?l2,那么,ω(A)?B?A?σˉ(B)ω(A)?B?A?σˉ(B)B?ω(A)?σˉσˉ(B)?A定理4設l1,l2為兩個層次,l1的粒度比l2粗糙,?A,B?l2,ω是從l1到l2的細化運算,σˉ,σˉσˉ,σˉ分別是l2到l1的內外粗化運算,則,σˉ(?)=σˉ(?)=?σˉ(l2)=σˉ(l2)=l1σˉ(A)?σˉ(A)σˉ(A)=(σˉ(Ac))cσˉ(A)=(σˉ(Ac))cσˉ(ω(A))=σˉ(ω(A))=Aω(σˉ(A))?AA?ω(σˉ(A))A?B?σˉ(A)?σˉ(B)A?B?σˉ(A)?σˉ(B)σˉ(A∩B)=σˉ(A)∩σˉ(B)σˉ(A∩B)?σˉ(A)∩σˉ(B)σˉ(A)∪σˉ(B)?σˉ(A∪B)σˉ(A∪B)=σˉ(A)∪σˉ(B)σˉ(?)=σˉ(?)=?σˉ(l2)=σˉ(l2)=l1σˉ(A)?σˉ(A)σˉ(A)=(σˉ(Ac))cσˉ(A)=(σˉ(Ac))cσˉ(ω(A))=σˉ(ω(A))=Aω(σˉ(A))?AA?ω(σˉ(A))A?B?σˉ(A)?σˉ(B)A?B?σˉ(A)?σˉ(B)σˉ(A∩B)=σˉ(A)∩σˉ(B)σˉ(A∩B)?σˉ(A)∩σˉ(B)σˉ(A)∪σˉ(B)?σˉ(A∪B)σˉ(A∪B)=σˉ(A)∪σˉ(B)粒計算的三元論模型以粒結構為基礎,包括3個部分,即哲學思想(結構化思維)、方法論(結構化問題求解)、計算模式(結構化信息處理),其將現(xiàn)有粒計算研究成果的共性抽象出來,為問題求