基于同構(gòu)理論的三支概念格的構(gòu)造方法與算法研究

錢婷 ，趙思雨 ，王軍濤

（1.西安石油大學(xué)理學(xué)院,陜西西安710065；2.咸陽師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,陜西咸陽712000；3.西北大學(xué)概念認(rèn)知與智能研究中心,陜西西安710127）

0 引 言

為了給格理論提供一個(gè)實(shí)際應(yīng)用的載體，德國數(shù)學(xué)家WILLE于1982年結(jié)合哲學(xué)中概念的定義及其層次結(jié)構(gòu)，提出了形式概念分析理論[1]。近年來，形式概念分析在中醫(yī)藥成分分析[2]、專家系統(tǒng)[3]、數(shù)據(jù)挖掘以及軟件工程[4]等領(lǐng)域得到了廣泛應(yīng)用，已經(jīng)成為數(shù)據(jù)分析與知識發(fā)現(xiàn)的有效工具。

形式概念分析與其他理論相結(jié)合，產(chǎn)生了多種不同的概念格模型,而對這些模型的進(jìn)一步研究成了學(xué)者們關(guān)注的熱點(diǎn)。2014年,祁建軍等[5]結(jié)合三支決策與形式概念分析理論提出了三支概念分析理論，此理論包括OE-概念格與AE-概念格2種模型[6-7]。隨后，三支概念格的構(gòu)造理論[8-9]、屬性約簡理論[10]、不完備形式背景的三支理論[11]等相繼被提出。基于這些理論，SHIVHARE等[12]結(jié)合BAM解釋了三支概念,并討論了認(rèn)知記憶如何以自然的方式進(jìn)行決策。此外，LI等[13]還研究了三支概念的認(rèn)知理論。

綜合以往研究，筆者發(fā)現(xiàn)，同一形式背景下，三支概念格的結(jié)構(gòu)明顯較概念格復(fù)雜，而有關(guān)概念格的構(gòu)造理論已有豐富的研究成果[14-16]。因此，對于三支概念格的理論研究，提出以下思考:

首先，能否直接利用已有的概念格理論研究三支概念格。目前已有不少學(xué)者從形式背景、屬性特征角度研究概念格[17-18]，如智慧來等[17]基于必然屬性給出了概念格中的粒描述。事實(shí)上，YU等[19]從代數(shù)的角度刻畫了與三支概念格同構(gòu)的結(jié)構(gòu)，但并未從形式背景的角度研究同構(gòu)問題。其次，能否通過刻畫形式背景的特點(diǎn)，得到概念格與三支概念格之間的關(guān)系，特別是同構(gòu)關(guān)系。

基于上述分析及思考，本文主要研究某種特殊形式背景，并討論在此背景下概念格與OE-概念格之間的關(guān)系，進(jìn)一步給出OE-概念格的構(gòu)造方法。

1 基礎(chǔ)知識

1.1 形式概念分析

定義1[20]稱(G,M,I)為一個(gè)形式背景，其中G為對象集，G中每個(gè)元素稱為一個(gè)對象;M為屬性集，M中每個(gè)元素稱為一個(gè)屬性；I為G和M之間的二元關(guān)系，即I?G× M。若(g,m)∈I，則表示對象g擁有屬性m，也記為gIm。

在對象子集X?G和屬性子集A?M上定義一對對偶算子：

X*表示X中所有對象共同具有的屬性集合，A*表示共同具有A中所有屬性的對象集合。如果一個(gè)二元組 (X,A)滿足X*=A，且A*=X，則稱 (X,A)是一個(gè)形式概念，簡稱概念。其中，X為概念的外延，A為概念的內(nèi)涵。當(dāng)X={g}(A={m})時(shí),X*={g}*=g*(A*={m}*=m*)。

性質(zhì)1[20]對于形式背景(G,M,I)，有以下基本性質(zhì)(?X1,X2,X?G且?B1,B2,B?M):

用L(G,M,I)表示形式背景(G,M,I)的全體概念，LE(G,M,I)表示所有概念外延構(gòu)成的集合。在偏 序關(guān)系(X1,A1)≤(X2,A2)?X1?X2(A1? A2)下，可以證明

也是概念，從而L(G,M,I)是格，并且是完備格，稱其為形式背景(G,M,I)的概念格(文中稱為經(jīng)典概念格)。

定義 2[20]設(shè)K1=(G,M,I)，K2=(H,N,J)是 2個(gè)形式背景。α,β分別為G到H，M到N的雙射。若 gIm?α(g)Jβ(m)，則稱 K1與 K2是同構(gòu)的。

基于上述定義,有

定理1[20]同構(gòu)的形式背景相應(yīng)的概念格是同構(gòu)的。

定義3[20]設(shè)(G,M,I)為形式背景，對于任意對象 g,h，若 g*=h*?g=h，且對于任意屬性 m,n，若m*=n*?m=n，則稱形式背景(G,M,I)為凈化形式背景。

事實(shí)上，本文所涉及的凈化形式背景可以弱化為只針對屬性凈化。

1.2 三支概念格

結(jié)合形式概念分析與三支決策的思想，QI等[6-7]提出了三支概念分析。首先，給出集合間的運(yùn)算規(guī)律。

設(shè)G是一個(gè)非空有限集合，?(G)是G的冪集，?(G)=?(G)×?(G)。對于(X,Y),(Z,W)∈?(G)，定義

與形式概念分析不同的是，三支概念分析不僅考慮原背景上“共同擁有”的信息，也進(jìn)一步考慮了補(bǔ)背景上“共同不擁有”的信息。針對“共同不擁有”的信息，QI等[6-7]提出以下算子。

定義4[6-7]設(shè)(G,M,I)是一個(gè)形式背景，X?G,A?M，負(fù)算子定義如下:

相對于上述負(fù)算子，QI等[6-7]稱原背景上的*算子為正算子，并將形式背景的正算子與負(fù)算子相結(jié)合，給出了三支算子的定義與性質(zhì)。

定義5[6-7]設(shè)(G,M,I)是一個(gè)形式背景，X,Y?G,A,B?M，一對由對象導(dǎo)出的三支算子定義如下:

性質(zhì)2[6-7]對象導(dǎo)出的三支算子有以下性質(zhì):

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

定義6[6-7]設(shè)(G,M,I)是一個(gè)形式背景，X?G，A,B?M。若X?=(A,B)且(A,B)?=X，則稱(X,(A,B))為由對象導(dǎo)出的三支概念，簡稱OE-概念。其中X為(X,(A,B))的外延，(A,B)為OE-概念的內(nèi)涵。

記所有OE-概念外延構(gòu)成的集合為OELE(G,M,I)，所有OE-概念構(gòu)成的集合為OEL(G,M,I)。在偏序關(guān)系(X1,(A1,B1))≤(X2,(A2,B2))(A2,B2)?(A1,B1)X1?X2下，OEL(G,M,I)構(gòu)成完備格。

2 三支概念格與概念格的同構(gòu)關(guān)系

以下研究在何種形式背景下，三支概念格與概念格是同構(gòu)的。首先研究形式背景中關(guān)系特殊的一對屬性。

定義7設(shè)(G,M,I)為形式背景，a∈M。若存在b∈M，有a*∩b*=? 且a*∪b*=G，則稱b為a的對偶屬性。

由上述定義，易得

性質(zhì)3設(shè)(G,M,I)為形式背景，a,b,c∈M，

(1)若b為a的對偶屬性，則a也為b的對偶屬性;

(2)若b,c均為a的對偶屬性，則b*=c*。

下面通過具體例子說明對偶屬性的特征。

例1設(shè)(G,M,I)為形式背景，G={1,2,3}，M={a,b,c,d}，I的關(guān)系如表1所示。由定義7知，屬性c為屬性b的對偶屬性。

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

基于上述對偶屬性，下面給出一種特殊的形式背景。

定義8設(shè)(G,M,I)為形式背景，若對于任意a∈M，均存在對偶屬性，則稱(G,M,I)為屬性對偶背景。

例2(續(xù)例1) 形式背景如表1所示。由定義7知，a的對偶屬性為d，b的對偶屬性為c，c的對偶屬性為b，d的對偶屬性為a。故由定義8知，(G,M,I)為屬性對偶背景。

下面討論屬性對偶背景的性質(zhì)。

定理2若(G,M,I)為凈化的屬性對偶背景，則|M|為偶數(shù)。

證明因?yàn)?G,M,I)為屬性對偶背景，所以對于任意的a∈M均存在對偶屬性。下證對偶屬性唯一。

若b，c均為a的對偶屬性，顯然b*=c*，此與(G,M,I)為凈化背景矛盾。因此，對于任意的a∈M，有且僅有一個(gè)對偶屬性，從而屬性成對存在，故|M|為偶數(shù)。

證畢。

定理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?*; 同時(shí)，由IC=G×MI知,Gm?*=m?-*, 所以m*=m?-*。因此g∈m?-*，即gIC m?。

因?yàn)間=α(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)。

設(shè)(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(續(xù)例1) 表1中，(G,M,I)為凈化的屬性對偶背景。L(G,M,I),L(G,M,IC)及OEL(G,M,I)分別如圖1～圖3所示。3個(gè)格圖清晰地展示了3個(gè)格之間的同構(gòu)關(guān)系。

思考當(dāng)(G,M,I)不是凈化的對偶背景時(shí)，L(G,M,I)與OEL(G,M,I)的同構(gòu)關(guān)系是否存在？

事實(shí)上，若(G,M,I)是對偶背景但不是凈化背景，即對于a∈M，存在多個(gè)對偶屬性，假設(shè)存在2個(gè)對偶屬性b,c,由性質(zhì)3，易知b*=c*。則根據(jù)約簡的性質(zhì)可知，在構(gòu)造格時(shí)，c可看作可約屬性，進(jìn)而可將原背景化為凈化的對偶背景。由此可以將定理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)。

進(jìn)一步，當(dāng)(G,M,I)不是對偶背景，即當(dāng)某一屬性a∈M不存在對偶屬性時(shí)，L(G,M,I)與OEL(G,M,I)的同構(gòu)關(guān)系是否存在？由此，進(jìn)一步研究形式背景屬性特征。

定義9設(shè)(G,M,I)為形式背景，a∈M，若存在ai∈M(i=1,2, …,t)，t≤|M|，使得Ga*=∩a*i, 則稱a為對偶可交屬性。

注1對偶屬性可以看成特殊的對偶可交屬性。

下面通過例子研究對偶可交屬性的特點(diǎn)。

例4設(shè)(G,M,I)為形式背景，G={1,2,3}，M={a,b,c,d,e}，I的關(guān)系如表2所示。由定義9知,Ga*=2=b*∩c*，故a為對偶可交屬性。

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

基于對偶可交屬性，下面給出另一種特殊的形式背景。

定義10設(shè)(G,M,I)為形式背景，若對于任意a∈M,a均為對偶可交屬性，則稱(G,M,I)為屬性對偶可交背景。

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

例5(續(xù)例4) 因G*=3=a*∩c*，故b為對偶可交屬性;因Gc*=1=a*∩d*，故c為對偶可交屬性;因Gd*=23=c*∩e*，故d為對偶可交屬性;因Ge*=1=a*∩d*，故e為對偶可交屬性。結(jié)合例4知，表2所對應(yīng)的形式背景(G,M,I)為屬性對偶可交背景。

基于上述定義及例子，很明顯有些對偶背景的性質(zhì)是不成立的。但仍有以下結(jié)論：

定理6若(G,M,I)為屬性對偶可交背景，則L E(G,M,IC)?L E(G,M,I)。

證明因?yàn)?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-*))。

首先證?為單射。因?yàn)?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)。因?yàn)?X,(A,B))∈OEL(G,M,I)，所以A=X*,B=X-*且X=A*∩B-*，顯然A為(G,M,I)的概念內(nè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)。又因?yàn)?A*,A)∈L(G,M,I)，所以X=A*。

最后證?為序同構(gòu)。若(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)的 序 同 構(gòu) ，即L(G,M,I)?OEL(G,M,I)。

證畢。

例6(續(xù)例4) 表2中，形式背景的L(G,M,I),L(G,M,IC)及 OEL(G,M,I)分別如圖 4～圖 6所示。3個(gè)格圖很明顯地展示了同一背景下3個(gè)格之間的關(guān)系。

圖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 判斷三支概念格與概念格同構(gòu)的方法

3.1 判斷形式背景是否為對偶（可交）背景的算法

基于第2節(jié)的討論，給出判定形式背景是否為對偶(可交)背景的算法。這里,假設(shè)形式背景都是普通的形式背景。

以下為判斷形式背景是否為屬性對偶背景的算法。

算法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)函數(shù)。

算法2fun(m)

N=fun(m)

N=?;

while(m1∈M{m})

N1=N;

while(n∈N1)

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

end

end

end

returnN;

通過調(diào)用算法2中的fun(m)函數(shù)，利用增量法可給出判斷形式背景是否為屬性對偶可交背景的算法。

算法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 同構(gòu)理論下三支概念格的構(gòu)造方法

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

定理8若(G,M,I)為屬性對偶背景，則OEL(G,M,I)={X(A,A?)|(X,A)∈L(G,M,I)且A?={a|a∈A}，其中a是a的對偶屬性。

當(dāng)形式背景是屬性對偶可交背景時(shí)，由定理7的證明過程知，三支概念格可通過概念格得到。

定理9若(G,M,I)為屬性對偶可交背景,則OEL(G,M,I)={(X(A,X*-)|(X,A)∈L(G,M,I)}。

4 結(jié) 語

三支概念分析理論較形式概念理論增加了負(fù)信息。事實(shí)上，同時(shí)利用正負(fù)信息進(jìn)行數(shù)據(jù)分析，所獲得的知識更全面。目前三支概念分析已發(fā)展成為數(shù)據(jù)分析與知識發(fā)現(xiàn)的有效工具。本文主要通過研究形式背景的特征，討論了三支概念格與概念格的同構(gòu)關(guān)系，證明了在屬性對偶背景及屬性對偶可交背景下，對象誘導(dǎo)的三支概念格與概念格是同構(gòu)的，并給出了判定其是否為屬性對偶背景和屬性對偶可交背景的方法。事實(shí)上，可將此理論進(jìn)一步推廣至屬性誘導(dǎo)的三支概念格與概念格的關(guān)系。