面向?qū)傩?對(duì)象)概念格基于直觀圖的保并(交)約簡

梁新月, 萬 青, 魏 玲

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

?

·數(shù)理科學(xué)·

面向?qū)傩?對(duì)象)概念格基于直觀圖的保并(交)約簡

梁新月, 萬 青, 魏 玲

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

屬性約簡是形式概念分析中的一個(gè)重要問題, 文中主要研究面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡竦谋３植?交)不可約元外延不變的約簡。給出面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡竦谋２⒓s簡和保交約簡的定義; 研究了這兩個(gè)格的保并約簡和保交約簡之間的關(guān)系; 利用形式背景直觀圖, 給出獲取這兩種格的保并約簡和保交約簡的理論與方法。

面向?qū)傩愿拍罡?面向?qū)ο蟾拍罡?保并約簡;保交約簡;直觀圖

形式概念分析理論是由德國數(shù)學(xué)家Wille于1982年提出來的[1-2], 是一種非常有力的數(shù)據(jù)分析和知識(shí)發(fā)現(xiàn)的數(shù)學(xué)工具, 廣泛應(yīng)用于人工智能和信息檢索等領(lǐng)域[3-4]。

粗糙集理論和概念格理論是兩種不同的數(shù)據(jù)分析方法。雖然兩種理論有許多不同, 但它們之間存在著諸多相似之處[5], 有很多學(xué)者將二者結(jié)合起來研究, 以便更好地分析數(shù)據(jù)和理解數(shù)據(jù)[5-6]。Duntsch和Gediga 通過定義modal-style算子, 并由粗糙近似算子構(gòu)造了面向?qū)傩愿拍罡馵7], Yao Y.Y.借用該思想建立了面向?qū)ο蟾拍罡? 且證明了面向?qū)傩愿拍罡衽c面向?qū)ο蟾拍罡竦耐瑯?gòu)[8], 為數(shù)據(jù)分析提供了新的理論依據(jù)。

隨著網(wǎng)絡(luò)的發(fā)展, 信息量的增大, 從龐大的數(shù)據(jù)庫中找到我們需要的知識(shí)越來越困難, 研究概念格的簡化越來越有價(jià)值。國內(nèi)外有關(guān)概念格約簡的研究已有了一些研究成果。 張文修、魏玲等人研究了形式背景在概念格同構(gòu)意義下的屬性約簡理論和方法[9], 王霞等基于概念格的交(并)不可約元分別研究了經(jīng)典形式背景的概念格、面向?qū)ο蟾拍罡褚约懊嫦驅(qū)傩愿拍罡竦膶傩约s簡問題[10], 萬青、魏玲從對(duì)象集的每一個(gè)等價(jià)類所擁有的屬性子集之間的包含關(guān)系出發(fā), 構(gòu)造相應(yīng)的Hasse圖, 直接得到面向?qū)傩愿拍罡竦牟⒊砻茏蛹痆11]。本文從直觀圖出發(fā), 尋找一種保持面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡竦牟?交)不可約元外延不變的屬性約簡, 對(duì)概念格結(jié)構(gòu)進(jìn)行簡化, 從而達(dá)到簡化知識(shí)庫的目的。

1 理論基礎(chǔ)

定義1[1]稱三元組(G,M,I)是一個(gè)形式背景, 其中G={g1，g2，…，gn}為對(duì)象集, 每個(gè)gi稱為一個(gè)對(duì)象;M={m1，m2，…，ms}為屬性集, 每個(gè)mj稱為一個(gè)屬性,I是G和M之間的一個(gè)二元關(guān)系, 且I?G×M。若(g,m)∈I, 則稱g具有屬性m。

對(duì)于形式背景(G,M,I), 在對(duì)象子集X?G和屬性子集B?M上分別定義運(yùn)算*與′[1-2]

X*={m|m∈M,?g∈X, (g,m)∈I}，

B′={g|g∈G,?m∈B,(g,m)∈I}。

若?g∈G,g*≠?,g*≠M(fèi), 且?m∈M,m′≠?,m′≠G,?gi,gj,gi*≠gj*,?mi,mj∈M,mi′≠mj′,則稱形式背景(G,M,I)是凈化的[2]。本文在有限的凈化背景下研究。

設(shè)(G,M,I)是形式背景, 在對(duì)象集X?G及屬性集B?M上分別定義算子“□”與“”[7-8]

X□={m∈M|m′?X}，

B□={g∈G|g*?B}，

X={m∈M|m′∩B≠?}，

B={g∈G|g*∩B≠?}。

定理1[7-8]設(shè)(G,M,I)為形式背景,?X,X1,X2?G及?B,B1,B2?M, 算子“□”與“”有以下性質(zhì):

1)X1?X2?X1□?X2□,X1?X2;

2)B1?B2?B1□?B2□,B1?B2;

3)X?X?X，B?B?B;

4)X=X□,X=X,B=B□,B=B;

5) (X1∩X2)□=X1□∩X2□,

(X1∪X2)=X1∪X2,

(B1∩B2)□=B1□∩B2□,

(B1∪B2)=B1∪B2。

Duntsch和Gediga提出了面向?qū)傩愿拍罡馵7], Yao Y.Y.提出了面向?qū)傩愿拍罡馵8]。下面給出這兩種概念格的定義。

定義2[7]設(shè)(G,M,I)為形式背景,?X?G,B?M, 滿足X=B□且B=X, 則稱二元組(X,B)為面向?qū)傩愿拍?。其? 稱X為面向?qū)傩愿拍畹耐庋?B為面向?qū)傩愿拍畹膬?nèi)涵。通常用LP(G,M,I)表示形式背景(G,M,I)上所有的面向?qū)傩愿拍钏M成的集合。

?(X1,B1),(X2,B2)∈LP(G,M,I), 定義:

(X1,B1)≤(X2,B2)?X1?X2(?B1?B2)

則“≤”是LP(G,M,I)上的偏序關(guān)系。

在LP(G,M,I)上定義:

(X1,B1)∧(X2,B2)=((X1∩X2), (B1∩B2))，

(X1,B1)∨(X2,B2)=((X1∪X2),B1∪B2)，

易知LP(G,M,I)是一個(gè)完備格, 稱為形式背景(G,M,I)的面向?qū)傩愿拍罡瘛?/p>

定義3[8]設(shè)(G,M,I)為形式背景, 如果?X?G,B?M, 滿足X=B且B=X□, 則稱二元組(X,B)為面向?qū)ο蟾拍?。通常用LO(G,M,I)表示形式背景(G,M,I)上所有的面向?qū)ο蟾拍钏M成的集合。

?(X1,B1), (X2,B2)∈LO(G,M,I), 定義:

(X1,B1)≤(X2,B2)?X1?X2(?B1?B2)

則“≤”是LO(G,M,I)上的偏序關(guān)系。

在LO(G,M,I)上定義:

(X1,B1)∧(X2,B2)=((X1∩X2),B1∩B2)，

(X1,B1)∨(X2,B2)=((X1∪X2, (B1∪B2))，

易知LO(G,M,I)是一個(gè)完備格, 稱為形式背景(G,M,I)的面向?qū)ο蟾拍罡瘛?/p>

設(shè)(G,M,I)為形式背景, 稱(G,B,IB)為(G,M,I)的子背景,其中IB=I∩G×B。為了敘述簡潔, 用“#”統(tǒng)一表示算子*,′，,□。 因此,?X?G,B?M,X#B=X#∩B,B#X=B#∩X。

定義4[10]設(shè)L是格, 如果x∈L滿足以下兩個(gè)條件:

1)x≠0(L存在0元);

2)?a,b∈L, 當(dāng)x=a∨b時(shí), 有x=a或者x=b;

則稱元素x∈L是格L的并不可約元。

對(duì)偶地, 如果x∈L滿足條件:

1)x≠1(L存在單位元1時(shí));

2)?a,b∈L, 當(dāng)x=a∧b時(shí), 有x=a或者x=b。

則稱元素x是格L的交不可約元。

設(shè)(G,M,I)是形式背景,?B?M,記LP(G,B,IB)中所有并不可約元和所有交不可約元分別記為JB(LP)和MB(LP),LO(G,B,IB)中所有并不可約元和所有交不可約元分別記為JB(LO)和MB(LO)。當(dāng)B=M時(shí), 分別記作J(LP),M(LP),J(LO),M(LO)。記Ext(J(LP))={X|(X,B)∈J(LP)}, Ext(J(LO))={X|(X,B)∈J(LO)};Ext(M(LP))={X|(X,B)∈M(LP)}; Ext(M(LO))={X|(X,B)∈M(LO)}。

例1 表1是一個(gè)形式背景(G,M,I)。對(duì)象集G={1, 2, 3, 4, 5, 6, 7, 8, 9}, 屬性集M={a, b, c, d, e, f, g, h, i}。該背景的面向?qū)傩愿拍罡馤P(G,M,I)和面向?qū)ο蟾拍罡馤O(G,M,I)分別如圖1和圖2所示。

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

圖1 LP(G,M,I)Fig.1 LP(G,M,I)

Ext(J(LP))={{1,2,3,4,5,8,9},{1,2,3,4,8,9},{1,2,3}{1},{2},{6},{9}}，

Ext(M(LP))={{1,2,3,4,5,8,9}，{1,2,3,4,6,7,8,9},{1,2,3,8,9},{1,2,6,9},{1,2,3,6},{6,9}{2,9},{1}}，

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

Ext(J(LO))={{2,3,4,5,6,7,8,9},{1,3,4,5,6,7,8}{1,2,3,4,5,7,8}{3,4,5,7,8}{4,5,7,8,9},{4,5,6,7},{6,7},{5}}，

Ext(M(LO))={{1,2,3,4,5,6,7,8},{2,3,4,5,6,7,8,9},{1,3,4,5,6,7,8,9},{1,2,3,4,5,7,8,9},{4,5,6,7,8,9},{5,6,7},{6,7}}。

2 面向?qū)傩?對(duì)象)概念格的保并(交)約簡

2.1 基本定義和相關(guān)性質(zhì)

本節(jié)給出面向?qū)傩?對(duì)象)概念格保并、保交約簡定義, 并利用這兩種格之間的關(guān)系研究保并、保交約簡之間的關(guān)系。

定義5 設(shè)(G,M,I)為形式背景, 若存在屬性集B?M, 使得Ext(JB(LP))=Ext(J(LP)), 則稱B是面向?qū)傩愿拍罡馤P(G,M,I)的保并協(xié)調(diào)集; 若?b∈B,Ext(JB-(LP))≠Ext(J(LP)), 則稱B為LP(G,M,I)的保并約簡。將LP(G,M,I)的所有保并約簡記為Red(JP)。

類似地,可定義面向?qū)ο蟾拍罡竦谋２⒓s簡。若存在屬性集B?M, 使得Ext(JB(LO))=Ext(J(LO)), 則稱B是面向?qū)ο蟾拍罡馤O(G,M,I)的保并協(xié)調(diào)集;若?b∈B, Ext(JB-(LO))≠Ext(J(LO)), 則稱B為LO(G,M,I)的保并約簡。將LO(G,M,I)的所有保并約簡記為Red(JO)。

定義6 設(shè)(G,M,I)為形式背景, 若存在屬性集B?M, 使得Ext(MB(LP))=Ext(M(LP)), 則稱B是面向?qū)傩愿拍罡馤P(G,M,I)的保交協(xié)調(diào)集; 若?b∈B, Ext(MB-(LP))≠Ext(M(LP)), 則稱B為LP(G,M,I)的保交約簡。將LP(G,M,I)的所有保交約簡記為Red(MP)。

類似地,可定義面向?qū)ο蟾拍罡竦谋＝患s簡。若存在屬性集B?M, 使得Ext(MB(LO))=Ext(M(LO)), 則稱B是面向?qū)ο蟾拍罡馤O(G,M,I)的保交協(xié)調(diào)集; 若?b∈B, Ext(MB-(LO))≠Ext(M(LO)) 則稱B為LO(G,M,I)的保交約簡。將LO(G,M,I)的所有保交約簡記為Red(MO)。

定理2 設(shè)(G,M,I)為形式背景,則有:

1) Red(MP)=Red(JO);

2) Red(JP)=Red(MO)。

證 明 ?(X,B)∈LP(G,M,I)

有(XC,BC)∈LO(G,M,I)。

又因?yàn)長P(G,M,I)≌LO(G,M,I),?B?M, 有

Ext(M(LP))={Xi|(Xi,Bi)∈M(LP)}，

Ext(J(LO))={XiC|(Xi,Bi)∈M(LP)}，

Ext(MB(LP))={Xj|(Xj,Bj)∈MB(LP)}，

Ext(JB(LO))={XjC|(Xj,Bj)∈MB(LP)}。

若B∈Red(MP), 則Ext(M(LP))=Ext(MB(LP))。故Ext(J(LO))=Ext(JB(LO)), 所以B∈Red(JO)。

類似地,?B∈Red(JO), 有B∈Red(MP)。

綜上得Red(MP)=Red(JO)。

同理可證Red(JP)=Red(MO)。

2.2 基于直觀圖的面向?qū)傩?對(duì)象)概念格的保并(交)約簡

本節(jié)依據(jù)文獻(xiàn)[11], 定義了直觀圖, 并給出了尋找面向?qū)傩?對(duì)象)概念格的保交、保并約簡。

定義7[11]設(shè)(G,M,I)為形式背景, 記R={(gi,gj)|gi*=gj*,?gi,gj∈G},HG={([g]R,g*)|g∈G, [g]R∈G/R1}。顯然,R1是G上的等價(jià)關(guān)系，定義([g1]R,g1*)≤([g2]R,g2*)?g1*?g2*, 則“≤”為HG上的偏序關(guān)系, 因此可得到Hasse圖(HG,≤), 我們稱其為(G,M,I)的對(duì)象直觀圖。

類似地,可定義(G,M,I)的屬性直觀圖(HM, ≤)。 記P={(ms,mt)|(ms′=mt′,?ms,mt∈M},HM={(m′,[m]P|m∈M, [m]P∈M/P}。顯然,P是M上的等價(jià)關(guān)系, 定義([m1]P,m1′)≤([m2]P,m2′)?m1′?m2′, “≤”為HM上的偏序關(guān)系。

由于本文的形式背景都是凈化的, 則HG={(g,g*)|g∈G}，HM={(m′,m)|m∈M}。記min(HG)為HG的極小元, min(HM)為HM的極小元。

定義8[12]?a,b, 若a

定理3 設(shè)(G,M,I)是形式背景, (HG，≤)為該形式背景的對(duì)象直觀圖,?g∈G, 有以下結(jié)論:

2) min(HG)?J(LP)；

3) (g,g*)?min(HG)且滿足g*-∪i∈τgi*≠?, 則(g,g)∈J(LP)。其中(gi,gi*)(g,g*)。

證 明 1)由于(g,g)∈LP(G,M,I), 我們只需要證為單點(diǎn)集, 由算子的定義可得g=g*。由于gi*?g*, 則有g(shù)={x∈G|x*?g=g*}=∪i∈τgi。綜上有

2)設(shè)(g,g*)∈min(HG), 由1)有(g,g*)∈LP(G,M,I)。由定義8，?(g,g*)∈min(HG), 不存在gi∈G使得gi*?g*。因此,g*≠∪{gi*|gi*?g*，?gi∈G}。因此, min(HG)?J(LP)得證。

對(duì)偶的, (HM，≤)為該形式背景的屬性直觀圖, 則有以下定理。

定理4 ?m∈M, 有以下結(jié)論

2) min(HM)?J(LO)；

3) (m′,m)?min(HM)且滿足m′-∪s∈Sms′≠?, 則(m,m)∈J(LO)。其中(ms′,ms)(m′,m)。

定理5 設(shè)(G,M,I)是形式背景, (HM，≤)為其屬性直觀圖, 記D={m∈G|(m′,m)∈min(HM)∨(m′,m) ?min(HM)?m′-∪s∈Sms′≠?, (ms′,ms)(m′,m)}，則Red(JO)={D}。

證 明 若取Ic=G×MI, 稱(G,M,Ic)為(G,M,I)的補(bǔ)背景, 相應(yīng)的格記為Lc, 保持其概念格結(jié)構(gòu)不變的約簡記為Red(Lc), 保交約簡為Red(Mc)。由文獻(xiàn)[13]可得Red(LP)=Red(Lc),?(X,B)∈LP(G,M,I), 有(X,BC)∈Lc(G,M,I)，則LP(G,M,I)和Lc(G,M,I)有相同的偏序關(guān)系。因此, Red(MP)=Red(Mc), 而Red(Lc)=Red(Mc), Red(MP)=Red(JO)。所以Red(JO)=Red(Lc)。

結(jié)合定理5, 可知Red(MP)=Red(JO)={D}。

即從屬性直觀圖直接可得到面向?qū)ο蟾拍罡竦谋２⒓s簡和面向?qū)傩愿拍罡竦谋＝患s簡。

例2 對(duì)于表1形式背景, 求其面向?qū)ο蟾拍罡竦谋２⒓s簡和面向?qū)傩愿拍罡竦谋＝患s簡。

圖3 (HM≤)Fig.3 LO(G,M,I)

圖3是表1對(duì)應(yīng)的屬性直觀圖, 根據(jù)D的定義, 逐一驗(yàn)證屬性特點(diǎn)可得D={a,c,d,e,f,g,h,i}。則Red(MP)=Red(JO)={D}。其相應(yīng)的面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡穹謩e如圖4, 圖5所示。屬性集D保持面向?qū)傩愿拍罡竦慕徊豢杉s元外延不變, 保持面向?qū)ο蟾拍罡竦牟⒉豢杉s元的外延不變。

圖4 LP(G，D，ID)Fig.4 LP(G，D，ID)

圖5 LO(G，D，ID)Fig.5 LO(G，D，ID)

記J(HG)={{g}|(g,g)∈J(LP)}。L={Lg|Lg=∪i∈τgi, (gi,gi*)(g,g*)且{g}∈J(HG)min(HG)}，F(xiàn) =LJ(HG)，E =J(HG)∪F 。

引理1 設(shè)(G,M,I)為形式背景(HG，≤)為其屬性直觀圖。若存在{g}∈J(HG), 有Lg∈L且|Lg|>1，則Lg=∪i∈τgi, 其中(gi,gi*)(g,g*)。

證 明 不失一般性,假設(shè)Lg={g1,g2}。由算子的定義和性質(zhì)可得Lg=g1∪g2。Lg={gi|gi*?g1*∪g2*}={gi|gi*?g1*∪g2*}。由于(gi,gi*)(g,g*), 則不存在gj使得gj≠gi有g(shù)j*?g1*∪g2*,gj*g1*,gj*g2*。因此Lg=∪i∈τgig□。

引理2 設(shè)(G,M,I)為形式背景，B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集,則?Lg∈L, 有Lg≠g。

證 明 由于B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集,?{g}∈J(HG), 有g(shù)=g且{g}∈JB(HG)。?Lg∈L,由L的定義知,Lg=∪i∈τgi, 其中(gi,gi*)(g,g*)。因?yàn)?gi,gi)∈LP(G,M,I), 所以gi=∪j∈Jgij，其中g(shù)ij∈J(HG); 當(dāng)gi∈J(HG)時(shí),gij=gi。由Lg=∪i∈τgi, 則Lg=∪i∈τgi，兩邊同時(shí)交B, 有Lg=∪i∈τgi。由gi=∪j∈Jgij有g(shù)i=∪j∈Jgij，故Lg=∪i∈τ(∪j∈Jgij)。假設(shè)g=Lg，于是有g(shù)=∪i∈τ(∪j∈Jgij), 故g-∪i∈τ(∪j∈Jgij)=?。由gi=gi*?g*=g，gi=∪j∈Jgij，則gij?gi?g，故gij≠g, 又由gij∈J(HG),g∈J(HG)，故gij≠g。因?yàn)锽是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集, 則有g(shù)ij=gij,g=g,gij≠g。故gij≠g, 又由于gij?g，則gij?g, 故gij?g。于是gij*B?g*B。因此對(duì)于(gk,gk*B)(g,g*B), 一定有∪i∈τ(∪j∈Jgij*B)?∪k∈Kgk*B, 則有g(shù)*B-∪k∈Kgk*B?g*B-∪i∈τ(∪j∈Jgij*B)=?, 由定理3知{g}?JB(HG), 此與{g}∈JB(HG)矛盾。故Lg≠g。

定理6 設(shè)(G,M,I)為形式背景，B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集??E∈E 有E=E。

證 明 必要性。由E∈E , 則E∈J(HG)或E∈F 。

當(dāng)E∈J(HG)時(shí), 由于B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集, 則E=E。

當(dāng)E∈F 時(shí), 則存在Lg, 使得E=Lg=∪i∈τgi, (gi,gi*)(g,g*)且g*-∪i∈τgi*≠?。由引理1可知Lg=∪i∈τgi。由定理3中1)可得gi=∪j∈Jgij, 其中g(shù)ij*?gi*。故Lg=∪i∈τ(∪j∈Jgij)。由算子的定義有Lg={gk|gk*B?Lg}={gk|gk*B?∪i∈τgi}。對(duì)于上述任意的gij, 由于gij*?gi*?g*。則gij*B?g*B=g。 由gij的任意性知,Lg?Lg。即E?E。假設(shè)E≠E, 即Lg≠Lg。則存在gk∈Lg, 且gk?Lg。由g=g∪(∪i∈τ(∪j∈Jgij))=g∪Lg，則ggg=g∪Lg, 故gk=g或gk∈Lg。由于gk?Lg, 從而gk=g。所以gk*B=g*B=g。由于gk*B?Lg?g, 故Lg=g。由引理2知,當(dāng)B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集時(shí)，Lg≠g。故矛盾。從而E=E。綜上,?E∈E 有E=E。

充分性。要證明B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集, 即證?{g}∈J(HG), 有g(shù)=g且{g}∈JB(HG)。由于J(HG)?E ，故?{g}∈J(HG), 有g(shù)=g。下證{g}∈JB(HG)。因?yàn)?{g}∈J(HG), 有(g,g*)∈ min(HG)或(g,g*)?min(HG)且滿足g*-∪i∈τgi*≠?, 其中(gi,gi*)(g,g*)。

當(dāng)(g,g*)∈min(HG)時(shí), (g,g)=(g,g*)∈J(LP), 由于g=g, 則(g,g)=(g,g*B), 故{g}∈JB(HG)。

當(dāng)(g,g*)?min(HG)時(shí),g*-∪i∈τgi*≠?, 其中(gi,gi*)(g,g*)。由于Lg=∪i∈τgi, 則Lg=∪i∈τgi*。因此g*-Lg≠?, 故Lg?g=g*。由于g=g∪(∪i∈τgi)且{g}∈J(HG), 由引理1可得g=g∪Lg,g?Lg。又由于g=g,Lg=Lg, 則g=g∪Lg且g?Lg。即不存在gj, 滿足(gj,gj*)≤(g,g*), 使得gj*B=g*B。因此g?∪k∈Kgk且g=g∪(∪k∈Kgk), 其中(gk,gk*B)(g,g*B)。又g=g∪Lg且g?Lg, 故Lg=∪k∈Kgk。從而Lg=∪k∈Kgk。故?≠g-Lg=g-∪k∈Kgk=g*B-∪k∈Kgk*B。由定理3可得{g}∈JB(HG)。 綜上,B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集。

定義9 ?Ei,Ej∈E , 定義D(Ei,Ej)=Ei-Ej，稱∧={D(Ei,Ej)|Ei,Ej∈E }為面向?qū)傩愿拍罡竦谋２⒈孀R(shí)屬性矩陣。

定理7 設(shè)(G,M,I)是形式背景?≠B?M,則下列命題等價(jià):

1)B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集;

2)?D(Ei,Ej)≠?, 有B∩D(Ei,Ej)≠?;

3)?C?M,C∩B≠?, 則C?L。

證 明 1)?2) 若B是面向?qū)傩愿拍罡竦谋２⒓s簡, 由定理6知:?E∈E ,E=E。要證B∩D(Ei,Ej)≠?, 即證Ei-Ej≠?。假設(shè)Ei-Ej=?, 則Ei?Ej, 于是有Ei?Ej。又因?yàn)镋i=Ei，Ej=Ej, 所以Ei?Ej, 故Ei?Ej, 這與D(Ei,Ej)≠?矛盾。即有B∩D(Ei,Ej)≠?。

2)?1) 假設(shè)B不是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集, 則存在E∈E ,E≠E，即存在g∈G, 使得g∈E,g?E或g?E，g∈E。若g∈Eg?E, 則有g(shù)?E，所以B∩D({g},E)=?, 與已知條件矛盾。若g?E,g∈E, 則有g(shù)E,g?EB∩D({g},E)≠?,D({g},E)=?。由D({g},E)=?, 則B∩D({g},E)=?。這與B∩D({g},E)≠?矛盾, 故B是面向?qū)傩愿拍罡竦谋２f(xié)調(diào)集。

2)?3) 顯然成立。

定義10 設(shè)(G,M,I)是形式背景, 定義

M=∧{∨D(Ei,Ej)|D(Ei,Ej)∈L,D(Ei,Ej)≠?}

稱M為面向?qū)傩愿拍罡竦谋２⒈孀R(shí)屬性函數(shù)。這里∧,∨分別表示合取和析取。

定理8 設(shè)(G,M,I)是形式背景?≠D?M,則D是面向?qū)傩愿拍罡竦谋２⒓s簡, 當(dāng)且僅當(dāng)∧aj∈Daj是M的最小析取范式的一個(gè)析取支。

證 明 由定理7和差別函數(shù)中最小析取范式形成的定義直接得到。

例1 對(duì)于表1的形式背景, 圖6為其對(duì)象直觀圖。判定其面向?qū)傩愿拍罡竦谋２⒓s簡和面向?qū)ο蟾拍罡竦谋＝患s簡。

圖6 (HG≤)Fig.6 (HG≤)

由圖6,逐一驗(yàn)證得到E ={{1}, {2}, {3}, {4}, {5}, {6}, {8}, {9}, {1,2}}。

表2是由定義9得到的面向?qū)傩愿拍罡竦谋２⒈孀R(shí)矩陣。

表2 LP(G，M，I)保并辨識(shí)矩陣表Tab.2 LP(G，M，I)

通過表2可以得到面向?qū)傩愿拍罡竦谋２⒈孀R(shí)屬性函數(shù):

M=(a∧c∧e∧f∧g∧h∧i∧b)∨(a∧c∧e∧f∧g∧h∧i∧d)。

根據(jù)定理8,面向?qū)傩愿拍罡竦谋２⒓s簡集:D1={a, c, d, e, f, g, h, i},D2={a, b, c, e, f, g, h, i}。則Red(MO)=Red(JP)={D1,D2},當(dāng)約簡為D1時(shí), 其對(duì)應(yīng)背景的面向?qū)傩愿拍罡駷閳D4, 其對(duì)應(yīng)的屬性概念格為圖5。當(dāng)約簡為D2時(shí), 圖7為其對(duì)應(yīng)背景的面向?qū)傩愿拍罡? 圖8為其面向?qū)ο蟾拍罡瘛?/p>

圖7 LP(G,D2,ID2)Fig.7 LP(G,D2,ID2)

圖8 LO(G,D2,ID2)Fig.8 LO(G,D2,ID2)

3 結(jié) 語

概念格作為一種概念數(shù)據(jù)分析和知識(shí)處理的數(shù)學(xué)工具, 已被廣泛應(yīng)用于眾多領(lǐng)域。本文主要基于直觀圖尋找面向?qū)傩?對(duì)象)概念格的保并(交)約簡方法。由于不可約元在概念格中非常重要, 利用直觀圖減化了求約簡的過程, 并最終實(shí)現(xiàn)對(duì)面向?qū)傩?對(duì)象)概念格的簡化。該方法避免了畫出格圖, 簡化了找約簡的過程, 從而也反應(yīng)了這兩種格之間的聯(lián)系。進(jìn)一步的, 我們還可以通過直觀圖找這兩種格的粒約簡, 并研究這三種約簡之間的關(guān)系。

[1]WILLER.Restructuringlatticetheory:anapproachbasedonhierarchiesofconcepts[C].RIVALI(Ed.),OrderedSets.Dordrecht:Reidel, 1982:445-470.

[2]GANTERB,WILLER.FormalConceptAnalysis[M].NewYork：MathematicalFoundations.Springer-Verlag, 1999.

[3]CARPINETOC,ROMANOG.Alatticeconceptualclusteringsystemanditsapplicationtobrowsingretrieval[J].MachineLearning, 1996, 10: 95-122.

[4]CHENYH,YAOYY.Amultiviewapproachforintelligentdataanalysisbasedondataoperators[J].InformationSciences，2008, 178(1):1-20.

[5]KENTRE.Roughconceptanalysis:asynthesisofroughsetsandformalconceptanalysis[J].FundamentaInformaticae, 1996, 27: 169-181.

[6]HUKY,SUIYF,LUYC,etal.Conceptapproximationinconceptlattice[J].LectureNotesinComputerScience, 2001, 20(35):167-173.

[7]DUNTSCHI,GEDIGAG.Approximationoperatorsinqualitativedataanalysis[C]//TheoryandApplicationofRelationalStructuresasKnowledgeInstruments.Heidelberg:Springer, 2003.

[8]YAOYY.Acomparativestudyofformalconceptanalysisandroughsettheoryindataanalysis[J].LectureNotesinArtificialIntelligence, 2004, 3066: 59-68.

[9] 張文修, 魏玲, 祁建軍, 概念格的屬性約簡理論與方法[J].中國科學(xué)(E輯信息科學(xué)), 2005, 35(6);628-639.

[10] 王霞. 概念格約簡理論與方法[D].西安:西安交通大學(xué), 2008.

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

[12]DAVEYBA,PRIESTLEYHA.IntroductiontoLatticesandOrder[M].Cambridge：CambridgeUniversityPress, 2002.

[13]MEDINAJ.Relatingattributereductioninformal,object-orientedandproperty-orientedconceptlattices[J].ComputersandMathematicswithApplication,2012,64:1990-2002.

(編 輯亢小玉)

MIE-preserving reduction and JIE-preserving reduction of property(object)-oriented concept lattices based on the pictorial diagram

LIANG Xin-yue,WAN Qing, WEI Ling

(School of Mathematics, Northwest University, Xi′an 710127， China)

Attribute reduction is an important issue in formal concept analysis. This paper mainly studies MIE(meet irreducible element)-preserving reduction and JIE(join irreducible element)-preserving reduction of property-oriented and object-oriented concept lattices. Firstly, the definitions of MIE-preserving reduction and JIE-preserving reduction of property-oriented and object-oriented concept lattices are given. Then, the relationship between MIE(JIE)-preserving reduction in property-oriented and its counterpart in object-oriented concept lattices is presented. Finally, pictorial diagram is used to give the theory and method of finding the MIE-preserving reduction and JIE-preserving reduction.

attribute-oriented concept lattices; object-oriented concept lattices; MIE-preserving reduction; JIE-preserving reduction; pictorial diagram

2014-04-17

國家自然科學(xué)基金資助項(xiàng)目(11371014,11071281)

梁新月，女，陜西西安人，從事形式概念分析、粗糙集理論研究。

魏玲，女，陜西西安人，教授，博士生導(dǎo)師，從事形式概念分析、粗糙集理論、概率論等研究。

TP18；O29

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-003