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所示。

通过上面的分析可以看到，粒度划分格与概念递阶有相通之处，即通过对论域的粒度划分构造“格”结构，再进一步分析概念，通过层次递阶来进行概念的泛化与细化。因此，在新粒计算模型中引入“格”的概念，使知识在递阶方面忽略不必要的冗余，达到更高的效率。