本节介绍三元形式概念分析的基本理论.

定义1^[1] 设F=(U, A, I)为形式背景, 其中

$U=\left\{u_{1}, u_{2}, \cdots, u_{l}\right\}, $

表示对象集,

$A=\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$

表示属性集.I表示笛卡尔积U× A上的二元关系, (u, a)∈ I表示对象u拥有属性a, 或属性a被对象u拥有.

$\forall U_{i} \subseteq U, A_{j} \subseteq A$, 定义如下算子:

$f\left(U_{i}\right)=\left\{a \in A \mid \forall u \in U_{i}, (u, a) \in I\right\}, $

表示U_i中所有对象共同拥有的属性集;

$g\left(A_{j}\right)=\left\{u \in U \mid \forall a \in A_{j}, (u, a) \in I\right\}, $

表示拥有A_j中所有属性的对象集.若

$f\left(U_{i}\right)=A_{j}, g\left(A_{j}\right)=U_{i}, $

则称序对(U_i, A_j)为概念, 其中U_i为概念的外延, A_j为概念的内涵.本文将所有形式概念组成的集合记为Ω .

对于$\forall U_{1} \subseteq U, U_{2} \subseteq U, \forall A_{1} \subseteq A, A_{2} \subseteq A$, 有如下性质成立:

1)$U_{1} \subseteq U_{2} \Rightarrow f\left(U_{2}\right) \subseteq f\left(U_{1}\right), $

2)$A_{1} \subseteq A_{2} \Rightarrow g\left(A_{2}\right) \subseteq g\left(A_{1}\right), $

3)$f\left(U_{1} \cup U_{2}\right)=f\left(U_{1}\right) \cap f\left(U_{2}\right), $

4)$f\left(U_{1} \cap U_{2}\right) \supseteq f\left(U_{1}\right) \cup f\left(U_{2}\right) .$

不仅如此, ∀ (U₁, A₁)∈ Ω , (U₂, A₂)∈ Ω , 上述算子满足关系:

$\begin{array}{l} \left(U_{1}, A_{1}\right) \vee\left(U_{2}, A_{2}\right)=\left(g f\left(U_{1} \cup U_{2}\right), A_{1} \cap A_{2}\right), \\ \left(U_{1}, A_{1}\right) \wedge\left(U_{2}, A_{2}\right)=\left(U_{1} \cap U_{2}, f g\left(A_{1} \cup A_{2}\right)\right) . \end{array}$

上述内容介绍形式概念分析的基本理论, 包括属性与对象之间的关系及概念定义.此外给出概念之间的关系, 即随着对象增多, 它们拥有的属性减少; 随着对象减少, 它们拥有的属性增多.

定义2^[14] 设T=(U, A, C, Y)为一个三元背景, 其中

U={u₁, u₂, …, u_l}

表示对象集, 每个u_i(i≤ l)表示一个对象;

A={a₁, a₂, …, a_m}

表示属性集, 每个a_j(j≤ m)表示一个属性;

C={c₁, c₂, …, c_n}

表示条件集, 每个c_k(k≤ n)表示一个条件.Y为U、A和C之间的三元关系:

Y⊆U× A× C.

若u、a和c具有关系Y, 记为(u, a, c)∈ Y, 表示对象u在条件c下具有属性a.

∀ U_i⊆U, Z⊆A_j× C_k, (* )-诱导算子定义如下:

$\begin{array}{l} U_{i}^{(* )}= \\ \left\{\left(a_{j}, c_{k}\right) \in A_{j} \times C_{k} \mid \forall u_{i} \in U_{i}, \left(u_{i}, a_{j}, c_{k}\right) \in Y\right\}, \\ Z^{(* )}=\left\{u_{i} \in U_{i} \mid \forall\left(a_{j}, c_{k}\right) \in Z, \left(u_{i}, a_{j}, c_{k}\right) \in Y\right\} \end{array}$

当$A_{j} \subseteq A, C_{k} \subseteq C, $定义(i, j, C_k)-诱导算子如下:

$\begin{array}{l} U_{i}^{\left(i, j, C_{k}\right)}= \\ \left\{a_{j} \in A_{j} \mid \forall\left(u_{i}, c_{k}\right) \in U_{i} \times C_{k}, \left(u_{i}, a_{j}, c_{k}\right) \in Y\right\}, \\ A_{j}^{\left(i, j, C_{k}\right)}= \\ \left\{u_{i} \in U_{i} \mid \forall\left(a_{j}, c_{k}\right) \in A_{j} \times C_{k}, \left(u_{i}, a_{j}, c_{k}\right) \in Y\right\} . \end{array}$

例1 表1为一个三元背景T=(U, A, C, Y), 该三元背景描述不同季节中5种植物的状态.5种植物分别为梅花(u₁)、蒲公英(u₂)、松树(u₃)、向日葵(u₄)和菊花(u₅), 构成对象集{u₁, u₂, u₃, u₄, u₅}.3种状态分别为花朵(a₁)、种子(a₂)和叶子(a₃), 构成属性集{a₁, a₂, a₃}.4个季节分别为春季(c₁)、夏季(c₂)、秋季(c₃)和冬季(c₄), 构成条件集{c₁, c₂, c₃, c₄}.表中, 1表示某个植物在特定季节处于某种特定状态, 0表示不处于该状态.

表1

Table 1

表1(Table 1)

表1 三元背景T=(U, A, C, Y) Table 1 A triadic context T=(U, A, C, Y) 春季 夏季 秋季 冬季 花朵 种子 叶子 花朵 种子 叶子 花朵 种子 叶子 花朵 种子 叶子 梅花 1 0 1 0 1 1 0 0 1 1 0 0 蒲公英 1 1 1 0 1 1 0 0 1 0 0 0 松树 1 0 1 0 0 1 0 1 1 0 0 1 向日葵 0 0 0 1 0 1 0 1 1 0 0 0 菊花 0 0 1 0 0 1 1 0 1 0 1 0

表1 三元背景T=(U, A, C, Y) Table 1 A triadic context T=(U, A, C, Y)

定义3^[14] 设T=(U, A, C, Y)为一个三元背景,

U_i⊆U, A_j⊆A, C_k⊆C.

若满足

$\begin{array}{l} U_{i}=\left(A_{j} \times C_{k}\right)^{(* )}, \\ A_{j}=\left(U_{i} \times C_{k}\right)^{(* )}, \\ C_{k}=\left(U_{i} \times A_{j}\right)^{(* )}, \end{array}$

则称(U_i, A_j, C_k)为三元背景T的三元概念, 并称U_i为外延, A_j为内涵, C_k为方式.记T中所有三元概念组成的集合为Ω .

定义4^[14] 设T=(U, A, C, Y)为一个三元背景, ∀ C_k⊆C, C_k≠ Ø , 称(U, A, C_k, YCk)为一个三元子背景, 其中

$Y_{C_{k}} \subseteq Y \cap(U \times A \times C) .$

特别地, 当|C_k|=1时, 三元子背景退化为二元形式背景.

为了后续并行算法的有效开展, 本节提出临时概念、临时属性-条件三元概念及过程三元概念的定义, 并基于这些概念计算对象-属性三元概念和属性-条件三元概念.同时也表明, 所有三元概念均可通过合并对象-属性三元概念和属性-条件三元概念构造生成.

定义5 设T=(U, A, C, Y)为一个三元背景, C₁, C₂, …, Cr0为C的子集.若

$C=\bigcup_{r=1}^{r_{0}} C_{r}, $

且

$C_{r} \cap C_{s}=\emptyset$

对所有的r≠ s均成立, 则称条件集C被划分为r₀个互不相交的子集.当r₀=n时, 称T_r=(U, A, C_r, YCr)为一个单条件三元背景; 否则T_r为一个多条件三元背景.

定义6 设T_r=(U, A, C_r, YCr)为单条件三元背景, 若∀ u_m∈ U满足

B_s∈ 2^A\Ø , s=1, 2, …, 2^|A|-1,

其中|A|表示集合的元素个数, 则称(u_m, B_s, c)为临时概念, 其中u_m为对象, B_s为在给定条件c下该对象u_m拥有的属性.全部临时概念组成的集合记为Ω _uc.

定义7 设T_r=(U, A, C_r, YCr)为单条件三元背景.若∀ U'⊆U, A'⊆A, 当(U', A')∈ ΩCr时, 则称(U', A', C_r)为过程三元概念, 其中 ΩCr表示三元背景在条件C_r下对应形式背景的形式概念组成的集合.

假设(u', A', c)为临时概念, 接下来给出使用临时概念集合Ω _uc和由临时概念“ 外延合并” 生成的中间概念Ω ₁进一步生成过程三元概念集合Ω ₂的构造方法.具体步骤如下.

1)外延合并.将Ω _uc中的全部临时概念在条件和内涵相同时合并外延形成新的集合:

$\begin{aligned} \mathcal{U}_{1}= & \left\{\left(\cup\left\{U^{\prime} \mid\left(U^{\prime}, A^{\prime}, c\right) \in \mathcal{U}_{u c}, A^{\prime}=A_{0}^{\prime}\right\}, A_{0}^{\prime}, c_{0}\right) \mid\right. \\ & \left.\forall\left(U_{0}^{\prime}, A_{0}^{\prime}, c_{0}\right) \in \widetilde{U}_{u c}\right\} . \end{aligned}$

2)内涵合并.将Ω ₁中所有临时概念在条件和外延相同时合并内涵, 形成新的集合:

$\begin{aligned} \mathcal{U}_{2}= & \left\{\left(U_{0}^{\prime}, \cup\left\{A^{\prime} \mid\left(U^{\prime}, A^{\prime}, c\right) \in U_{1}, U^{\prime}=U_{0}^{\prime}\right\}, c_{0}\right) \mid\right. \\ & \left.\forall\left(U_{0}^{\prime}, A_{0}^{\prime}, c_{0}\right) \in \widetilde{U}_{1}\right\} . \end{aligned}$

因此Ω ₂为通过上述两个步骤形成过程三元概念组成的集合.

定理1 设Ω _uc为临时概念的集合, 通过外延合并和内涵合并两步操作从集合Ω _uc生成的集合Ω ₂为过程三元概念.

证明 设∀ U₁⊆U, U₂⊆U, A₁⊆A, A₂⊆A, (U₁, A₁, c)为单条件三元背景T_r的一个过程三元概念.假设

$\left(U_{1}, A_{1}, c\right) \notin U_{2}, $

则一定存在一个过程三元概念(U₂, A₂, c)满足U₁⊆U₂或A₁⊆A₂.

若U₁⊆U₂且A₁=A₂, 则∃u∈ U₂\U₁, 使得(U₁∪ {u}, A₁, c)构成一个过程三元概念.

若U₁=U₂且A₁⊆A₂, 则∃a∈ A₂\A₁, 使得(U₁, A₁∪ {a}, c)构成一个过程三元概念.

若U₁⊆U₂且A₁⊆A₂, 则这种情况一定经过上述两个步骤生成过程三元概念

$\left(U_{1} \cup\{u\}, A_{1} \cup\{a\}, c\right) .$

在3种情况下假设(U₁, A₁, c)∉Ω ₂导致能构造新的过程三元概念, 而这种构造与初始假设矛盾, 即(U₁, A₁, c)∈ Ω ₂成立.由此定理1得证.

定理1表明, 对于单条件三元背景, 当条件唯一时, 先对相同内涵但不同外延的临时概念求并集, 然后对相同外延但不同内涵的临时概念求并集, 从而计算全部的过程三元概念.根据定义6可知单条件三元背景的临时概念也是生成形式概念的中间结构.

例2 根据定义7和定理1, 计算例1中春天这一条件下的所有单条件三元背景对应的全部过程三元概念:

$\begin{array}{l} \left(\left\{u_{1}, u_{2}, u_{3}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{1}, a_{2}, a_{3}\right\}, \left\{c_{1}\right\}\right) \\ \left(\left\{u_{1}, u_{2}, u_{3}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(U, \emptyset, c_{1}\right) . \end{array}$

类似地, 在条件c₂、c₃和c₄下可计算例1对应的单条件三元背景下的所有过程三元概念的集合.

定义8 设T=(U, A, C, Y)为一个三元背景, 若∀ (U', A')∈ ΩCr, ∃C'⊆C, 使得三元组(U', A', C')满足

$\begin{array}{l} U^{\prime}=\left(A^{\prime} \times C^{\prime}\right)^{(* )}, \\ A^{\prime}=\left(U^{\prime} \times C^{\prime}\right)^{(* )}, \\ C^{\prime}=\left(U^{\prime} \times A^{\prime}\right)^{(* )}, \end{array}$

则称UA=(U', A', C')为一个对象-属性三元概念.

根据定义7和定义8可知, 当一个过程三元概念的内涵和外延都分别为另一个过程三元概念的内涵和外延的子集时, 合并这些条件就可生成一个对象-属性三元概念, 所有对象-属性三元概念组成的集合记为Ω _UA.

例3 例2已得到所有过程三元概念, 依据前述结论, 可进一步计算所有的对象-属性三元概念:

$\begin{array}{l} \left(\left\{u_{1}, u_{2}, u_{3}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{2}\right\}, \left\{c_{4}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{1}, a_{2}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{1}, u_{2}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{4}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{3}, u_{4}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ \left(\left\{u_{3}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}, c_{4}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}\right\}\right), \\ (U, \emptyset, C), \\ (\emptyset, A, C), \\ \left(\left\{u_{1}\right\}, \left\{a_{1}\right\}, \left\{c_{1}, c_{4}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}, u_{4}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{2}, c_{3}\right\}\right) . \end{array}$

定理2 设T=(U, A, C, Y)为三元背景,

$h:\left(U_{i}, A_{j}\right) \mapsto\left(U_{i}, A_{j}, \left(U_{i} \times A_{j}\right)^{(* )}\right), $

定义映射

$h:\left(U_{i}, A_{j}\right) \mapsto\left(U_{i}, A_{j}, \left(U_{i} \times A_{j}\right)^{(* )}\right), $

其中

$\Omega_{C}=\bigcup_{r=1}^{n} \Omega_{C_{r}}, $

则该映射h为一个单射.

证明 首先, 证明映射h的合理性.

$\forall\left(U_{i}, A_{j}\right) \in \Omega_{C}, \exists C_{k} \subseteq C\left(C_{k} \neq \emptyset\right)$

满足

$U_{i}^{\left(i, j, C_{k}\right)}=A_{j}$

且

$A_{j}^{\left(i, j, C_{k}\right)}=U_{i}, $

显然

$C_{k} \subseteq\left(U_{i} \times A_{j}\right)^{(* )} .$

设

$c \in\left(U_{i} \times A_{j}\right)^{(* )}, $

则可推导出

$A_{j}^{\left(i, j, C_{k}\right)} \subseteq A_{j}^{(i, j, c)}$

且

$U_{i}^{\left(i, j, C_{k}\right)} \subseteq U_{i}^{(i, j, c)} .$

故如下等式成立:

$\begin{aligned} U_{i}^{\left(i, j, C_{k}\right)}= & \cap\left\{U_{i}^{(i, j, c)} \mid c \in\left(U_{i} \times A_{j}\right)^{(* )}\right\}= \\ & U_{i}^{\left(i, j, \left(U_{i} \times A_{j}\right)^{(* )}\right)}=A_{j}, \end{aligned}$

$\begin{aligned} A_{j}^{\left(i, j, C_{k}\right)}= & \cap\left\{A_{j}^{(i, j, c)} \mid c \in\left(U_{i} \times A_{j}\right)^{(* )}\right\}= \\ & A_{j}^{\left(i, j, \left(U_{i} \times A_{j}\right)^{(* )}\right)}=U_{i}, \end{aligned}$

因此

$\forall\left(U_{i}, A_{j}\right) \in \Omega_{C}, \left(U_{i}, A_{j}, \left(U_{i} \times A_{j}\right)^{(* )}\right) \in U_{0} .$

然后证明映射h为单射.根据定义方式可直接得到.

定理2表明, 对于Ω _C中不同的形式概念而言, 可生成与之对应的三元概念.然而, 对于全部三元概念构成的集合Ω 中却有一部分三元概念并不能通过Ω _C集合中的形式概念诱导生成.因此, 该映射h不是满射.

定义9 设T_r=(U, A, C_r, YCr)为单条件三元背景, U₁, U₂, …, Uv0为U的子集.若

$U=\bigcup_{v=1}^{v_{0}} U_{v}, $

则集合U被划分为v₀个互不相交的子集U₁, U₂, …, Uv0.特别地, 当v₀=l时, 称T_{v, r}=(U_v, A, C_r, YUv, Cr)为一个单对象-单条件三元背景, 即对象集被划分为只包含一个对象的子集.

设T_{v, r}=(U_v, A, C_r, YUv, Cr)为一个单对象-单条件三元背景, T_u=(u, A, C, Y_{u, C})为合并T_{v, r}的条件生成的单对象-多条件三元背景, T_v生成的全部形式概念的集合记为 ΩUv.

定义10 设T_u=(u, A, C, Y_{u, C})为单对象-多条件三元背景, 若∀ c_n∈ C, 满足

$B_{n} \in 2^{A} \backslash \emptyset, $

则称(u, B_n, c_n)为临时属性-条件三元概念, 其中u为对象, B_n为在给定对象u时条件c_n拥有的属性.

$\forall A^{\prime \prime} \subseteq A, C^{\prime \prime} \subseteq C, $当$\left(A^{\prime \prime}, C^{\prime \prime}\right) \in \Omega_{U_{v}}$时, 称(u, $ A^{\prime \prime}, C^{\prime \prime}$)为一个过程三元概念.

定义11 设T=(U, A, C, Y)为一个三元背景, 若∀ (A″, C″)∈ ΩUv, ∃U″⊆U, 使三元组(U″, A″, C″)满足

$\begin{aligned} U^{\prime \prime} & =\left(A^{\prime \prime} \times C^{\prime \prime}\right)^{(* )}, \\ A^{\prime \prime} & =\left(U^{\prime \prime} \times C^{\prime \prime}\right)^{(* )}, \\ C^{\prime \prime} & =\left(U^{\prime \prime} \times A^{\prime \prime}\right)^{(* )}, \end{aligned}$

则称AC=(U″, A″, C″)为一个属性-条件三元概念.

根据(u, A″, C″)和定义11可知, 当一个过程三元概念的内涵和方式都分别包含于另一个过程三元概念的内涵和方式时, 合并它们的对象可生成一个属性-条件三元概念.所有属性-条件三元概念组成的集合记为Ω _AC.

例4 基于例1, 并结合定义10和定义11, 可计算所有的属性-条件三元概念Ω _AC如下:

$ \begin{array}{l} \left(\left\{u_{1}, u_{2}, u_{3}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}\right\}\right), \\ \left(\left\{u_{4}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{1}, a_{2}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{3}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}, c_{4}\right\}\right), \\ \left(\left\{u_{1}, u_{2}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}, u_{4}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{2}, c_{3}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{2}\right\}, \left\{c_{4}\right\}\right), \\ \left(\left\{u_{3}, u_{4}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ (U, A, \emptyset), \\ \left(\left\{u_{1}\right\}, \left\{a_{1}\right\}, \left\{c_{1}, c_{4}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{1}, c_{2}\right\}\right) . \end{array}$

定理3 设T=(U, A, C, Y)为三元背景,

$ \forall\left(A_{j}, C_{r}\right) \in \Omega_{U}, \left(\left(A_{j} \times C_{r}\right)^{(* )}, A_{j}, C_{r}\right) \in U, $

定义映射:

$ h:\left(A_{j}, C_{r}\right) \mapsto\left(\left(A_{j} \times C_{r}\right)^{(* )}, A_{j}, C_{r}\right), $

其中

$\Omega_{U}=\bigcup_{v=1}^{l} \Omega_{U_{v}}, $

则该映射为Ω _U到Ω 的单射.

证明 具体过程与定理2类似, 故不再赘述.

定理4 设T=(U, A, C, Y)为三元背景,

$\widetilde{V}^{\prime}=\widetilde{U}_{U A} \cup \widetilde{U}_{A C}, $

若∀ (U', A', C')∈ Ω '且(U, A, C)∈ Ω , 映射

$p:\left(U^{\prime}, A^{\prime}, C^{\prime}\right) \mapsto(U, A, C)$

为从Ω '到Ω 的双射.

证明 首先证明映射p为单射.根据定义方式可直接得到.

然后证明映射p为满射.利用反证法, 假设p不是满射, 则∃(U, A, C)∈ Ω , 使得对所有

$\left(U^{\prime}, A^{\prime}, C^{\prime}\right) \in \widetilde{J}^{\prime}, $

都有

$p\left(U^{\prime}, A^{\prime}, C^{\prime}\right) \neq(U, A, C) .$

由定义3可知, 必有A∈ ΩCk或A∈ Ω _r.根据定理2和定理3, 必然∃(U', A', C')∈ Ω ', 使得A'=A, 因此假设不成立, 故p是满射.

综上可知p为双射.

定理4表明, 所有的三元概念都可通过合并对象-属性三元概念和属性-条件三元概念这两类基本三元概念生成.这意味着在三元关系的框架内, 任何复杂的三元概念都可通过这两种基本类型三元概念的组合进行构建, 从而简化三元概念的构建过程.

例5 通过例3和例4的结果, 以及定理4, 可将所有对象-属性三元概念和属性-条件三元概念合并为最终的三元概念.因此例1计算的最终的三元概念结果如下:

$\begin{array}{l} \left(\left\{u_{1}, u_{2}, u_{3}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}\right\}\right), \\ \left(\left\{u_{4}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{1}, a_{2}, a_{3}\right\}, \left\{c_{1}\right\}\right), \\ \left(\left\{u_{3}\right\}, \left\{a_{3}\right\}, \left\{c_{1}, c_{2}, c_{3}, c_{4}\right\}\right), \\ \left(\left\{u_{1}, u_{2}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{2}\right\}\right), \\ \left(\left\{u_{2}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{1}, c_{2}\right\}\right), \\ \left(\left\{u_{1}, u_{2}, u_{3}, u_{4}, u_{5}\right\}, \left\{a_{3}\right\}, \left\{c_{2}, c_{3}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{1}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ \left(\left\{u_{5}\right\}, \left\{a_{2}\right\}, \left\{c_{4}\right\}\right), \\ (U, \emptyset, C), \\ \left(\left\{u_{3}, u_{4}\right\}, \left\{a_{2}, a_{3}\right\}, \left\{c_{3}\right\}\right), \\ (\emptyset, A, C), \\ \left(\left\{u_{1}\right\}, \left\{a_{1}\right\}, \left\{c_{1}, c_{4}\right\}\right), \\ (U, A, \emptyset) . \end{array}$

为了更直观地描述三元概念, 通过图1展示例5中的15个三元概念构成的三元图.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 三元背景T上的三元图Fig.1 Triadic diagram of triadic context T

图1的上方线图称为方式图, 其中每个圆圈表示一个三元概念的方式, 包含该圆圈所示条件及其右侧连接的圆圈所示的条件.左下方的线图称为内涵图, 每个圆圈表示一个三元概念的内涵, 包含该圆圈所示的属性以及其左上方连接的圆圈所示的属性.右下方的线图称为外延图, 每个圆圈表示一个三元概念的外延, 包含该圆圈所示的对象及其左下方连接的圆圈所示的对象.三元图中间的倒三角区域中的每个圆圈表示一个三元概念, 通过虚线与外延图、内涵图和方式图中的圆圈相连, 分别表示该三元概念的外延、内涵和方式.

本文研究分布式并行三元概念的构建, 设计基于Spark框架的算法, 构建形式概念和三元概念, 并采用两阶段优化策略优化数据倾斜问题.在不同数据集上的增强实验表明:分布式并行算法在概念构建中效率较高, 可有效利用内存和CPU资源.

Spark框架的并行算法性能良好, 但仍存在一些局限性.当属性和条件数量增加时, 如何设计算法避免生成大量无用的临时概念是一个挑战.其次, 设计一种算法优化Spark并行计算框架的内存, 进一步提升内存利用效率亦值得思考.为了实现更高的计算效率, 可利用增强型并行框架Flink, 设计增量式分布式并行算法, 更有效地构建三元概念.今后将考虑基于Flink框架和更合理的分布式数据库开发更高效的并行算法, 进一步提升三元概念的构造效率.

本文责任编委 苗夺谦

Recommended by Associate Editor MIAO Duoqian