伽羅瓦連接在構(gòu)造擬陣中的應(yīng)用*

王 剛,毛 華,武振宇

(1.河北大學(xué)生命科學(xué)學(xué)院,河北 保定 071002;2.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002)

1 引言

擬陣是由Whitney[1]于1935年提出的，構(gòu)造擬陣是其研究內(nèi)容之一。伴隨著擬陣在許多領(lǐng)域的應(yīng)用[2 - 20]，原始的擬陣結(jié)構(gòu)[1]在不斷地?cái)U(kuò)展[14 - 18]。從這些擬陣的擴(kuò)展過程推測，將處理數(shù)據(jù)的理念用到擬陣論研究中是可行的。事實(shí)上，如何將處理數(shù)據(jù)的有效方法應(yīng)用到構(gòu)建擬陣結(jié)構(gòu)，促使擬陣論以更多方式應(yīng)用到數(shù)據(jù)處理中，是目前擬陣論研究中需解決的問題之一。

伽羅瓦連接(Galois Connection)根植于伽羅瓦理論，由背景(Context)產(chǎn)生。該定義不僅在形式概念分析(或稱概念格FCA(Formal Concept Analysis))中得以應(yīng)用[12,13,21 - 24]，而且還在數(shù)據(jù)挖掘等領(lǐng)域也有運(yùn)用[25 - 29]。概念格理論是由Wille[30]始創(chuàng)的，是支持?jǐn)?shù)據(jù)分析的一種有效工具。構(gòu)建概念格是其研究內(nèi)容之一，現(xiàn)已有不少有關(guān)的算法[21,22,31 - 33]。近來，人們關(guān)注背景與映射之間的關(guān)系問題，以及背景與完備格、閉包算子和擬陣之間的關(guān)系等問題，取得了不少成果[9 - 12,21,22,34 - 43]。

為探討擬陣、伽羅瓦連接、概念格和背景之間內(nèi)在作用，已有學(xué)者研究在一些擬陣和一些概念格之間的關(guān)系[9 - 11,43]，以及利用與貪心算法有關(guān)的方法[2,3,15 - 18,44]找到一些特殊背景下的概念格[45,46]，還有用粗糙集理論等構(gòu)建擬陣結(jié)構(gòu)[8,36]。

綜上可知，需要有更新的方法融入到構(gòu)造擬陣的研究中。雖然構(gòu)造概念格的方法很多，但是構(gòu)造擬陣的方法相對較少。如果改變這個現(xiàn)狀，那么對擬陣的發(fā)展和應(yīng)用必會起到推動作用，對FCA理論應(yīng)用領(lǐng)域的擴(kuò)大也會有效。為此，分析已有的一些相關(guān)性質(zhì)是必要的，現(xiàn)總結(jié)如下：(1) 由擬陣閉包公理可知，1個擬陣可由1種特殊的閉包算子唯一確定[2,3]。(2) 結(jié)合已有結(jié)果[7,9 - 13,20 - 22]確信，擬陣有能力成為研究FCA的一個工具，而FCA中的一些結(jié)果也能應(yīng)用到擬陣研究中。(3) 從概念格定義可知[21,22]，對1個背景(O,P,R)，存在2個映射′和′：一個是定義在P(O)上的′，另一個是定義在P(P)上的′。(O,P,R)的概念格就是由構(gòu)成1對伽羅瓦連接[21,22]的映射(′,′)所決定的。

由(1)～(3)可知：深入的研究需找到擬陣與背景之間的深層關(guān)系，而關(guān)鍵問題是：對于以σ為閉包算子的集合O上的擬陣，以及1個背景(O,P,R)上所產(chǎn)生的1對映射(′,′)，在何種條件下有σ=′′成立？為尋找到此問題的答案，首先分析已有的一些相關(guān)結(jié)果：(1)文獻(xiàn)[2,3]給出了擬陣與幾何格之間的關(guān)系;(2)文獻(xiàn)[3,47]給出了有向擬陣的格理論特征;(3)文獻(xiàn)[4,48]分別給出了格論與Coxeter擬陣之間的一些關(guān)系線索；(4)文獻(xiàn)[21,22]得到了背景與格論之間的關(guān)系，還得到完備格與概念格之間有相互對應(yīng)的關(guān)系；(5)文獻(xiàn)[10]利用簡單擬陣的閉集族的格論性質(zhì)，給出簡單擬陣與某些背景之間的關(guān)系。

綜合這些結(jié)果可推斷：伽羅瓦連接和格論在探討擬陣的構(gòu)建中會起到重要作用，或許通過這種作用可找到上述關(guān)鍵問題的答案。本文研究將沿此思路進(jìn)行。具體工作如下所示：(1) 借助伽羅瓦連接揭示背景與擬陣之間的關(guān)系；(2) 找到由1個擬陣構(gòu)造伽羅瓦背景的方法；(3) 找到由1個伽羅瓦背景建立擬陣的一些方法；(4) 用實(shí)例說明所得方法的有效性。

本文其余安排如下：第2節(jié)說明后續(xù)工作所需定義和術(shù)語；第3節(jié)挖掘伽羅瓦背景與擬陣之間的關(guān)系，給出所求關(guān)鍵問題的答案；借用構(gòu)造概念格的一些已有方法，在第4節(jié)將得到建立擬陣的一些方法；第5節(jié)為實(shí)例；第6節(jié)為結(jié)束語。規(guī)定本文所討論的內(nèi)容均為有限。

2 預(yù)備知識

設(shè)S為1個集合，用P(S)代表S的所有子集構(gòu)成的集合。

定義1(1)令O和P為2個集合，R?O×P。若X?O，Y?P，則令K(X)={y∈P|?x∈X，(x,y)∈R}；L(Y)={x∈O|?y∈Y，(x,y)∈R}。稱這對映射(K,L)是O和P之間的1個伽羅瓦連接[49]。若J:P(O)→P(O)滿足條件①～③，則稱J為O上的1個閉包算子。令X,Y?O，有：①X?J(X)；②X?Y?J(X)?J(Y)；③J(J(X))=J(X)。

對于X∈P(O)，若J(X)=X，則稱X為閉的。閉包算子J的所有閉集構(gòu)成的集合記為B(J)。

(2)設(shè)M1=(E1,I1)和M2=(E2,I2)是2個擬陣，其中Ij為Mj的獨(dú)立集族。若存在雙射f:E1→E2滿足：X∈I1?f(X)∈I2，則稱M1和M2是同構(gòu)的，記為M1≌M2[2,3,50]。

說明1(1) 定義1中的伽羅瓦連接和閉包算子，均與文獻(xiàn)[21,22]中相關(guān)內(nèi)容一致。

(2)定義1(1)中稱(K,L)為1個伽羅瓦連接是對的，因其與伽羅瓦理論中相關(guān)內(nèi)容[51]一致。

有關(guān)格論的內(nèi)容參見文獻(xiàn)[21,22,52]。下面給出FCA的內(nèi)容，未盡事宜參見文獻(xiàn)[21,22]。

定義2(1)一個背景是指1個3元組(O,P,R)，其中的O和P是集合，R?O×P。對于A?O和B?P，定義A′={m∈P|?g∈A，(g,m)∈R}，B′={g∈O|?m∈B，(g,m)∈R}。稱(′,′)為(O,P,R)衍生的1對算子。若A′=B且B′=A，則稱(A,B)為(O,P,R)的一個概念(Concept)。(A,B)的外延是A，內(nèi)涵是B。(O,P,R)的所有概念集合記為Gal(O,P,R)[21,22]。

(2)設(shè)(Oj,Pj,Rj)為1個背景(j=1,2),f:O1→O2和g:P1→P2為1對雙射。若(f,g)滿足：(n,m)∈R1?(f(n),g(m))∈R2,則稱(O1,P1,R1)同構(gòu)于(O2,P2,R2)，記為(O1,P1,R1)≌(O2,P2,R2)[21]。

引理1設(shè)O和P為2個集合，R?O×P。

(1)令K:P(O)→P(P),L:P(P)→P(O)為1個伽羅瓦連接，則LK為O上的閉包算子[49]。

(2)設(shè)(′,′)為定義2中給出的(O,P,R)衍生的1對算子，則(′,′)形成1個伽羅瓦連接[21]。

說明2從定義1、定義2和引理1(2)可得，對一背景(O,P,R)，必存在O和P之間的1個伽羅瓦連接(K,L)。有時(shí)也稱(K,L)是從(O,P,R)產(chǎn)生的，或說(K,L)是對應(yīng)于(O,P,R)的。

引理2(1)由Gal(O,P,R)產(chǎn)生1個格結(jié)構(gòu)，將此格稱為概念格(Concept Lattice)，或稱伽羅瓦格，仍記為Gal(O,P,R)[21,22]。

(2)令BO:={A?O|A″=A}，則BO是(O,P,R)外延的全體，并且(BO,?)是1個同構(gòu)于Gal(O,P,R)的格，稱(BO,?)為外延格，簡記為BO[22]。

引理3設(shè)(O,P,R)為1個背景。若(K,L)為對應(yīng)于(O,P,R)的1個伽羅瓦連接。(′,′)為定義2中給出的，由(O,P,R)衍生的算子，則LK=″。

證明由引理1(2)知，(′,′)形成1個伽羅瓦連接。再考慮定義2得：對于X?O有X′={y∈P|對于任何x∈X都有(x,y)∈R},進(jìn)一步地有(X′)′={a∈O|對于任何b∈X′都有(a,b)∈R}。根據(jù)已知條件，(K,L)為對應(yīng)于(O,P,R)的1個伽羅瓦連接。再考慮定義1得：對于X?O有K(X)={y∈P|?x∈X，(x,y)∈R}。進(jìn)一步地有，L(K(X))={c∈K(X)|?d∈K(X)，(c,d)∈R}。對比(X′)′和L(K(X))得(X′)′=L(K(X))。若簡記(X′)′為(X)″，L(K(X))為LK(X)，則有(X)″=LK(X)。又據(jù)X的任意性，必有LK=″。

□

說明3設(shè)(O,P,R)為1個背景，(K,L)為對應(yīng)于(O,P,R)的伽羅瓦連接。

(1) 由定義1和定義2確信：對?X?O和?Y?P有K(X)=X′和L(Y)=Y′。再由引理3得BO=B(LK)。

(2) 引理3說明，上面(1)蘊(yùn)含著：對應(yīng)(O,P,R)的伽羅瓦連接是唯一的。

此處利用文獻(xiàn)[2,3]給出擬陣的一些性質(zhì)。有關(guān)擬陣的其它內(nèi)容參見文獻(xiàn)[2,3]。

引理4令M為集合E上的1個擬陣，且F為其閉集族。

(1)P(E)上的1個函數(shù)σ是M的閉包算子，當(dāng)且僅當(dāng)σ為E上的1個閉包算子，并且滿足條件(s4)：對于任何的Y∈E以及y,z∈E，若y?σ(Y)但是y∈σ(Y∪z)，則z∈σ(Y∪y)[2,3]。

(2)(F,?)是1個幾何格[2,3]。

(3)由幾何格L產(chǎn)生的定義在L的原子集合上的擬陣M(L)，這一對應(yīng)是有限幾何格族與簡單擬陣族之間的1個雙射[2]。

說明4根據(jù)引理4(1)，本文用(E,σ)表示集合E上的1個擬陣M，其中σ為M的閉包算子。雖然由定義1和引理4(1)知，σ是P(E)上的1個閉包算子，但是E上任一個閉包算子J不一定是E上的某擬陣的閉包算子。由定義1(2)以及引理4(1)可知，對于2個擬陣M1=(E1,σ1)和M2=(E2,σ2)，若M1≌M2，即存在M1到M2的同構(gòu)映射f，則對?X?E1有：X=σ1(X)?f(X)=σ2(f(X))。

3 伽羅瓦連接與擬陣的關(guān)系

本節(jié)要找到伽羅瓦連接與擬陣之間的關(guān)系。挖掘用擬陣的閉包算子建立擬陣的方法，它們不同于以往的方法[2-4,8,10,12,13,36,53,54]。本節(jié)結(jié)果將會回答第1節(jié)提出的關(guān)鍵問題。

首先給出1個定義。

定義3設(shè)(O,P,R)為1個背景，(K,L)為由(O,P,R)產(chǎn)生的伽羅瓦連接。若(O,LK)是1個擬陣，則稱(O,P,R)為1個伽羅瓦背景。

注1(1) 根據(jù)引理2(1)和文獻(xiàn)[21,22]可知：為了獲得關(guān)鍵問題的答案，需要關(guān)注伽羅瓦背景。

(2) 由引理3、定義1和定義3，下文視情況討論伽羅瓦連接與擬陣的關(guān)系和背景的伽羅瓦性質(zhì)。

下面的引理將保證：對于1個給定的擬陣一定存在1個與其相關(guān)的伽羅瓦背景。

引理5設(shè)M=(O,σ)為1個擬陣，定義R?O×P(O)為：對于x∈O和Y?O，有(x,Y)∈R?x∈σ(Y)。若(K,L)為由背景(O,P(O),R)產(chǎn)生的伽羅瓦連接，則σ=LK。

證明分2步完成證明。

步驟1 證明(O,P(O),R)是1個背景。

由定義2(1)以及R的定義可得所需。

步驟2 證明σ=LK。分2方面進(jìn)行。

一方面證：LK?σ。令X?O且x∈X。則由定義1知：K(X)={Z?O|?x∈X,(x,Z)∈R}且L(K(X))= {a∈O|?Z∈K(X),(a,Z)∈R}。又由引理4和定義1得x∈σ(X)。因此，σ(X)∈K(X)。令a∈L(K(X))且U∈K(X)。依據(jù)LK和R的定義有a∈σ(U)成立。再由σ(X)∈K(X)，可得a∈σ(X)。故L(K(X))?σ(X)。

另一方面證明：σ?LK。令X,Z?O，對于任意的x∈X，若x∈σ(Z)，則X?σ(Z)。進(jìn)而根據(jù)定義1(1)和引理4(1)必有σ(X)?σ(σ(Z))=σ(Z)。因此，若b∈σ(X)，則有：對于任意Z∈K(X)有b∈σ(Z)。所以有(b,Z)∈R。故而，b∈L(K(X))成立。即有σ(X)?L(K(X))。

□

注2運(yùn)用構(gòu)造性的方法，引理5給出從1個擬陣產(chǎn)生一個伽羅瓦背景的方法。該引理也說明定義3是有意義的。

考慮引理5的逆命題是否成立?答案是不一定。原因如下：

(1)例1表明對某些伽羅瓦連接(K,L)，必有1個以LK為其閉包算子的擬陣。

例1令(O,P,R)為1個背景，滿足R=O×T，此處T?P。令(K,L)是由(O,P,R)產(chǎn)生的伽羅瓦連接。由定義1，對于任意的X?O，必有K(X)={y∈P|?x∈X,(x,y)∈R}=T且L(K(X))=O。因此，易得LK滿足引理4(1)中的條件(s4)。從而由引理4(1)知：M=(O,LK)是1個擬陣，并且B(LK)= {O}。

(2)如果假設(shè)引理5的逆命題總是成立，那么討論如下：令(O,P,R)為1個背景。由于定義1和說明3(2)，存在且僅存在1個從(O,P,R)產(chǎn)生的伽羅瓦連接(K,L)。根據(jù)引理1，LK是O上的1個閉包算子。假設(shè)M=(O,σ)是1個擬陣且σ=LK。由定義1和引理4(1)知M的所有閉集集合F為{X?O|σ(X)=X}。又由定義1知：LK的所有閉集的集合B(LK)={X?O|LK(X)=X}。故由σ=LK有F=B(LK)。依據(jù)引理4(2)，(F,?)是1個幾何格。這導(dǎo)致(B(LK),?)是幾何的。結(jié)合說明3(1)得BO=B(LK)，有(BO,?)是幾何格。再用引理2知格Gal(O,P,R)是幾何的。然而對任一背景(O1,P1,R1)，格Gal(O1,P1,R1)不一定是幾何的[10]。這就導(dǎo)致矛盾。該矛盾說明引理5的逆命題不成立。

基于此，下方引理將會發(fā)現(xiàn)，何種條件下1個伽羅瓦連接(或說1個背景)可創(chuàng)建1個擬陣。

引理6設(shè)(O,P,R)為1個背景，(K,L)為由(O,P,R)產(chǎn)生的伽羅瓦連接。如果LK滿足條件(s4)，那么(O,LK)是1個擬陣。

證明根據(jù)說明3(2)知，(K,L)=(′,′),再由引理3有LK=″。從引理1得知：LK為集合O上的1個閉包算子，進(jìn)一步地，據(jù)引理4(1)，以及LK滿足條件(s4)，可確信(O,LK)為1個擬陣。

□

引理6看上去簡單，但卻是判定(O,LK)為擬陣的基礎(chǔ)。

接下來，將繼續(xù)討論擬陣與伽羅瓦連接之間的關(guān)系問題。

例2設(shè)(O,P,R1)和(O,P,R2)為2個背景，此處，對于某個t∈P和T2?P滿足T2 ≠?有R1=O×{t}且R2=O×T2。設(shè)(Kj,Lj)(j=1,2)為對應(yīng)于(O,P,Rj)的伽羅瓦連接。顯然，R1≠R2使得(K1,L1)和(K2,L2)之間存在差異。然而，例1的結(jié)果保證：LjKj是擬陣Mj=(O,LjKj)的閉包算子(j=1,2)。類似地，對于任意的X?O必有L1K1(X)=O=L2K2(X)。因此，由引理4(1)和L1K1=L2K2得到：M1=M2成立。

例2表明，不同的伽羅瓦背景可能產(chǎn)生相同的擬陣。下面將討論在何種條件下，可以克服這個非唯一性。先引入如下的定義。

定義4[12]設(shè)(Oj,Pj,Rj)為1個背景，其相應(yīng)的伽羅瓦連接為(Kj,Lj)，j=1,2。若存在1個雙射π：O1→O2滿足：對于任意的X?O1有：X=L1K1(X) ?πX=L2K2(πX)。則：(1) 稱(K1,L1)是伽羅瓦同構(gòu)(Galois Isomorphic)于(K2,L2)，記為(K1,L1)≌G(K2,L2)；(2) 稱π為(K1,L1)和(K2,L2)之間的1個伽羅瓦同構(gòu)映射；(3) 稱π為(O1,P1,R1)與(O2,P2,R2)之間的1個伽羅瓦同構(gòu)映射；(4) 稱(O1,P1,R1) 是伽羅瓦同構(gòu)于(O2,P2,R2)，記為(O1,P1,R1)≌G(O2,P2,R2)。

說明5(1)文獻(xiàn)[2]指出，對于2個擬陣M1=(O1,σ1)和M2=(O2,σ2)，即使(F1,?)≌(F2,?)，仍不能夠保證存在1個雙射π0：O1→O2滿足：X∈F1?π0(X)∈F2。即此時(shí)不能夠保證有M1≌M2。

(2) 對于背景(O,P,R)，最實(shí)質(zhì)的研究是：構(gòu)造格Gal(O,P,R)(或者在格同構(gòu)意義下構(gòu)造(BO,?))。從說明2和引理3可以發(fā)現(xiàn)，若(K,L)是從(O,P,R)產(chǎn)生的伽羅瓦連接，則有BO=B(LK)。

(3)文獻(xiàn)[12]指出：(O1,P1,R1)≌(O2,P2,R2)?(O1,P1,R1)≌G(O2,P2,R2)，但反之不然。這表明，伽羅瓦同構(gòu)是比同構(gòu)要求條件弱的一種形式。

為了處理背景與擬陣之間的關(guān)系，需要下面的擬陣和伽羅瓦背景的性質(zhì)：

引理7[12](1) 設(shè)(Oj,Pj,Rj)為對應(yīng)于1個擬陣Mj=(Oj,σj)的伽羅瓦背景，并且(Kj,Lj)為從(Oj,Pj,Rj)產(chǎn)生的伽羅瓦連接，j=1,2。那么M1≌M2?(O1,P1,R1)≌G(O2,P2,R2)。

(2) 設(shè)(Oj,Pj,Rj)為一個背景且(Kj,Lj)為與其對應(yīng)的伽羅瓦連接，j=1,2。那么(K1,L1)≌G(K2,L2)?(O1,P1,R1)≌G(O2,P2,R2)。

定義3、定義4和引理7結(jié)合可得到下面的結(jié)果：

定理1在伽羅瓦同構(gòu)和擬陣同構(gòu)意義下，伽羅瓦背景族與擬陣族之間存在1個雙射。

證明令Mj為集合Oj上的擬陣，且σj為其閉包算子，j=1,2。由引理5可發(fā)現(xiàn)1個由Mj產(chǎn)生的伽羅瓦背景(Oj,P(Oj),Rj)，j=1,2。若M1≌M2，則據(jù)引理7(1)有(O1,P(O1),R1)≌G(O2,P(O2),R2)。

反之，令(Oj,Pj,Rj)為1個伽羅瓦背景，(Kj,Lj)為由(Oj,Pj,Rj)產(chǎn)生的伽羅瓦連接，j=1,2。那么由定義4知：存在1個定義在Oj上的擬陣Mj，滿足LjKj為其閉包算子，j=1,2。若(O1,P1,R1)≌G(O2,P2,R2)成立，則由引理7(1)有M1≌M2成立。

□

推論1在伽羅瓦同構(gòu)與擬陣同構(gòu)意義下，由伽羅瓦背景產(chǎn)生的伽羅瓦連接族與擬陣族之間，存在1個雙射。

證明考慮定理1、定義3、定義4和引理7(2)，很容易得到所需結(jié)論。

□

注3(1) 結(jié)合說明3(2)可以斷言：定理1和推論1回答了第1節(jié)提出的關(guān)鍵問題。

(2) 定理1和推論1提供了將擬陣?yán)碚搼?yīng)用到伽羅瓦連接研究中的堅(jiān)實(shí)基礎(chǔ)。

說明6(1) 對背景(O,P,R)，引理5的逆命題不成立，故或許無擬陣M=(O,σ)滿足σ=LK，其中(K,L)為(O,P,R)產(chǎn)生的伽羅瓦連接。這與例1之后的(2)結(jié)果一致。這也說明了定理1的正確性。

(2) 在伽羅瓦同構(gòu)與擬陣同構(gòu)意義下，存在唯一1個擬陣對應(yīng)于伽羅瓦背景(O,P,R)。

4 伽羅瓦連接構(gòu)造擬陣的方法

現(xiàn)已知的一些構(gòu)造擬陣算法分別依據(jù)擬陣的獨(dú)立集公理[2,3,50,53]、覆蓋圖[10]、格結(jié)構(gòu)[6,12]等[8,36]原理完成算法過程。據(jù)擬陣的定義[2,3,50]，對1個分別以I，F(xiàn)為其獨(dú)立集族和閉包集族的擬陣，必有|F|≤|I|。所以第3節(jié)是有意義的。本節(jié)將提供2種利用伽羅瓦連接建造擬陣的方法。

算法1構(gòu)造M的算法

輸入：(O,P,R)為1個背景。

輸出：是否有1個擬陣M，且LK為M的閉包算子。

步驟1找到BO(也就是B(LK))，即{X?O|X=LK(X)}。

步驟2對于任意的X∈B(LK)和a,b∈O，若a∈LK(X∪b)LK(X)成立，則檢查是否有b∈LK(X∪a)。若為是，則轉(zhuǎn)步驟3,否則轉(zhuǎn)步驟4。

步驟3由引理4(1)知B(LK)為O上擬陣M=(O,LK)的閉集族。

步驟4由定理1知LK不為O上任何擬陣的閉包算子。

說明7(1) 已有的得到BO的算法(或者由說明3(1)等價(jià)地說，得到B(LK)的算法，或者由引理2(2)等價(jià)地說，得到Gal(O,P,R)的方法)[21,22,32,33]，其中任一個都可完成步驟1中的任務(wù)。

(2) 由引理 6，若要構(gòu)造1個擬陣(O,σ)滿足σ=LK，則需執(zhí)行步驟2。

(3) 事實(shí)上，到現(xiàn)在為止，用擬陣的閉集族的性質(zhì)構(gòu)建1個擬陣的方法不多[10,12,13]。雖然已有在同構(gòu)意義下，找到1個閉包算子的所有閉集的方法[55]，但是對于1個具體的問題，文獻(xiàn)[55]給出的算法，對于有附加要求的結(jié)構(gòu)性質(zhì)來說通常不作考慮。因此可以斷定：算法1可成功地利用伽羅瓦連接的閉集族完成擬陣構(gòu)建。

(4)在已有的方法中[21,22,32,33]，NextClosure算法[21]是得到BO的最著名算法。對于任何A?O,得到A+∈BO的算法時(shí)間復(fù)雜度是O(|O||P|2)，這是線性時(shí)間，從而也是一個多項(xiàng)式時(shí)間。得到BO的全體，即{A+|A?O}的時(shí)間復(fù)雜度為O(|O||P|2|BO|)。對于X∈BO，步驟2的時(shí)間復(fù)雜度為O(|O|2)，因此步驟2的時(shí)間復(fù)雜度為O(|O|2|BO|)。由于|BO|≤2|O|，所以算法1的時(shí)間復(fù)雜度為O(|O|(|O|+|P|2)2|O|)。再因?yàn)橐阎Ｓ玫那驜O的算法中，在時(shí)間復(fù)雜度方面，NextClosure算法是較低的。即便如此，讀者可根據(jù)問題的實(shí)際情況和喜好方便程度，決定采用哪一種方法完成步驟1。若設(shè)步驟1的時(shí)間復(fù)雜度為C，則算法1的復(fù)雜度為O(|O|22|O|+C)。

算法2構(gòu)造O上1個擬陣

輸入：(O,P,R)為1個背景。

輸出：是否有1個以LK為閉包算子O上的1個擬陣M。

步驟1用已有的方法，或者如文獻(xiàn)[56]中的軟件,得到格Gal(O,P,R)，再可得到(BO,?)，即(B(LK),?)；或者采用1個已有的直接得到(BO,?)的方法，即得到(B(LK),?)。

步驟2判斷(B(LK),?)是否為幾何的。若是，則轉(zhuǎn)步驟3；若否，則轉(zhuǎn)步驟4。

步驟3在同構(gòu)意義下，B(LK)是O上的1個擬陣M的閉集族并且LK為其閉包算子。

步驟4由引理4(3)，得出在O上不存在1個擬陣M以LK為其閉包算子。

說明8(1) 根據(jù)已有的討論[2,3,52]，要完成步驟2，需要完成下面2項(xiàng)判定工作。第1項(xiàng)：(B(LK),?)中的每1個元都是原子(即在(B(LK),?)中覆蓋最小元的元)的并。第2項(xiàng)：在(B(LK),?)中，對任何x,y∈B(LK)都有：x和y覆蓋x∧y?x∨y覆蓋x和y。

(2) 當(dāng)?shù)?B(LK),?)時(shí)，第1項(xiàng)完成。故可在進(jìn)行第1項(xiàng)工作時(shí)，直接選擇能夠生成(B(LK),?)的格圖(即Hasse示圖)的方法，例如文獻(xiàn)[56]中給出的方法,可以很快得到(B(LK),?)的原子集。

(3) 由文獻(xiàn)[2,3,52]，第2項(xiàng)工作可等價(jià)地陳述為：在(B(LK),?)中，任何2個元x,y之間的極大鏈有相同的長度且h(x)+h(y)≥h(x∧y)+h(x∨y)，此處h為高函數(shù)。從定義發(fā)現(xiàn)，在時(shí)間復(fù)雜度方面，判斷極大鏈的長度和得到h與第2項(xiàng)工作一致，故可根據(jù)實(shí)際問題選擇第2項(xiàng)的具體方法。

(4) 雖然文獻(xiàn)[56]是公開的，但在時(shí)間復(fù)雜度方面并無公開信息。步驟2的時(shí)間復(fù)雜度為O(2|B(LK)|)。文獻(xiàn)[22]中BO和(BO,?)同時(shí)產(chǎn)生的算法時(shí)間復(fù)雜度為O(2|O||P|)。但是，該方法尚未找到對應(yīng)的軟件。

算法1和算法2比較如下：

(1) 2個算法的步驟2在時(shí)間復(fù)雜度上都是O(2|B(LK)|)，故無太大區(qū)別，只是方法上有所不同。

(2) 2個算法的步驟1均需找B(LK)。算法1無需從(B(LK),?)上尋找某種性質(zhì)，故對任何生成B(LK)或Gal(O,P,R)的方法，都可使用。算法2需考慮(B(LK),?)的原子全體，故為了使所得(B(LK),?)的結(jié)果中，其原子全體可以直觀地顯示出來，建議在選擇算法或軟件時(shí)，采用可以直接生成(B(LK),?)的全體，又可同時(shí)得到(B(LK),?)的Hasse示圖的算法或軟件。

(3) 算法1產(chǎn)生的擬陣是唯一的，但不一定是簡單的。算法2得到的擬陣一定是簡單的，且在擬陣的同構(gòu)意義下和格的同構(gòu)意義下，得到的擬陣是唯一的。

說明9由于本文中給出的2種構(gòu)造擬陣的算法，利用了處理數(shù)據(jù)的有效工具FCA中一些理念和思想，所以當(dāng)將算法1和算法2與已知的方法比較時(shí)，選取的對比方法也須是與處理數(shù)據(jù)有關(guān)的方法，這樣才會更有說服力。在已有的研究成果中，文獻(xiàn)[10，12]的方法相對更好一些。

算法1和算法2與一些已知方法的比較結(jié)果如表1和表2所示。

Table 1 Comparison between algorithm 1and method in reference [12]

Table 2 Comparison between algorithm 2and method in reference [10]

從表1和表2可以總結(jié)如下：

(1) 從計(jì)算機(jī)的輔助工作方面：算法1和算法2優(yōu)于文獻(xiàn)[10]和文獻(xiàn)[12]的。

(2) 可以推測：算法1和算法2在未來的工作中，必會結(jié)合其它理論和想法，應(yīng)用到FCA的探索中，而文獻(xiàn)[10]和文獻(xiàn)[12]的方法則不一定。

(3) 算法1構(gòu)造的擬陣不一定是簡單的，文獻(xiàn)[10]的方法得的擬陣一定是簡單的，所以算法1比文獻(xiàn)[10]中的方法適用范圍更廣。在實(shí)現(xiàn)過程中，算法2的工作量小于文獻(xiàn)[10]的方法的工作量。

(4) 算法1和算法2是直接產(chǎn)生擬陣，而文獻(xiàn)[12]的方法在數(shù)據(jù)的存儲空間上比算法1和算法2的都大。

5 應(yīng)用舉例

本節(jié)通過實(shí)際例子說明第4節(jié)給出的算法的應(yīng)用與實(shí)現(xiàn)。

例3采用文獻(xiàn)[10]中表2的數(shù)據(jù),其對應(yīng)的數(shù)學(xué)表示如表3所示。

Table 3 Mathematical representation oftable 2 in reference [10]

下面將用算法2構(gòu)造該背景的擬陣。利用文獻(xiàn)[56]的軟件得到表3對應(yīng)的形式背景(O,P,R)的伽羅瓦格，如圖1所示，其中O={aj:j=1,2,3,4}，P={bj:j=1,2,3},R如表3所示。其中，R?O×P,aiRbj在表3中對應(yīng)的值為1，否則為0(i=1,…,4,j=1,2,3),在表3中，a1=鉤刺豆芫菁，a2=墨江豆芫菁，a3=扁角豆芫菁，a4=戈勒姆豆芫菁，b1=體腹側(cè)并不全都散布黑毛，b2=體背側(cè)主要散布棕毛，b3=體腹側(cè)散布有黑色長毛，0為“是”，1為“否”。

Figure 1 Galois lattice of (O,P,R)圖1 (O,P,R)的伽羅瓦格

由BO和Gal(O,P,R)的關(guān)系，立刻得到：BO={{?},{a1},{a2},{a4},{a1,a2},{a2,a4},{a1,a3,a4},{a1,a2,a3,a4}}。利用Gal(O,P,R)≌(BO,?)，以及BO=B(LK)可得(B(LK),?)的原子集是{{a1},{a2},{a4}}。還可以直接獲得(B(LK),?)中其他非最小元的元與原子的關(guān)系，進(jìn)而可知(B(LK),?)是一個幾何格。由算法2中的步驟3可知，(O,LK)為1個擬陣，并且B(LK)是該擬陣的閉集族，LK是該擬陣的閉包算子。

說明10將例3與文獻(xiàn)[10]中的例2相比較可知，對于同一個背景，由于算法2與文獻(xiàn)[10]構(gòu)造擬陣的方法不同，得到的擬陣不一樣，也說明算法2是一個創(chuàng)新的方法。

例4用文獻(xiàn)[57]中表3給出的數(shù)據(jù)，其對應(yīng)的數(shù)學(xué)表示如表4所示。易知(O={aj:j=1,…,16},P={bj:j=1,…,9},R1)為1個背景，R1如表4所示。R1?O×P,aiR1bj在表4中對應(yīng)的值為1，否則為0(i=1,…,16;j=1,…,9)。

Table 4 Mathematical representation oftable 3 in reference [57]

令S?{aj:j=1,…,16}×{bj:j=1,…,9}定義為：xSy?{x}′={y}′。易證S為等價(jià)關(guān)系，且由定義2(1)得：[a1]S={a1},[a2]S={a2,a15},[a3]S={a3},[a4]S={a4,a5,a6,a8,a13},[a7]S={a7},[a9]S={a9,a10},[a11]S={a11,a12},[a14]S= {a14},[a16]S={a16},其中[x]S為關(guān)于S的x所在的等價(jià)類。令[a1]S=o1,[a2]S=o2,[a3]S=o3,[a4]S=o4,[a7]S=o5,[a9]S=o6,[a11]S=o7,[a14]S=o8,[a16]S=o9。由表4得到依S產(chǎn)生的聚類背景表，如表5所示。 則得背景(O1={oj:j=1,…,9},P={bj:j=1,…,9},R2)，R2如表5所示。R2?O1×P,oiR2bj在表5中對應(yīng)的值為1，否則為0(i=1,…,9;j=1,…,9)。

Table 5 Clustering context produced from table 4 based onS

Figure 2 Galois latticeGal(O1,P,R2) corresponding to table 5圖2 表5的伽羅瓦格Gal(O1,P,R2)

根據(jù)文獻(xiàn)[56]可以得到表5的伽羅瓦格Gal(O1,P,R2)如圖2所示。由B(LK)與Gal(O1,P,R2)的關(guān)系可得B(LK)={{?},{o1},{o2},{o5},{o6},{o8},{o9},{o3,o8},{o2,o6},{o2,o7},{o1,o2},{o2,o8},{o1,o4,o9},{o2,o6,o7},{o1,o4,o8,o9},{o1,o4,o6,o9},{o2,o3,o7,o8},{o1,o3,o4,o8,o9},{o1,o2,o4,o6,o8},{o1,o2,o3,o4,o5,o6,o7,o8,o9}}。取X={o1}，則X∈B(LK)且LK(X)=X。取o8,o9∈O1，則o8,o9?LK(X)。因LK(X∪o9)=LK({o1,o9})={o1,o4,o9}，LK(X∪o8)=LK({o1,o8})={o1,o4,o8,o9}，故o9?LK(X∪o8)，而o8?LK(X∪o9)。由算法1知：LK不為O1上任何擬陣的閉包算子。

說明11(1) 在生物聚類分析中，若2個樣本具有完全相同的生物特征，則認(rèn)為兩者為一類。例4中的二元關(guān)系S在生物上是有意義的。

(2) 雖然例4中LK不為O1上任何擬陣的閉包算子，進(jìn)一步地，伽羅瓦格Gal(O,P,R1)與Gal(O1,P,R2)是同構(gòu)的[21,22]。故在昆蟲聚類分析中，對表4的分析也可說是對表5的聚類分析。對表4的聚類分析中，目前生物學(xué)家們常用聚類圖一種樹狀結(jié)構(gòu)圖，表示分析的結(jié)果。又由樹為一個無圈簡單圖，由此可以得該樹的圈擬陣[2,3,50]，該擬陣的獨(dú)立集族與閉集族完全一致。

(3) 從文獻(xiàn)[57]中對于表4的聚類結(jié)果，即文獻(xiàn)[57]中的圖1可知，將該圖從左向右看，圖中最上的坐標(biāo)標(biāo)尺為l,則可以得到以下結(jié)論：第0層(l=0)組成元有：{aj},j=1,…,16；第1層(l=1)組成元有：{[aj]S},j=1,…,16；第2層(0

從組成元與圖2對比可知：第0層為表4的對象集；第1層為表5的對象集；第2層中{[a3]S,[a14]S}為{o3,o8}在圖2的對應(yīng)節(jié)點(diǎn)，文獻(xiàn)[57]中圖1得到此點(diǎn)是根據(jù)[a3]S和[a14]S有共同的生物特征b6和b8，而在圖2中此節(jié)點(diǎn)為(o3o8,b6b8)。

事實(shí)上，擁有b3和b6昆蟲的是為{o1,o4,o8,o9}={[a1]S,[a4]S,[a14]S,[a16]S}={a1,a4,a5,a6,a8,a13,a14,a16}。即文獻(xiàn)[57]中的圖1沒能將擁有生物特征b3和b6的所有昆蟲全部找出來。圖2中{o1o4o8o9,b3b6}恰好將所有擁有生物特征b3和b6的昆蟲全部顯示的1個節(jié)點(diǎn)。繼續(xù)分析文獻(xiàn)[57]的圖1中第k層組成元(k=3,…,8)也會出現(xiàn)類似于上述關(guān)于第2層分析的情況。另外，圖2還給出了文獻(xiàn)[57]圖1中沒有出現(xiàn)的其它一些節(jié)點(diǎn)，如(o1o3o4o8o9,b6)，它們在生物上也是有意義的，這里不再展開。分析發(fā)現(xiàn)圖2在生物上是有意義的。圖2也是一個圖，一定存在多個生成樹，哪一個生成樹更能體現(xiàn)所研究的生物背景的聚類結(jié)構(gòu)，將是今后數(shù)學(xué)和生物學(xué)者們共同考慮研究的問題。

6 結(jié)束語

通過分析擬陣、背景、伽羅瓦連接、閉包算子之間的關(guān)系，得到背景之間同構(gòu)定義的一種拓廣形式，即伽羅瓦同構(gòu)。進(jìn)一步地，得到在何種條件下，一個擬陣的閉包算子為一個背景產(chǎn)生的伽羅瓦連接。再者，用這種關(guān)系，得到由伽羅瓦連接構(gòu)建擬陣的2種方法。

在未來：(1) 對背景(O,P,R)，將會研究如何選取已有構(gòu)造概念格的算法，找到檢查(O,P,R)是否為一個伽羅瓦背景的新算法。(2)在伽羅瓦背景或說在伽羅瓦連接幫助下，得到新的擬陣閉包公理，搜尋到更多擬陣族的格結(jié)構(gòu)。(3)考慮將擬陣應(yīng)用到生物聚類分析的研究中。