德国数学家R.Wille于1982年首先提出了形式概念分析理论^[1],用于概念的发现、排序和显示。形式背景与形式概念是形式概念分析的基本概念,形式概念是由形式背景中的对象集和属性集组成的统一体,形式概念之间可形成一种有序的层次结构，即概念格,概念格的构造^[2-5]是形式概念分析理论的主要研究内容之一。目前,已提出的概念格构造方法主要有2种,增量算法与批处理算法。增量算法是在数据信息不确定或不完整的情况下,当有少量数据变动时,对已经构造的概念格进行更新和维护^[3,6]; 批处理算法是在数据比较完整的情况下，依据形式背景初次构造概念格的一种更有效的方法，它主要分为枚举、自顶向下和自底向上3种算法^[7-8]。此外,还有将大背景横向拆分为若干小形式背景,再将各小形式背景的概念格进行横向合并,从而构建出相应的原形式背景概念格的方法^[9]; 以及从对象集的每一个等价类所拥有的属性子集之间的包含关系出发，构造相应的Hasse图，从而得到概念格^[10]的方法。本文对并不可约元(交不可约元)下集格中的元素定义运算,得到相应概念格的内涵集(外延集),进而扩充为概念。

1 理论基础

定义1^[11] 称(G,M,I)为一个形式背景,其中G={g₁,g₂,...,g_t}为对象集,每个g_i(i≤t)称为一个对象; M={m₁,m₂,…,m_s}为属性集,每个m_j(j≤s)称为一个属性; I为G和M之间的二元关系I⊆G×M。若(g,m)∈I,则称g具有属性m,用gIm表示; 否则,记为gɫm。

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

∀g∈G,记{g}^*为g^*; ∀m∈M,记{m}′为m′。若∀g∈G,,g*≠M,且∀m∈M,,,则称形式背景(G,M,I)是正则的。本文提到的形式背景都是正则的。

定义2^[11] 设(G,M,I)是形式背景,对X⊆G,B⊆M,若满足X^*=B且X=B′,则称(X,B)是一个形式概念,简称概念; 其中X称为概念的外延,B称为概念的内涵。形式背景(G,M,I)的全体概念记为L(G,M,I)。

定义:

则L(G,M,I)是完备格,称为概念格。

定义3^[11] 设(G,M,I)为形式背景,∀g∈G,m∈M,称为对象概念,为属性概念。

定义4^[12] 设L是格,若满足下列条件,则称x∈L是并不可约元：

1)x≠0(如果L有零元);

2) 或x=b(a,b∈L)。

对偶地,可得到交不可约元的定义。格L的全体并不可约元记为J(L),交不可约元记为M(L)。

定义5^[12] 设P为一个偏序集,Q⊆P,如果∀x∈Q,y∈P且y≤x时有y∈Q,则称Q为下集。记P的所有下集为ο(P),称ο(P)为P的下集格。

定理1^[12] 设L为有限格,L中的任意元素可表示成某些并不可约元(交不可约元)的并(交)。

定义6^[11] 设(G,M,I)为形式背景,∀g∈G,,并且,若g^*⊆h^*且g^*≠h^*,则有,并且,若且,则有并且。

定理2^[11] 下面断言对每个背景都成立：

1)对象概念是并不可约元⇌存在一个m∈M，使g↙m;

2)属性概念是交不可约元⇌存在一个g∈G，使;

下面断言对每个有限背景都成立：

3)对象概念是并不可约元⇌存在一个m∈M，使；

4)属性概念是交不可约元⇌存在一个g∈G，使。

记：是概念格L(G,M,I)所有外延构成的集合;

是概念格L(G,M,I)所有内涵构成的集合;

为概念格L(G,M,I)的并不可约元的外延集;

为概念格L(G,M,I)的交不可约元的内涵集。

2 基于不可约元下集格的概念获取

本节主要给出通过不可约元做下集格,再定义映射找到全部概念的方法。首先,根据定义6确定形式背景中的箭头关系,根据定理2找到该形式背景所对应概念格的并不可约元,其次对并不可约元的外延集做下集格,再对下集格中的元素定义映射,从而得到概念格的全部内涵集,进一步得到全部概念。利用对偶性,对交不可约元的内涵集做下集格,定义相应的映射,得到概念格的全部外延集,进而得到所有概念。

定义映射如下: ,,,且将ο(J_G(L))中所有元素的像集记为L_M(J_G(L))。

性质1 映射具有以下性质:1)f₁是满射; 2) f₁具有逆序性,即,若,则。

证明 1)根据f₁的定义,L_M(J_G(L))中的元素均是由ο(J_G(L))中元素的元素取并然后做*运算得到的。即∀B∈L_M(J_G(L)),使f₁(χ)=B;

2)当χ₁χ₂时有。由于,且*算子有逆序性,即对X₁⊆X₂,有,从而有: 。

定理3  。

证明 一方面: ∀B∈L_M(J_G(L)),,使。即有。又根据*算子的性质知道,即,使。所以有。

另一方面:∀A∈L_M(G,M,I),设y=A′,显然有(y,A)∈ L(G,M,I)。由于概念格中的每一对概念都可以由并不可约元的并得到。从而。又,,因此A∈L_M(J_G(L)),得证。

该结论表明:并不可约元外延集的下集格经f₁映射后得到的集合为相应概念格的内涵集。进一步,可对所有内涵做′算子得到相应的外延,进而得到概念。对偶地,下面给出从交不可约元出发获取其下集格及所有概念的过程。

定义映射如下: 且将ο(M_M(L))中的所有元素的像集记为L_G(M_M(L))。

性质2 具有以下性质:1) f₂是满射；2) f₂具有逆序性,即∀A₁,A₂∈ο(M_M(L)),若A₁⊆A₂,则。

证明 1)根据f₂的定义,L_G(M_M(L))中的元素均是由ο(M_M(L))中元素的元素取并再做′运算得到的。即使f₂(A)=X。

2)当A₁⊆A₂时有∪A_i⊆∪A_j,A_i∈A₁,A_j∈A₂。由于f₂(A)=(∪A)′且′算子有逆序性,即对A₁⊆A₂,有A₂′⊆A₁′,从而有: f₂(A₂)⊆f₂(A₁)。

定理4 L_G(M_M(L))=L_G(G,M,I)。

证明 一方面:∀X∈L_G(M_M(L)),∃A∈ο(M_M(L)),使f₂(A)=X。令。即有A′=X。又根据′算子的性质，知道,即∃A∈ο(M_M(L)),使。所以有X∈L_G(G,M,I)。

另一方面:∀Y∈L_G(G,M,I),设C=Y^*,显然有(Y,C)∈L(G,M,I)。由于概念格中的每一对概念都可以由交不可约元的交得到。从而∃C∈ο(M_M(L)),C=∪C_i,(C_i∈C)。又由于Y∈L_G(G,M,I),C′=Y^*′=Y,因此Y∈L_G(M_M(L)),得证。

该结论表明:交不可约元属性集的下集格经f₂映射后得到的集合为相应概念格的外延集。进一步，可对所有外延做^*算子得到相应的内涵,进而得到概念。

例1 形式背景(G,M,I)如表 1所示,其中G={1,2,3,4,5},M={a,b,c,d,e}。

首先,根据定义2.6给出该形式背景的箭头关系,如表 2所示。

由表 2的箭头关系以及定理2,得到L(G,M,I)的并不可约元为(1^*′,1^*),(2^*′,2^*),(3^*′,3^*),(4^*′,4^*),(5^*′,5^*)。即J(L)={(1,ace),(2,abde),(23,abe),(45,bcd)}。因此,J_G(L)={{1},{2},{2,3},{4,5}}。其Hasse图如图 1所示：

根据Hasse图可得： ,{{1}},{{2}},{{4,5}},{{1},{2}},{{1},{4,5}},{{2},{2,3}},{{2},{4,5}},{{1},{2},{4,5}},{{2},{2,3},{4,5}},{{1},{2},{2,3}},{{1},{2},{2,3},{4,5}}}。

,计算f1(χ),得到:

由定理3可知该属性集合为L(G,M,I)的全部内涵，扩充为概念后可得: ,(1,ace),(2,abde),(45,bcd),(23,abe),(245,bd),(145,c),(123,ae),(2345,b),。

概念格如图 2所示:

对偶地,由表 2的箭头关系以及定理2,得到L(G,M,I)的交不可约元为(a′,a′^*),(b′,b′^*),(c′,c′^*),(d′,d′^*),(e′,e′^*),即M(L)={(123,ae),(2345,b),(145,c),(245,bd)}。因此,M_M(L)={{a,e},{b},{c},{b,d}}。其Hasse图如图 3所示：

根据Hasse图,可得

,{{a,e}},{{b}},{{c}},{{a,e},{b}},{{a,e},{c}},{{b},{c}},{{b,d},{b}},{{a,e},{b,d},{b}},{{a,e},{b},{c}},{{b,d},{b},{c}},{{a,e},{b,d},{b},{c}}}。

∀A∈ο(M_M(L)),计算f2(A)得到

由定理4可知该对象集合为L(G,M,I)的全部外延。扩充为概念后可得: (1,ace),(2,abde),(45,bcd),(23,abe),(245,bd),(145,c),(123,ae),(2345,b),。概念格如图 4所示。

3 不完备形式背景的完备化

在实际问题中,由于受到各种原因的影响,有可能导致形式背景的部分对象与属性之间出现关系缺失的现象,即这部分对象与属性之间是否存在关系无法获知,在概念格理论中,将这种含有缺失值的形式背景称为不完备形式背景。针对不完备形式背景,可以根据不完备形式背景的决策信息对缺失的信息进行预测,从而将其补全为完备的形式背景^[13]; 也可以利用模糊关系的多划分技术,得到其完备化模型^[14]。本节给出基于前文方法的不完备形式背景的完备化。

在本节中,不完备形式背景的缺失信息用#表达。将#全部替换为0,得到的形式背景记为(G,M,I₁),相应的概念格记为L₁; 将#全部替换为1,得到的形式背景记为(G,M,I₂),相应的概念格记为L₂。

本节借用上节概念获取的方法,对不完备形式背景的缺失信息进行补全。首先,分析形式背景(G,M,I₁)与(G,M,I₂),由于其概念个数不同,概念个数较多的信息系统所包含的信息要相对完整一些,因而选择从概念个数较多的形式背景出发对其完备化; 然后,找到选择出形式背景并不可约元外延集的下集格,并对其中的元素在另一个形式背景上做映射f₁，得到象集后构造新集合; 最后定义映射将#映射为1或0。对偶地,找到其交不可约元的内涵集,利用相似方法对其进行完备化。

定义集合P₁={A|A∈L_M(J_G(L₁)),X∈L_1M(G,M,I₁)且∀m∈M，A≠m′^*或A∈L_M(J_G(L₁)),A∈L_1M(G,M,I₁)且∀m∈M，A≠m′^*}。其中,L₁M(G,M,I₁)为L₁的内涵集; m′^*为(G,M,I₂)的属性概念的内涵。

定义7映射如下:

定义集合,X∈L_1G(G,M,I₁)且∀g∈G,X≠g^*′或^X∉(M_M(L₁)),X∈L_1G(G,M,I₁)且。其中,L_1G(G,M,I₁)为L₁的外延集; 的对象概念的外延。

定义8 映射如下:

相应地,定义集合P₂={A|A∈L_M(J_G(L₂)),X∉L_2M(G,M,I₂)且或,且。其中,L_2M(G,M,I₂)为概念格L₂的内涵集; m′^*为(G,M,I₁)的属性概念的内涵。

定义9 映射如下:

定义集合Q₂={X|X∈L_G(M_M(L₂)),X∉L_2G(G,M,I₂)且或,X∈L_2G(G,M,I₂)且。其中,L_2G(G,M,I₂)为概念格L₂的外延集; g^*′为(G,M,I₁)的对象概念的外延。

定义10 映射如下:

例2 表 3给出了一个不完备形式背景(G,M,I,#),其中G={1,2,3,4},M={a,b,c,d,e}。

表 3中第1行的“#”符号,表示对象1是否拥有属性c是不确定的; 该表中第2行的“#”符号,表示对象2是否拥有属性d是不确定的。

下面将其完备化：

1)将不完备形式背景(G,M,I,#)中的#全部替换为0,得到形式背景(G,M,I₁),如表 4所示。将不完备形式背景(G,M,I,#)中的#全部替换为1,得到形式背景(G,M,I₂),如表 5所示。

2)概念格L₁如图 5所示,概念格L₂如图 6所示:

显然,L₂的概念多,所表达的信息更加完整,下面从形式背景(G,M,I₂)出发,对不完备形式背景(G,M,I,#)完备化。

3)概念格L₂的并不可约元如下:

4)将所有并不可约元的外延构成集合:J_G(L₂)={{1},{2},{3},{4}}。其Hasse图如图 7所示。

5) JG(L₂)的下集格如下:

,{{1}},{{2}},{{3}},{{4}},{{1},{2}},{{1},{3}},{{1},{4}},{{2},{3}},{{2},{4}},{{3},{4}},{{1},{2},{3}},{{1},{2},{4}},{{1},{3},{4}},{{2},{3},{4}},{{1},{2},{3},{4}}}。

6) ,在形式背景(G,M,I₁)上计算f₁(χ),可得

7)根据集合P₂的定义,可得:P₂={{d},{a,c},{b,d},{a,c,d}}

8)根据映射h₂₁得到I(1,c)=0,I(2,d)=0。从而得到补全后的完备的形式背景(G,M,I₃)如表 6所示:

对偶地,从L₂交不可约元出发对不完备形式背景完备化。

1)概念格L₂的交不可约元如下:

2)将所有交不可约元的内涵构成集合:M_M(L₂)={{a},{d},{b},{a,e},{a,c}}。其Hasse图如图 8所示:

3)M_M(L₂)的下集格如下:

4)∀A∈ο(M_M(L₂)),在形式背景(G,M,I₁)上计算f₂(A)可得:

5)根据集合Q₂的定义,可得: Q₂={{1,2},{1,3},{2}}

根据映射h₂₂得到I(1,c)=0,I(2,d)=0。从而得到补全后的完备的形式背景(G,M,I₄),如表 7。

最后,以看出基于2种不可约元的下集格完备化得到的形式背景相同。因而,将其作为最终完备化的结果。

4 结束语

本文提出了一种通过并不可约元(交不可约元)的下集格获取概念的方法。首先利用箭头关系找到该背景对应概念格的并不可约元(交不可约元),对并不可约元(交不可约元)的外延集(内涵集)做下集格; 其次对下集格中的元素做相应的运算,得到的属性集合(对象集合)可证明就是概念格的内涵集(外延集)；最后将其扩充成为概念。此外，根据这种概念获取的方法利用下集格已经将并不可约元(交不可约元)的并(交)经行了初步筛选,所以对于不完备形式背景来说从概念较多的形式背景(G,M,I₁)或(G,M,I₂)的并不可约元出发,在另一个形式背景上进行特定的映射，最后根据定义的映射将其完备化。同样可以从交不可约元出发，对不完备形式背景进行扩充。并且基于2种不可约元扩充后的结果相同。