基于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.