基于OE概念格的理想因子分解

郭奇瑞, 魏 玲

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

形式概念分析(Formal concept analysis, FCA)是一種基于形式背景進(jìn)行規(guī)則提取和數(shù)據(jù)分析的理論工具,由Wille首先提出[1]。形式概念與概念格共同構(gòu)成FCA的基礎(chǔ)。 概念格是形式概念的層次結(jié)構(gòu), 一方面它描述了對象與屬性之間的聯(lián)系, 另一方面它刻畫了概念之間的泛化與例化關(guān)系[2-3], 因此概念格通常被用來研究決策分析和屬性約簡等問題[4-12]。 三支概念分析(Three-way concept analysis, 3WCA)是由Qi等以FCA為基礎(chǔ)提出的一種新理論。 該理論結(jié)合了FCA與三支決策[13]的思想, 提出了對象(屬性)導(dǎo)出三支概念與對象(屬性)導(dǎo)出三支概念格[14], 并進(jìn)一步研究了兩種三支概念格與經(jīng)典概念格之間的關(guān)系[15]。

FCA中, 因子分解通過將形式背景對應(yīng)的布爾矩陣分解為兩個矩陣的布爾乘積的形式來降低數(shù)據(jù)維度, 對于理解和管理數(shù)據(jù)有著至關(guān)重要的作用[16-17]。 Lee和Seung首先提出了通過非負(fù)矩陣因子分解將一個約束矩陣分解為兩個約束矩陣的乘積[18], Belohlavek和Vychodil在FCA中利用矩陣分解的方法尋找二元數(shù)據(jù)中的理想因子[19-20], Keprt和Sn?el提出了用形式概念作為因子解決因子分解問題, 并給出了少量數(shù)據(jù)的實驗結(jié)果[21]。 在此基礎(chǔ)上, Glodeanu進(jìn)一步研究了基于三元數(shù)據(jù)的因子分解問題[22]。 事實上, 三支概念格在結(jié)構(gòu)上比經(jīng)典概念格更為復(fù)雜, 通過理想因子分解, 可以減少原OE概念格中OE概念的個數(shù), 以便于我們進(jìn)行更深層次的數(shù)據(jù)分析研究。

本文將探討如何基于OE概念格對形式背景進(jìn)行理想因子分解, 并對相關(guān)性質(zhì)進(jìn)行討論。

1 基礎(chǔ)知識

首先給出文中所需有關(guān)三支概念分析中OE概念格以及FCA中理想因子分解的基本概念及性質(zhì)。

1.1 OE概念格的基本概念

定義1[2]稱三元組(G,M,I)為一個形式背景, 其中G={x1,x2, …,xn}, 每一個xi(i≤n)被稱為一個對象;M={a1,a2, …,am}, 每一個aj(j≤m)是一個屬性; 對于x∈G與a∈M, 如果xIa或(x,a)∈I, 則稱對象x擁有屬性a, 或者屬性a被對象x擁有。

對于形式背景(G,M,I),X?G,A?M, Wille定義了如下一對算子,

*: P(G) →P(M),X*={a∈M|?x∈X, (x,a)∈I};

*: P(M) →P(G),A*={x∈G|?a∈A, (x,a)∈I}。

若二元組(X,A)滿足X*=A且A*=X, 則稱(X,A)是一個形式概念, 簡稱為概念。X叫作概念的外延,A叫作概念的內(nèi)涵[2]。

定義2[2]設(shè)(G,M,I)是一個形式背景, 用L(G,M,I)表示由(G,M,I)生成的所有概念的集合。 對于(X1,A1), (X2,A2)∈L(G,M,I), 定義其偏序關(guān)系為(X1,A1) ≤ (X2,A2) ?X1?X2?A2?A1。 定義其下確界和上確界分別為

(X1,A1)∧ (X2,A2)=(X1∩X2,

(A1∪A2)**),

(X1,A1)∨ (X2,A2)=((X1∪X2)**,

A1∩A2),

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

概念格的相關(guān)知識可以參看文獻(xiàn)[2]。

若(G,M,I)是一個形式背景, 稱(G,M,Ic)是背景(G,M,I)的補(bǔ)背景, 其中Ic=(G×M)-I。

在三支概念分析的理論框架中需要一種新的算子去描述“共同不擁有”的信息, 為了使形式概念中的信息更加完整, Qi等首先提出了負(fù)算子, 并稱定義1中的算子為正算子。

定義3[13]設(shè)(G,M,I)是一個形式背景。 對于X?G,A?M, 一對負(fù)算子被定義為

用NL(G,M,I)表示由形式背景(G,M,I)在負(fù)算子下生成的所有概念的集合, 并且NL(G,M,I)在上述 “≤” 偏序關(guān)系下也是一個完備格。

定義4[14]設(shè)(G,M,I)是一個形式背景,X?G,A?M, 三支算子被定義如下:

其逆運(yùn)算定義如下:

·>: DP (M) →P (G),

由此產(chǎn)生了對象導(dǎo)出三支概念。

定義5[14]設(shè)(G,M,I)是一個形式背景, (X,(A,B))叫做對象導(dǎo)出三支概念, 簡稱OE概念, 當(dāng)且僅當(dāng)X<·=(A,B)且(A,B)·>=X, 其中X?G,A,B?M。X叫作OE概念的外延, (A,B)叫作OE概念的內(nèi)涵。

對于(X, (A,B)), (Y, (C,D)), 定義其偏序關(guān)系如下: (X, (A,B)) ≤ (Y, (C,D))?X?Y?(C,D) ? (A,B)?C?A且D?B。

用OEL(G,M,I)表示由形式背景(G,M,I)生成的所有OE概念的集合, 則OEL(G,M,I)在如上定義的偏序關(guān)系 “≤” 下是一個完備格, 稱之為對象導(dǎo)出三支概念格, 簡記為OE概念格。 其中下確界和上確界分別為:

(X, (A,B))∧(Y, (C,D))=(X∩Y, ((A,B)∪(C,D))·><·),

(X, (A,B))∨(Y, (C,D))=((X∪Y)<··>, (A,B)∩(C,D))。

下面兩個引理給出形式背景上經(jīng)典概念與OE概念之間的關(guān)系。

例1設(shè) (G,M,I)為形式背景。 其中G={1, 2, 3, 4}是對象集,M={a,b,c,d,e}是屬性集。

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

該形式背景所對應(yīng)的概念格L(G,M,I),OE概念格OEL(G,M,I)如圖1和圖2所示。

圖1 概念格L(G, M, I)Fig.1 Concept lattice L(G, M, I)

圖2 OE概念格OEL(G, M, I)Fig.2 Object-induced three-way concept lattice OEL(G, M, I)

本文主要研究基于OE概念格的理想因子分解, 下面給出FCA中基于矩陣分解的二元因子分解的基本概念。

1.2 FCA中的理想因子分解

理想因子分解, 是用形式概念分析中的形式概念作為因子來尋找一個關(guān)于形式背景的理想分解, 以此來降低數(shù)據(jù)維度, 以便于更好地理解和管理數(shù)據(jù)。 通過矩陣分解的方法尋找二元數(shù)據(jù)中的理想因子, 利用理想因子概念對形式背景進(jìn)行因子分解, 從而產(chǎn)生對象-因子矩陣和因子-屬性矩陣, 分別描述了對象與因子之間、因子與變量之間的相互關(guān)系。

布爾矩陣乘積奠定了因子分解的基礎(chǔ), Glodeanu給出在FCA中因子分解的定義如下:

對于形式背景(G,M,I), 為構(gòu)造布爾矩陣, 記對象集G={x1,x2, …,xn}中每一個對象xi(i≤n)為i, 屬性集M={a1,a2, …,am}中每一個屬性aj(j≤m)為j, 若F={(X1,A1), …, (Xt,At)} ?L(G,M,I), 構(gòu)造布爾矩陣XF和AF如下:

則形式背景(G,M,I)所對應(yīng)的布爾矩陣W可分解為如上方法所構(gòu)造的兩個布爾矩陣乘積的形式XF°AF，事實上, 任意的形式背景(G,M,I)這樣的分解都存在, 如定理1所示。

定理1[20](概念因子的普遍性)設(shè)(G,M,I)為形式背景,W是其所對應(yīng)的布爾矩陣,L(G,M,I)是概念格,則存在F ?L(G,M,I)使得W=XF°AF。

在此基礎(chǔ)上, 進(jìn)一步給出概念因子的最優(yōu)性定理。

定理2[20](概念因子的最優(yōu)性)設(shè)(G,M,I)為形式背景,W是其所對應(yīng)的布爾矩陣,W=X°A,X,A分別為n×k階和k×m階布爾矩陣, 則存在關(guān)于W的形式概念的子集F ?L(G,M,I), |F |≤k, 使得對于n×|F |階和|F |×m階布爾矩陣XF和AF, 有W=XF°AF。

設(shè)g∈G,m∈M, 記O (G,M,I)={({g}**, {g}*) |g∈G}是對象概念集, A(G,M,I)={({m}*, {m}**) |m∈M}是屬性概念集。 下面的定理將說明, 對于任意一個形式背景(G,M,I), 既是對象概念又是屬性概念的形式概念一定包含于每個分解W=XF°AF的集合F 中。

定理3[20]設(shè)(G,M,I)是一個形式背景,L(G,M,I)是概念格, 如果F?L(G,M,I)有W=XF°AF, 則O (G,M,I)∩A(G,M,I) ?F。

文獻(xiàn)[20]中稱滿足以上條件的形式概念為強(qiáng)制性因子。

例2(續(xù)例1) 形式背景(G,M,I)所對應(yīng)的布爾矩陣如下

令F={(13,d), (24,abc), (1,abde)},F ?L(G,M,I), 其中(X1,A1)=(13, 4), (X2,A2)=(24, 123), (X3,A3)=(1,1245), 則

AF=

顯然XF°AF=W, F 是基于經(jīng)典概念格的因子分解, 該因子分解中的概念不包含原始概念格中的頂元與底元, 以及概念(124,ab)。

2 形式背景上基于OE概念格的因子分解

本節(jié)在基于經(jīng)典概念格的理想因子分解問題研究的基礎(chǔ)上, 提出形式背景上基于OE概念格的理想因子分解, 并研究該因子分解的存在性、最優(yōu)性以及強(qiáng)制性因子定理。 下面首先給出基于OE概念格的理想因子分解的定義。

對于FOE={(X1, (A1,B1)), …, (Xt, (At,Bt))} ?OEL(G,M,I), 構(gòu)造布爾矩陣XFOE和AFOE如下:

例3(續(xù)例2) 令FOE={(13, (d,c)), (24, (abc,de)), (1, (abde,c))},FOE?OEL(G,M,I), 其中(X1, (A1,B1)=(13, (4, 3)), (X2, (A2,B2)=(24, (123, 45)), (X3, (A3,B3)=(1, (1245, 3)), 則

顯然XFOE°AFOE=W, FOE是基于OE概念格的因子分解, 該因子分解中的概念不包含原OE概念格中的頂元與底元, 以及OE概念(234, (?,e)), (124, (ab, ?)), (3, (d,abce))。

由此給出以下定理。

定理4對任意的形式背景(G,M,I), 存在基于OE概念格的因子分解和理想因子分解。

定理5對任意的形式背景(G,M,I),W是其所對應(yīng)的布爾矩陣, 則一定存在OE概念格的子集FOE?OEL(G,M,I), 使得W=XFOE°AFOE。

基于以上研究, 進(jìn)一步給出基于OE概念格因子分解的最優(yōu)性定理。

定理6對任意的形式背景(G,M,I),W是其所對應(yīng)的布爾矩陣,X,A分別為n×k階和k×m階布爾矩陣,W=X°A, 則存在OE概念格的子集FOE?OEL(G,M,I), |FOE|≤k, 使得對于n×|FOE|階和|FOE|×m階布爾矩陣XFOE和AFOE, 有W=XFOE°AFOE。

證明首先, 由于W是形式背景(G,M,I)所對應(yīng)的布爾矩陣, 由引理2, 存在映射g:OEL(G,M,I)→L(G,M,I), 對任意的(X, (A,B))∈OEL(G,M,I),g((X, (A,B)))=(A*,A) ∈L(G,M,I), 則每一個由OE概念轉(zhuǎn)換而來的形式概念分別對應(yīng)于布爾矩陣W中由1所構(gòu)成的最大矩形塊。 其次, 由W=X°A,X,A分別為n×k階和k×m階布爾矩陣, 則W可以寫成任意k個包含1的矩形塊∨的形式(這些矩形塊并不完全是最大矩形塊)。 即由于Wij=Xi1·A1j∨…∨Xil·Alj,W是矩形塊Jl=Xl°Al(l=1,…,k)的并, 其中Xl°Al是n×m階布爾矩陣, 通過X的第l列與A的第l行作布爾乘積可得。 例如,W=X°A為

該分解可以寫成矩形塊J1∨J2∨J3∨J4的形式:

基于以上對象OE概念和正屬性O(shè)E概念, 我們可以找出形式背景上基于OE概念格因子分解的強(qiáng)制性因子。

定理7設(shè)FOE為形式背景(G,M,I)上基于OE概念格的因子分解且W=XFOE°AFOE, 則OOEL(G,M,I)∩AOEL(G,M,I) ?FOE。

證明若任意(X(A,B)) ∈OOEL(G,M,I)∩AOEL(G,M,I), 由定義知, 對于g∈G, (X, (A,B))=({g}<··>, {g}<·), 同樣對于m∈M, (X, (A,B))=((m,?)·>, (m,?)·><·)。 假設(shè)g∈X1,m∈A1, (X1, (A1,B1)) ∈OOEL(G,M,I)∩AOEL(G,M,I), 則由{g}?X1, 可得X={g}<··>?X1<··>=X1, 由算子<·的反序性, (A1,B1)=X1<·?X<·=(A,B)。 又由于m∈A1, 則(m,?) ? (A1,B1), (A,B)=(m,?)·><·? (A1,B1)·><·=(A1,B1), 從而(A,B)=(A1,B1),X=X1。 因此對于g∈X,m∈A, (X(A,B)) 在OEL(G,M,I)中唯一, 即對g∈X,m∈A,g所對應(yīng)的行與m所對應(yīng)的列交差位置是1的最大矩形所對應(yīng)的OE概念(X, (A,B))在OEL(G,M,I)中唯一。 又FOE為形式背景(G,M,I)上基于OE概念格的因子分解且W=XFOE°AFOE, 則(X(A,B)) ∈FOE, 再由(X(A,B))的任意性可得OOEL(G,M,I)∩AOEL(G,M,I) ? FOE。

例4(續(xù)例3) FOE={(13, (d,c)), (24, (abc,de)), (1, (abde,c))}是例1中形式背景(G,M,I)基于OE概念格的因子分解且W=XFOE°AFOE。

對于形式背景(G,M,I): OOEL(G,M,I)={(1, (abde,c)), (24, (abc,de)), (3, (d,abce)}, AOEL(G,M,I)={(124, (ab, ?)), (24, (abc,de)), (13, (d,c)), (1, (abde,c))}。

則OOEL(G,M,I)∩AOEL(G,M,I)={(1, (abde,c)), (24, (abc,de))}, 顯然有OOEL(G,M,I)∩AOEL(G,M,I) ?FOE。

3 結(jié) 語

Qi等在三支概念分析中分別從對象和屬性兩個角度, 提出了兩種三支概念格，進(jìn)而深入研究了形式背景三支概念的層次結(jié)構(gòu)[14-15]。本文基于OE概念格, 給出了形式背景上的理想因子分解, 并研究了OE概念格的(理想)因子的相關(guān)性質(zhì)。

對于補(bǔ)背景上基于OE概念格的理想因子分解問題, 可類似研究。 對于基于屬性導(dǎo)出三支概念格, 即基于AE概念格的理想因子分解以及相關(guān)性質(zhì), 不同概念格中因子概念特殊性及其性質(zhì)研究的問題等, 我們將在本文的基礎(chǔ)上, 作進(jìn)一步的研究探索。

參考文獻(xiàn)：

[1] WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]∥RIVAL I, ed. Ordered Sets. Reidel: Dordrecht-Boston, 1982:445-470.

[2] GANTER B. Formal Concept Analysis: Mathematical Foundations[M].New York:Springer-Verlag,1997.

[3] PAWLAK Z. Rough sets[J].International Journal of Parallel Programming, 1982, 38(5):88-95.

[4] 魏玲, 萬青, 錢婷,等. 三元概念分析綜述[J].西北大學(xué)學(xué)報(自然科學(xué)版), 2014, 44(5): 689-699.

[5] YAO Y . Concept lattices in rough set theory[C]∥Fuzzy Information, 2004. Processing Nafips ′04. IEEE Meeting of the. IEEE Xplore, 2004:796-801 Vol.2.

[6] SHYNG J Y, SHIEH H M, TZENG G H. An integration method combining Rough Set theory with formal concept analysis for personal investment portfolios[J].Knowledge-Based Systems, 2010, 23(6):586-597.

[9] 張文修, 姚一豫, 梁怡. 粗糙集與概念格[M].西安: 西安交通大學(xué)出版社, 2006.

[10] 張文修, 梁怡, 吳偉志. 信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京: 科學(xué)出版社, 2003.

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

[12] 魏玲, 祁建軍, 張文修. 決策形式背景的概念格屬性約簡[J].中國科學(xué)E輯(信息科學(xué)), 2008, 38(2): 195-208.

[13] YAO Y. Three-way decision: An interpretation of rules in rough set theory[C]∥International Conference on Rough Sets and Knowledge Technology. Springer-Verlag, 2009:642-649.

[14] QI J, WEI L, YAO Y. Three-way formal concept analysis[J].Lecture Notes in Computer Science, 2014, 8818: 732-741.

[15] QI J, QIAN T, WEI L. The connections between three-way and classical concept lattices[J].Knowledge-Based Systems, 2015, 91(C):143-151.

[16] GOLUB G H, VAN LOAN C F. Matrix computations (3rd ed.)[OL].http:∥d61p.uni-trier.de, 1996.

[17] MCDONALD R P. Factor Analysis and Related Methods[M].London:Psychology Press, 1985.

[18] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J].Nature, 1999, 401(6755):788 -791.

[21] KEPRT A, SNEL V. Binary factor analysis with help of formal concepts[C]∥Cla 2004 International Workshop on Concept Lattices and Their Applications, Ostrava, Czech Republic, September. DBLP, 2004:27-36.

[22] GLODEANU C. Triadic factor analysis[C]∥International Conference on Concept Lattices and Their Applications, Sevilla, Spain, DBLP, 2010：127-138.

[23] 朱曉敏, 祁建軍. 基于三支概念格線圖的混合蘊(yùn)含獲取[J].鄭州大學(xué)學(xué)報(理學(xué)版), 2017, 49(4):16-21.