面向属性（对象）多粒度概念格之间的关系*

杨 涵，秦克云

西南交通大学 数学学院，成都610000

1 引言

1982年，德国数学家Wille 提出了形式概念分析理论[1]（formal concept analysis，FCA），也称概念格理论。该理论是根据数据集中对象与属性之间的二元关系建立的一种概念层次结构，它反映了形式概念之间的泛化和专业化的关系。作为知识描述和总结的有用工具，概念格理论已广泛应用于知识工程、机器学习、模式识别、专家系统、决策分析、数据挖掘等领域。

面向属性的概念和面向对象的概念是形式概念的两个重要扩展。在Wille 概念格的基础上，Duntsch和Gediga[2]引入了一对近似模态算子构造了面向属性的概念格。它提供了关于经典形式概念分析的推导算子的补充数据视图。Yao[3-4]介绍了面向对象概念格的概念，并比较了不同概念格在数据分析中的作用。Wan 等[5]提出了一些基于属性集和对象集的近似概念获取方法。还讨论了近似概念、属性导向概念和面向对象概念之间的关系。此外，近年来已经提出了一些测量模糊形式概念之间相似程度的相似性[6-8]。这些相似性度量可用于分解相关的概念格，并构建因子格[9-10]。此外，已经做了许多努力来比较和组合形式概念分析和粗糙集理论。指出形式概念分析的推导算子是极性或模态逻辑中使用的充分运算符，粗糙集近似算子[11]实际上是模态逻辑中运算符的必要性和可能性[2-3]。因此，形式概念分析侧重于可以通过属性的连接来定义的概念，而粗糙集理论则侧重于可以通过属性的分离来定义的概念[3,12]。它们为数据分析提供相关和互补的方法。模态式算子的表述使能够更深入地了解粗糙集和形式概念分析的理论。

最近，受粗糙集中多粒度标记信息系统研究的启发[13-15]，多粒度计算越来越受到研究人员的关注。Qian 等[16]考虑了多个二元关系并提出了多粒度粗糙集模型MGRS（multi-granulation rough sets），其中目标概念被描述为一个整体上的多个二元关系。另外有人提出了MGRS 的一些扩展[17-18]。Li等[19]通过规则获取研究了多粒度粗糙集与概念格之间的关系，指出悲观多粒度粗糙集中的“AND”决策规则是概念格中的粒度规则。概念格中的非冗余析取规则是乐观多粒度粗糙集中“OR”决策规则的真实部分的多重组合。郝晨等[20]考虑了包含一个属性的多粒度标记形式背景。Xie 等[21]把多粒度标记信息系统直接理解成多粒度标记多值形式背景，在此基础上讨论了关联规则挖掘问题。李金海等[22]提出了形式概念分析的多粒度标记理论，通过正向尺度化和反向尺度化方法，研究信息系统与形式背景之间的相互转化关系，利用经典形式背景给出多粒度标记形式背景的定义，证明多粒度标记形式背景与多粒度标记信息系统在语义上等价。对于多粒度标记形式背景，不同粒度标记下的蕴涵规则之间可以相互推理。

本文基于多粒度形式背景，讨论了不同粒度下的极值算子之间的关系，以此研究了不同粒度的面向属性的概念格之间的关系，并提出了相关概念格的生成方法。再利用面向属性的概念格和面向对象的概念格之间的互补关系，得到了不同粒度的面向对象的概念格之间的关系。

2 预备知识

本章回顾形式概念分析中的一些基本概念和性质。

定义1[1]一个形式背景是一个三元组(G,M,I)，其中G={g1,g2,…,gn}为对象集，M={m1,m2,…,ml}为属性集，I为G和M之间的二元关系，I⊆G×M。若(g,m)∈I，则表示对象g具有属性m，或者属性m由对象g拥有，记具有m的所有对象组成的集合为Im。

对于形式背景(G,M,I)，在对象集X⊆G和属性集A⊆M上分别定义运算：

也就是说，X↑是X中所有对象拥有的最大属性集，A↓是A中具有所有属性的最大对象集。若X↑=A且A↓=X，则称二元组(X,A)为一个形式概念（简称概念），其中X称为形式概念的外延，A称为形式概念的内涵。(G,M,I)中的所有形式概念组成的集合构成一个格，称为概念格，记作L(G,M,I)，它的上下确界和序关系为：

为了方便起见，对∀g∈G，m∈M，{g}↑记为g↑，{m}↓记为m↓。(g↑↓,g↑)和(m↓,m↓↑)可以表示所有的形式概念。

定理1[1]∀X,X1,X2⊆G,A,A1,A2⊆M，有：

定义2[2](G,M,I)是形式背景，对∀X⊆G，A⊆M，Duntsch 和Gediga 曾定义一对模态算子⋄和□：

显然，X⋄={m∈M;m↓⋂X≠∅}，A□={g∈G;g↑⊆A}。对X⊆G和A⊆M，若X⋄=A且A□=X，则称二元组(X,A)为一个面向属性的概念。(G,M,I)中的所有面向属性的概念组成的集合构成一个完备格，称为面向属性的概念格，记作LP(G,M,I)，它的上下确界和序关系为：

对∀X⊆G和A⊆M，(X⋄□,X⋄)和(A□,A□⋄)都是面向属性生成的概念。

定理2[2]∀X,X1,X2⊆G,A,A1,A2⊆M，有：

Yao 通过粗糙集理论和形式概念分析的一些比较，研究了粗糙集模型中的概念格结构和形式背景中的粗糙近似，提出了面向对象概念格的概念。

定义3[3-4](G,M,I)是形式背景，对∀X⊆G，A⊆M，考虑以下算子：

显然，X□={m∈M;m↓⊆X}，A⋄={g∈G;g↑⋂A≠∅}。对X⊆G和A⊆M，若X□=A且A⋄=X，则称二元组(X,A)为一个面向对象的概念。(G,M,I)中的所有面向对象的概念组成的集合构成一个完备格，称为面向对象的概念格，记作LO(G,M,I)，它的上下确界和序关系为：

对∀X⊆G和A⊆M，(X□⋄,X□)和(A⋄,A⋄□)都是面向对象生成的概念。

定理3[3-4]∀X,X1,X2⊆G,A,A1,A2⊆M，有：

李金海受粗糙集中多粒度标记信息系统研究的启发，基于经典形式背景给出了多粒度标记形式背景的形式化定义。

定义4[19]对于形式背景(G,M,I)，假设a∈M所具有的对象集为Ia。若A⊆M的任意两个属性a、b所具有的对象集满足Ia⋂Ib=∅且则称A为(G,M,I)的对象划分集。

定义5[19]设(G,A1,I1) 和(G,A2,I2) 为两个形式背景。假设a∈A1所具有的对象集为Ia，称Bin(Ia)为集合Ia的布尔向量表示。对于∀b∈A2，如果存在at∈A1（t∈Tb，Tb是指标集）使得则称b是{att∈Tb}的融合属性。

例1[19]表1 是一个形式背景(G,A1,I1)，其中G={x1,x2,x3,x4,x5,x6},A1={a1,a2,a3,a4,a5,a6}。表2 是一个形式背景(G,A2,I2)，其中G={x1,x2,x3,x4,x5,x6},A2={b1,b2,b3,b4}。

Table 1 Formal context (G,A1,I1)表1 形式背景(G,A1,I1)

可计算得Ia1={x4,x5,x6}，那么集合Ia1的布尔向量为Bin(I1a1)=(0,0,0,1,1,1)。且由表1和表2易计算得：

Table 2 Formal context (G,A2,I2)表2 形式背景(G,A2,I2)

定义6[19]设(G,A1,I1) 和(G,A2,I2) 为两个形式背景。对于∀b∈A2，如果存在at∈A1（t∈Tb，Tb是指标集）使得b是{att∈Tb}的融合属性，且A1中的每个属性均被用来融合A2中的某一属性，则称(G,A2,I2)是(G,A1,I1)的融合形式背景，记为(G,A1,I1)≺(G,A2,I2)。

直观地，(G,A1,I1)≺(G,A2,I2)表示(G,A2,I2)的每一列均通过合并(G,A1,I1)的若干列得到，这种合并关系在实际中必须借助特定的属性语义完成。

3 不同粒度形成的面向属性概念格之间的关系

设(G,A1,I1) 和(G,A2,I2) 为两个形式背景，且(G,A1,I1)≺(G,A2,I2)，本章将讨论概念格LP(G,A1,I1) 和LP(G,A2,I2)之间的联系。(G,A1,I1)、(G,A2,I2)中的算子分 别为⋄1,□1与⋄2,□2，且假设b∈A2，b由Γb={at;t∈Tb}⊆A1融合得到，其中Tb为指标集。

定理4设(G,A1,I1)≺(G,A2,I2)，对于任意的X∈G，Z⊆A2，则：

证明（1）假设b∈X⋄2，则存在x∈X使得(x,b)∈I2。由可知，存在唯一的t∈Tb使得(x,at)∈I1，从而at∈X⋄1⋂Γb，即⋂Γb≠∅。

假设b∈A2使得X⋄1⋂Γb≠∅。不妨设at∈X⋄1⋂Γb,由at∈X⋄1可知存在x∈X，使得(x,at)∈I1,再由可知(x,b)∈I2,从而由x∈X可知

（2）对于任意m∈X⋄1，因A1中任一属性均被用来融 合A2中某一属性，存在c∈A2使得m∈Γc。由X⋄1⋂Γc≠∅及（1）可得c∈X⋄2，从而

（3）设x∈G使得x∈。若a∈A1满足(x,a)∈I1，不妨设a∈Γc，则(x,c)∈I2，从而由知c∈Z,从而

定理5设(G,A1,I1)≺(G,A2,I2)，对于任意的X∈G，Z⊆A2，则：

（1）如果(X,Z)∈LP(G,A2,I2)，则

（2）Ext(LP(G,A2,I2))⊆Ext(LP(G,A1,I1)),其中：

（3）定义φP:LP(G,A2,I2)→LP(G,A1,I1)为φP((X,Z))=，则φP是一个保交单射。

证明（1）由(X,Z)∈LP(G,A2,I2)，则X,则由定理4（3），可得因此(X,

（2）由（1）显然可得。

（3）对任意(X1,Z1),(X2,Z2)∈LP(G,A2,I2)有：

由X1,X2⊆Ext(LP(G,A1,I1))可得：

即φP((X1,A1)∧(X2,A2))=φP((X1,A1))∧φP((X2,A2)),故φP是一个保交映射，显然φP是单射。 □

定理6设(G,A1,I1)≺(G,A2,I2)，对于任意的X∈G，Z⊆A2，则：

证明若∃(X,Y)∈LP(G,A1,I1) 使得Z={b;Γb⋂Y≠∅}，则由定理4（3）可得由定理4（1）可得，Z={b;Γb⋂Y≠∅}={b;Γb⋂X⋄1≠∅}=X⋄2，从 而

反之，对任意的(V,W)∈LP(G,A2,I2)，有V⋄2=W,W□2=V,于是有(V,V⋄1)∈LP(G,A1,I1)。令Z={b;Γb⋂V⋄1≠∅}，则由定理4（1）可得Z=V⋄2=W，由定理4（3）可得从而结论成立。 □

推论1LP(G,A2,I2)={(X⋄2□2,X⋄2);X∈ExtLP(G,A1,I1)}。

例2参照例1 中的形式背景。

(G,A2,I2)中生成的所有面向属性生成的概念LP(G,A2,I2)如下：

4 不同粒度形成的面向对象概念格之间的关系

设(G,A1,I1)和(G,A2,I2)为两个形式背景，且(G,A1,I1)≺(G,A2,I2)，本章将讨论概念格LO(G,A1,I1)和LO(G,A2,I2)之间的联系。

定理7设(G,A1,I1)≺(G,A2,I2)，对于任意的X∈G，Z⊆A2，则：

证明（1）设b∈A2满足Γb⊆X□1。若x∈G使得(x,b)∈I2，则存在唯一t∈Tb使得(x,at)∈I1，由at∈Γb⊆X□1可知x∈X，从而b∈X□2。

反之，设c∈X□2。对于任意at∈Γc，t∈Tc，若x∈G使得(x,at)∈I1，则(x,c)∈I2。再由c∈X□2可得x∈X，从而at∈X□1。由at的任意性可得Γc⊆X□1。

（2）设x∈G满足x∈Z⋄2，则存在b∈Z使得(x,b)∈I2,从而存在at∈Γb使得(x,at)∈I1

反之，设x∈G满足于是存在b∈Z及at∈Γb，使得(x,at)∈I1，于是(x,b)∈I2。再由b∈Z可得x∈Z⋄2。 □

定理8若(X,Z)∈LO(G,A2,I2)，则(X,X□1)∈LO(G,A1,I1)。

证明若(X,Z)∈LO(G,A2,I2)，则由X∈Ext(LO(G,A2,I2))可得(G-X)∈Ext(LP(G,A2,I2))。再由定理5（2）可得(G-X)∈Ext(LP(G,A1,I1))，从而X∈Ext(LO(G,A1,I1))，即(X,X□1)∈LO(G,A1,I1)。 □

推论2Ext(LO(G,A2,I2))⊆Ext(LO(G,A1,I1)),其中：

定理9设(G,A1,I1)≺(G,A2,I2)，对于任意的X∈G，Z⊆A2，则：

证明若

反之，对任意的(V,W)∈LO(G,A2,I2)，有V□2=W,W⋄2=V,于是有(V,V□1)∈LO(G,A1,I1)。令Z=X□2，则从而结论成立。 □

由定理9 可知，LO(G,A2,I2) 中的任一概念可由LO(G,A1,I1)中的某些概念的外延生成，即有：

推论3LO(G,A2,I2)={(X□2⋄2,X□2);X∈ExtLO(G,A1,I1)}。

例3参照例1 中的形式背景。

(G,A2,I2) 中生成的所有面向对象生成的概念LO(G,A2,I2)如下：

5 结束语

本文的主要目的是提出一种研究多粒度概念格的新方法，研究了面向属性（对象）的概念格在不同粒度下之间的关系。主要得出结论：LP(G,A2,I2)中的任一概念可由LP(G,A1,I1)中的某些概念的外延生成（LO(G,A2,I2)中的任一概念可由LO(G,A1,I1)中的某些概念的外延生成）。基于这个结果，提供了从LP(G,A1,I1)和LO(G,A1,I1)生成面向属性的概念格LP(G,A2,I2)和面向对象的概念格LO(G,A2,I2)的方法。基于本文的研究结果，可以进一步讨论Wille 概念格在不同粒度下之间的关系。