两种多粒度形式概念分析模型的比较研究

折延宏，胡梦婷，贺晓丽，曾望林

1.西安石油大学 理学院，西安 710065

2.西安石油大学 计算机学院，西安 710065

1 引言

形式概念分析[1]是一种进行数据分析的有效数学工具，其核心概念为形式背景、形式概念与概念格。通过概念格所展现出的概念之间的特化与泛化关系，揭示了数据表的内在结构，刻画了对象与属性之间的依赖关系。

近年来，一个有趣的研究方向是将多粒度计算的思想融入到形式概念分析之中，由此产生了不同的多粒度形式概念分析模型[2-16]。形式概念分析的粒计算方法包括形式背景的对象粒化[2]、属性粒化[3-8]、关系粒化[9-11]等，这些方法除了可以缓解庞大的概念个数之外，还可以获取数据的多层次概念知识表示与处理方法[12]。

本文主要关注的是形式概念分析的属性粒化方法。属性粒化意味着属性的合并（或提升）、分解（或细化），通过属性粒化可实现知识的粗细转换，使人们在不同粒度的形式背景上进行概念分析。Belohlavek 等人在文献[3]中提出了基于属性粒化的形式概念分析方法，在该方法中，一个属性在不同粒度下可划分为不同的子属性，利用粒度树与剪枝（cut）等主要工具可导出不同粒度层次的形式背景，基于此，实现了在不同粒度层次下对数据的分析[3-5，15]。与此不同的是，基于属性聚类的多粒度形式概念分析模型是通过属性集上的先验知识或先验关系R实现的。文献[6]通过属性集上的一等价关系实现了属性的聚类，进而研究了聚类前后概念之间的内在联系与生成方式。可以说，文献[3]与文献[6]提出的方法迥然不同，前者通过粒度树、剪枝等方法实现，后者通过对属性聚类实现。本文对这两种不同的方法进行分析对比。

2 基于属性聚类与属性粒化的形式概念分析方法

2.1 形式概念分析的基本知识

三元组(G,M,I)为一形式背景。其中G为一非空有限对象集，M为一非空有限属性集，为与M之间的一二元关系，按如下方式定义两映射↑:2G→2M与↓:2M→2G:

若X↑=Y,Y↓=X,则称(X,Y)为一形式概念，也称为Wille 概念。全体形式概念之集L(G,M,I)在如下偏序关系下构成一格，简称为概念格：

文献[17-18]通过将粗糙近似算子引入到形式概念分析之中，引入了面向对象的形式概念分析模型，其概念生成算子是按照如下方式定义的：

若X□=Y,Y⋄=X,则称(X,Y)为一形式概念，也称为面向对象概念。全体面向对象概念之集Lο(G,M,I)在如下偏序关系下构成一格，简称为概念格：

以下命题给出了如上两种不同概念的性质，这种性质在本文的后续证明中起着重要的作用。

命题1[17-18]设(G,M,I)为一形式背景，∀X⊆G,Y⊆M：

（1）(X↑↓,X↑)∈L(G,M,L),(Y↓,Y↓↑)∈L(G,M,L)

（2）(X□⋄,X□)∈Lο(G,M,L),(Y⋄,Y⋄□)∈Lο(G,M,L)

（3）X⊆X↑↓,Y∈Y↓↑

定义1 若在M1与M2之间的一一映射f:M1→M2,使得 ∀g∈G,m1∈M1,gI1m1当且仅当gI2f(m1),则称两形式背景(G,M1,I1)与(G,M2,I2)是同构的。

在一一对应关系中不区分属性的情况下，可将两同构的形式背景视为相同的。

2.2 基于属性聚类的形式概念分析方法

如文献[6，12]中所述，通常情况下，根据某个特定需求，或基于先验知识，可将形式背景中的属性集聚在一起，形成更高一级的属性。数学上，这一想法可通过属性集上的等价关系来实现。基于等价关系，可将部分属性聚合在一起形成一个新的属性，由此可导出一个新的形式背景。与原形式背景相比，对象集是相同的，但属性集发生了变化，由此可在不同层次、不同粒度下进行概念分析。

具体地，设(G,M,I)为一形式背景，R为M上的等价关系，[m]R为包含m的属性等价类。基于(G,M,I)与R，可构造如下形式背景(G,MR,IR)，其中：

注意到：[m]R虽然是由形式背景(G,M,I)中的若干属性组成的，但在形式背景(G,MR,IR)中，它只是作为一个属性。此外，IR的定义与I有着密切的联系，在新的形式背景(G,MR,IR)中，对象g与属性[m]R具有关系IR当且仅当g与该等价类中某一个属性在原形式背景中具有关系I。

在新的形式背景(G,MR,IR)中，可定义如下形式的概念生成算子：

2.3 基于属性粒化的形式概念分析方法

文献[3]提出了一种基于属性粒化的形式概念分析方法。在该方法中，原形式背景(G,M,I)中的每一个属性在不同的粒度下可分解为不同的子属性，这些不同粒度的属性形成了一粒度树，文献[3]借助粒度树以及粒度树中的剪枝方法，从原背景出发导出了不同粒度的形式背景，为在不同粒度下进行概念分析提供了一个可能的框架。

定义2[3]设K=(G,M,I) 为一形式背景，m∈M。属性m的粒度树Tm是满足如下条件的一个含有根节点的树：

（l）树中的每一个节点都用一个属性名称来标记，根节点记作m；

（2）对于每一个节点z，赋予一对象集合{z}↓⊆G,该对象集{z}↓由具有属性z的对象所构成；

（3）若z1,z2,…,zn是节点z的子节点，则 {{z1}↓,{z2}↓,…,{zn}↓}是 {z}↓的一个划分。

为方便起见，往往用z↓，而不用{z}↓，其含义是不变的。

定义3[3]粒度树Tm中的一剪枝（原文称之为cut）C是满足如下条件的一节点集：对于每一个叶节点u而言，在从u到根节点m的路径上，存在唯一的节点v属于C。

例1 表1给出了一基于属性粒化的形式背景，在该表中，属性G具有两层粒度，图1给出了粒度树TG中的所有剪枝，即{G}与{IG,dG}。注意到C={G,dG}并不是粒度树TG的一剪枝，其原因在于从叶节点dG到根节点G的路径上，存在两个节点属于C。同理，{G,IG}也不是一剪枝。

表1 基于属性粒化的形式背景

图1 表1中的粒度树以及剪枝∀z ∈MC,(g,m)∈IC ⇔g ∈m↓

由定义2、定义3 以及例1 可见，每一个属性都有唯一的粒度树，但每一个粒度树上有不同的剪枝。在同一属性粒度Tm的剪枝集上定义如下偏序关系：C1={y1,y2,…,yr},C2={z1,z2,…,zs}∈Tm,C1≤C2当且仅当是的细化，即=是通过对中每个集合进一步划分后得到的。

设(G,M,I)为一形式背景，对于每一个属性m∈M而言，Tm为其粒度树，Cm是Tm上的一剪枝，不同属性粒度树上的剪枝可导出如下一形式背景(G,MC,IC)，其中。

在每个属性的粒度树上任意选取一剪枝，所有这些剪枝之集C代表了特定的属性粒化层次（Granularity Level）。对于任意两属性粒化层次C1与C2，用C1≤C2表示 ∀m∈M，C1m≤C2m,这里C1m与C2m分别表示属性m在两粒化层次中的剪枝。换言之，C1是C2的细化。由此，可在不同的粒化层次上进行概念分析。

在新的形式背景(G,MC,IC)中，可定义如下形式的概念生成算子：

为以下讨论方便，引入如下记号：设C1、C2为满足C1≤C2的两剪枝，对于用表示m1在中的父节点，用表示中的子节点集。

3 不同多粒度方法的比较研究

3.1 Wille概念模型框架内两方法的比较研究

由上文的介绍可以看得出，基于属性粒化与基于属性聚类的多粒度形式概念分析方法有着较为显著的差异，本节进一步分析两者的区别与内在联系。

定理1 设(G,M,I)为一形式背景，R为M上的一等价关系，则对于任意(A,B)∈L(G,MR,IR),存在(Ak,Bk)∈L(G,M,I)(k∈K)使得A=∪i∈K Ak。

证明对于(A,B)∈L(G,MR,IR)，以下分两种情形进行证明。

情形1B≠∅：此时不妨设B={[y1]R,[y2]R,…,[yn]R}。任意(m1,m2,…,mn)∈[y1]R×[y2]R×…×[yn]R,令(Ak,Bk)=({m1,m2,…,mn}↓，{m1,m2,…,mn}↓↑)。以下证明 (Ak,Bk)为满足条件的形式概念。

事实上，由命题1 知(Ak,Bk)∈L(G,M,I)。以下证明A=∪Ak。首先证明∪Ak⊆A。对于任意对象g∈G,若g∈∪Ak,即存在 (m1,m2,…,mn)∈[y1]R×[y2]R×…×[yn]R使得g∈{m1,m2,…,mn}↓,由式（2）知g同时具有属性m1,m2,…,mn,结合式（6）知g同时具有形式背景中的属性 [y1]R,[y2]R,…,[yn]R,因此，g∈B↓R={[y1]R,[y2]R,…,[yn]R}↓R,即g∈A。反过来，任取g∈A,由A=B↓R={[y1]R,[y2]R,…,[yn]R}↓R知g同时具有 (G,MR,LR)中属性[y1]R,[y2]R,…,[yn]R，由式（6）知必存在 (m1,m2,…,mn)∈[y1]R×[y2]R× … ×[yn]R使得gImi,i=1,2,…,n,因此，g ∈{m1,m2,…,mn}↓,即g属于某一Ak。综上A=∪i∈K Ak。

情形2B=∅：此时易知A=G,对于G中每个对象g而言，({g}↑↓,{g}↑)属于L(G,M,I)，且g∈{g}↑↓（命题1），因此G=∪g∈G{g}↑↓,得证。

以下将说明文献[3]的概念分解定理可看作定理1的特殊情形。首先注意到如下事实成立：在文献[3]中，C1≤C2意味着中每一属性都在中存在划分子属性，即使得从属性聚类的角度看，可看作是原背景，通过将中每个属性的划分子属性聚为一类，便可得到形式背景

两种不同背景下的概念分析算子有着密切的联系，这由如下命题可以看得出。

命题2 设(G,M,I)为一形式背景，C1、C2为两剪枝且C1≤C2,在上定义二元关系则：

（1）R为上的一等价关系；

（3）在同构意义下，∀X⊆G,X↑C2=X↑R。

证明（1）容易验证R满足自反性、对称性以及传递性，因此R为一等价关系。

（2）定 义 映 射容易验证f为一映射，在不区分m与f(m)的前提下，以下证明事实上，对于G中任意对象g以及中属性m2，若，由于中属性是中相应属性的划分，因此存在中属性z1使得，根据式（6）得故反过来，若由式（6）知存在[z]R中某一属性z1使得，对于z1，必然存在中一父节点z2使得，由于与存在一一对应关系，在将[z]R与z2不加以区分的情况下，便有得证。

（3）由（2）可立即推得。

由命题2可得如下推论。

推论1 若C1≤C2,则对于任一形式概念∈存在形式概念集k∈K使得 ∪k∈K Ak=A。

证明若C1≤C2,由命题2 知形式背景可看作是对形式背景进行属性聚类后得到的形式背景，则由定理1知结论成立。

注意到推论1 正是文献[3]所述的分解定理。综合以上结论，文献[3]给出的基于属性粒化的形式概念分析模型是本文提出的基于属性聚类概念分析模型的特殊情形。

3.2 面向对象概念分析模型中两种方法的比较

文献[15]在多粒度形式背景中研究了面向对象的形式概念，将已有的面向对象概念由单粒度拓展至多粒度情形，研究了在不同粒度下，面向对象概念之间的内在联系，证明了在不同粗细粒度下外延集相等的充分必要条件。

设(G,M,I)为一形式背景，对于任意属性m∈M,有一粒度树Tm,CM为Tm上一剪枝，不同粒度树的剪枝（每个粒度树上任意挑选一个剪枝）集可按之前的方式生成一形式背景(G,MC,IC),利用面向对象的概念生成算子（3）以及（4）可在不同的粒度下生成不同的面向对象概念格。本文用Lο(G,MC,IC)以及EXT(Lο(G,MC,IC))分别表示由形式背景(G,MC,IC)所生成的面向对象概念格以及外延集。

文献中主要结论如下：

命题3[15]若C1≤C2,则

命题4[15]若C1≤C2,则

事实上，利用属性聚类方法，可将文献[15]中的面向对象的多粒度形式概念分析模型推广至更为一般的情形。

定义4 设(G,M,I)为一形式背景，R为M上的一等价关系，(G,MR,IR)为其粒化后形式背景，X⊆G,Z⊆MR,若X□R=Z且Z⋄R=X,则称 (X,Z)为 (G,MR,IR)中一面向对象的概念。

命题5 设(G,M,I)为一形式背景，R为M上的一等价关系，则EXT(Lο(G,MR,IR))⊂EXT(Lο(G,M,I))。

证明任取X∈EXT(Lο(G,MR,IR)),根据定义，存在Y ⊆MR使 (X,Y)∈Lο(G,MR,IR),即X□R=Y且Y⋄R=X。要证明X∈EXT(Lο(G,M,I)),等价于证明 (X,X□)∈L(G,M,I),或等价地，X□⋄=X。任取g∈X⋄R,由式（4）知，存在属性m∈X□使得gIm，结合式（3）便知g∈X。反过来，任取g∈X，由Y⋄R=X知g∈Y⋄R,则存在[m]∈Y使gIR[m] ，结合IR的定义（即式（6））知存在m1∈[m]R使gIm1。以下说明m1∈X□,事实上，对于任意满足gIm1的对象g而言，由gIR[m1]=gIR[m] 以及[m]∈Y，X□R=Y知g∈X,从而根据式（3）可得m1∈X□。再结合gIm1以及式（4）便知g∈X□⋄。

命题6 设(G,M,I)为一形式背景，R为M上的一等价关系，则对于任意X⊆G,X□R⊆X□,{[m]R|m∈X⋄}⊆X⋄R。

证明任取y∈X□R，则存在X□R中一等价类[m]R使得y∈[m]R。对于满足gIy的任意对象g而言，gIR[m]R成立，结合[m]R∈X□R便知g∈X，因此 ∪X□R⊆X□。

任取 [y]R∈{[m]R|m∈X⋄} ，由g∈X⋄以及（4）知存在X中一对象g使得gIy，从而gIR[y]R，结合g∈X便知[y]R∈X⋄R，从而 {[m]R|m∈X⋄}⊆X⋄R。

命题7 设(G,M,I)为一形式背景，R为M上的一等价关系，则EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR)),当且仅当对于任一等价类[m]R∈MR，存在Z⊆MR，使得对于任意。

证明充分性：对于形式背景(G,M,I)而言，由命题1知，对于任一外延X∈EXT(L(G,M,I))而言，存在Y⊆M使得X=∪mi∈Y y↓，又由题设条件知对于每一个属性mi,存在Z⊆MR,使得对于任意，这样，由命题1知X也属于EXT(L(G,MR,IR))。结合命题5便知EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR))。

必要性：若EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR))，则对于EXT(Lο(G,M,I))中任一外延X,X也一定属于EXT(Lο(G,MR,IR))，由命题1便知该结论成立。

事实上，类似于命题2，可以证明基于属性粒化的面向对象概念分析模型可看作为基于属性聚类的面向对象概念分析的特殊情形。

命题8 设(G,M,I)为一形式背景，C1、C2为两剪枝且C1≤C2,在上定义二元关系，则：

（1）R为上的一等价关系；

证明可类似于命题2得证。

命题8告诉人们，对于属性粒化中的两剪枝C1、C2而言，若C1≤C2，则C2可看作是经过对C1中的属性聚类得到的，两种方法得到的面向对象概念近似算子是相等的。由命题8知，命题3可看作为命题5的特殊情形，命题7所得结论要比命题4更具一般性。

4 结束语

本文对多粒度形式概念分析中的两种不同方法进行了分析对比，指出基于属性粒化的方法可看作是已有的基于属性聚类方法的特殊情形。下一步，可基于属性聚类的方法设计有效的概念生成算法，也可以研究基于属性聚类的多尺度信息表的规则提取方法。