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

石慧，何苗，魏玲

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

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

1 理論基礎

定義1[11]稱(G,M,I)為一個形式背景, 其中G={g1,g2,...,gt}為對象集, 每個gi(i≤t)稱為一個對象;M={m1,m2,…,ms}為屬性集, 每個mj(j≤s)稱為一個屬性;I為G和M之間的二元關系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]設(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]設(G,M,I)為形式背景,?g∈G,m∈M, 稱(g′,g)為對象概念, (m′,m′)為屬性概念。

定義4[12]設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]設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,m∈M:gmgm, 并且, 若g?h且g≠h, 則有hIm;gmgm, 并且, 若m′?n′且m′≠n′, 則有gIn;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確定形式背景中的箭頭關系, 根據(jù)定理2找到該形式背景所對應概念格的并不可約元, 其次對并不可約元的外延集做下集格, 再對下集格中的元素定義映射, 從而得到概念格的全部內(nèi)涵集, 進一步得到全部概念。 利用對偶性, 對交不可約元的內(nèi)涵集做下集格, 定義相應的映射, 得到概念格的全部外延集, 進而得到所有概念。

定義映射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) 當χ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), 設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映射后得到的集合為相應概念格的內(nèi)涵集。 進一步, 可對所有內(nèi)涵做′算子得到相應的外延, 進而得到概念。對偶地, 下面給出從交不可約元出發(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)當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), 設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映射后得到的集合為相應概念格的外延集。 進一步，可對所有外延做算子得到相應的內(nèi)涵, 進而得到概念。

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

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

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

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

由表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)}。 因此,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)涵，擴充為概念后可得: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的箭頭關系以及定理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)的全部外延。擴充為概念后可得:L(G,M,I)={(,M),(1,ace),(2,abde),(45,bcd),(23,abe), (245,bd), (145,c),(123,ae), (2345,b), (G,)}。概念格如圖4所示。

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

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

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

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

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

定義集合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(#)=

相應地, 定義集合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的概念多, 所表達的信息更加完整, 下面從形式背景(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={j5i0abt0b,{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},j5i0abt0b,,{a,e},{a,c}}。 其Hasse圖如圖8所示:

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

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

ο(MM(L2))={,{{a}},{},{j5i0abt0b},{{a},}, {,j5i0abt0b},{{a},j5i0abt0b},{{a,e},{e}},{{a,c},{a}},{{a}, ,j5i0abt0b},{{a,e},{a},},{{a,e},{a},j5i0abt0b},{{a,c},{a}, },{{a,c},{a},j5i0abt0b},{{a,e},{a,c},{a}},{,j5i0abt0b, {a,e},{a}},{,j5i0abt0b,{a,c},{a}},{,{a,e},{a,c}, {a}},{j5i0abt0b,{a,e},{a,c},{a}},{{a},,{a,c},j5i0abt0b,{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é)束語

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

參考文獻:

[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]. 電子學報, 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]. 西北大學學報, 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]. 西安: 西安交通大學, 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]. 計算機工程與設計, 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.