一種新的粒表示方法及其距離計算

摘 要:傳統(tǒng)粒的表示上存在其局限性導致粒的適用性不強，難以滿足用戶對粒描述的興趣點。在傳統(tǒng)粒計算理論的基礎上，對粒的表示方法加以改進，從而使粒更具適用性，進而定義了新表示方法下粒的幾個運算，研究了新表示方法下粒的距離及相似度。這種理論方法注重從粒的語法上去研究粒的運算、距離及相似度，更清晰準確地揭示了粒的本質(zhì)。

關鍵詞:粒計算; 表示方法; 距離; 相似度; 粒熵

中圖分類號:TP18文獻標志碼:A

文章編號:1001-3695(2010)06-2034-03

doi:10.3969/j.issn.1001-3695.2010.06.010

New description method of granular and its distance computing

XU Jiu-cheng， CHENG Wan-li， SUN Lin

(Key Laboratory for Intelligent Information Processing， College of Computer Information Technology， Henan Normal University， Xinxiang Henan 453007， China)

Abstract:The represention of traditional granule exists limitations which leads to low application， so it is difficult to meet users’points of interest about granule discription. Based on the theory of traditional granular computing， this paper improved the representation method of granular， making granular more applicable. Besides， defined several operations between granulars by the new method. Finally， studied granular’s distance and similarity. This theory emphasizes on researching granular’s operations， distance and similarity in granular’s grammar， which reveals the essence of granular more clearly and accurately and makes grannular computing better used in solving the problems about uncertainty relation.

Key words:granular computing; representation method; distance; similarity; granular entropy

0 引言

粒計算是一種新的基于問題概念空間劃分的智能計算方法[1~4]。關于粒計算的問題，通常可以從兩個方面進行研究，即粒子的結(jié)構和粒子的計算。前者主要是解決粒子的形成、表示和解釋;后者主要是解決粒子的使用問題。在目前粒計算的研究中，對粒的結(jié)構描述，文獻[3]中把一個基本粒表示為m(a，v)的形式。其中(a，v)是一個原子式。而實際應用中，如在數(shù)據(jù)庫中，屬性v的取值可能有數(shù)百個，僅一個屬性就對應數(shù)百個原子式，而要考察的是屬性在某個取值區(qū)間上的情況，如在數(shù)據(jù)庫檢索時，如果描述一個類似“av>x且av

本文在傳統(tǒng)粒計算理論的基礎上，對粒的表示方法進行改進，把一個原子式(a，v)重新定義為(a， M)。其中M不再是一個值，而是一個值域，從而使新定義的粒更具有適用性，進而定義了新表示方法下的粒的運算。在這些運算的基礎上本文定義了粒的距離和相似度并研究了其相關性質(zhì)，最后將粒的距離計算應用到粒熵計算與屬性取值重要度的計算上。這種理論方法滿足了用戶對粒描述的興趣點，從而使粒計算更好地用于解決不確定性關系問題。

1 基本概念

定義1[3] 在信息系統(tǒng)S=(U，A，V，f)中，令a∈A， v∈Va，(a，v)為一原子式，以下簡寫為av，定義如下的rough邏輯公式:

a)av是原子式，原子式是公式;

b)如果A和B是原子式，那么~A、A∧B、A∨B、(A)、A→B是公式;

c)按a)和b)定義的公式，使用連接詞~、∨、∧、→、 進行有限次運算所組成的式子是公式。

根據(jù)以上定義可以看出，在等價關系下，某個屬性集上的屬性值相等的對象可以構成一集合，且這些對象在該屬性集上滿足等價關系，可以利用這個集合來定義粒。

定義2[3] 粒的定義。函數(shù)h(a，v)表示在屬性a(a∈A)上的值為v的對象集，信息系統(tǒng)S=(U，A，V，f)中粒的定義為Gr=((a，v)，h (a，v))。其中(a，v)為粒Gr的語法，Gr被稱為信息系統(tǒng)中的原子粒。設ω和Ψ是形如(a，v)的原子式使用邏輯連接詞~、∨、∧、→、所得邏輯組合，h(ω)表示滿足邏輯組合ω的對象集合。Gr=(ω，h(ω))被稱為滿足邏輯組合ω的組合粒。

2 一種粒表示方法及運算

定義3 公式的定義。在信息系統(tǒng)S=(U，A，V，f)中，令a∈A， MVa，(a，M)為一原子式，以下簡寫為aM，定義如下的rough邏輯式:

a)aM是原子式，原子式是公式;若M=Va，則aM對應的對象為整個論域，并把該類原子式記為T;若M=，則稱aM為空公式。

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

定義4 粒的定義。函數(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)中的原子粒。設ω是形如(a1，M1)∧(a2，M2)∧…∧ (an，Mn)的由原子式使用邏輯連接詞∧所得邏輯組合，h(ω)表示滿足邏輯組合ω的對象集合。Gr=(ω，h(ω))被稱為滿足邏輯組合ω的組合粒。函數(shù)F(Gr)表示滿足粒Gr的對象集合。

定義3與4是在文獻[3]基礎上對公式和粒重新定義，其主要區(qū)別是將原子式(a，v)重新定義為(a，M) (a∈A，v∈Va， MVa)，意義在于擴大粒的適用范圍。同時，為了簡化粒的運算，公式的邏輯組合所用連接詞只取“∧”。

性質(zhì)1 設ω是公式，對原子式aM，若M=，則h(a， M)=;若M=Va，則h(a， M)=U，且滿足ω∧aM=ω，ω∨aM=aM。

定義5 粒分解。一個粒Gr=(ω，h(ω))。其中:ω=(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))。

定義6 交運算。對于任意兩個粒Gr1=(ω1，h(ω1))，Gr2=(ω2，h(ω2))。其中:ω1=(a1，M1)∧(a2，M2)∧…∧(an，Mn)，ω2=(a1，K1)∧(a2，K2)∧…∧(an，Kn)，則定義其交運算(∧)為Gr1∧Gr2=(ω3，h(ω3))。其中ω3=(a1，M1∧K1)∧(a2，M2∧K2)∧…∧ (an，Mn∧Kn)。

定義7 并運算。對于任意兩個粒Gr1=(ω1，h(ω1))，Gr2=(ω2， h(ω2))。其中:ω1=(a1，M1)∧(a2，M2)∧…∧ (an，Mn)，ω2=(a1，K1)∧(a2，K2)∧…∧(an，Kn)，則定義其并運算(∨)為Gr1∨Gr2=(ω3，h(ω3))。其中ω3=(a1，M1∨K1)∧(a2，M2∨K2)∧…∧ (an，Mn∨Kn)。

定理1 對于任意兩個組合粒Gri=(ωi， h(ωi))，Grj=(ωj，h(ωj))。其中ωi=(a1，M1)∧(a2，M2)∧…∧(an，Mn)，ωj=(a1，K1)∧(a2，K2)∧…∧(an，Kn)，則滿足Gri∧Grj=∧{Gr|Gr∈dec(Gri)∪dec(Grj)}，Gri∨Grj=∨{Gr| Gr∈dec(Gri)∪dec(Grj)}。

證明 由定義5可得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))。所以∧{Gr| Gr∈dec(Gr1)∨dec(Gr2)}=∧{Gri1，Gri2，…，Grin，Grj1Grj2，…，Grjn}=Gri1∧Grj1∧…∧Grin∧Grjn=((a1，M1∧K1)，h(a1，M1∧K1)) ∧…∧((an，Mn∧Kn)，h(an，Mn∧Kn))。由定義12可得Gri∧Grj= (ωk，h(ωk))。其中ωk=(a1，M1∧K1)∧(a2，M2∧K2)∧…∧ (an，Mn∧Kn)，所以得Gri∧Grj=∧{Gr| Gr∈dec(Gri)∨dec(Grj)}。

同理可得Gri∨Grj=∨{Gr|Gr∈dec(Gri)∨dec(Grj) }。

性質(zhì)2 對于任意兩個粒Gr1=(ω1，h(ω1))，Gr2=(ω2，h(ω2))，Gr1=Gr2當且僅當Gr1∧Gr2= Gr1∨Gr2。

證明顯然成立。

定義8 對于任意兩個粒Gr1=(ω1，h(ω1))，Gr2=(ω2，h(ω2))，若滿足Gr1∨Gr2=Gr1且Gr1∧Gr2=Gr2，則稱粒子Gr1是Gr2父粒，或者稱Gr2是Gr1的子粒，記為Gr2Gr1。

性質(zhì)3 對于任意組合粒Gr=(ω，h(ω))，其中ω=(a1，M1)∧(a2，M2)∧…∧ (an，Mn)，N∈dec(Gr)，則GrN。

證明 由N∈dec(Gr)，所以令N=((ai，Mi)，h(ai，Mi))，因為ω∧(ai，Mi)=ω，所以Gr∧N=Gr;又有ω∨(ai，Mi)=(ai，Mi)，得Gr∨N=N，再由定義8可得GrN。

例1 設S=(U，A，V，f)為一信息系統(tǒng)(表1)，其中U={x1，x2，x3，x4，x5，x6}，A={a，b，c}。

a)描述在屬性a上取值大于0，屬性b上取值不等于0，屬性c上取值等于1的粒Gr1;

b)描述在屬性a上取值小于3，屬性c上取值大于0的粒Gr2;

c)求Gr1∧Gr2和Gr1∨Gr2。

表1 信息表S

UabcUabc

x1130x4004

x2-10.51x5501

x3312x6211

由以上定義可得，在屬性a上取值大于0的原子式表示為(a，{a(x)| a(x)>0})，簡寫為{a(x)>0};同理，屬性b上取值不為空的原子式表示為{b(x)≠0};屬性c上取值等于1的原子式表示為{c(x)=1}，則粒子Gr1可以表示為(Ψ1，h(Ψ1))。其中Ψ1= {a(x)>0}∧{b(x)≠0}∧{c(x)=1}。同理，Gr2可以表示為(Ψ2，h(Ψ2))。其中Ψ2= {a(x)<3}∧{c(x)>0}，Gr1∨Gr2=(Ψ3，h(Ψ3))。其中Ψ3= {c(x)>0}，同理，Gr1∧Gr2=(Ψ4，h(Ψ4))。其中Ψ4= {0

3 粒的距離計算及性質(zhì)

定義9 在信息系統(tǒng)S=(U，A，V，f)中，對于任意兩個粒Gr1與Gr2，則定義Gr1與Gr2的絕對距離GD (Gr1，Gr2)如下:

GD(Gr1，Gr2)=(|F(Gr1∨Gr2)|-|F(Gr1∧Gr2)|)/|U|

其中:|#8226;|表示集合的基數(shù)。

定理2 在信息系統(tǒng)S=(U，A，V，f)中，對于任意兩個粒Gr1與Gr2，則必有GD(Gr1，Gr2)=GD(Gr2，Gr1)成立。

證明顯然成立。

定理3 直線定理。若P、Q、R為信息系統(tǒng)S=(U，A，V，f )中的三個粒且滿足PQR，則必有GD(P，R)=GD(P，Q)+ GD(Q，R)。

證明 設P=(ω1，h(ω1))，Q=(ω2，h(ω2))，R=(ω3，h(ω3))，由于PQR，根據(jù)定義8得P∧Q=P，P∨Q=Q， P∧R=P，P∨R=R，Q∨R=R，Q∧R=Q。由定義9得GD(P，R)=((F(P∨R)|- |F(P∧R)|))|U|=(|F(R)|-|F(P)|) /|U|。

同理，GD(P，Q)= (|F(P∨Q)|- |F(P∧Q)|)/|U|=(|F(Q)|-|F(P)|) /|U|，GD(Q，R)= (|F(Q∨R)|- |F(Q∧R)|)/|U|=(|F(R)|-|F(Q)|) /|U|，所以GD(P，Q)+GD(Q，R)= (|F(Q)|-|F(P)|) /|U| + (|F(R)|-|F(Q)|)/|U|=(|F(R)|-|F(P)|) /|U|=GD(P，R)，即GD(P，R)=GD(P，Q)+ GD(Q，R)。

性質(zhì)4 在信息系統(tǒng)S=(U，A，V，f )中，對于任意兩個粒Gr1與Gr2，則有0≤GD(Gr1，Gr2)≤1。

推論1 對于任意兩個粒Gr1和Gr2，若:

a)GD(Gr1，Gr2)=1當且僅當F(Gr1∧Gr2)=且F(Gr1∨Gr2)=U。

b)Gr1=Gr2的充分必要條件是GD(Gr1，Gr2)=0。

推論1說明兩個粒之間的距離最大時，它們所對應的對象集是互補的;距離最小時兩個粒相等。該距離反映了兩個粒之間的絕對差異程度。如果考慮兩個粒之間的相似程度就需要計算它們之間的相對距離。下面給出粒的相似度定義及相對距離的定義。

定義10 定義Gr1與Gr2的相似度sim(Gr1，Gr2)為

sim(Gr1，Gr2)=|F(Gr1∧Gr2)|/|F(Gr1∨Gr2)|

性質(zhì)5 在信息系統(tǒng)S=(U，A，V，f )中，對于任意兩個粒Gr1與Gr2，則有0≤sim(Gr1，Gr2)≤1。

定義11 在信息系統(tǒng)S=(U，A，V，f )中，對于任意兩個粒Gr1與Gr2，則定義Gr1與Gr2的覆蓋系數(shù)cov(Gr1，Gr2)=|F(Gr1∨Gr2)| /|U|。

下面用定義9的粒的絕對距離與定義11的覆蓋系數(shù)來定義粒的相對距離。

定義12 在信息系統(tǒng)S=(U，A，V，f)中，對于任意兩個粒Gr1與Gr2，則定義Gr1與Gr2的相對距離GD(Gr1，Gr2)為

GDU(Gr1，Gr2)=GD(Gr1，Gr2)/cov(Gr1，Gr2)

性質(zhì)6 在信息系統(tǒng)S=(U，A，V，f)中，對于任意兩個粒Gr1與Gr2，則有sim(Gr1，Gr2)+GDU(Gr1，Gr2)=1。

證明 由定義9和定義11可得

GDU(Gr1，Gr2)=((|F(Gr1∨Gr2)|-|F(Gr1∧Gr2)|)/|U|)/(|F(Gr1∨Gr2)| /|U|)

=(|F(Gr1∨Gr2)|-|F(Gr1∧Gr2)|)/|F(Gr1∨Gr2)|=1-|F(Gr1∧Gr2)|/|F(Gr1∨Gr2)|

由定義10有sim(Gr1，Gr2)= |F(Gr1∧Gr2)|/|F(Gr1∨Gr2)|，顯然，sim(Gr1，Gr2)+GDU(Gr1，Gr2)=1。

性質(zhì)5說明，粒的相對距離與粒的相似度滿足嚴格的互補關系。

例2 計算例1中粒Gr1與Gr2的絕對距離、相似度及相對距離。

由例1計算得Gr1∨Gr2=(Ψ3，h(Ψ3))。其中Ψ3=(c)>0，Gr1∧Gr2=(Ψ4，h(Ψ4))。其中Ψ4=0<(a)<3∧(b)∧(c)=1。

GD(Gr1，Gr2)=(|F(Gr1∨Gr2)|-|F(Gr1∧Gr2)|)/|U|=

(|{x2，x3，x4，x5，x6}|-|{x6}|)/|U|=2/3

GDU(Gr1，Gr2)=GD(Gr1，Gr2)/Cov(Gr1，Gr2)=

((|F(Gr1∨Gr2)|-F(Gr1∧Gr2)|)/|U|)/(|F(Gr1∨Gr2)| /|U|)=

(|{x2，x3，x4，x5，x6}|-|{x6}|)/|{x2，x3，x4，x5，x6}|=

4/5 sim (Gr1，Gr2)=|F(Gr1∧Gr2)|/|F(Gr1∨Gr2)|=

|{x6}|/|{x2，x3，x4，x5，x6}|=1/5

通過上例說明，這里粒的距離考慮的是從粒的語法上去計算，而通常的知識距離計算都只從粒的語義上考慮，即兩個粒之間最大相同對象與最大包容對象的比值，但只從語義上計算的距離顯然并不能很準確地表示粒之間的差異程度。例如兩個語法完全不同的粒但卻可能包含有相同對象，這些對象意義可能完全不同。本文所提出的粒的距離無論從語法還是語義上都是符合邏輯的。同時上例也說明本文提出的相似度與絕對距離是嚴格互補的，類似的方法容易驗證定理3距離的直線定理的正確性。

4 粒的距離的應用

粒的距離不僅度量了兩個粒之間的差異程度，在信息系統(tǒng)S=(U，A，V，f)中，設γ=(ω，U)為論域粒，顯然，若把論域粒看做系統(tǒng)中最粗的粒，則任意粒與論域粒之間的距離反映了該粒的粗細程度。則粒Gr的粗細程度可以用Gr與γ的距離來度量。Gr與γ的距離越大說明粒Gr越細，Gr與γ的距離越小說明粒Gr越粗。

定義13 在信息系統(tǒng)S=(U，A，V，f)中，粒Gr=(Ψ，h(Ψ))的粒熵GEr(Gr)定義為Er(Gr)= GD (Gr，γ)= (|F(Gr∨γ)|-|F(Gr∧γ)|)/|U|=1- |F(Gr)|/|U|。其中γ=(ω，U)為該論域粒。

由上面理論可知，概念粒的距離不僅度量了在同一論域下粒之間的差異程度，而且在存在序關系的粒之間，其距離顯然能刻畫出粒中因某個原子式的變化導致粒粗細變化的程度。例如在信息系統(tǒng)S=(U，A，V，f)中，將原子粒Gr=(aM，h(aM))的原子式aM中的M去掉一個取值v(v∈M)后，得到一個新的概念粒Gr′=(aM-v，h(aM-v))，Gr與Gr′的距離度量了因粒Gr的原子式變化所導致粒的變化程度，因此可以用這個距離度量某個屬性取值v對粒Gr的重要度，距離越大，認為v對Gr越重要。

定義14 在信息系統(tǒng)S=(U，A，V，f)中，對于原子粒Gr=(aM，h(aM))，a∈A，MVa，v∈M，屬性取值v的重要度表示為sigGr(av)=GD(Gr，Gr′)/ Er(Gr)。其中Gr′=(aM-v，h(aM-v))。

由定義14可得以下性質(zhì):

性質(zhì)7 0≤sigGr(av)≤1。

性質(zhì)8 屬性取值v對原子粒Gr是必要的當且僅當sigGr(av)>0。定理4 在信息系統(tǒng)S=(U，A，V，f)中，對于原子粒Gr=(aM，h(aM))，a∈A，MVa，v∈M，sigGC(av)=0的充分必要條件是h(aM)=h(aM-v)

證明 a)充分性。由于sigGC(av)=0，根據(jù)屬性取值v重要度的定義則有GD(Gr， Gr′) =0，即| h(aM)-h(aM-v)|/|U|=0，所以h(aM)=h(aM-v)。

b)必要性。根據(jù)屬性取值v重要度的定義，顯然成立。

定理4表明粒作為一個完整的結(jié)構體，像粗糙集理論中的信息系統(tǒng)一樣可能存在冗余信息，實際應用中簡潔完備的粒結(jié)構對一個智能系統(tǒng)起著極其重要的作用。在這種新的粒表示方法下，粒的約簡也將成為一個重要研究方向，在完善粒計算理論中將起著一定的作用。

5 結(jié)束語

借鑒已有軟計算理論的成果，對粒的表示方法加以改進，從而使粒更具適用性，進而定義了新表示方法下粒的幾個運算。在這幾個運算的基礎上研究了新表示方法下粒的距離及相似度，最后給出這種理論方法的應用。有待于進一步研究的是新的粒的表示方法下粒計算在知識發(fā)現(xiàn)與規(guī)則提取上的應用。

參考文獻:

[1]王國胤， 張清華， 胡軍. 粒計算研究綜述[J]. 智能系統(tǒng)學報，2007，2(6):8-26.

[2]PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Science，1982，11(5):341-356.

[3]劉清，劉群. 粒及粒計算在邏輯推理中的應用[J]. 計算機研究與發(fā)展，2004，41(4):546-551.

[4]曾毅，姚一豫，鐘寧. 基于粒結(jié)構的知識檢索[J]. 計算機科學，2008，35(3):194-224.

[5]王寶麗，梁吉業(yè). 信息系統(tǒng)中的知識距離與知識粗糙熵[J]. 計算機科學，2007，34(3):151-154.

[6]徐久成，孟慧麗，郭林鵬，等. 粗糙集的劃分貼近度及基于劃分貼近度的屬性約簡[J]. 計算機科學，2008，35(83):213-215.

[7]徐久成，孟慧麗，郭林鵬. 基于劃分貼近度的不完備信息系統(tǒng)屬性約簡[J]. 計算機工程與應用，2008，32(4):163-166.

[8]CHEN Bo， SUN Ming， ZHOU Ming-tian. Granular rough theory:a representation semantics oriented theory of roughness[J]. Applied Soft Computing，2009，9(2):786-805.

[9]PAL S K， SHANKAR U B， MITRA P. Granular computing， rough entropy and object extraction[J]. Pattern Recognition Letters，2005，26(16):2509-2517.

[10]徐久成，成萬里，史進玲. 基于信息系統(tǒng)的概念粒及其距離計算[J].廣西大學學報:自然科學版，2009，34(5):667-671.