2.2 粒度劃分格

2.2.1 格論基礎

定義2-1 設A是一個集合，如果A上有一個關系R，對于x,y,z∈A，滿足如下條件。

①自反性：xRx。

②反對稱性：xRy,yRxx=y。

③傳遞性：xRy,yRzxRz。

則稱R是A上的一個偏序關系，記作“≤”，則序偶<A,≤>稱為偏序集。

定義2-2 設<A,≤>為偏序集且BA為一個子集，a∈A。如果對B的任意元素x，都滿足x≤a，則稱a為子集B的一個上界。反之，如果對B的任意元素x，都滿足a≤x，則稱a為子集B的一個下界。

定義2-3 設<A,≤>為偏序集且BA為一個子集，a為B的一個上界，且對于B的任意上界y均有a≤y，則稱a為B的最小上界或上確界（supremum），記作sup(B)。反之，若b為B的一個下界，且對于B的任意下界z均有z≤b，則稱b為B的最大下界或下確界（infimum），記作inf(B)。

定義2-4 設<A,≤>為偏序集，如果A中任意2個元素都有上確界和下確界，則稱<A,≤>為格。

定義2-5 設<A,≤>是一個格，如果在A上定義2個二元運算∧和∨，使對于任意的a,b∈A，a∨b等于a和b的上確界，a∧b等于a和b的下確界，那么格<A,≤>往往記為<A,∨,∧>，這是一個含有2個二元運算的代數系統，其中，二元運算∧和∨分別稱為并運算和交運算。

2.2.2 劃分和劃分布爾格的粒度化

對論域U的粒度變化可基于等價關系或劃分來定義，假設RU×U表示U上的等價關系，其中，×代表集合的笛卡爾積，即R是自反、對稱、傳遞的，等價關系R將U劃分為一系列不相交的子集，稱為對U的空間劃分，記作。劃分中的子集叫作等價類。相應地，給定論域的劃分π，定義等價關系Rπ：和y在π劃分的同一等價類中。

根據劃分與等價的一對一關系，可以等價地使用其中任意一個。對U的所有劃分組成的集合上定義一個順序關系，如劃分π1比另一個劃分π2更細或劃分π2比另一個劃分π1更粗糙，記作π1≤π2。如果π1的每一個等價類都包含π2的某一個等價類，那么在等價關系里可表示為。

≤是半序的，即滿足自反性、非對稱性、傳遞性。給定2個劃分π1和π2，它們的合取π1∧π2是比π1、π2都細的最大劃分，它們的析取π1∨π2是比π1、π2都粗糙的最細劃分。因此，合取的等價類是π1和π2等價類的非空交集，而析取的等價類恰好是π1和π2等價類的最小子集。

定理2-1 論域U上的所有劃分Π(U)在偏序關系≤下構成劃分格。

證明 要證明定理2-1，即證明π1,π2,π3∈Π(U)，滿足以下條件。

①冪等律：π1∧π2=π1,π1∨π1=π1。

②交換律：π1∧π2=π2∧π1,π1∨π2=π2∨π1。

③結合律：(π1∧π2)∧π3=π1∧(π2∧π3)；(π1∨π2)∨π3=π1∨(π2∨π3)。

④吸收律：π1∨(π1∧π2)=π1；π1∧(π∨π2)=π1。

下面依次給予證明。

①冪等律可由定義直接證明，故在此可省略。

②由于Π(U)中的任意2個元素的最大上界和最小下界與順序無關，因此交換律得證。

③(π1∧π2)∧π3≤π3，且(π1∧π2)∧π3≤(π1∧π2)≤π2，所以有(π1∧π2)∧π3≤π1∧(π2≤π3)，同理得到π1∧(π2∧π3)≤(π1∧π2)∧π3。故有π1∧(π2∧π3)=(π1∧π2)∧π3。同理可證得π1∨(π2∨π3)=(π1∨π2)∨π3。由此結合律得證。

④π1≤(π1∨π2),π1≤π1，故有π1≤π1∧(π1∨π2)，又因為π1∧(π1∨π2)≤π1，故有π1∨(π1∧π2)=π1。同理可證得π1∧(π1∨π2)=π1。由此吸收律得證。下面討論粒度劃分格的一些性質。

對π1,π2,π3∈Π(U)，有以下關系成立。

①若π2≤π3，則π1∧π2≤π1∧π3，π1∨π2≤π1∨π3。

②若π1≤π2，π3≤π4，則π1∨π3≤π2∨π4，π1∧π3≤π2∧π4；

若π1≤π2≤π3，且π3∧π4=π1，則π2∧π4=π1；

若π1≥π2≥π3，且π3∨π4=π1，則π2∨π4=π1。

③π1,π2,π3∈Π(U)，若π3≤π1，則π1∧(π2∨π3)≤π3∨(π1∧π2)。

2.2.3 信息的粒度劃分格與概念遞階

定義2-6 信息系統由一個三元組(U,D,R)表示，其中，U是對象的集合，D是屬性的集合，R是U和D之間的二元關系。對于x∈U，若x具有屬性y，那么x與y是有關的，記為xRy。與對象x∈U相關的屬性可表示為

同理，擁有屬性y∈D的對象可表示為

在對象集合U的冪集P(U)和屬性集合D的冪集P(D)之間可以建立對象與屬性之間的聯系。與對象集合X相關的屬性集合為

擁有屬性集合Y的對象表示為

基于對象與屬性間的聯系來定義概念。

定義2-7 對于X*∈P(U)，Y*∈P(D)，如果X和Y滿足(X,Y)=(Y*,X*)，則稱(X,Y)是一個概念。其中，X是概念的外延，用Ex(X,Y)表示；Y是概念的內涵，用In(X,Y)表示。設所有概念的集合用L(k)表示，在L(k)中的元素間可以建立一種偏序關系≤。給定L(k)中的2個概念H1=(X1,Y1)和H2=(X2,Y2)，若有

則由該偏序關系誘導出的L(k)也是一個格結構。

根據粒度化概念的分析可以看到，概念描述事實上與粒計算的概念描述是等價的。也就是說，在分析概念時，都是由對象與屬性之間的關系來確定的。概念的構成定義為(X,Y)=(Y*,X*)，而粒度劃分的DL語言在描述概念時所使用的形式為m(φ)。事實上，m(φ)對應于Ex(X,Y)，φ對應于In(X,Y)。這樣，(X,Y)就可以等價表示為m(φ)。

令屬性a∈D在對象x∈U上的取值為a(x)，擴展屬性子集AD，A(x)表示x在屬性集合A上的取值，這可以看作a(x)的一個向量，a∈A作為其中一個元素。對于a∈A，一個等價關系Ra可以這樣給定，即對于x,y∈U，有。

在單屬性的情況下，2個對象被視為無差別的前提是當且僅當它們擁有相同的值。屬性子集A∈D的等價關系RA定義為

對于屬性集合A，2個對象x、y無差別的前提是當且僅當對A中的每一個屬性它們都擁有相同的值。

空集Φ產生最粗糙的關系，即RΦ=U×Ua。若應用整個屬性集，則產生最優關系RD。進一步，若沒有2個對象有相同的描述，RD就變為同一關系，代數({RA}A∈D}就是一個擁有零元素RD的更低半格。

等價關系的定義是將一個概念的精確描述與每個等價類聯系起來。在DL語言中，給定一個原子公式a=v（其中a∈D）。若φ,ψ是公式，那么都是公式。模型是一個信息表，它提供對符號和DL公式的解釋。對象x對公式φ的滿意度記為x|=φ，并給出以下結論。

若φ為公式，那么集合m(φ)定義為

式(2.6)稱作公式φ的意義。對RA的等價類可以用這種形式表示：∧a∈Aa=va。進一步，，其中，a(x)為x在屬性a上的值。

基于上述概念以及等價類與粒度劃分格的關系，在進行概念的粒度劃分時都是根據不同的屬性基數或對象基數來進行的。也就是說，不同層次的概念所包含的信息量不同。根據信息量的不同對論域進行粒度劃分。因此，概念與粒度劃分都是基于（對象,屬性）對來進行描述的。也就是說，在研究粒度劃分的過程中，可以根據格的構建過程來進行概念的粗化與細化。

根據粒度化的細度，定義粒度化的分層遞階結構。設π0≤π1≤…≤πn是論域U上的一簇由粗到細的劃分，其中，π0表示論域本身，即最粗的劃分，πn表示x,y∈U，，即最細的劃分，如圖2-1所示。

令Le1,Le2,…,Len分別表示第一層、第二層到第n層，對于任意概念H1x∈Le1,H2y∈Le2,…,Hnz∈Len，有H1x≤H2y≤…≤Hnz（其中，1x、2y表示各層的序號）。可以看出，粒度劃分在分層分析概念時都是基于概念結構的。這種形式的概念分析在進行概念細化（粗化）的過程中都是基于屬性的累加（減少）來實現的，即在概念的層次模型中隨著新節點的增加產生了格結構，并且通過概念的合取與析取來實現概念的泛化與細化，其結構如圖2-2所示。

通過上面的分析可以看到，粒度劃分格與概念遞階有相通之處，即通過對論域的粒度劃分構造“格”結構，再進一步分析概念，通過層次遞階來進行概念的泛化與細化。因此，在新粒計算模型中引入“格”的概念，使知識在遞階方面忽略不必要的冗余，達到更高的效率。