基于同构理论的三支概念格的构造方法与算法研究

钱婷 ，赵思雨 ，王军涛

（1.西安石油大学理学院,陕西西安710065；2.咸阳师范学院数学与信息科学学院,陕西咸阳712000；3.西北大学概念认知与智能研究中心,陕西西安710127）

0 引 言

为了给格理论提供一个实际应用的载体，德国数学家WILLE于1982年结合哲学中概念的定义及其层次结构，提出了形式概念分析理论[1]。近年来，形式概念分析在中医药成分分析[2]、专家系统[3]、数据挖掘以及软件工程[4]等领域得到了广泛应用，已经成为数据分析与知识发现的有效工具。

形式概念分析与其他理论相结合，产生了多种不同的概念格模型,而对这些模型的进一步研究成了学者们关注的热点。2014年,祁建军等[5]结合三支决策与形式概念分析理论提出了三支概念分析理论，此理论包括OE-概念格与AE-概念格2种模型[6-7]。随后，三支概念格的构造理论[8-9]、属性约简理论[10]、不完备形式背景的三支理论[11]等相继被提出。基于这些理论，SHIVHARE等[12]结合BAM解释了三支概念,并讨论了认知记忆如何以自然的方式进行决策。此外，LI等[13]还研究了三支概念的认知理论。

综合以往研究，笔者发现，同一形式背景下，三支概念格的结构明显较概念格复杂，而有关概念格的构造理论已有丰富的研究成果[14-16]。因此，对于三支概念格的理论研究，提出以下思考:

首先，能否直接利用已有的概念格理论研究三支概念格。目前已有不少学者从形式背景、属性特征角度研究概念格[17-18]，如智慧来等[17]基于必然属性给出了概念格中的粒描述。事实上，YU等[19]从代数的角度刻画了与三支概念格同构的结构，但并未从形式背景的角度研究同构问题。其次，能否通过刻画形式背景的特点，得到概念格与三支概念格之间的关系，特别是同构关系。

基于上述分析及思考，本文主要研究某种特殊形式背景，并讨论在此背景下概念格与OE-概念格之间的关系，进一步给出OE-概念格的构造方法。

1 基础知识

1.1 形式概念分析

定义1[20]称(G,M,I)为一个形式背景，其中G为对象集，G中每个元素称为一个对象;M为属性集，M中每个元素称为一个属性；I为G和M之间的二元关系，即I⊇G× M。若(g,m)∈I，则表示对象g拥有属性m，也记为gIm。

在对象子集X⊇G和属性子集A⊇M上定义一对对偶算子：

X*表示X中所有对象共同具有的属性集合，A*表示共同具有A中所有属性的对象集合。如果一个二元组 (X,A)满足X*=A，且A*=X，则称 (X,A)是一个形式概念，简称概念。其中，X为概念的外延，A为概念的内涵。当X={g}(A={m})时,X*={g}*=g*(A*={m}*=m*)。

性质1[20]对于形式背景(G,M,I)，有以下基本性质(∀X1,X2,X⊆G且∀B1,B2,B⊆M):

用L(G,M,I)表示形式背景(G,M,I)的全体概念，LE(G,M,I)表示所有概念外延构成的集合。在偏 序关系(X1,A1)≤(X2,A2)⇔X1⊇X2(A1⊇ A2)下，可以证明

也是概念，从而L(G,M,I)是格，并且是完备格，称其为形式背景(G,M,I)的概念格(文中称为经典概念格)。

定义 2[20]设K1=(G,M,I)，K2=(H,N,J)是 2个形式背景。α,β分别为G到H，M到N的双射。若 gIm⇔α(g)Jβ(m)，则称 K1与 K2是同构的。

基于上述定义,有

定理1[20]同构的形式背景相应的概念格是同构的。

定义3[20]设(G,M,I)为形式背景，对于任意对象 g,h，若 g*=h*⇒g=h，且对于任意属性 m,n，若m*=n*⇒m=n，则称形式背景(G,M,I)为净化形式背景。

事实上，本文所涉及的净化形式背景可以弱化为只针对属性净化。

1.2 三支概念格

结合形式概念分析与三支决策的思想，QI等[6-7]提出了三支概念分析。首先，给出集合间的运算规律。

设G是一个非空有限集合，ℙ(G)是G的幂集，ℙ(G)=ℙ(G)×ℙ(G)。对于(X,Y),(Z,W)∈ℙ(G)，定义

与形式概念分析不同的是，三支概念分析不仅考虑原背景上“共同拥有”的信息，也进一步考虑了补背景上“共同不拥有”的信息。针对“共同不拥有”的信息，QI等[6-7]提出以下算子。

定义4[6-7]设(G,M,I)是一个形式背景，X⊆G,A⊆M，负算子定义如下:

相对于上述负算子，QI等[6-7]称原背景上的*算子为正算子，并将形式背景的正算子与负算子相结合，给出了三支算子的定义与性质。

定义5[6-7]设(G,M,I)是一个形式背景，X,Y⊆G,A,B⊆M，一对由对象导出的三支算子定义如下:

性质2[6-7]对象导出的三支算子有以下性质:

基于上述算子，得到了OE-概念及OE-概念格。

定义6[6-7]设(G,M,I)是一个形式背景，X⊆G，A,B⊆M。若X⊲=(A,B)且(A,B)⊳=X，则称(X,(A,B))为由对象导出的三支概念，简称OE-概念。其中X为(X,(A,B))的外延，(A,B)为OE-概念的内涵。

记所有OE-概念外延构成的集合为OELE(G,M,I)，所有OE-概念构成的集合为OEL(G,M,I)。在偏序关系(X1,(A1,B1))≤(X2,(A2,B2))(A2,B2)⊆(A1,B1)X1⊆X2下，OEL(G,M,I)构成完备格。

2 三支概念格与概念格的同构关系

以下研究在何种形式背景下，三支概念格与概念格是同构的。首先研究形式背景中关系特殊的一对属性。

定义7设(G,M,I)为形式背景，a∈M。若存在b∈M，有a*∩b*=∅ 且a*∪b*=G，则称b为a的对偶属性。

由上述定义，易得

性质3设(G,M,I)为形式背景，a,b,c∈M，

(1)若b为a的对偶属性，则a也为b的对偶属性;

(2)若b,c均为a的对偶属性，则b*=c*。

下面通过具体例子说明对偶属性的特征。

例1设(G,M,I)为形式背景，G={1,2,3}，M={a,b,c,d}，I的关系如表1所示。由定义7知，属性c为属性b的对偶属性。

表1 形式背景（G，M，I）Table 1 The formal context（G，M，I）

基于上述对偶属性，下面给出一种特殊的形式背景。

定义8设(G,M,I)为形式背景，若对于任意a∈M，均存在对偶属性，则称(G,M,I)为属性对偶背景。

例2(续例1) 形式背景如表1所示。由定义7知，a的对偶属性为d，b的对偶属性为c，c的对偶属性为b，d的对偶属性为a。故由定义8知，(G,M,I)为属性对偶背景。

下面讨论属性对偶背景的性质。

定理2若(G,M,I)为净化的属性对偶背景，则|M|为偶数。

证明因为(G,M,I)为属性对偶背景，所以对于任意的a∈M均存在对偶属性。下证对偶属性唯一。

若b，c均为a的对偶属性，显然b*=c*，此与(G,M,I)为净化背景矛盾。因此，对于任意的a∈M，有且仅有一个对偶属性，从而属性成对存在，故|M|为偶数。

证毕。

定理3若(G,M,I)为净化的属性对偶背景，则L(G,M,I)≅L(G,M,IC)，其中IC=G×MI。

证明定义α:G→G，对于任意g∈G，α(g)=g。β:M→M，对于任意m∈M,β(m)=m̂,其中m̂为m的对偶属性。显然α为双射。由于(G,M,I)为净化的对偶背景，由定理2知，对于任意m∈M，m̂存在且唯一，所以β也为双射。

若gIm，则g∈m*。由m̂是m的对偶属性知，m*∪m̂*=G且m*∩m̂*=∅，从 而m*=Gm̂*; 同时，由IC=G×MI知,Gm̂*=m̂-*, 所以m*=m̂-*。因此g∈m̂-*，即gIC m̂。

因为g=α(g)，m̂=β(m)，所以α(g)ICβ(m)。同理可得,若α(g)ICβ(m)，则gIm。

综 上 ，gIm⇔α(g)ICβ(m)。 则 由 定 义 2 知 ，(G,M,I)≅(G,M,IC)，又 由 定 理 1 可 得 ，L(G,M,I)≅L(G,M,I C)。

证毕。

定理4若(G,M,I)为净化的属性对偶背景，则L(G,M,I)≅OEL(G,M,I)。

证明由定理3知，L(G,M,I)≅L(G,M,IC)，且由证明过程知，若m与m̂为对偶属性,则m*=m̂-*。

由 于 (X,A)∈L(G,M,I)，则 (X,(A,X-*))∈OEL(G,M,I)，即L E(G,M,I)⊆OELE(G,M,I)。下证 OELE(G,M,I)⊆L E(G,M,I)。

设(X,(A,B))∈OELE(G,M,I)，由三支概念的定 义 知 ，X*=A，X-*=B且A*∩B-*=X。 由L E(G,M,I)=L E(G,M,IC)知，B-*∈L E(G,M,IC)，则B-*∈L E(G,M,I)。由于外延具有保交性，所以A*∩B-*∈L E(G,M,I)，即X∈L E(G,M,I)。 故OELE(G,M,I)⊆L E(G,M,I)。

综 上 ，L E(G,M,I)=OELE(G,M,I)。 从 而L(G,M,I)≅OEL(G,M,I)。

证毕。

例3(续例1) 表1中，(G,M,I)为净化的属性对偶背景。L(G,M,I),L(G,M,IC)及OEL(G,M,I)分别如图1～图3所示。3个格图清晰地展示了3个格之间的同构关系。

思考当(G,M,I)不是净化的对偶背景时，L(G,M,I)与OEL(G,M,I)的同构关系是否存在？

事实上，若(G,M,I)是对偶背景但不是净化背景，即对于a∈M，存在多个对偶属性，假设存在2个对偶属性b,c,由性质3，易知b*=c*。则根据约简的性质可知，在构造格时，c可看作可约属性，进而可将原背景化为净化的对偶背景。由此可以将定理3和定理4简化为定理5。

图2 L（G，M，IC）Fig.2 L（G，M，IC）

图3 OEL（G，M，I）Fig.3 OEL（G，M，I）

定理5若(G,M,I)为属性对偶背景，则L(G,M,I)≅L(G,M,IC)且L(G,M,I)≅OEL(G,M,I)。

进一步，当(G,M,I)不是对偶背景，即当某一属性a∈M不存在对偶属性时，L(G,M,I)与OEL(G,M,I)的同构关系是否存在？由此，进一步研究形式背景属性特征。

定义9设(G,M,I)为形式背景，a∈M，若存在ai∈M(i=1,2, …,t)，t≤|M|，使得Ga*=∩a*i, 则称a为对偶可交属性。

注1对偶属性可以看成特殊的对偶可交属性。

下面通过例子研究对偶可交属性的特点。

例4设(G,M,I)为形式背景，G={1,2,3}，M={a,b,c,d,e}，I的关系如表2所示。由定义9知,Ga*=2=b*∩c*，故a为对偶可交属性。

表2 形式背景（G，M，I）Table 2 T he formal context（G，M，I）

基于对偶可交属性，下面给出另一种特殊的形式背景。

定义10设(G,M,I)为形式背景，若对于任意a∈M,a均为对偶可交属性，则称(G,M,I)为属性对偶可交背景。

注2由于对偶属性是特殊的对偶可交属性，因此，属性对偶背景一定是特殊的属性对偶可交背景。

例5(续例4) 因G*=3=a*∩c*，故b为对偶可交属性;因Gc*=1=a*∩d*，故c为对偶可交属性;因Gd*=23=c*∩e*，故d为对偶可交属性;因Ge*=1=a*∩d*，故e为对偶可交属性。结合例4知，表2所对应的形式背景(G,M,I)为属性对偶可交背景。

基于上述定义及例子，很明显有些对偶背景的性质是不成立的。但仍有以下结论：

定理6若(G,M,I)为属性对偶可交背景，则L E(G,M,IC)⊆L E(G,M,I)。

证明因为(G,M,I)为属性对偶可交背景，所以对于任意a∈M，均有Ga*=∩a*i，其中ai∈M(i=1,2, …,t)，t≤|M|，即a-*∩a*i。对于任意(X,A)∈可交性，所以X∈L E(G,M,I)，从而L E(G,M,IC)⊆L E(G,M,I)。

证毕。

定理7若(G,M,I)为属性对偶可交背景，则L(G,M,I)≅OEL(G,M,I)。

证明定义∅:L(G,M,I)→OEL(G,M,I)，对 于 任 意 (X,A)∈L(G,M,I)，有 ∅(X,A)=(X,(A,X-*))。

首先证∅为单射。因为(X,A)∈L(G,M,I)，所以X*=A,A*=X。又X⊆X-*-*,故A*∩X-*-*=X∩X-*-*=X。所以(X,(A,X-*))∈ OEL(G,M,I)。显然∅是有意义的。由∅的定义,易知∅为单射。

其次证∅为满射。即对于任意(X,(A,B))∈OEL(G,M,I)，都存在原像。只需证(A*,A)∈L(G,M,I)。因为(X,(A,B))∈OEL(G,M,I)，所以A=X*,B=X-*且X=A*∩B-*，显然A为(G,M,I)的概念内涵。从而A**=A，故(A*,A)∈L(G,M,I)。可断言:∅(A*,A)=(X,(A,B))。由∅的定义知,∅(A*,A)=(A*,(A,A*-*))∈OEL(G,M,I)。因此，要使∅(A*,A)=(X,(A,B))，只需证X=A*。由于(X,(A,B))∈OEL(G,M,I)，所以X=A*∩B-*。由于B-*∈L E(G,M,IC)，由 定 理 6 知 ，L E(G,M,IC)⊆L E(G,M,I)，所以B-*∈L E(G,M,I)。由外延具有可交性，得X∈L E(G,M,I)，从而(X,X*)∈L(G,M,I)。因 为 (X,(A,B))∈OEL(G,M,I)，所 以X*=A，即(X,A)∈L(G,M,I)。又因为(A*,A)∈L(G,M,I)，所以X=A*。

最后证∅为序同构。若(X1,A1)≤(X2,A2)，则X2⊇X1。由∅的定义知，∅(X1,A1)=(X1,(A1,X1-*))且 ∅(X2,A2)=(X2,(A2,X2-*))。 因 为X2⊇X1，所 以(X1,(A1,X1-*))≤(X2,(A2,X2-*))，即 ∅(X1,A1)≤∅(X2,A2)，反之也成立。从而∅是L(G,M,I)到OEL(G,M,I)的 序 同 构 ，即L(G,M,I)≅OEL(G,M,I)。

证毕。

例6(续例4) 表2中，形式背景的L(G,M,I),L(G,M,IC)及 OEL(G,M,I)分别如图 4～图 6所示。3个格图很明显地展示了同一背景下3个格之间的关系。

图4 L（G，M，I）Fig.4 L（G，M，I）

图5 L（G，M，IC）Fig.5 L（G，M，IC）

图6 OEL（G，M，I）Fig.6 OEL（G，M，I）

3 判断三支概念格与概念格同构的方法

3.1 判断形式背景是否为对偶（可交）背景的算法

基于第2节的讨论，给出判定形式背景是否为对偶(可交)背景的算法。这里,假设形式背景都是普通的形式背景。

以下为判断形式背景是否为属性对偶背景的算法。

算法1判断是否为对偶背景

输入(G,M,I)

N=∅;

while(m∈M)

while(n∈N)

if(Gm*==n*)N=N∪{m};

N=N∪{n};

end

end

end

if(N==M)

return true;

else

return false;

end

为了判定形式背景是否为属性对偶可交背景，首先给出fun(m)函数。

算法2fun(m)

N=fun(m)

N=∅;

while(m1∈M{m})

N1=N;

while(n∈N1)

N=N∪{m1*∩n*};

end

end

end

returnN;

通过调用算法2中的fun(m)函数，利用增量法可给出判断形式背景是否为属性对偶可交背景的算法。

算法3判断是否为对偶可交背景

输入(G,M,I)

while(m∈M)N=fun(m)

flag=0;

while(n∈N)

if(Gm*==n)

flag=1;

break;

end

end

if(flag==0)return false;

end;

end

return true;

3.2 同构理论下三支概念格的构造方法

由定理4的证明过程知，三支概念格可以通过概念格得到。

定理8若(G,M,I)为属性对偶背景，则OEL(G,M,I)={X(A,Â)|(X,A)∈L(G,M,I)且Â={a|a∈A}，其中a是a的对偶属性。

当形式背景是属性对偶可交背景时，由定理7的证明过程知，三支概念格可通过概念格得到。

定理9若(G,M,I)为属性对偶可交背景,则OEL(G,M,I)={(X(A,X*-)|(X,A)∈L(G,M,I)}。

4 结 语

三支概念分析理论较形式概念理论增加了负信息。事实上，同时利用正负信息进行数据分析，所获得的知识更全面。目前三支概念分析已发展成为数据分析与知识发现的有效工具。本文主要通过研究形式背景的特征，讨论了三支概念格与概念格的同构关系，证明了在属性对偶背景及属性对偶可交背景下，对象诱导的三支概念格与概念格是同构的，并给出了判定其是否为属性对偶背景和属性对偶可交背景的方法。事实上，可将此理论进一步推广至属性诱导的三支概念格与概念格的关系。