河南師范大學(xué)計算機與信息技術(shù)學(xué)院 王 川

粒的運算及其分層結(jié)構(gòu)研究

河南師范大學(xué)計算機與信息技術(shù)學(xué)院 王 川

在傳統(tǒng)粒計算理論的基礎(chǔ)上，對粒的表示方法加以改進(jìn)，從而使粒計算更具適用性，進(jìn)而構(gòu)建粒子空間，并將粒子空間投影到信息系統(tǒng)中得到其層次結(jié)構(gòu)圖，該分層結(jié)構(gòu)能滿足用戶對數(shù)據(jù)局部分析或概化分析的興趣點。

粒計算 分層結(jié)構(gòu) 投影

一、引言

粒計算是一種新的基于問題概念空間劃分的智能計算方法[1-6]。本文結(jié)合傳統(tǒng)粒計算理論，考慮實際中數(shù)據(jù)分析興趣習(xí)慣，在對粒的表示方法進(jìn)行改進(jìn)研究的基礎(chǔ)上，進(jìn)一步對新的粒結(jié)構(gòu)進(jìn)行分析并嘗試應(yīng)用，進(jìn)而構(gòu)建粒子空間，并將粒子空間投影到信息系統(tǒng)中得到粒的分層結(jié)構(gòu)，從而滿足用戶對數(shù)據(jù)局部分析或概化分析的興趣點，同時提高了數(shù)據(jù)分析的效率。

二、粒的表示方法及其運算

定義1 （公式的定義） 在信息系統(tǒng)S = (U, A, V, F )中，令a∈A，M?Va，(a, M)為一原子公式定義，以下簡寫為aM，定義如下的rough邏輯公式：

（1）aM是原子公式，原子公式是公式；若M = Va，則稱aM為可缺省原子公式，不參與粒運算。

（2）如果A和B是原子公式，那么A∧B是公式，使用連接詞∧進(jìn)行有限次運算所組成的式子是公式。

定義2 （粒的定義） 函數(shù)h(a, M)表示所有在屬性a(a∈A)上的值屬于M(M?Va)的對象集，即h(a, M) = {x|a(x)∈M}，其中x∈U，則信息系統(tǒng)S = (U, A, V, F )中粒的定義為：Gr = ((a, M)，h(a, M))，其中(a, M)為粒Gr的語法，Gr被稱為信息系統(tǒng)中的原子粒，若M = ?，則h(a, M) = ?，對應(yīng)的原子粒Gr為空粒。設(shè)w是形如(a1, M1)∧(a2, M2)∧…∧ (an, Mn)的由原子公式使用邏輯連接詞∧所得邏輯組合，

h(w)表示滿足邏輯組合w的對象集合。Gr = (w, h(w))被稱為滿足邏輯組合w的組合粒。

定義1與定義2是在文獻(xiàn)[3]基礎(chǔ)上對公式和粒重新定義，其主要區(qū)別將原子公式(a, v)，a∈A，v∈Va，重新定義為(a, M)，a∈A，M?Va，意義在于擴大原子公式的適用范圍。

定義 3 （粒分解運算） 一個組合粒Gr = (w, h(w))，其中w = (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，則Gr的分解Dec(Gr) = {Gr1, Gr2, …, Grn}，其中Gr1= ((a1, M1),h(a1, M1))，Gr2= ((a2, M2), h(a2, M2))，…，Grn= ((an, Mn), h(an, Mn))。

定義4 （交運算） 對于任意兩個粒Gr1= (w1, h(w1))，Gr2= (w2, h(w2))，其中w1= (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，w2= (a1, K1)∧(a2, K2)∧…∧ (an, Kn)，則定義其交運算（∧）為：Gr1∧Gr2= (w3, h(w3))，其中w3= (a1, M1∧K1)∧(a2, M2∧K2)∧…∧ (an, Mn∧Kn)。

定義5 （并運算） 對于任意兩個粒Gr1= (w1, h(w1))，Gr2= (w2, h(w2))，其中w1= (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，w2= (a1, K1)∧(a2, K2)∧…∧ (an, Kn)，則定義其并運算（∨）為：Gr1∨Gr2= (w3, h(w3))，其中w3= (a1, M1∨K1)∧(a2, M2∨K2)∧…∧ (an, Mn∨Kn)。

定理1對于任意兩個組合粒Gri= (wi, h(wi))，Grj= (wj, h(wj))，其中wi= (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，wj= (a1, K1)∧(a2, K2)∧…∧ (an, Kn)，則滿足Gri∧Grj= ∧(Dec(Gri)∨Dec(Grj))，Gri∨Grj= ∨(Dec(Gri)∨Dec(Grj))。

證明：由定義3可得，Dec(Gri) = {Gri1, Gri2, …, Grin}，其中Gri1= ((a1, M1), h(a1, M1))，Gri2= ((a2, M2), h(a2, M2))，…，Grin= ((an, Mn), h(an, Mn))；Dec(Grj) = {Grj1, Grj2, …, Grjn}，其中Grj1= ((a1, K1), h(a1, K1))，Grj2= ((a2, K2), h(a2, K2))，…，Grjn= ((an, Kn), h(an, Kn))。所以∧(Dec(Gr1)∨Dec(Gr2)) =∧{Gri1, Gri2, …, Grin, Grj1, Grj2, …, Grjn} = Gri1∧Grj1∧…∧Grin∧Grjn= ((a1, M1∧K1), h(a1, M1∧K1))∧…∧((an, Mn∧Kn), h(an, Mn∧Kn))，由定義4可得，Gri∧Grj= (wk, h(wk))，其中wk= (a1, M1∧K1)∧(a2, M2∧K2) ∧…∧(an, Mn∧Kn)，所以得Gri∧Grj= ∧(Dec(Gri)∨Dec(Grj))，同理可得Gri∨Grj=∨(Dec(Gri)∨Dec(Grj))。

性質(zhì)1 對于任意兩個粒Gr1= (w1, h(w1))，Gr2= (w2, h(w2))，Gr1= Gr2當(dāng)且僅當(dāng)Gr1∧Gr2= Gr1∨Gr2

定義6 對于任意兩個粒Gr1= (w1, h(w1))，Gr2= (w2, h(w2))，若滿足Gr1∨Gr2= Gr1且Gr1∧Gr2= Gr2，則稱粒子Gr1是Gr2父粒，或者稱Gr2是Gr1的子粒，記為Gr2pGr1。

性質(zhì)2 對于任意組合粒Gr = (w, h(w))，其中w = (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，滿足GrpN，其中，N∈Dec(Gr)。

證明：由N∈Dec(Gr)，所以令N = ((ai, Mi), h(ai, Mi))，因為w∧(ai, Mi) = w，所以Gr∧N = Gr；又有w∨(ai, Mi) = (ai, Mi)，所以Gr∨N = N。由定義6得GrpN。

三、粒的分層結(jié)構(gòu)

定義7 （粒子空間） 設(shè)U為有限對象集，G為有限原子粒集合，原子粒((a, M), h(a, M))∈G，X，X1，X2?U，B，B1，B2?G，f：?(G)→?(U)為粒集到對象集的映射算子；g：?(U)→?(G)表示從對象集合到粒集上的映射算子。若f-滿足：

且g滿足：

則稱GCs = (U, G, I)為粒子空間，其中I = U×G表示對象與粒之間的二元關(guān)系。對于任意粒子Gr∈G，x∈U，若(x，Gr)∈I表示對象x滿足粒Gr，若(x，Gr)?I表示對象x不滿足粒Gr。

性質(zhì)3 對粒子空間GCs = (U, G, I)，令X，X1，X2?U；B，B1，B2?G，則有

證明：

（1）已知B1?B2，則f(B1∪B2) = f(B2)，又由粒子空間的定義知f(B1∪B2) = f(B1)∩f(B2)，所以f(B2) = f(B1)∩f(B2)，而f(B1)∩f(B2)?f(B1)，因此f(B2)?f(B1)，同理有X1?X2? g(X2) ?g(X1)。

（2）類似于（1）的證明。

（3）由于B1∩B2?B1，B1∩B2?B2，則由性質(zhì)（1）可得f(B1∩B2)?f(B1)，f(B1∩B2)?f(B2)，所以f(B1∩B2)?f(B1)∪f(B2)成立。

定義8 在信息系統(tǒng)S = (U, A, V, F)中，對于任意粒Gr = (Ψ, h(Ψ))，其中Ψ = (a1, M1)∧(a2, M2)∧…∧ (an, Mn)，Dec(Gr) = {Gr1, Gr2, …, Grn}，該粒在信息系統(tǒng)S中對應(yīng)的粒子空間可以表示為(U’, G, I)，其中U’ = U – {x|(x, Gri)?I , Gri}，Gri∈Dec(Gr)}，G = Dec(Gr)。定義9 在信息系統(tǒng)S = (U, A, V, F)中，粒Gr對應(yīng)的的粒子空間為GCs = (U, G, I)，對于一個二元對（B, f(B)），其中B?G，如果滿足B = g(f(B))，則稱該二元對為該粒子的子粒節(jié)點。

定理2 在信息系統(tǒng)S = (U, A, V, F)中，對于任一給定二元對(Bn-1，Xn-1)其中Bn-1?G，Xn-1?U，經(jīng)以下有限次迭代運算：

則必然存在一子粒節(jié)點(Bn’，f(Bn’))與之對應(yīng)。

證明：顯然運算中Xn是單調(diào)增加的，又因為論域U是有限集，必然存在Xn’= Xn’+1?U由運算（1），使得Xn’= Xn’+1= Xn’∪f(Bn’)，由運算（2）Bn’= g(Xn’)，又由運算（3）有Bn’= Bn’∪g(Xn’) = g(Xn’)，又因為Xn’= Xn’+1，所以Bn’= g(Xn’+1)，再由運算（4）可得Xn’+1= f(Bn’+1)，于是(Bn’，f(Bn’))為一子粒節(jié)點。

定義10 在信息系統(tǒng)S = (U, A, V, F)中，粒Gr對應(yīng)的的粒子空間為GCs = (U, G, I)，設(shè)P = {(B, f(B))|B∈G, B = g(f(B))}為GCs中所有子粒節(jié)點的集合，則存在唯一偏序集(P, p)與之對應(yīng)，且該偏序集中子粒節(jié)點都存在唯一的最小父粒（下確界）和一個唯一最大子粒（上確界），這個偏序集產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)稱為Gr在信息系統(tǒng)S中的投影。

在一個粒子對應(yīng)的粒子空間中，對于每個子粒節(jié)點總是存在一個唯一的最小下確界和一個唯一的最大上確界。由此得到該粒子在相應(yīng)信息系統(tǒng)中的投影。顯然這個投影描述出的是一個特征粒在某個信息系統(tǒng)中的具體層次結(jié)構(gòu)。如果將其所有子粒節(jié)點按照父粒在上，子粒在下的原則用線段連接起來就得到該特征粒的層次結(jié)構(gòu)圖。

四、結(jié)束語

本文試圖從應(yīng)用的角度構(gòu)建粒的結(jié)構(gòu)，為了滿足應(yīng)用的需求，對粒的表示方法加以改進(jìn)，從而使粒計算更具適用性，進(jìn)而構(gòu)建粒子空間，并將粒子空間投影到信息系統(tǒng)中得到其分層結(jié)構(gòu)圖，從而滿足用戶對數(shù)據(jù)局部分析或概化分析的興趣點，并嘗試通過這種粒結(jié)構(gòu)來協(xié)助用戶進(jìn)行知識檢索，構(gòu)建基于新的粒結(jié)構(gòu)的知識檢索的具體模型及系統(tǒng)功能的設(shè)計與實現(xiàn)。

[1] 苗奪謙, 王國胤, 劉清, 林早陽, 姚一豫. 粒計算：過去、現(xiàn)在與展望[M]. 北京: 科學(xué)出版社, 2007.

[2] 徐久成, 史進(jìn)玲, 張倩倩. 基于粒計算的序決策規(guī)則提取算法[J]. 模式識別與人工智能, 2009, 4(4)：660-665.

[3] 王國胤, 張清華. 不同知識粒度下粗糙集的不確定性研究[J]. 計算機學(xué)報, 2008, 31(9): 1588-1598.

book=118,ebook=118