利用二部圖生成概念格

竇林立，展正然

形式概念分析又稱概念格[1-2]，是由德國(guó)Wille教授在20世紀(jì)80年代首次提出的，它提供了一種支持?jǐn)?shù)據(jù)分析和知識(shí)處理的數(shù)學(xué)工具[3-4]。近些年來(lái)，國(guó)內(nèi)外各位學(xué)者提出了許多的構(gòu)造算法。例如：Godin等[5]提出了概念格的漸進(jìn)生成算法；Ho[6]提出了基于概念格的概念聚類算法；張文修等[7]給出了在保持格同構(gòu)的條件下建立概念格的屬性約簡(jiǎn)的方法；Elloumi等[8]基于模糊形式背景建立了一個(gè)多層次的約簡(jiǎn)理論。

近幾年許多學(xué)者從圖論方面對(duì)概念格進(jìn)行研究。例如：Amilhastre 等[9]與 Berry 等[10-12]將二部圖與概念格進(jìn)行了交叉研究；李立峰等[13-14]利用弦二部圖和鏈圖對(duì)概念格進(jìn)行表示；張濤等[15-17]利用屬性樹和屬性拓?fù)鋱D來(lái)表示形式背景，簡(jiǎn)化了形式背景的表示結(jié)構(gòu)，并提出了基于樹圖的屬性約簡(jiǎn)算法。本文通過二部圖的極大完全子圖的概念來(lái)生成概念格，給出了基于二部圖的深度優(yōu)先的概念格的迭代算法。

1 基本概念

本節(jié)主要介紹概念格與二部圖的基本知識(shí)。關(guān)于概念格的更多內(nèi)容參見文獻(xiàn)[1,18]，有關(guān)圖論的詳細(xì)內(nèi)容參見文獻(xiàn)[19-20]。

1.1 概念格

定義1 1)在形式概念分析中，一個(gè)形式背景是一個(gè)三元數(shù)組，其中O是對(duì)象集合，M是屬性集合，I是O與M之間的一個(gè)二元關(guān)系。用表示“對(duì)象有屬性” 。對(duì)于及， 定 義 ：，。則形式背景的概念定義為元素對(duì)，其中，，，。概念的外延是A，內(nèi)涵是B。

通過上述兩種方法約簡(jiǎn)形式背景后，就可以有效地減少形式背景中屬性集合中的元素個(gè)數(shù)，從而降低生成概念格的難度，更迅速地生成概念格。

表1 形式背景(O,M,I)Table 1 Formal context (O,M,I)

表2 約簡(jiǎn)后的形式背景(O,M,I)Table 2 Reduced formal context (O,M,I)

1.2 圖論

由概念格和二部圖的定義可知，每個(gè)形式背景都對(duì)應(yīng)一個(gè)二部圖，其中二部圖的頂點(diǎn)集為，頂點(diǎn)與之間有一條邊當(dāng)且僅當(dāng)與滿足關(guān)系I。

下面用具體實(shí)例來(lái)說明以上定義。

例2 圖1是例1中約簡(jiǎn)后的形式背景表2對(duì)應(yīng)的二部圖，圖2是表2對(duì)應(yīng)的概念格，原形式背景表1對(duì)應(yīng)的概念格即為圖3。

圖1 表2對(duì)應(yīng)的二部圖Fig. 1 Bipartite graph for table 2

圖2 表2對(duì)應(yīng)的概念格Fig. 2 Concept lattice for table 2

圖3 表1對(duì)應(yīng)的概念格Fig. 3 Concept lattice for table 1

2 利用二部圖生成概念格

形式背景中的數(shù)據(jù)，在很多情況下，對(duì)象的個(gè)數(shù)較大，而屬性的個(gè)數(shù)則相對(duì)較少，在這種情況下，基于屬性來(lái)生成概念格，可以有效地減少算法的執(zhí)行時(shí)間。本文基于屬性，利用二部圖子圖和鄰集的知識(shí)來(lái)生成概念格。

本節(jié)中的形式背景是指約簡(jiǎn)后的形式背景，二部圖也指約簡(jiǎn)后的形式背景所對(duì)應(yīng)的二部圖。

首先給出二部圖的極大完全子圖的定義。

定義4 若 S 是二部圖 G 的子圖，且 S是完全二部圖，對(duì)任意的 v ∈V(G)?V(S)， G 由 V (S)∪v導(dǎo)出的子圖 G [V(S)∪v]不是完全二部圖，則 S稱為二部圖G的極大完全子圖。

下面給出二部圖的極大完全子圖與概念的對(duì)應(yīng)關(guān)系。

證明 由概念格的定義知充分性顯然成立。

下面的定理2和定理3就是利用二部圖的極大完全子圖得到頂層概念 (O ,?)的直接子概念。

定理2 形式背景 K =(O,M,I)對(duì)應(yīng)的二部圖為G=(O,M;E)，i 為圖 G 的頂點(diǎn)集 M 中度數(shù)最大的頂 點(diǎn) ， N(i)=P ，則i 與 P 構(gòu) 成 的 G 的 導(dǎo) 出 子 圖G[P∪i]是 G 的極大完全子圖，即 (P ,i)為概念，且(P,i)為頂層概念( O ,?)的直接子概念。

證明 用反證法。假設(shè) G [P∪i]不是 G的極大完全子圖，即存在 o ∈O?P ，有 S1=(P∪o,i;E1)為完全二部圖，或存在 m ∈M，有 S2=(P,i∪m;E2)為完全二部圖。若有第一種情況，則頂點(diǎn) i 與 P ∪o相鄰，此與 N (i)=P矛盾。若有第二種情況，由完全二部圖的定義知 i ∪m與P中每個(gè)頂點(diǎn)都相鄰，如果m的鄰集恰好為P，則i與m應(yīng)約簡(jiǎn)為im，與i和m是兩個(gè)頂點(diǎn)矛盾；如果m的鄰集包含P，即至少存在 o1∈O ，使 m 與 P ∪o1相鄰，則 m 的度數(shù)大于i的度數(shù)，此與i為 M 中 度數(shù)最大的頂點(diǎn)矛盾。因此，G[P∪i]是G的極大完全子圖，即 (P ,i)為概念。且其為頂層概念 (O ,?)的直接子概念，因?yàn)椴淮嬖诟拍?C ，使(P,i)＜C ＜ (O,?)。

定理3 若 j 是形式背景 K =(O,M,I)對(duì)應(yīng)的二部圖 G =(O,M;E)的頂點(diǎn)集 M 中除i外度數(shù)最大的頂點(diǎn)， N (j)=P?。若 P?? P ，則 (P?,j)為頂層概念(O,?)的直接子概念；若 P?? P ，則以 P?為外延的概念應(yīng)為 (P ,i)的子概念。

證明同定理2。

證明 (P ,i)為形式背景 K 的概念， ( Q,j)為形式背景 K?的概念，前文已證。下證 (Q ,i∪j)為形式背景 K 的概念，即需證 G Q,i∪j 為二部圖 G 的極大完全子圖。

用反證法。假設(shè) G Q,i∪j 不是二部圖 G 的極大完全子圖，那么可能有下列兩種情況：1）至少存在 o ∈P?Q,使 G Q∪o,i∪ j為完全二部圖；2）至少存在 m ∈M?i?j ，使 G Q,i∪ j∪m為完全二部圖。如果出現(xiàn)第一種情況，由完全二部圖的定義知在圖 S 中頂點(diǎn) j 與 Q ∪o中的每個(gè)頂點(diǎn)相鄰，此與在形式背景 K?中 N (j)=Q矛盾。如果出現(xiàn)第二種情況，由完全二部圖定義知在圖S中m與集Q中的每個(gè)頂點(diǎn)相鄰，那么m在S中的鄰集必包含j在S中的鄰集，這與形式背景已約簡(jiǎn)且j是S的頂點(diǎn)集中 度數(shù)最大的頂點(diǎn)相矛盾。所以為形式背景K的概念，并且不能找到集合B，使，因此 (Q ,i∪j)是( P ,i)的直接子概念。

根據(jù)定理4可以通過求 G 的導(dǎo)出子圖的概念來(lái)簡(jiǎn)化形式背景，并求出 (P ,i)的直接子概念。這樣經(jīng)過反復(fù)的分解和約簡(jiǎn)，使形式背景越來(lái)越簡(jiǎn)化，同時(shí)也能求出的所有子概念。

因此便能生成頂層概念的所有直接子概念以及它們各自的子概念。這便是基于二部圖的深度優(yōu)先的概念格的迭代算法。

基于二部圖的深度優(yōu)先的概念格的迭代算法：

1) 最頂層概念為 (O ,?)，標(biāo)號(hào)為1。

2) 形式背景 K =(O,M,I)(約簡(jiǎn)后)，其對(duì)應(yīng)的二部圖為 G =(O,M;E)，取屬性M中度數(shù)最大的頂點(diǎn)i ， N (i)=P ，則 (P ,i)為頂層概念 (O ,?)的直接子概念，標(biāo)號(hào)為21。

3) 畫出 G 的導(dǎo)出子圖 S1=G[P∪(N(P)?i)](約簡(jiǎn)后)，其對(duì)應(yīng)的形式背景為 K1。取二部圖 S1的屬性集 N (P)?i 中度數(shù)最大的頂點(diǎn) i1， N (i1)= P1，則(P1,i1)為形式背景 K1的概念， ( P1,i∪i1)為形式背景K 中概念 (P ,i)的直接子概念，標(biāo)號(hào)為31。

4) 畫出 S1的導(dǎo)出子圖S2=S1[P1∪(N(P1)?i1)](約簡(jiǎn)后)，其對(duì)應(yīng)的形式背景為 K2，取二部圖 S2的屬性集 N (P1)?i1中度數(shù)最大的頂點(diǎn) i2， N (i2)=P2，則 (P2,i2)為形式背景 K2的概念，故 (P2,i∪i1∪i2)為形式背景K中概念 (P1,i∪i1)的直接子概念，標(biāo)號(hào)為41。繼續(xù)下去，直到 Pl為 單點(diǎn)集，則(Pl,i∪i1∪i2···∪il)為形式背景K的倒數(shù)第二層概念，它由導(dǎo)出子圖Sl生成，其直接子概念為最底層概念 (? ,M)，標(biāo)號(hào)為 (l +2)1，最底層概念 (? ,M)的標(biāo)號(hào)為 l+ 3。

5) 從標(biāo)號(hào)為 r1 的概念回到生成它的導(dǎo)出子圖Sr?2，考察二部圖 Sr?2的屬性集中未考慮過的度數(shù)最大的頂點(diǎn) ir?2?。如果 N (ir?2?)=Pr?2?是已生成的概念的外延，且當(dāng)此已生成概念的內(nèi)涵包含i∪i1∪i2···∪ir?2?時(shí)，說明以 Pr?2?為外延的概念及其子概念已生成，則不必再考慮此頂點(diǎn)；而當(dāng)此已生成概念的內(nèi)涵等于時(shí)，則是的直接子概念，且此概念及其子概念已生成(已標(biāo)號(hào))，此頂點(diǎn)也不必再往下考慮。如果 Pr?2?不 是 已 生 成 概 念 的 外 延 ， 則 (Pr?2?,ir?2?)是(Pr?1,ir?1)的直接子概念，標(biāo)號(hào)為 (r ?1)2，然后按步驟3）和步驟4）的方法畫出 Sr?2的導(dǎo)出子圖Sr?1?=Sr?2[Pr?1?∪ (N(Pr?1?)? ir?1?)]，接著再取未考慮過的最大度數(shù)頂點(diǎn)生成概念，直到倒數(shù)第二層概念。

3 實(shí)例

下面通過例3來(lái)具體說明此方法如何產(chǎn)生概念格。

例3 形式背景同例1，其中的對(duì)象O={1,2,3,4,5,6,7}表示1班至7班共7個(gè)班級(jí)，屬性M={a,b,c,d,e,f,g}表示班級(jí)特色，其中a表示團(tuán)結(jié)，b表示紀(jì)律嚴(yán)明，c表示學(xué)風(fēng)端正，d表示衛(wèi)生環(huán)境好，e表示干部隊(duì)伍過硬，f表示英語(yǔ)四六級(jí)通過率高，g表示課余活動(dòng)豐富。

下面用基于二部圖的深度優(yōu)先的概念格的迭代算法來(lái)生成概念格。

1) 最頂層概念為 (1 234567,?)，標(biāo)號(hào)為1。

2) 畫出形式背景(約簡(jiǎn)后)所對(duì)應(yīng)的二部圖G，其屬性中度數(shù)最大的頂點(diǎn)為 b ，N(b)={1,3,4,5,6}，故 (1 3456,b)為 (1 234567,?)的直接子概念，標(biāo)號(hào)為21。

3) 畫出 G 的由 P ={1,3,4,5,6}和 N (P)?b={a,c,df,e}導(dǎo)出的子圖 S1，二部圖 S1的屬性集中度數(shù)最大的頂點(diǎn) c ， N (c)={1,4,5,6}，故 (1 456,bc)為(13456,b)的直接子概念，標(biāo)號(hào)為31。

4) 畫出 S1的由 P1={1,4,5,6}和 N (P1)?c={a,df,e}導(dǎo)出的子圖 S2，二部圖 S2的屬性集中度數(shù)最大的頂點(diǎn) a ， N (a)={1,6}，故 (1 6,abc)為 (1 456,bc)的直接子概念，標(biāo)號(hào)為41。畫出 S2的由 P2={1,6}和N(P2)?a={e}導(dǎo)出的子圖 S3，二部圖 S3的屬性集中度數(shù)最大的頂點(diǎn) e ， N (e)={1}，故 (1 ,abce)為(16,abc)的直接子概念，標(biāo)號(hào)為51。此時(shí) P3={1}為單點(diǎn)集，故 (1 ,abce)為倒數(shù)第二層概念，其直接子概念只有 (? ,abcdef)， ( ?,abcdef)為最底層概念，標(biāo)號(hào)為6。

5) 從標(biāo)號(hào)為51的概念 (1 ,abce)開始返回到生成它的二部圖 S3，其屬性集中除 e外無(wú)其他頂點(diǎn)。所以返回到標(biāo)號(hào)為41的概念 (1 6,abc)的二部圖 S2，其屬性集中除 a 外還有頂點(diǎn) d f 和 e 。先看 d f，N(df)={5}，未出現(xiàn)過以5為外延的概念，故(5,bcdf)為 (1 456,bc)的直接子概念，標(biāo)號(hào)為42，此時(shí)P2?={5}為單點(diǎn)集，故 (5 ,bcdf)為倒數(shù)第二層概念，其直接子概念只有 (? ,abcdef)。再看 e ， N (e)={1}，已出現(xiàn)過以1為外延的概念 (1 ,abce)，且其內(nèi)涵 a bce真包含 b ce，故此處不再考慮。

現(xiàn)在返回到生成標(biāo)號(hào)為31的概念 (1 456,bc)的二部圖 S1，其屬性集中除 c 外還有頂點(diǎn) a ,df,e。其中N(a)={1,6}， N (e)={1}，已出現(xiàn)過以16和1為外延的概念 (1 6,abc)和 (1 ,abce)，且其內(nèi)涵真包含 a b和be ，故此二頂點(diǎn)不再考慮。而 N (df)={3,5}，未出現(xiàn)過以35為外延的概念，故 (3 5,bdf)為 (1 3456,b)的直接子概念，標(biāo)號(hào)為32。然后接著畫出 S1的由P1?={3,5}和N(P1?)?df={c}導(dǎo)出的子圖 S2??，二部圖S2??的屬性集中度數(shù)最大的頂點(diǎn)為 c ， N (c)={5}，已出現(xiàn)過以5為外延的概念 (5 ,bcdf)，此概念的內(nèi)涵恰好為 b cdf ，則 (5 ,bcdf)也為 (3 5,bdf)的直接子概念，此頂點(diǎn)不再考慮。

現(xiàn)在返回到生成標(biāo)號(hào)為21的概念 (1 3456,b)的二部圖 G ，其屬性集中除 b外 ，還有 a、 c 、 d f 和 e。其中N(a)={1,6}，N(c)={1,4,5,6}，已出現(xiàn)過以16和1456為外延的概念 (1 6,abc)和 (1 456,bc)，且其內(nèi)涵真包含 a和 c，故此二頂點(diǎn)不再考慮。 N (df)={2,3,5}，未出現(xiàn)過以235為外延的概念，故 ( 235,df)為(1234567,?)的直接子概念，標(biāo)號(hào)為22。然后接著畫出 G 的由 P?={2,3,5}和 N (P?)?df = {b,c,e}導(dǎo)出的子圖 S1?，二部圖 S1?的屬性集中度數(shù)最大的頂點(diǎn)為b，N(b)={3,5}，已出現(xiàn)過以35 為外延的概念 (3 5,bdf)，此概念的內(nèi)涵恰好為 b df ，則 (3 5,bdf)也為(235,df)的直接子概念，此頂點(diǎn)不再考慮。 S1?的屬性集中除 b 外，還有 c 和 e ， N (c) = {5}，已出現(xiàn)外延為5的概念 (5 ,bcdf)，且其內(nèi)涵真包含 c df，故此頂點(diǎn)不再考慮。 N (e)={2}，未出現(xiàn)過以2為外延的概念，故(2,def)為 (2 35,df)的直接子概念，標(biāo)號(hào)為33。此時(shí)其外延 P1?={2}為單點(diǎn)集，其直接子概念只有(?,abcdef)。

返回二部圖 G 中的屬性 e ， N (e)={1,2,7}，未出現(xiàn)過以127為外延的概念，故 (1 27,e)為(1234567,?)的直接子概念，標(biāo)號(hào)為23。接著畫出G的由P??={1,2,7}和N(P??)?e={a,b,c,df}導(dǎo)出的子圖 S1??，二部圖 S1??的屬性集中 a 、b 、c的鄰集相等，約簡(jiǎn)后屬性集中度數(shù)最大的頂點(diǎn)為 a bc 和 d f ， N (abc)={1}，N(df)={2}，已出現(xiàn)過以1和2為外延的概念(1,abce)和 (2 ,def)，其內(nèi)涵恰好為 a bce 和 d ef，則(1,abce)和 (2 ,def)也為 (1 27,e)的直接子概念，此二頂點(diǎn)不再考慮。

到此已生成所有概念，見圖4。其概念格見圖3。

圖4 生成概念格的過程Fig. 4 Process of generating concept lattice

4 結(jié)束語(yǔ)

本文結(jié)合圖論的內(nèi)容，將概念格的形式背景和一個(gè)二部圖相對(duì)應(yīng)，利用二部圖的極大完全子圖來(lái)尋找概念，并且同時(shí)得到概念之間的父子關(guān)系，最終構(gòu)造出概念格。此方法同時(shí)生成Hasse圖，簡(jiǎn)單直觀，能夠快速生成概念格?；诟拍罡竦男问奖尘芭c圖論內(nèi)容的高度關(guān)聯(lián)性，二者之間其余理論的相互應(yīng)用是我們下一進(jìn)努力的方向。