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

郭奇瑞, 魏 玲

(西北大學 數學學院, 陜西 西安 710127)

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

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

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

1 基礎知識

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

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叫作概念的內涵[2]。

定義2[2]設(G,M,I)是一個形式背景, 用L(G,M,I)表示由(G,M,I)生成的所有概念的集合。 對于(X1,A1), (X2,A2)∈L(G,M,I), 定義其偏序關系為(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)是一個完備格, 稱為概念格。

概念格的相關知識可以參看文獻[2]。

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

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

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

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

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

其逆運算定義如下:

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

由此產生了對象導出三支概念。

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

對于(X, (A,B)), (Y, (C,D)), 定義其偏序關系如下: (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)在如上定義的偏序關系 “≤” 下是一個完備格, 稱之為對象導出三支概念格, 簡記為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))。

下面兩個引理給出形式背景上經典概念與OE概念之間的關系。

例1設 (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)

該形式背景所對應的概念格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中的理想因子分解

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

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

對于形式背景(G,M,I), 為構造布爾矩陣, 記對象集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), 構造布爾矩陣XF和AF如下:

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

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

在此基礎上, 進一步給出概念因子的最優性定理。

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

設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]設(G,M,I)是一個形式背景,L(G,M,I)是概念格, 如果F?L(G,M,I)有W=XF°AF, 則O (G,M,I)∩A(G,M,I) ?F。

文獻[20]中稱滿足以上條件的形式概念為強制性因子。

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

令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 是基于經典概念格的因子分解, 該因子分解中的概念不包含原始概念格中的頂元與底元, 以及概念(124,ab)。

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

本節在基于經典概念格的理想因子分解問題研究的基礎上, 提出形式背景上基于OE概念格的理想因子分解, 并研究該因子分解的存在性、最優性以及強制性因子定理。 下面首先給出基于OE概念格的理想因子分解的定義。

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

例3(續例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是其所對應的布爾矩陣, 則一定存在OE概念格的子集FOE?OEL(G,M,I), 使得W=XFOE°AFOE。

基于以上研究, 進一步給出基于OE概念格因子分解的最優性定理。

定理6對任意的形式背景(G,M,I),W是其所對應的布爾矩陣,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)所對應的布爾矩陣, 由引理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概念轉換而來的形式概念分別對應于布爾矩陣W中由1所構成的最大矩形塊。 其次, 由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概念和正屬性OE概念, 我們可以找出形式背景上基于OE概念格因子分解的強制性因子。

定理7設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,?)·><·)。 假設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所對應的行與m所對應的列交差位置是1的最大矩形所對應的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(續例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 結 語

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

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

參考文獻：

[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].西北大學學報(自然科學版), 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].西安: 西安交通大學出版社, 2006.

[10] 張文修, 梁怡, 吳偉志. 信息系統與知識發現[M].北京: 科學出版社, 2003.

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

[12] 魏玲, 祁建軍, 張文修. 決策形式背景的概念格屬性約簡[J].中國科學E輯(信息科學), 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] 朱曉敏, 祁建軍. 基于三支概念格線圖的混合蘊含獲取[J].鄭州大學學報(理學版), 2017, 49(4):16-21.