概念格是由Wille^[1]于1982年提出的理论，一般可用于解决数据处理等相关的问题。Yao^[2]于2009年将延迟决策引入粗糙集的二支决策中，将二支决策进而拓展为更符合现实决策情况的三支决策理论。三支决策被引入概念格理论，Qi等^[3]提出了三支概念的定义，将三支概念分为对象三支概念与属性三支概念。

从完备性方面区分，形式背景分为完备形式背景与不完备形式背景。本文研究建立在完备形式背景之上。对完备形式背景的研究中，研究方向通常分为对三支概念的属性约简、概念构建以及其他方面的研究。在属性约简方面，Ren等^[4]设计了4种属性约简方法，对4种约简方法之间的联系进行了分析；在三支概念构建方面，Qi等^[5]在对标准形式概念的分析基础上，设计了一种利用标准概念求得三支概念的方法；汪文威等^[6]在CbO算法的基础上进行调整，提出了CbO3C算法用于构建三支概念；Qian等^[7]利用上位背景和下位背景，设计了一种三支概念构建方法；Mao等^[8]研究了标准概念与对象(属性)三支概念间的关系，并根据所得关系设计了构建三支概念的算法；在其他方面，刘琳等^[9]利用属性三支概念对规则提取问题进行了讨论；Singh^[10]通过对中智图、中智格和Gödel剩余格的性质分析，设计了基于模糊概念格生成分量式三支模糊概念的方法，并将其层次顺序可视化；Singh^[11]利用单值中智图的概念格的性质对医学数据集进行分析，提出了计算三支模糊概念的欧几里德距离的方法。其他三支概念格方面的研究参考文献[12-16]。

在采用矩阵结构进行三支概念的研究中，李美争等^[17]定义了对象−概念辨识矩阵来研究三支近似概念的约简问题；陈雪等^[18]利用差别矩阵及差别函数计算得到了决策形式背景下的属性约简结果。

本文将矩阵思想与三支概念构建的研究相结合，定义出属性（对象）矩阵，并利用属性（对象）矩阵结构设计了构建三支概念的算法。

1 基础知识

对于相对成熟的矩阵理论，在此不做赘述，相关内容详见文献[19]。本节将对利用到的标准形式概念及三支概念的一些定义及性质进行说明，其中标准形式概念的内容详见文献[20]，三支概念的相关知识详见文献[3, 5]。

定义1^[20] 　形式背景 $(G,M,I)$ 是由两个集合 $G$ 和 $M$ 以及 $G$ 与 $M$ 间的二元关系 $I$ 组成。 $G$ 为对象集， $M$ 为属性集， $I \subseteq G \times M$ 。在对象集合 $A \subseteq G$ 中，令

$ {A^*}: = \{ m \in M|I_{gm}{\text{对于任意}}g \in A{\rm{\} }} $

其中 ${I_{gm}}$ 表示对象 $g$ 与属性 $m$ 间满足二元关系 $I$ (或者对象 $g$ 具有属性 $m$ )。

在属性集合 $B \subseteq M$ 中，令

$ {B^*}: = \{ g \in G|I_{gm}{\text{对于任意}}m \in B{\rm{\} }} $

若对集合 A、B 有 ${A^*} = B$ 和 ${B^*} = A$ 同时成立，则 $(A,B)$ 称为一个标准形式概念。其中标准形式概念的外延为 $A$ ，标准形式概念的内涵为 $B$ 。

所有基于正算子“ $^{*}$ ”形成的概念 $(A,B)$ 构成集合 ${\rm{CL}}(G,M,I)$ 。

任意的概念 $({A_1},{B_1})$ 与 $({A_{\rm{2}}},{B_{\rm{2}}})$ 间的关系如下：

$({A_1},{B_1}) \leqslant ({A_{\rm{2}}},{B_{\rm{2}}}) \Leftrightarrow {A_1} \subseteq {A_2}( \Leftrightarrow {B_1} \supseteq {B_2})。$

定义2 ^[20] 　假设 $(G,M,I)$ 是一个形式背景， ${I^c} = (G \times M)- I$ ，对象集合 $A \subseteq G$ ，定义

${A^{\bar *}} = \{ m \in M|\forall g \in A({I}_{gm}^c)\} $

属性集合 $B \subseteq M$ ，定义

${B^{\bar *}} = \{ g \in G|\forall m \in B({I_{gm}^c})\} $

如果 ${A^{{\rm{\bar *}}}}{\rm{ = }}B$ 和 ${B^{\bar *}} = A$ 同时成立，则称 $(X,A)$ 为一个标准形式概念。所有负算子“ $^{{\rm{\bar *}}}$ ”下成立的标准形式概念 $(X,A)$ 记成集合 ${\rm{NCL}}(G,M,I)$ 。

定义3^[5] 　假设 $(G,M,I)$ 形式背景， $^{ < \cdot }:P(G) \to {\rm{DP}}(M)$ 和 $^{ \cdot > }:{\rm{DP}}(M) \to P(G)$ 分别为集合 $X \subseteq G$ 和 $A,B \subseteq M$ 上的基于对象导出的算子。算子运算方式如下：

$ {X^{ < \cdot }} = ({X^*},{X^{\bar *}}) $

$ {(A,B)^{ \cdot > }} = \{ x \in G|x \in {A^*},x \in {B^{\bar *}}\} = {A^*} \cap {B^{\bar *}}。$

$(G,M,I)$ 是一个形式背景。 $^{ < \cdot }:P(M) \to {\rm{DP}}(G)$ 和 $^{ \cdot > }:{\rm{DP}}(G) \to P(M)$ 分别为集合 $X,Y \subseteq G$ 和 $A \subseteq M$ 上的基于属性导出的算子。算子运算方式如下：

${A^{ < \cdot }} = ({A^*},{A^{\bar *}}),$

${(X,Y)^{ \cdot > }} = \{ v \in M|v \in {X^*},v \in {Y^{\bar *}}\} = {X^*} \cap {Y^{\bar *}}。$

定义4^[5] 　形式背景 $(G,M,I)$ ，如果在对象集合 $X \subseteq G$ ，属性集合 $A,B \subseteq M$ 上， ${X^{ < \cdot }} = (A,B)$ 和 ${(A,B)^{ \cdot > }} = X$ 同时成立，则称 $(X,(A,B))$ 为对象三支概念。全体 $((X,Y),A)$ 记入集合 ${\rm{OEL}}(G,M,I)$ 。

任意三支概念 $(X,(A,B))$ 和 $(Y,(C,D))$ 之间的关系定义如下：

$ (X,(A,B)) \leqslant (Y,(C,D)) \Leftrightarrow X \subseteq Y \Leftrightarrow (C,D) \subseteq (A,B) $

性质1^[5] 　对于集合 $X,{X_1},{X_2} \subseteq G;A,{A_1},{A_2},B,{B_1},$ ${B_2} \subseteq M$ ，则有以下性质成立：

$({\rm{OE}}_1)\;X \subseteq {X^{ < \cdot \cdot > }},(A,B) \subseteq {(A,B)^{ \cdot > < \cdot }}$

$ ({\rm{OE}}_2)\;{X_1} \subseteq {X_2} \Rightarrow X_2^{ < \cdot } \subseteq X_1^{ < \cdot },({A_1},{B_1}) \subseteq ({A_2},{B_2})\Rightarrow $

$ {({A_2},{B_2})^{ \cdot > }} \subseteq {({A_1},{B_1})^{ \cdot > }} $

$({\rm{OE}}_3)\;{X^{ < \cdot }} = {X^{ < \cdot \cdot > < \cdot }},{(A,B)^{ \cdot > }} = {(A,B)^{ \cdot > < \cdot \cdot > }}$

$({\rm{OE}}_4)\;X \subseteq {(A,B)^{ \cdot > }} \Leftrightarrow (A,B) \subseteq {X^{ < \cdot }}$

$ ({\rm{OE}}_5)\;{({X_1} \cup {X_2})^{ < \cdot }} = X_1^{ < \cdot } \cap X_2^{ < \cdot },(({A_1},{B_1}) \cup ({A_2} $

$ {B_2}){)^{ \cdot > }} = {({A_1},{B_1})^{ \cdot > }} \cap {({A_2},{B_2})^{ \cdot > }} $

$ ({\rm{OE}}_6)\;{({X_1} \cap {X_2})^{ < \cdot }} \supseteq X_1^{ < \cdot } \cup X_2^{ < \cdot },(({A_1},{B_1}) \cap ({A_2}, $

$ {B_2}){)^{ \cdot > }} = {({A_1},{B_1})^{ \cdot > }} \cup {({A_2},{B_2})^{ \cdot > }}。$

定义5^[5] 　形式背景 $(G,M,I)$ ，如果在属性集合 $A \subseteq M$ ，对象集合 $X,Y$ $ \subseteq G$ 上 ${A^{ < \cdot }} = (X,Y)$ 和 ${(X,Y)^{ \cdot > }} = A$ 同时成立，则称 $((X,Y),A)$ 为属性三支概念。全体三支概念 $((X,Y),A)$ 记入集合 ${\rm{AEL}}(G,M,I)$ 。

对于任意的属性三支概念 $((X,Y),A)$ 和 $((Z,W),B)$ ，给出如下定义：

$ ((X,Y),A) \leqslant ((Z,W),B) \Leftrightarrow (X,Y) \subseteq (Z,W) \Leftrightarrow B \subseteq A $

性质2^[5] 　在集合 $X,{X_1},{X_2},Y,{Y_1},{Y_2} \subseteq G,A,{A_1}$ ， ${A_2} \subseteq M$ 上有以下性质成立：

$({\rm{AE}}_1)\;(X,Y) \subseteq {(X,Y)^{ \cdot > < \cdot }},A \subseteq {A^{ < \cdot \cdot > }}$

$ ({\rm{AE}}_2)\;({X_1},{Y_1}) \subseteq ({X_2},{Y_2}) \Rightarrow {({X_2},{Y_2})^{ \cdot > }} \subseteq {({X_1},{Y_1})^{ \cdot > }} $

$ {A_1} \subseteq {A_2} \Rightarrow A_2^{ < \cdot } \subseteq A_1^{ < \cdot } $

$({\rm{AE}}_3)\;{(X,Y)^{ \cdot > }} = {(X,Y)^{ \cdot > < \cdot \cdot > }},{A^{ < \cdot }} = {A^{ < \cdot \cdot > < \cdot }}$

$ ({\rm{AE}}_4)\;(X,Y) \subseteq {A^{ < \cdot }} \Leftrightarrow A \subseteq {(X,Y)^{ \cdot > }} $

$ ({\rm{AE}}_5)\;{(({X_1},{Y_1}) \cup ({X_2},{Y_2}))^{ \cdot > }} = {({X_1},{Y_1})^{ \cdot > }} \cap ({X_2}, $

$ {Y_2}{)^{ \cdot > }},{({A_1} \cup {A_2})^{ < \cdot }} = A_1^{ < \cdot } \cap A_2^{ < \cdot } $

$ ({\rm{AE}}_6)\;{(({X_1},{Y_1}) \cap ({X_2},{Y_2}))^{ \cdot > }} \supseteq {({X_1},{Y_1})^{ \cdot > }} \cup ({X_2}, $

$ {Y_2}{)^{ \cdot > }},{({A_1} \cap {A_2})^{ < \cdot }} \supseteq A_1^{ < \cdot } \cup A_2^{ < \cdot }。$

2 概念的构建 2.1 依据属性矩阵构建属性三支概念

定义6　形式背景 $(G,M,I)$ ，其中属性集合 $M = \{ {a_1},{a_2}, \cdots ,{a_n}\} $ 。定义：令 ${{W}} = ({w_{ij}});{w_{ij}} = (a_i^* \cap a_j^*,$ $a_i^{\bar *} \cap a_j^{\bar *});{a_i},{a_j} \in M;n \in {Z^ + }; \;i,j = 1,2, \cdots ,n$ 。则 ${{W}}$ 为一个 $n \times n$ 的属性矩阵，易得属性矩阵 ${{W}}$ 为对称矩阵。

例1　形式背景 $({G_1},{M_1},{I_1})$ 如表1所示，在此基础上构建属性矩阵 ${{{W}}_{{1}}}$ 。

由表1可知： ${w_{11}}\! =\! ({a^*} \cap {a^*},{a^{\bar *}} \!\cap\! {a^{\bar *}}) \!=\! (123,4),{w_{12}} \!=\! ({a^*} \!\cap\! {b^*},$ ${a^{\bar *}} \! \cap\! {b^{\bar *}}) \!= (3,{\text{Ø}} ), \cdots ,{w_{34}} = ({c^*} \cap {d^*},{c^{\bar *}} \cap {d^{\bar *}}) = (2,3),$ ${w_{44}} = $ $({d^*} \cap {d^*},{d^{\bar *}} \cap {d^{\bar *}}) = (24,13){\text{。}}$

所以

${{{W}}_{{1}}} = \left[ {\begin{array}{*{20}{c}} {(123,4)}&{(3,{\text{Ø}} )}&{(12,{\text{Ø}} )}&{(2,{\text{Ø}} )} \\ {}&{(34,12)}&{(4,{\text{Ø}} )}&{(4,1)} \\ {}&{}&{(124,3)}&{(24,3)} \\ {}&{}&{}&{(24,13)}\\ \end{array}} \right]$

构建属性三支概念的算法过程如算法1。

算法1　属性三支概念生成算法。

输入　形式背景 $(G,M,I)$ 。

输出　 ${\rm{AEL}}(G,M,I)\backslash \{ ((G,G),{\text{Ø}} )\}$ 。

1)生成形式背景 $(G,M,I)$ 的属性矩阵 ${{W}}$ ，并将属性矩阵 ${{W}}$ 的所有元素构成的集合记成集合 $P$ ；

2) $ i = 1$ ；

3) $ j = 1$ ；

4) $ s = 1$ ；

5) $ w = {w_{ij}} \cap {w_{is}}$ ；

6) 如果 $w \notin P$ ，则 $P = P \cup \{ w\} $ ， $s = s + 1$ 并执行7)；反之 $s = s + 1$ ，并执行7)；

7) 如果 $s \leqslant \left| P \right|$ ，则执行5)；反之 $j = j + 1$ ，执行8)；

8) 如果 $j \leqslant \left| P \right|$ ，则执行4)；反之 $i = i + 1$ ，执行9)；

9) 如果 $i \leqslant \left| P \right|$ ，则执行3)；反之执行10)；

10)对更新过的集合 $P$ 递归调用2)~ 9)，直至集合 $P$ 不再更新；

11) $Y = {\text{Ø}} $ ， $i = 1$ ；

12) $ j = i$ ；

13) 如果 $w \subseteq {w_{ij}}$ ，则 $Y = Y \cup \{ {a_i}\} \cup \{ {a_j}\} $ ， $j = j + 1$ ，执行14)；

14) 如果 $j \leqslant n$ ，则执行13)；反之 $i = i + 1$ 并执行15)；

15) 如果 $i \leqslant n$ ，则执行12)；反之执行16)；

16) 输出三支概念 $(w,Y)$ 。

因为集合 $P$ 为有限集合，所以算法1在有限步后可以停止。

复杂度分析：

1)首先，生成属性矩阵的复杂度为 $O({{{{\left| M \right|}^2}} / 2})$ ；其次，得外延集的复杂度为 $O({\left| M \right|^{4{{\log }_2}\left| M \right|}})$ ；最后，寻找满足条件的 $w$ 对应的属性集，共比较 ${{\left| M \right|(\left| M \right| + 1)} / 2}$ 次，循环 $\left| P \right|$ 次，所以复杂度为 $O({{\left| M \right|(\left| M \right| + 1)\left| P \right|} / 2})$ ；因此，算法1的复杂度为 $O({\left| M \right|^{4{{\log }_2}\left| M \right|}})$ 。

2)文献[5]中的复杂度受生成标准形式概念的复杂度的影响，选择的方法不同，复杂度则不同；其次，通过找等价类进行概念构建的最大时间复杂度为 $\max \{ {2^{2\left| M \right|}},{2^{\left| G \right| \times \left| M \right|}}\} $ ，因此，两相比较，本文方法较好。

3)文献[6]中的时间复杂度为 $O(\left| G \right|{\left| M \right|^2}\left| C \right|)$ ，其中 $C$ 表示属性三支核心概念的个数。两相比较，本文算法较好。

下面给出算法1正确性的理论支持。

定理1　 $(G,M,I)$ 为一形式背景，基于属性矩阵 ${{W}}$ 得到的概念均为属性三支概念。

证明　如果 $({A^{ < \cdot }},A)$ 不是属性三支概念，则 ${A^{ < \cdot \cdot > }} \ne A$ 。令 ${A^{ < \cdot \cdot > }} = {A_0}$ 。

下面证明 $A_0^{ < \cdot } = {A^{ < \cdot }}$ ：由AE₁、AE₂性质可知， $A \subseteq {A^{ < \cdot \cdot > }} = {A_0}$ ，则 $A_0^{ < \cdot } \subseteq {A^{ < \cdot }}$ ；另外，由 ${A^{ < \cdot \cdot > }} = {A_0}$ 可知， ${A^{ < \cdot \cdot > < \cdot }} = A_0^{ < \cdot }$ ，又因为 ${A^{ < \cdot }} \subseteq {A^{ < \cdot \cdot > < \cdot }}$ ，所以 ${A^{ < \cdot }} \subseteq A_0^{ < \cdot }$ 。因此 $A_0^{ < \cdot } = {A^{ < \cdot }}$ 成立。

定理2　 $(G,M,I)$ 为一形式背景，矩阵 ${{W}}$ 为 $(G,M,I)$ 上的属性矩阵，则算法1可得到除 $((G,G),{\text{Ø}} )$ 外的所有属性三支概念。

证明　属性矩阵 ${{W}}$ 中的元素构成的集合记为集合 $P$ ，下面分3种情况对集合 $P$ 进行讨论：①若算法1中5)的结果为空集，因为 ${\text{Ø}} $ 为任何集合的子集，所以矩阵 ${{W}}$ 中包含了所有的外延；②若算法1中5)的结果仍属于集合 $P$ ，则集合 $P$ 中包含了所有的外延；③若算法1中5)的结果不属于集合 $P$ ，则算法1中的6)能够将其纳入集合 $P$ 中，因此，执行有限次后，集合 $P$ 包含所有的外延。最后，对每个外延寻找相应属性集即可得属性三支概念。

例2　利用文献[8]中的形式背景 $({G_2}, {M_2}, {I_2})$ (见表2)对算法1的运行过程及有效性进行说明。对象集 ${G_2}$ 为5个病人组成的集合，属性集 ${M_2}$ 为病症的集合，分别为腰痛、尿急、排尿困难、尿道肿胀以及急性膀胱炎。为了能够对数据集做出合理分析，可先基于该背景进行三支概念构建，以此对后续判断提供依据。

首先，由表2中形式背景可知：

$ {w_{11}} = ({a^*} \cap {a^*},{a^{\bar *}} \cap {a^{\bar *}}) = (1245,3),{w_{12}} = ({a^*} \cap {b^*},$ ${a^{\bar *}} \cap {b^{\bar *}}) = (25,3), \cdots ,{w_{45}}\! = \!({d^*} \cap {e^*},{d^{\bar *}} \cap {e^{\bar *}})\! =\! ({\text{Ø}} ,$ $134),{w_{55}} \!= \!({e^*} \cap {e^*}, {e^{\bar *}} \cap {e^{\bar *}}) \!=\! (2,1345) {\text{。}}$

可得

${{{W}}_{{2}}} = \left[\!\!\!\! {\begin{array}{*{20}{c}} {(1245,3)}\!\!&\!\!{(25,3)}\!\!&\!\!{(125,{\text{Ø}} )}\!\!&\!\!{(5,3)}\!\!&\!\!{(2,3)} \\ {}\!\!&\!\!{(25,134)}\!\!&\!\!{(25,4)}\!\!&\!\!{(5,134)}\!\!&\!\!{(2,134)} \\ {}\!\!&\!\!{}\!\!&\!\!{(1235,4)}\!\!&\!\!{(5,4)}\!\!&\!\!{(2,4)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(5,1234)}\!\!&\!\!{({\text{Ø}} ,134)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(2,1345)} \\ \end{array}} \!\!\!\!\right]$

其次，令 $ P = \{ (1245,3),(25,3),(125,{\text{Ø}} ), \cdots ,$ $(5,1234), ({\text{Ø}} ,134),(2,1345)\} $ ，对集合 $P$ 中元素进行相交，所得结果中 $(25,{\text{Ø}} ),(5,{\text{Ø}} ),(2,{\text{Ø}} ),({\text{Ø}} ,3),({\text{Ø}} ,$ $4),({\text{Ø}} ,{\text{Ø}} ) \notin P$ ，将其添加到集合 $P$ 中，再次两两相交，相交结果均为空。所以得 $P = \{ (1245,3),(25,3),$ $(125,{\text{Ø}} ), \cdots , (5,1234),\; ({\text{Ø}} ,134),\;(2,1345),\;(25,{\text{Ø}} ),\;(5,{\text{Ø}} ),\;$ $(2,{\text{Ø}} ),({\text{Ø}} ,3), ({\text{Ø}} ,4), ({\text{Ø}} ,{\text{Ø}} )\}{\text{。}} $

之后，执行算法1中11)~16)得到三支概念。例如，在矩阵 ${{{W}}_{{2}}}$ 中， $(1245,3) \subseteq {w_{11}}$ ，可得三支概念 $((1245,3),a)$ ；对 $(25,3)$ 来说，在矩阵 ${{{W}}_{{2}}}$ 中， $(25,3) \subseteq {w_{11}},{w_{12}},{w_{22}}$ ，可得三支概念 $((25,3),ab)$ 。

因此，三支概念 ${\rm{AEL}}({G_2},{M_2},{I_2})\backslash \{ (({G_2},{G_2}), {\text{Ø}} )\}$ 的结果，见表3。

依据定理1、2对算法的正确性及有效性进行了验证，且实例2运用算法1所得结果与文献[8]中所得一致，再次说明本文方法有效。

形式背景 $({G_2},{M_2},{I_2})$ 中 $\left| {{M_2}} \right| = 5$ ，所以，执行算法1的2)~10)复杂度为 $O({{\rm{5}}^{4{{\log }_2}{\rm{5}}}})$ ；11)~16)的复杂度为 $O({{(5 \times 6 \times 21)}/ 2})$ ；因此，对例2执行算法1的复杂度为 $O({{\rm{5}}^{4{{\log }_2}{\rm{5}}}})$ 。

2.2 依据对象矩阵构建对象三支概念

本小节将对对象三支概念的算法进行设计，给出相关定义、算法以及实例说明。

定义7　形式背景 $(G,M,I)$ ，其中对象集合 $G = \{ {b_1},{b_2}, \cdots ,{b_n}\} $ ，定义： ${{V}} = ({v_{kt}}),{v_{kt}} = (b_k^* \cap b_t^*,$ $b_k^{\bar *} \cap b_t^{\bar *}), {b_k},{b_t}(k,t = 1,2,$ $ \cdots ,n) \in G$ 。称矩阵 ${{V}}$ 为一个 $n \times n$ 对象矩阵。

例3　形式背景 $({G_1},{M_1},{I_1})$ 见表1。

由表1可知：

$ {v_{11}}\!\! = \!\!({1^*} \cap {1^*},{1^{\bar *}} \cap {1^{\bar *}})\!\! =\!\! (ac,bd),{v_{12}}\! =\! ({1^*} \cap {2^*},{1^{\bar *}} \cap $ ${2^{\bar *}}) = (ac,b), \cdots ,{v_{34}} = ({3^*} \cap {4^*},{3^{\bar *}} \cap {4^{\bar *}}) = (b,{\text{Ø}} ),$ ${v_{44}} = ({4^*} \cap {4^*},{4^{\bar *}} \cap {4^{\bar *}}) = (bcd,a)${\text{。}}

可得：

${{{V}}_{{1}}} = \left[ {\begin{array}{*{20}{c}} {(ac,bd)}&{(ac,b)}&{(a,d)}&{(c,{\text{Ø}} )} \\ {}&{(acd,b)}&{(a,{\text{Ø}} )}&{(cd,{\text{Ø}} )} \\ {}&{}&{(ab,cd)}&{(b,{\text{Ø}} )} \\ {}&{}&{}&{(bcd,a)}\\ \end{array}} \right]$

构建对象三支概念的算法过程如算法2。

算法2　生成对象三支概念的算法。

输入　形式背景 $(G,M,I)$ 。

输出　 ${\rm{OEL}}(G,M,I)\backslash \{ ({\text{Ø}} ,(M,M))\}$ 。

1)利用定义7生成形式背景 $(G,M,I)$ 的对象矩阵 ${{V}}$ ，将对象矩阵 ${{V}}$ 的所有元素记入集合 $F$ ；

2) $ k = 1$ ；

3) $ t = 1$ ；

4) $ c = 1$ ；

5) $ v = {v_{kt}} \cap {v_{kc}}$ ；

6) 如果 $v \notin F$ ，则 $F = F \cup \{ v\} $ ，并执行7)；反之直接执行7)；

7) $c=c+1 $ ，如果 $c \leqslant \left| F \right|$ ，则执行5)；反之令 $t = t + 1$ ，执行8)；

8) 如果 $t \leqslant \left| F \right|$ ，则执行4)；反之令 $k = k + 1$ ，执行9)；

9) 如果 $k \leqslant \left| F \right|$ ，则执行3)；反之执行10)；

10) 对更新过的集合 $F$ 递归调用2)~ 9)，直至集合 $F$ 不再更新；

11) $ H = {\text{Ø}} ,k = 1$ ;

12) $ t = k$ ；

13) 如果 $v \subseteq {v_{kt}}$ ，则令 $H = H \cup \{ {b_k}\} \cup \{ {b_t}\} $ ， $t = t + 1$ ，执行14)；

14) 如果 $t \leqslant \left| G \right|$ ，则执行13)；反之令 $k = k + 1$ 并执行15)；

15) 如果 $k \leqslant \left| G \right|$ ，则执行12)；反之执行16)；

16) 输出三支概念 ${\rm{OEL}}(G,M,I)\backslash \{ ({\text{Ø}} ,(M, M))\} = \cup \{ (H,v)\}$ 。

由算法1的分析理论可知，算法2在有限步后可以停止，复杂度为 $O({\left| G \right|^{4{{\log }_2}\left| G \right|}})$ 。

例4　采用形式背景 $({G_2},{M_2},{I_2})$ 对算法2的运行过程进行说明。

$ {v_{11}}\!\!=\!\! ({1^*} \cap {1^*},{1^{\bar *}} \cap {1^{\bar *}})\!\!=\!\!(ac,bde),{v_{12}}\!\!=\!\!({1^*} \cap {2^*},{1^{\bar *}} \cap {2^{\bar *}})$ $\! = (ac,d), \cdots ,{v_{45}} = ({4^*} \cap {5^*},{4^{\bar *}} \cap {5^{\bar *}}) = (a,e),{v_{55}} = ({5^*} \cap {5^*},$ ${5^{\bar *}} \cap {5^{\bar *}}) = (abcd,e){\text{。}}$

可得

${{{V}}_{{2}}} = \left[\!\! {\begin{array}{*{20}{c}} {(ac,bde)}\!\!&\!\!{(ac,d)}\!\!&\!\!{(c,bde)}\!\!&\!\!{(a,bde)}\!\!&\!\!{(ac,e)} \\ {}\!\!&\!\!{(abce,d)}\!\!&\!\!{(c,d)}\!\!&\!\!{(a,d)}\!\!&\!\!{(abc,{\text{Ø}} )} \\ {}\!\!&\!\!{}\!\!&\!\!{(c,abde)}\!\!&\!\!{({\text{Ø}} ,bde)}\!\!&\!\!{({\text{Ø}} ,e)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(a,bcde)}\!\!&\!\!{(a,e)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(abcd,e)}\\ \end{array}} \!\!\right]$

令 $ F = \{ (ac,bde),(ac,d),(c,bde), \cdots ,(a,bcde),(a,e),$ $(abcd,e)\} $ ，对集合 $F$ 中两两元素相交，其中结果 $(ac,{\text{Ø}} ),$ $(a,{\text{Ø}} ),(c,{\text{Ø}} ),(c,e),({\text{Ø}} ,d),({\text{Ø}} ,{\text{Ø}} ) \notin F$ ，将上述结果添加到集合 $F$ 中，再次相交，计算结果为空。可得 $F = \{ (ac,bde),(ac,d),(c,bde), \cdots ,(a,bcde),(a,e),$ $ (abcd,e),(ac,{\text{Ø}} ),(a,{\text{Ø}} ),(c,{\text{Ø}} ),(c,e),({\text{Ø}} ,d),({\text{Ø}} ,{\text{Ø}} )\} $ 。

之后，在矩阵 ${{{V}}_{{2}}}$ 中，分别对集合 $F$ 中每一元素执行算法2的11)~16)：例如，对 $(ac,{\text{Ø}} )$ 来说，在矩阵 ${{{V}}_{{2}}}$ 中， $(ac,{\text{Ø}} ) \subseteq {v_{11}},$ ${v_{12}},{v_{15}},{v_{22}},{v_{25}},{v_{55}}$ ，可得三支概念 $(125,(ac,{\text{Ø}} ))$ ；对 $(a,bde)$ 来说，在矩阵 ${{{S}}_{{2}}}$ 中， $(a,bde) \subseteq {v_{11}},{v_{14}},{v_{44}}$ ，可得三支概念 $(14,(a,bde))$ 。

因此，三支概念 ${\rm{OEL}}({G_2},{M_2},{I_2})\backslash \{ ({\text{Ø}} ,({M_2},$ ${M_2}))\} $ 的结果见表4。

在本例中 $\left| {{G_2}} \right| = 5$ ，所以执行算法2的复杂度为 $O({{\rm{5}}^{4{{\log }_2}{\rm{5}}}})$ 。

3 结束语

本文给出了属性矩阵与对象矩阵的定义。利用属性(对象)矩阵，设计了构建属性(对象)三支概念的算法。经验证，上述算法均有效，且在复杂度方面，有所改善。后期，将继续对三支概念的应用方面进行研究。