形式概念分析(Formal Concept Analysis, FCA) ^[1-2]是德国数学家Wille R.于1982年提出的一种处理二维数据的重要理论与方法。近年来, 形式概念分析在构建概念格^[3]、属性约简^[4]以及规则提取^[5]等方面已取得了诸多理论成果, 且形式概念分析的约简理论对复杂的二维数据在信息简化方面提供了理论依据。

受Peirce C.三个论域范畴的实用主义哲学^[6]的影响, Wille R.等人又于1995年提出了一种新的数据处理方法:三元概念分析(Triadic concept analysis, TCA) ^[7-8]。该理论可用于处理三维数据, 可从三维数据集(对象、属性及条件)的三元关系中得到三元概念及其层次结构。由于三元概念分析相关理论较形式概念分析而言更加复杂, 因此三元概念分析的研究成果也较少。魏玲等人从概念三元格的构造^[7-10]、三元蕴含及关联规则挖掘^[11-13]、三元模态算子^[14]、三元概念聚类^[15-18]以及三元背景的因子分析^[19-22]等角度对三元概念分析的现有研究工作进行了梳理总结, 使我们对三元概念分析有一个更全面的认识^[23]。

随着信息时代的到来, 三维数据日益增多, 三元概念分析的应用更加广泛。为了简化三元概念分析中的知识发现过程及知识表示结果, 本文从属性约简的角度出发, 对三元背景中的三个论域同时进行约简, 以确定保持各个论域中二元关系不变的最小子背景; 进而讨论约简中不同类型元素的相关性质; 最后给出约简前后三元概念之间的关系。

1 三元概念分析基础知识

三元概念分析中的基本概念与形式概念分析中类似, 包括三元背景, 诱导算子, 三元概念等。本节逐个给出。

定义1^[7-8]  称(K₁, K₂, K₃, Y)为一个三元背景, 其中K₁={g₁, …，g_p}为对象集, 每个g_i(i≤p)称为一个对象; K₂={m₁, …，m_q}为属性集, 每个m_j(j≤q)称为一个属性; K₃={b₁, …，b_r}为条件集, 每个b_k(k≤r)称为一个条件; Y为K₁, K₂和K₃之间的三元关系, Y⊆K₁×K₂×K₃。若(g, m, b)∈Y, 则表示对象g在条件b下有属性m, 若(g, m, b)∉Y, 则表示对象g在条件b下不具有属性m。

例1^[7]   表 1是一个关于人物特点评价的三元背景(K₁, K₂, K₃, Y)。其中对象集K₁={A, B, C}表示不同的人物特点; 属性集K₂={1, 2, 3, 4, 5, 6}给出了6种属性特征; 条件集K₃={a, b, c, d}给出了4种条件。交叉符号表示分属于3个不同集合的相应元素具有三元关系Y。

三元概念分析中有两类诱导算子, (i)-诱导算子与(i, j, X_k)-诱导算子, 具体定义如下。

定义2^[7-8]   设为三元背景, {i, j, k}={1, 2, 3}，且j < k，X⊆K_i。Z⊆ K_j×K_k, (i)-诱导算子定义为

X⁽ⁱ⁾={(a_j, a_k)∈K_j×K_k|(a_i, a_j, a_k)∈Y, ∀a_i∈K_i},

Z⁽ⁱ⁾={a_i∈K_i|(a_i, a_j, a_k)∈Y, ∀(a_j, a_k)∈Z}。

此类诱导算子实为经典形式背景 (K_i, K_j×K_k, Y⁽ⁱ⁾)上的算子, ∀g∈ K_i, m∈K_j, b∈ K_k, 有

(g, m, b)∈Y。

定义3^[7-8]   设 =(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}。X_i⊆ K_i, X_j⊆ K_j, X_k⊆ K_k, (i, j, X_k)-诱导算子定义为

X_i^{(i, j, X_k)}={a_j∈K_j|(a_i, a_j, a_k)∈Y, ∀(a_i, a_k)∈X_i×X_k},

X_j^{(i, j, X_k)}={a_i∈K_i|(a_i, a_j, a_k)∈Y, ∀(a_j, a_k)∈X_j×X_k}。

此类诱导算子实为经典形式背景 (K_i, K_j, Y_Xk^ij)上的算子, 其中

(a_i, a_j)∈Y_Xk^ij⇔∀ a_k∈ X_k, (a_i, a_j, a_k)∈Y。

由这两种诱导算子的定义及其与经典形式背景中算子的关系可知, 一个三元背景可看作是3个论域中两两之间关系所对应的三类形式背景的一种组合表示。其形式看似复杂, 本质上却比3类形式背景要简洁, 而所反映的信息一致。

利用这两类诱导算子可定义三元概念如下:

定义4^[7]   设 =(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且j < k。若X_i=(X_j×X_k)⁽ⁱ⁾, 则称(X_i, X_j，X_k)为三元背景的三元概念。其中, 称X_i为外延, X_j为内涵, X_k为方式。记三元背景的所有三元概念的集合为。

例2   例1中三元背景(K₁, K₂, K₃, Y)的所有三元概念的集合, 123456, abcd), (C, 126, abcd), (C, 123456, ab), (B, 15, cd), (A, 124, d), (AC, 12, abcd), (AC, 126, c), (BC, 6, b), (ABC, ∅, abcd), (ABC, 1, acd), (ABC, 123456, ∅)}, 相应的概念三元格如图 1所示, 其中从下到上、从左到右编号为1, 2, …，11的三元概念分别与上述集合中的概念一一对应。同一个方向直线上的点代表商集, 即该直线上的三元概念关于第i维是等价的(第i维上取值相同):水平直线上的概念关于第1维(对象集K₁)是等价的, 朝向左下方的直线上的概念关于第2维(属性集K₂)是等价的, 朝向右下方的直线上的概念关于第3维(条件集K₃)是等价的。例如, 标号分别为2与3的三元概念(C, 126, abcd)与(C, 123456, ab)在第1维上相等, 即关于第1维是等价的, 因此在图像上表现为这两个概念对应的点在同一条水平线上。

定义5   设 (K₁, K₂, K₃, Y)是一个三元背景, N_i⊆K_i, i=1, 2, 3, 称 =(N₁, N₂, N₃, Y∩(N₁×N₂×N₃))为的子背景。

定义6   设 =(K₁, K₂, K₃, Y)为三元背景, x, y∈K_k, {i, j, k}={1, 2, 3}且i < j。如果L(K_i, K_j, Y_x^ij)=L(K_i, K_j, Y_y^ij), 则称x与y是等价元素, 所有满足该式的y的集合记为[x], 读作x的等价元素类。

2 三元背景基于二元关系的约简

本节给出三元背景基于二元关系的约简的定义, 并依据约简将各个论域中的元素进行分类, 进而讨论不同类型的元素的性质。

2.1 约简的相关定义

定义7   设 =(K₁, K₂, K₃, Y)为三元背景, 如果存在集合N_i⊆K_i, {i, j, k}={1, 2, 3}, 满足, 则称N_i为论域K_i的保持二元关系不变的协调集, 称子背景(N₁, N₂, N₃, Y∩(N₁×N₂×N₃))为原三元背景的协调子背景。进一步, 若∀a_i∈N_i, 都有, 则称N_i为论域K_i的保持二元关系不变的约简(本文简称约简), 称子背景(N₁, N₂, N₃, Y∩(N₁×N₂×N₃))为原三元背景的约简背景。

实际上, K_i的保持二元关系不变的约简保持了该论域中所有元素所对应的形式背景上的概念不变; 而同时对3个论域进行约简, 约简后得到的子背景即为原三元背景的约简背景。

定义8   设 =(K₁, K₂, K₃, Y)为三元背景, K_i(i=1, 2, 3)上的所有约简为{N_ih|h∈τ_i}。集合K_i中的元素可以划分为以下3类(τ_i为K_i上的指标集):

1) 核心元素集;

2) 相对可删除元素集;

3) 绝对可删除元素集。

定理1  设(K₁, K₂, K₃, Y)为有限的三元背景, 论域K₁, K₂, K₃各自的约简必存在, 且约简背景必存在。

证明   若∀a_i∈K_i, {i, j, k}={1, 2, 3}且i < j, 都有

, 则K₁, K₂, K₃本身就是约简, (K₁, K₂, K₃, Y)就是其约简背景。若∃a_i∈K_i, {i, j, k}={1, 2, 3}且i < j, 有

, 则研究B_i1=K_i-{a_i}, 若∀b_i1∈B_i1, 都有

, 则B_i1为K_i的约简。否则, 进一步研究B_i2=B_i1-{b_i1}, 重复上述过程。由于K_i是有限集, 总可以找到至少一个约简。因此, K₁, K₂, K₃上的约简必存在; 相应地, 三元背景(K₁, K₂, K₃, Y)的约简背景必存在。

例3   续例1。固定K₃中的每个元素, 所产生的形式概念如表 2所示。

由定义7可知, a∈K₃可被删除, 因为(K₁, K₂, Y_a¹²)中的3个概念都可以从K₃其他元素确定的形式背景获得; 且由定义8知, {a}为K₃上的绝对可删除元素集合, {b, c, d}为K₃上的核心元素集合。类似计算可知2, 3∈K₂可被删除, {2, 3}为K₂上的绝对可删除元素集合, {1, 4, 5, 6}为K₂上的核心元素集合。因此, 原背景的约简背景为 =(K₁, K₂-{2, 3}, K₃-{a}, Y_new), 如表 3所示。

该约简背景所有三元概念的集合为 ={(∅, 1456, bcd), (B, 15, cd), (C, 16, bcd), (C, 1456, b), (A, 14, d), (AC, 1, bcd), (AC, 16, c), (BC, 6, b), (ABC, ∅, bcd), (ABC, 1, cd), (ABC, 1456, ∅)}, 相应的概念三元格如图 2所示, 其从下到上, 从左到右标记的11个概念依次与上述集合中的三元概念一一对应。对比图 1与图 2可知, 背景约简后, 三元概念的个数没有变化, 而三元概念格的结构更为简洁。

2.2 元素分类的相关性质

我们对各个论域上的元素根据其在约简过程中的作用进行分类, 进而逐个研究其性质。

定义9   设(K₁, K₂, K₃, Y)为三元背景, K_i(i=1, 2, 3)的所有约简为{N_ih|h∈τ_i}, 记Q_i为K_i上的相对可删除元素集, I_i为K_i上的绝对可删除元素集。对任意x_i∈Q_i, 称[x_i]为K_i上x_i的相对可删除类; 对任意x_i∈I_i, 称[x_i]为K_i上x_i的绝对可删除类。

因此，结合定义6可知:相对可删除类就是相对可删除元素集合中元素的等价元素类, 绝对可删除类就是绝对可删除集中元素的等价元素类。

2.2.1 绝对可删除类的性质

结合定义7及定义9, 我们可得到绝对可删除类的相关结论如下。

性质1  设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i < j, x_i为K_i上的一个绝对可删除元素, [x_i]为x_i相应的绝对可删除类, 则

证明   设为K_i上的所有约简, 由定义7知, ，所以

由定义9知, , 即 K_i-[x_i], 又∀N_ih, 有, 所以

故。

由性质1可知, 当x_i为K_i上的绝对可删除元素时, 其对应的整个绝对可删除类[x_i]对应的形式背景中的二元关系可由K_i中的其他元素所对应的形式背景的二元关系表示, 所以可将其全部删除。如例3中的绝对可删除元素a∈K₃, 从表 2可以看出, (K₁, K₂, Y_a¹²)的3个概念都可以从K₃其他元素确定的形式背景获得, 且其相应的绝对可删除类仅它一个元素。进而由定义6知, 该x_i所对应的形式背景产生的所有形式概念与[x_i]所对应的形式背景产生的所有形式概念相同, 因此可得如下推论。

推论1   设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i < j, x_i为K_i上的绝对可删除元素, [x_i]为K_i上的绝对可删除类, ∀x∈[x_i], 有

事实上, 绝对可删除类一般不止一个, 对于一个普通的绝对可删除元素而言, 我们结合定义6与定义9, 由推论1可得推论2。

推论2  设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i<j, K_i上的所有约简为{N_ih|h∈τ_i}, 则,

证明  因为, 由推论1知。又由于{x_i}⊆[x_i], 则K_i-[x_i]⊆K_i-{x_i}, 所以, 故L(K_j, K_k, 。

推论2表明, 当x_i为K_i集合的绝对可删除元素时, 该元素所对应形式背景中的二元关系可由该论域中的其他元素所对应的形式背景中的二元关系表示。

例4   续例3, 由表 2知,

因此,

2.2.2 相对可删除类的性质

接下来, 我们给出相对可删除类的相关性质。

性质2  设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i < j, [x_i]为K_i上的相对可删除类, Q为相对可删除元素集合, 则L(K_j, K_k, Y_xi^jk) 。进一步, 集合∅⊂M_i⊂[x_i]时, 有

证明  由于[x_i]⊆N_ih-∩N_ih且[x_i]⊄K_i-∪N_ih, 结合定义7, 有

且。

又因为, 且Q=∪[x_i], 则, 所以。进一步, 由定义6知, ∀x∈[x_i], 有L(K_j, K_k, Y_xi^jk)=L(K_j, K_k, Y_x^jk), 则对∅⊂M_i⊂[x_i], 有L(K_i, K_j, Y_xi^ij)⊆ 。

性质2表明, 当x_i为相对可删除元素时, 不能完全删除集合[x_i], 要至少保留[x_i]中的一个元素, 才能保证原三元背景中所有的二元关系不变, 进而保证所有的形式概念不变。

2.2.3 非核心元素的性质

由定义8知, 非核心元素集为, 其中包含绝对可删除元素和相对可删除元素。因此, 结合推论2和性质2可得如下定理。

定理2   设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i<j, K_i上的所有约简为{N_ih|h∈τ_i}, 则, 有

证明   设。若x_i为绝对可删除元素, 由推论2知

, 故; 若x_i为相对可删除元素, 令M={x_i}, 则由性质2知,

综上所述, 该定理得证。

定理2表明, 当x_i为集合K_i的非核心元素时, 该元素所对应形式背景中的二元关系可由该论域中的其他元素所对应的形式背景中的二元关系来表示和反映; 自然地, 一个论域中任意非核心元素所对应形式背景中的概念一定是该元素所在论域约简后的其他元素所对应形式背景的某个概念。

推论3   设(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且i < j, K_i上的所有约简为{N_ih|h∈τ_i}, 则, 有

证明  由定理2知, , 。又有

且由定义7知,

, 所以, 。

因此, 利用反证法, 可得到与推论3等价的性质。

性质3   设(K₁, K₂, K₃, Y)为三元背景, K_i(i=1, 2, 3)上的所有约简为{N_ih|h∈τ_i}, 则

, ∃b∈N_ih, 使得

1) i=1, 即(a, y, z)∈Y时, 必有(a, y, z)=(b, y, z);

2) i=2, 即(x, a, z)∈Y时, 必有(x, a, z)=(x, b, z);

3) i=3, 即(x, y, a)∈Y时, 必有(x, y, a)=(x, y, b)。

证明   设, 由定理2知。取i=1, 即。假设∀b∈N_ih, 都有(a, y, z)≠(b, y, z)。则有, Y_x²³), 与推论3矛盾, 故(a, y, z)=(b, y, z)。i=2, 3，同理可证。综上所述, 该性质得证。

3 约简前后三元概念之间的关系

由2.2节知, 在对每一个论域进行约简时, 该论域约简前后所有元素所对应的形式背景的形式概念不变。本节我们考虑约简前后原三元背景与约简背景上的三元概念之间的关系。

定理3   设 =(K₁, K₂, K₃, Y)为三元背景, N₁, N₂, N₃分别为K₁, K₂, K₃的约简, 记D₁=K₁-N₁, D₂=K₂-N₂, D₃=K₃-N₃, ={K₁-D₁, K₂-D₂, K₃-D₃, Y_R}, 其中Y_R=Y∩((K₁-D₁)×(K₂-D₂)×(K₃-D₃)), 则(B₁, B₂, B₃)∈ (B₁-D₁, B₂-D₂, B₃-D₃)∈ 。

证明   记中的Z⁽ⁱ⁾算子为Z^(i_R)。由定义4知, 只需证以下3式成立, 则定理得证。

(1)

(2)

(3)

证式(1)：由于

((B₁-D₁)×(B₂-D₂))^(3_R)= {a₃∈K₃-D₃|(a₁, a₂, a₃)∈Y_R, ∀a₁∈B₁-D₁, ∀a₂∈B₂-D₂}= {a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁-D₁, ∀a₂∈B₂-D₂}-D₃，

且。则由性质3知, ∀b₁∈D₁, (b₁, a₂, a₃)∈Y, ∃a₁∈K₁-D₁, 满足(a₁, a₂, a₃)=(b₁, a₂, a₃); ∀b₂∈D₂, (a₁, b₂, a₃)∈Y, ∃a₂∈K₂-D₂, 满足(a₁, a₂, a₃)=(a₁, b₂, a₃)。所以, 前面等式的第一项

{a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁-D₁, ∀a₂∈B₂-D₂}={a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈(B₁-D₁)∪(B₁∩D₁), ∀a₂∈B₂-D₂}={a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈(B₁-D₁)∪(B₁∩D₁), ∀a₂∈(B₂-D₂)∪(B₂∩D₂)}={a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂}=B₃，

故((B₁-D₁)×(B₂-D₂))^(3_R)=B₃-D₃。

同理可证式(2), (3)。

例5  由例2知(C, 126, abcd)∈ , 由例3知(C, 16, bcd)∈ , D₁=∅, D₂={2, 3}, D₃={a}, 又有{C}-D₁={C}, {126}-D₂={16}, {abcd}-D₃={bcd}, 因此有(C, 126, abcd)∈ (C-D₁, 126-D₂, abcd-D₃)∈ , 同理可得其他原三元背景的三元概念与约简背景的三元概念之间也满足此关系。

由定理3可知, 原来的三元概念在相应的维度上去掉D₁, D₂, D₃后就是约简背景的三元概念。下面的定理4说明约简背景的三元概念是由原三元概念去掉D₁, D₂, D₃之后产生的。

定理4  设=(K₁, K₂, K₃, Y)为三元背景, N₁, N₂, N₃分别为K₁, K₂, K₃的约简。记D₁=K₁-N₁, D₂=K₂-N₂, D₃=K₃-N₃, ={K₁-D₁, K₂-D₂, K₃-D₃, Y_R}, 其中Y_R=Y∩((K₁-D₁)×(K₂-D₂)×(K₃-D₃)), (B₁, B₂, B₃)∈ , (B₁-D₁, B₂-D₂, B₃-D₃)∈ 。则

(4)

(5)

(6)

证明   记删除集合D₁后, 三元背景中的三元关系为Y_R1。

证式(4)：因为

(B₁×B₂)⁽³⁾= {a₃∈K₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂}= {a₃∈K₃-D₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂} ∪{a₃∈D₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂}。

又。则由性质3知

{a₃∈K₃-D₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂}={a₃∈K₃-D₃|(a₁, a₂, a₃)∈Y_R1, ∀a₁∈B₁-D₁, ∀a₂∈B₂}={a₃∈K₃-D₃|(a₁, a₂, a₃)∈Y_R, ∀a₁∈B₁-D₁, ∀a₂∈B₂-D₂}=((B₁-D₁)×(B₂-D₂))^(3_R)。

又由于{a₃∈D₃|(a₁, a₂, a₃)∈Y, ∀a₁∈B₁, ∀a₂∈B₂}=(B₁×B₂)⁽³⁾∩D₃, 因此, (B₁×B₂)⁽³⁾=((B₁-D₁)×(B₂-D₂))^(3_R)∪((B₁×B₂)⁽³⁾∩D₃), 所以, (B₁×B₂)⁽³⁾-D₃=((B₁-D₁)×(B₂-D₂))^(3_R), 式(4)得证。

同理可证式(5)，(6)。

例6  由例2得, (C, 126, abcd)∈ , 再由例3知, D₁=∅, D₂={2, 3}, D₃={a}。于是, {C}-D₁={C}, {1, 2, 6}-D₂={1, 6}, {a, b, c, d}-D₃={b, c, d}, 则(C, 16, bcd)∈。

4 结语

属性约简是FCA的重要研究方向之一, 但是在TCA中还没有相关研究。本文在TCA框架下, 提出了保持三元背景上所有二元关系不变的属性约简问题, 给出了各个论域中绝对可删除类、相对可删除类的相关性质; 研究了各个论域在属性约简前后概念格的关系; 最后, 获得了约简前后三元概念之间的关系, 即原三元概念删去可删除元素后可得到新三元概念, 新三元概念是由原三元概念删去可删除元素获得的。

FCA中的属性约简有很多不同的角度和意义, 后期, 针对三元背景, 也可以根据实际问题从不同角度出发发掘出有意义的约简, 进而对TCA框架下的属性约简问题进行较为深入的研究; 也可以将本文所提出的约简与其他约简进行比较, 探讨它们之间的关系。

主持人语

形式概念分析理论是20世纪80年代由德国数学家Wille提出的一种数据分析理论。该理论以形式背景(由对象和属性组成的二维交叉表)为基础，从中提炼出形式概念，从而对哲学中的概念这一人类思维的基本单元进行了形式化表达，进一步又形成概念格这一核心数据结构，以进行知识的可视化表示。在形式概念分析中，通过对形式背景增加决策属性可得到决策形式背景，以此为基础可以研究决策规则获取并实现决策分析；若把形式概念的表现形式从经典集变为区间集，则可得到区间集概念这一新的数据表示方式，进而可提供对于概念知识的新理解与新解释，以及获取知识的新方法；三支决策是一种基于人类认知的决策模式，其思想普遍存在于生活的各个方面，把三支决策与形式概念分析相结合产生的三支概念分析就是一种新的进行数据分析和知识发现的新理论。此外，以形式背景扩展出的三元背景(由对象、属性和条件组成的三维交叉表)为基础的三元概念分析理论，是受实用主义哲学启发而提出的一种新的信息处理方法，是分析三维数据的新框架，对于形式概念分析理论的发展是一个很好的补充和完善。

本次专题针对形式概念分析理论中的一些重要问题进行研究，包括三元背景基于二元关系不变的约简，基于属性概念的决策形式背景协调性研究，区间集概念格的构造，以及概念格与三支决策的研究展望等四个方面的内容。这些工作有针对新问题的讨论，有对已有问题从新角度进行的重新认识，都将为形式概念分析理论的进一步研究打下基础。

主持人：魏玲，西北大学数学学院教授，博士生导师。