石慧，何苗，魏玲

(西北大學(xué) 數(shù)學(xué)系，陜西 西安 710127)

德國數(shù)學(xué)家R.Wille 于1982年首先提出了形式概念分析理論[1], 用于概念的發(fā)現(xiàn)、排序和顯示。 形式背景與形式概念是形式概念分析的基本概念, 形式概念是由形式背景中的對象集和屬性集組成的統(tǒng)一體, 形式概念之間可形成一種有序的層次結(jié)構(gòu)，即概念格, 概念格的構(gòu)造[2-5]是形式概念分析理論的主要研究內(nèi)容之一。目前, 已提出的概念格構(gòu)造方法主要有2種, 增量算法與批處理算法。 增量算法是在數(shù)據(jù)信息不確定或不完整的情況下, 當(dāng)有少量數(shù)據(jù)變動時, 對已經(jīng)構(gòu)造的概念格進(jìn)行更新和維護(hù)[3,6]; 批處理算法是在數(shù)據(jù)比較完整的情況下，依據(jù)形式背景初次構(gòu)造概念格的一種更有效的方法，它主要分為枚舉、自頂向下和自底向上3種算法[7-8]。 此外, 還有將大背景橫向拆分為若干小形式背景, 再將各小形式背景的概念格進(jìn)行橫向合并, 從而構(gòu)建出相應(yīng)的原形式背景概念格的方法[9]; 以及從對象集的每一個等價類所擁有的屬性子集之間的包含關(guān)系出發(fā)，構(gòu)造相應(yīng)的Hasse圖，從而得到概念格[10]的方法。 本文對并不可約元(交不可約元)下集格中的元素定義運算, 得到相應(yīng)概念格的內(nèi)涵集(外延集), 進(jìn)而擴(kuò)充為概念。

1 理論基礎(chǔ)

定義1[11]稱(G,M,I)為一個形式背景, 其中G={g1,g2,...,gt}為對象集, 每個gi(i≤t)稱為一個對象;M={m1,m2,…,ms}為屬性集, 每個mj(j≤s)稱為一個屬性;I為G和M之間的二元關(guān)系I?G×M。 若(g,m)∈I, 則稱g具有屬性m, 用gIm表示; 否則, 記為gm。

對于形式背景(G,M,I), 在對象集X?G和屬性集B?M上分別定義運算:

X={mm∈M, ?g∈X,gIm}

B={gg∈G, ?m∈B,gIm}

?g∈G, 記{g}為g; ?m∈M, 記{m}為m。 若?g∈G,g≠,g≠M, 且?m∈M,m≠,m≠G, 則稱形式背景(G,M,I)是正則的。 本文提到的形式背景都是正則的。

定義2[11]設(shè)(G,M,I)是形式背景, 對X?G,B?M, 若滿足X=B且X=B′, 則稱(X,B)是一個形式概念, 簡稱概念; 其中X稱為概念的外延,B稱為概念的內(nèi)涵。 形式背景(G,M,I)的全體概念記為L(G,M,I)。

? (X1,B1), (X2,B2)∈L(G,M,I),

定義:

(X1,B1) ∧ (X2,B2) = (X1∩X2, (B1∪B2)′)

(X1,B1) ∨ (X2,B2) = ((X1∪X2)′,B1∩B2)

則L(G,M,I)是完備格, 稱為概念格。

定義3[11]設(shè)(G,M,I)為形式背景,?g∈G,m∈M, 稱(g′,g)為對象概念, (m′,m′)為屬性概念。

定義4[12]設(shè)L是格, 若滿足下列條件, 則稱x∈L是并不可約元：

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

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

對偶地, 可得到交不可約元的定義。 格L的全體并不可約元記為J(L), 交不可約元記為M(L)。

定義5[12]設(shè)P為一個偏序集,Q?P, 如果?x∈Q,y∈P且y≤x時有y∈Q, 則稱Q為下集。 記P的所有下集為ο(P), 稱ο(P)為P的下集格。

定理1[12]設(shè)L為有限格,L中的任意元素可表示成某些并不可約元(交不可約元)的并(交)。

定義6[11]設(shè)(G,M,I)為形式背景, ?g∈G,m∈M:gmgm, 并且, 若g?h且g≠h, 則有hIm;gmgm, 并且, 若m′?n′且m′≠n′, 則有g(shù)In;gmgm并且gm。

定理2[11]下面斷言對每個背景都成立：

1) 對象概念(g′,g)是并不可約元存在一個m∈M，使gm;

2) 屬性概念(m′,m′)是交不可約元存在一個g∈G，使gm;

下面斷言對每個有限背景都成立：

3) 對象概念(g′,g)是并不可約元存在一個m∈M，使gm；

4) 屬性概念(m′,m′)是交不可約元存在一個g∈G，使gm。

記：LG(G,M,I)={X(X,B)∈L(G,M,I)}是概念格L(G,M,I)所有外延構(gòu)成的集合;

LM(G,M,I)={B(X,B)∈L(G,M,I)}是概念格L(G,M,I)所有內(nèi)涵構(gòu)成的集合;

JG(L)={X(X,B)∈J(L)}為概念格L(G,M,I)的并不可約元的外延集;

MM(L)={B(X,B)∈M(L)}為概念格L(G,M,I)的交不可約元的內(nèi)涵集。

2 基于不可約元下集格的概念獲取

本節(jié)主要給出通過不可約元做下集格, 再定義映射找到全部概念的方法。 首先, 根據(jù)定義6確定形式背景中的箭頭關(guān)系, 根據(jù)定理2找到該形式背景所對應(yīng)概念格的并不可約元, 其次對并不可約元的外延集做下集格, 再對下集格中的元素定義映射, 從而得到概念格的全部內(nèi)涵集, 進(jìn)一步得到全部概念。 利用對偶性, 對交不可約元的內(nèi)涵集做下集格, 定義相應(yīng)的映射, 得到概念格的全部外延集, 進(jìn)而得到所有概念。

定義映射f1:ο(JG(L))→LM(JG(L))如下: ?χ∈ο(JG(L)),f1(χ)=∩Xi=(∪Xi),Xi∈χ, 且將ο(JG(L))中所有元素的像集記為LM(JG(L))。

性質(zhì)1 映射f1:ο(JG(L))→LM(JG(L))具有以下性質(zhì):1)f1是滿射;2)f1具有逆序性, 即?χ1,χ2∈ο(JG(L)), 若χ1?χ2, 則f1(χ2)?f1(χ1)。

證明1) 根據(jù)f1的定義,LM(JG(L))中的元素均是由ο(JG(L))中元素的元素取并然后做*運算得到的。 即 ?B∈LM(JG(L)), ?χ∈ο(JG(L))使f1(χ)=B;

2) 當(dāng)χ1?χ2時有∪?Xi?∪Xj,Xi∈χ1,Xj∈χ2。由于f1(χ)=(∪X)(X∈χ), 且*算子有逆序性, 即對X1?X2, 有X2?X1, 從而有:f1(χ2)?f1(χ1)。

定理3LM(JG(L))=LM(G,M,I)。

證明一方面: ?B∈LM(JG(L)), ?χ∈ο(JG(L)), 使f1(χ)=B, 令χ=∪Xi, (Xi∈χ)。 即有χ=B。 又根據(jù)*算子的性質(zhì)知道χ=χ′, 即?χ∈ο(JG(L)), 使B=χ′。 所以有B∈LM(G,M,I)。

另一方面: ?A∈LM(G,M,I), 設(shè)y=A′, 顯然有(y,A)∈L(G,M,I)。 由于概念格中的每一對概念都可以由并不可約元的并得到。 從而?y∈ο(JG(L)),y=∪Yi, (Yi∈y)。 又A∈LM(G,M,I),χ=A′=A, 因此A∈LM(JG(L)), 得證。

該結(jié)論表明: 并不可約元外延集的下集格經(jīng)f1映射后得到的集合為相應(yīng)概念格的內(nèi)涵集。 進(jìn)一步, 可對所有內(nèi)涵做′算子得到相應(yīng)的外延, 進(jìn)而得到概念。對偶地, 下面給出從交不可約元出發(fā)獲取其下集格及所有概念的過程。

定義映射f2:ο(MM(L))→LG(MM(L))如下: ?А∈ο(MM(L)),f2(χ)=∩Aj′=(∪Aj)′,Aj∈A, 且將ο(MM(L))中的所有元素的像集記為LG(MM(L))。

性質(zhì)2f2:ο(MM(L))→LG(MM(L))具有以下性質(zhì):1)f2是滿射；2)f2具有逆序性, 即?A1,A2∈ο(MM(L)), 若A1?A2, 則f2(A2)?f2(A1)。

證明1) 根據(jù)f2的定義,LG(MM(L))中的元素均是由ο(MM(L))中元素的元素取并再做′運算得到的。 即?X∈LG(MM(L)), ?A∈ο(MM(L))使f2(A)=X。

2)當(dāng)A1?A2時有∪Ai?∪Aj,Ai∈A1,Aj∈A2。 由于f2(A)= (∪A)′且′算子有逆序性, 即對A1?A2, 有A2′?A1′, 從而有:f2(A2)?f2(A1)。

定理4LG(MM(L))=LG(G,M,I)。

證明一方面: ?X∈LG(MM(L)), ?A∈ο(MM(L)), 使f2(A)=X。 令χ=∪Ai, (Ai∈χ)。 即有A′=X。 又根據(jù)′算子的性質(zhì)，知道A′=A′′, 即?A∈ο(MM(L)), 使X=A′′。 所以有X∈LG(G,M,I)。

另一方面: ?Y∈LG(G,M,I), 設(shè)C=Y, 顯然有(Y,C)∈L(G,M,I)。 由于概念格中的每一對概念都可以由交不可約元的交得到。 從而?C∈ο(MM(L)),C=∪Ci, (Ci∈C)。 又由于Y∈LG(G,M,I),C′=Y′=Y, 因此Y∈LG(MM(L)), 得證。

該結(jié)論表明: 交不可約元屬性集的下集格經(jīng)f2映射后得到的集合為相應(yīng)概念格的外延集。 進(jìn)一步，可對所有外延做算子得到相應(yīng)的內(nèi)涵, 進(jìn)而得到概念。

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

表1 形式背景(G,M,I)

首先, 根據(jù)定義2.6給出該形式背景的箭頭關(guān)系, 如表2所示。

表2 箭頭關(guān)系下的形式背景(G,M,I)

由表2的箭頭關(guān)系以及定理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)}。 因此,JG(L)={{1}, {2}, {2, 3}, {4, 5}}。 其Hasse圖如圖1所示：

圖1 JG(L)的Hasse圖Fig.1 Hasse of JG(L)

根據(jù)Hasse圖可得：ο(JG(L))={,{{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}}}。

?χ∈ο(JG(L)), 計算f1(χ), 得到:

LM(JG(L))={M, {a,c,e}, {a,b,d,e}, {b,c,d}, {a,e}, {c}, {a,b,e}, {b,d}, ,}。

由定理3可知該屬性集合為L(G,M,I)的全部內(nèi)涵，擴(kuò)充為概念后可得:L(G,M,I)={(,M), (1,ace), (2,abde), (45,bcd), (23,abe), (245,bd), (145,c), (123,ae), (2345,b), (G,)}。

概念格如圖2所示:

圖2 L(G,M,I)Fig.2 L(G,M,I)

對偶地, 由表2的箭頭關(guān)系以及定理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)}。 因此,MM(L)={{a,e},,{c},{b,d}}。 其Hasse圖如圖3所示：

圖3 MM(L)的Hasse圖Fig.3 MM(L)

根據(jù)Hasse圖, 可得

ο(MM(L))={,{{a,e}},{},{{c}},{{a,e},}, {{a,e},{c}},{,{c}},{{b,d},},{{a,e},{b,d},}, {{a,e},,{c}},{{b,d},,{c}},{{a,e},{b,d},, {c}}}。

?A∈ο(MM(L)), 計算f2(A)得到

LG(MM(L))={G,{1},{2},{4,5},{2,3},{2,4,5},{1,4,5}, {1,2,3},{2,3,4,5},}。

由定理4可知該對象集合為L(G,M,I)的全部外延。擴(kuò)充為概念后可得:L(G,M,I)={(,M),(1,ace),(2,abde),(45,bcd),(23,abe), (245,bd), (145,c),(123,ae), (2345,b), (G,)}。概念格如圖4所示。

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

在實際問題中, 由于受到各種原因的影響, 有可能導(dǎo)致形式背景的部分對象與屬性之間出現(xiàn)關(guān)系缺失的現(xiàn)象, 即這部分對象與屬性之間是否存在關(guān)系無法獲知, 在概念格理論中, 將這種含有缺失值的形式背景稱為不完備形式背景。 針對不完備形式背景, 可以根據(jù)不完備形式背景的決策信息對缺失的信息進(jìn)行預(yù)測, 從而將其補全為完備的形式背景[13]; 也可以利用模糊關(guān)系的多劃分技術(shù), 得到其完備化模型[14]。 本節(jié)給出基于前文方法的不完備形式背景的完備化。

圖4 L(G,M,I)Fig.4 L(G,M,I)

在本節(jié)中, 不完備形式背景的缺失信息用#表達(dá)。 將#全部替換為0, 得到的形式背景記為(G,M,I1), 相應(yīng)的概念格記為L1; 將#全部替換為1, 得到的形式背景記為(G,M,I2), 相應(yīng)的概念格記為L2。

本節(jié)借用上節(jié)概念獲取的方法, 對不完備形式背景的缺失信息進(jìn)行補全。 首先, 分析形式背景(G,M,I1)與(G,M,I2), 由于其概念個數(shù)不同, 概念個數(shù)較多的信息系統(tǒng)所包含的信息要相對完整一些, 因而選擇從概念個數(shù)較多的形式背景出發(fā)對其完備化; 然后, 找到選擇出形式背景并不可約元外延集的下集格, 并對其中的元素在另一個形式背景上做映射f1，得到象集后構(gòu)造新集合; 最后定義映射將#映射為1或0。 對偶地, 找到其交不可約元的內(nèi)涵集, 利用相似方法對其進(jìn)行完備化。

定義集合P1={A|A∈LM(JG(L1)),X∈L1M(G,M,I1)且?m∈M，A≠m′或A∈LM(JG(L1)),A∈L1M(G,M,I1)且?m∈M，A≠m′}。 其中,L1M(G,M,I1)為L1的內(nèi)涵集;m′為(G,M,I2)的屬性概念的內(nèi)涵。

定義7 映射h11: # → {0,1}如下:

h11(#)=

定義集合Q1={X|X∈LG(MM(L1)),X?L1G(G,M,I1)且?g∈G,X≠g′或X?LG(MM(L1)),X∈L1G(G,M,I1)且?g∈G,X≠g′}。 其中,L1G(G,M,I1)為L1的外延集;g′為(G,M,I2)的對象概念的外延。

定義8 映射h12: # → {0,1}如下:

h12(#)=

相應(yīng)地, 定義集合P2={A|A∈LM(JG(L2)),X?L2M(G,M,I2)且?m∈M,A≠m′或A?LM(JG(L2)),A∈L2M(G,M,I2)且?m∈M,A≠m′}。 其中,L2M(G,M,I2)為概念格L2的內(nèi)涵集;m′為(G,M,I1)的屬性概念的內(nèi)涵。

定義9 映射h21: # → {0,1}如下:

h21(#)=

定義集合Q2={X|X∈LG(MM(L2)),X?L2G(G,M,I2)且?g∈G,X≠g′或X?LG(MM(L2)),X∈L2G(G,M,I2)且?g∈G,X≠g′}。 其中,L2G(G,M,I2)為概念格L2的外延集;g′為(G,M,I1)的對象概念的外延。

定義10 映射h22: # → {0,1}如下:

h22(#)=

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

表3 不完備形式背景(G,M,I,#)

表3中第1行的“#”符號, 表示對象1是否擁有屬性c是不確定的;該表中第2行的“#”符號, 表示對象2是否擁有屬性d是不確定的。

下面將其完備化：

1)將不完備形式背景(G,M,I,#)中的#全部替換為0,得到形式背景(G,M,I1), 如表4所示。將不完備形式背景(G,M,I,#)中的#全部替換為1,得到形式背景(G,M,I2), 如表5所示。

2)概念格L1如圖5所示,概念格L2如圖6所示:

顯然,L2的概念多, 所表達(dá)的信息更加完整, 下面從形式背景(G,M,I2)出發(fā), 對不完備形式背景(G,M,I,#)完備化。

3)概念格L2的并不可約元如下:

J(L2) ={(1,acd), (2,bd), (3,ace), (4,abe)}。

4)將所有并不可約元的外延構(gòu)成集合:JG(L2)={{1},{2},{3},{4}}。其Hasse圖如圖7所示。

表4 (G,M,I1)

表5 (G,M,I2)

圖5 概念格L1Fig.5 L(G,M,I)

圖6 概念格L2Fig.6 L(G,M,I)

圖7 JG(L2)的Hasse圖Fig.7 Hasse of JG(L2)

5)JG(L2) 的下集格如下:

ο(JG(L2))={,{{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)?χ∈ο(JG(L2)), 在形式背景(G,M,I1)上計算f1(χ), 可得LM(JG(L2))={M,{a},,{a,d},{a,e},{a,c,e},{a,b,e},}

7)根據(jù)集合P2的定義, 可得:P2={syggg00,{a,c},{b,d},{a,c,d}}

8)根據(jù)映射h21得到I(1,c)=0,I(2,d)=0。 從而得到補全后的完備的形式背景(G,M,I3)如表6所示:

表6 完備形式背景(G,M,I3)

對偶地, 從L2交不可約元出發(fā)對不完備形式背景完備化。

1)概念格L2的交不可約元如下:

M(L2)={{134,a},{12,d},{24,b},{34,ae},{13,ac}}

2)將所有交不可約元的內(nèi)涵構(gòu)成集合:MM(L2)={{a},syggg00,,{a,e},{a,c}}。 其Hasse圖如圖8所示:

圖8 MM(L2)的Hasse圖Fig.8 Hasse of MM(L2)

3)MM(L2)的下集格如下:

ο(MM(L2))={,{{a}},{},{syggg00},{{a},}, {,syggg00},{{a},syggg00},{{a,e},{e}},{{a,c},{a}},{{a}, ,syggg00},{{a,e},{a},},{{a,e},{a},syggg00},{{a,c},{a}, },{{a,c},{a},syggg00},{{a,e},{a,c},{a}},{,syggg00, {a,e},{a}},{,syggg00,{a,c},{a}},{,{a,e},{a,c}, {a}},{syggg00,{a,e},{a,c},{a}},{{a},,{a,c},syggg00,{a,e}}}

4)?A∈ο(MM(L2)), 在形式背景(G,M,I1)上計算f2(A)可得:LG(MM(L2))={,{1},{3},{4},{2,4},{3,4},{1,3,4},G}

5)根據(jù)集合Q2的定義, 可得:Q2={{1,2},{1,3},{2}}

根據(jù)映射h22得到I(1,c)=0,I(2,d)=0。 從而得到補全后的完備的形式背景(G,M,I4),如表7。

表7 完備形式背景(G,M,I4)

最后, 以看出基于2種不可約元的下集格完備化得到的形式背景相同。 因而, 將其作為最終完備化的結(jié)果。

4 結(jié)束語

本文提出了一種通過并不可約元(交不可約元)的下集格獲取概念的方法。 首先利用箭頭關(guān)系找到該背景對應(yīng)概念格的并不可約元(交不可約元), 對并不可約元(交不可約元)的外延集(內(nèi)涵集)做下集格; 其次對下集格中的元素做相應(yīng)的運算, 得到的屬性集合(對象集合)可證明就是概念格的內(nèi)涵集(外延集)；最后將其擴(kuò)充成為概念。 此外，根據(jù)這種概念獲取的方法利用下集格已經(jīng)將并不可約元(交不可約元)的并(交)經(jīng)行了初步篩選, 所以對于不完備形式背景來說從概念較多的形式背景(G,M,I1)或(G,M,I2)的并不可約元出發(fā), 在另一個形式背景上進(jìn)行特定的映射，最后根據(jù)定義的映射將其完備化。 同樣可以從交不可約元出發(fā)，對不完備形式背景進(jìn)行擴(kuò)充。 并且基于2種不可約元擴(kuò)充后的結(jié)果相同。

參考文獻(xiàn):

[1]WILLE R. Restructuring lattices theory: an approach on hierarchies of concepts [M]. Dordrecht, Holland: Springer, 1982： 445-470.

[2]CARPINETO C, ROMANO G. Concept data analysis: theory and application[M]. [S.l.]:John Wiley & Sons, 2004: 21-35.

[3]GODIN R. Incremental concept formation algorithm based on Galois lattices [J]. Computational Intelligence, 1995, 11(2): 246-267.

[4]HO T B . Discovering and using knowledge from unsupervised data [J]. Decision Support System, 1997, 21(1):29-42.

[5]BELOHLAVEK R. fuzzy closure operators[J]. Journal of Mathematical Analysis and Applications, 2001(262): 473-489.

[6]NOURINE L, RAYNAUD O. A fast algorithm for building lattices [J]. Information Processing Letters, 1999, 47: 111-112.

[7]BODAT J P. Calcul pratique du treillis de galois d’ume correspondence [J]. Math Sci Hum, 1986, 96: 31-47.

[8]HO T B. Incremental conceptual clustering in the framework of galois lattice[C]//Proceedings of First Pacific-Asia Conference. Knowledge Discovery and Data Mining: Techniques and Applications. [S.l.], 1997: 49-64.

[9]李云, 劉宗田, 陳崚, 等. 多概念格的橫向合并算法[J]. 電子學(xué)報, 2004, 32 (11) : 1847-1854.

LI Yun， LIU Zongtian， CHEN Ling. Horizontal union algorithm of multiple concept lattices[J]. Acta Electronica Sinica, 2004, 32 (11) : 1847-1854.

[10]萬青, 魏玲, 李濤. 一種基于并不可約元的建格新方法[J]. 西北大學(xué)學(xué)報, 2013, 43 (1) : 10-14.

WAN Qing, WEI Ling, LI Tao. A new method of building lattice based on join-irreducible[J]. Journal of Northwest University: Natural Science Edition, 2013, 43 (1) : 10-14.

[11]GANTER B, WILLE R. Formal Concept Analysis [M]. Mathematical Foundations.SpringerVerlag, New York, 1999:21-24.

[12]DAVEY B A, PRIESTLEY H A. Introduction to lattices and order[M]. Cambridge: Cambridge University Press, 2002.

[13]李金海.面向規(guī)則提取的概念格約簡方法及其算法實現(xiàn)[D]. 西安: 西安交通大學(xué), 2012: 45-63.

LI Jinhai. Acquisition oriented reduction methods for concept lattices and their implementation algorithms[D].Xi'an: Xi'an Jiao Tong University, 2012: 45-63.

[14]康向平, 李德玉, 李瑞萍. 基于多劃分的不完備信息系統(tǒng)的完備化模型[J]. 計算機工程與設(shè)計, 2011(9): 3131-3134.

KANG Xiangping, LI Deyu, LI Ruiping. Completion model of incomplete information system based on multiple-partitions[J]. Computer Engineering and Design, 2011(9): 3131-3134.