三元概念的增量式构造方法

doi:10.13232/j.cnki.jnju.2022.01.003

三元概念的增量式构造方法

王霞^,¹^,², 全园¹, 李俊余¹^,², 吴伟志¹^,²

1.浙江海洋大学信息工程学院, 舟山, 316022

2.浙江省海洋大数据挖掘与应用重点实验室(浙江海洋大学), 舟山, 316022

Incremental construction method of triadic concepts

Wang Xia^,¹^,², Quan Yuan¹, Li Junyu¹^,², Wu Weizhi¹^,²

1.School of Information Engineering, Zhejiang Ocean University, Zhoushan, 316022, China

2.Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province (Zhejiang Ocean University), Zhoushan, 316022, China

通讯作者: E⁃mail： bblylm@126.com

收稿日期: 2021-06-16

基金资助:

国家自然科学基金. 61573321. 41631179. 61773349
浙江省自然科学基金. LY18F030017

Received: 2021-06-16

摘要

三元概念的构造方法是三元概念分析的核心问题之一，当条件逐个增加时，研究三元概念的增量式构造方法.首先，详细分析增加一个新的条件后原三元背景中三元概念的变化以及新增加的条件对新背景的三元概念的影响.分别针对下述四种情况给出充分必要条件：（1）新添加的条件对原背景的三元概念不影响，它仍旧是新三元背景的三元概念；（2）原背景的三元概念被替换掉，它不再是新三元背景的三元概念，替换后的三元概念的外延和内涵与原来一致，但是方式增加了新的条件；（3）原背景的三元概念与新的条件共同生成一个新的三元概念；（4）新增加的条件不借助任何原背景的三元概念生成新的三元概念.在此基础上给出基于条件的三元概念的增量式构造算法.最后，通过实例阐明增量式方法生成三元概念的详细过程.

关键词： 三元概念分析 ; 三元背景 ; 三元概念 ; 增量式构造方法

Abstract

The construction method of triadic concepts is one of the key problems in triadic concept analysis. When conditions increase one by one，the incremental construction method of triadic concepts is studied. First of all，it analyzes the changes of the original triadic concepts and the influence of the newly added condition on the new triadic concepts. Sufficient and necessary conditions are given for the following four cases. (1) The newly added condition has no effect on the original triadic concept. That is，it is still a triadic concept of the new triadic context. (2) The original triadic concept has been updated，which is no longer the triadic concept of the new triadic context. The extent and intent of the updated triadic concept are consistent with the original，but the newly added condition has been added to the modus of the updated triadic concept. (3) The original triadic concept and the newly added condition together generate a new triadic concept of the new triadic context. (4) The newly added condition generates a new triadic concept without the help of any original triadic concepts. Then the incremental construction algorithm of triadic concept based on conditions is given. Finally，an example is given to illustrate the detailed process of generating triadic concepts by incremental method.

Keywords： triadic concept analysis ; triadic context ; triadic concept ; incremental construction method

PDF (395KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

王霞, 全园, 李俊余, 吴伟志. 三元概念的增量式构造方法. 南京大学学报（自然科学）[J], 2022, 58(1): 19-28 doi:10.13232/j.cnki.jnju.2022.01.003

Wang Xia, Quan Yuan, Li Junyu, Wu Weizhi. Incremental construction method of triadic concepts. Journal of nanjing University[J], 2022, 58(1): 19-28 doi:10.13232/j.cnki.jnju.2022.01.003

1995年，Lehmann and Wille^［1］基于皮尔斯范畴三分理论提出三元概念分析，它可以看作是形式概念分析^［2-3］的推广.三元概念分析的基本概念是三元背景和三元概念.三元背景^［1］是一个四元组 $(K_{1}, K_{2}, K_{3}, Y)$ ，其中 $K_{1}, K_{2}, K_{3}$ 为非空集合， $Y$ 为 $K_{1}, K_{2}, K_{3}$ 之间的关系，即 $Y \subseteq K_{1} \times K_{2} \times K_{3}$ .分别称 $K_{1}, K_{2}, K_{3}$ 为对象集、属性集和条件集， $K_{1}, K_{2}, K_{3}$ 的元素为对象、属性和条件.若对象x、属性b和条件c具有关系Y，则记为 $(x, b, c) \in Y$ ，表示对象x在条件c下具有属性b，通常在三维交叉表的相应位置用“1”标出.若 $(x, b, c) \notin Y$ ，则在三维交叉表的相应位置用“0”标出.三元概念是由外延、内涵和方式三部分构成的一个三元组.一个三元概念正好是 $P (K_{1}) \times P (K_{2}) \times P (K_{3})$ 中（基于集合的包含关系）最大的三元组 $(X, B, C) \subseteq Y$ .

魏玲等^［4-5］对2014年以前三元概念分析的研究现状及发展趋势做了详细介绍.目前关于三元概念分析的研究主要集中在：概念三元格的构造及算法^{［1，6-10］}、三元蕴含及关联规则挖掘^［11-13］、三元模态算子^［14］、三元概念聚类^［15-17］、三元背景的因子分析^［18-21］、三元背景的模糊化^［22-26］、三元概念分析的认知系统模型^［27］、基于三元背景的约简^［28-29］、三元概念的推广^［30］、三元概念分析的分类问题^［31］、三元概念分析的应用^［32-35］等.在三元概念的构造方面，Lehmann and Wille^［1］给出了构造三元概念的枚举法，该方法对对象幂集、属性幂集和条件幂集的全部元素逐一检查是否构成三元概念，以此生成所有的三元概念.但利用这种方法处理规模较大的三元背景时计算量会很大.为了降低计算的复杂性，王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，该方法对对象集和条件集的全部元素逐一检查是否构成对象⁃条件三元概念，然后通过对象⁃条件三元概念计算其余三元概念.本文考虑增加一个新的条件后新背景的三元概念与原背景的三元概念之间的关系，并进一步探索构造三元概念的新方法.

本文首先考虑当有一个新的条件增加时原背景的三元概念可能产生的变化，并针对不同的变化给出了充要条件；其次，考虑条件逐一增加时三元概念的增量式构造算法，并通过实例给出增量式构造方法计算所有三元概念的详细过程.

1 相关工作

本节给出三元概念分析的相关概念和结论.

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $\{i, j, k\} = \{1,2, 3\}$ 且 $j < k$ ， $X \subseteq K_{i}$ ， $Z \subseteq K_{j} \times K_{k}$ .Lehmann and Wille^［1］定义了 $(i)$ ⁃诱导算子：

\begin{array}{l} X^{(i)} = \{(a_{j}, a_{k}) \in K_{j} \times K_{k}| \forall a_{i} \in K_{i}, \\ a_{i}, a_{j}, a_{k} 具 有 关 系 Y\} \end{array}

Z^{(i)} = \{a_{i} \in K_{i}| \forall (a_{j}, a_{k}) \in Z, a_{i}, a_{j}, a_{k} 具 有 关 系 Y\}

定义1^［1］

设 $(K_{1}, K_{2}, K_{3}, Y)$ 是一个三元背景，称 $(A_{1}, A_{2}, A_{3})$ 为三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 的一个三元概念，如果对任意 $\{i, j, k\} = \{1,2, 3\}$ ， $j < k$ 且 $A_{i} \subseteq K_{i}$ 有 $A_{i} = {(A_{j} \times A_{k})}^{(i)}$ .分别称 $A_{1}, A_{2}, A_{3}$ 为该三元概念的外延、内涵和方式.

三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 的所有三元概念构成的集合记为 $ℑ (K_{1}, K_{2}, K_{3}, Y)$ .

设 $(K_{1}, K_{2}, K_{3}, Y)$ 是一个三元背景， $X_{i} \subseteq K_{i}$ ，

X_{k} \subseteq K_{k}, \{i, j, k\} = \{1,2, 3\}

，定义：

b_{i k} (X_{i}, X_{k}) = (A_{1}, A_{2}, A_{3}), i \neq k

其中：

A_{j} = {(X_{i} \times X_{k})}^{(j)}, A_{i} = {(A_{j} \times X_{k})}^{(i)}, A_{k} = {(A_{i} \times A_{j})}^{(k)}

命题1^［4］

设 $(K_{1}, K_{2}, K_{3}, Y)$ 是一个三元背景， $X_{i} \subseteq K_{i}, X_{k} \subseteq K_{k}, \{i, j, k\} = \{1,2, 3\}$ ，则有：

\begin{array}{l} b_{i k} (X_{i}, X_{k}) = (A_{1}, A_{2}, A_{3}) \in ℑ (K_{1}, K_{2}, K_{3}, Y) \\ \forall (B_{1}, B_{2}, B_{3}) \in ℑ (K_{1}, K_{2}, K_{3}, Y) \end{array}

若 $X_{i} \subseteq B_{i}, X_{k} \subseteq B_{k}$ ，则 $B_{j} \subseteq A_{j}$ ，且当 $B_{j} = A_{j}$ 时 $A_{i} \supseteq B_{i}, A_{k} \subseteq B_{k}$ .

设 $(K_{1}, K_{2}, K_{3}, Y)$ 是一个三元背景， $\forall C \subseteq K_{3}$ ，

$C \neq \emptyset$ ，称 $(K_{1}, K_{2}, C, Y_{C})$ 为三元背景 $(K_{1}, K_{2},$

$K_{3}, Y)$ 的子背景，其中 $Y_{C} = Y ⋂ (K_{1} \times K_{2} \times C)$ ，此时，子背景 $(K_{1}, K_{2}, C, Y_{C})$ 的诱导算子定义为：

\forall X \subseteq K_{1}, \forall B \subseteq K_{2}, \forall C^{'} \subseteq C

，

X^{(1) Y_{C}} = \{(g, c) \in K_{2} \times C| \forall x \in X, (x, g, c) \in Y_{C}\}

B^{(2) Y_{C}} = \{(x, c) \in K_{1} \times C| \forall g \in B, (x, g, c) \in Y_{C}\}

{C^{'}}^{(3) Y_{C}} = {C^{'}}^{(3)}

{(X \times C^{'})}^{(2) Y_{C}} = {(X \times C^{'})}^{(2)}

{(B \times C^{'})}^{(1) Y_{C}} = {(B \times C^{'})}^{(1)}

{(X \times B)}^{(3) Y_{C}} = \{c \in C |\forall x \in X, \forall g \in B, (x, g, c) \in Y_{C}\}

例1表1是一个三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ ，其中：

K_{1} = \{x_{1}, x_{2}, x_{3}\}

K_{2} = \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}\}

K_{3} = \{c_{1}, c_{2}, c_{3}\}

表1 三元背景 $(K_{1}, K_{2}, K_{3}, Y)$

Table 1 A triadic context $(K_{1}, K_{2}, K_{3}, Y)$

	c₁						c₂						c₃
	g₁	g₂	g₃	g₄	g₅	g₆	g₁	g₂	g₃	g₄	g₅	g₆	g₁	g₂	g₃	g₄	g₅	g₆
x₁	1	1	0	0	1	1	1	1	0	0	1	0	0	1	1	0	0	1
x₂	1	0	0	1	0	1	0	0	0	1	0	1	1	0	1	0	1	0
x₃	0	1	1	1	0	0	1	1	1	1	1	0	1	1	0	1	0	1

新窗口打开| 下载CSV

对对象幂集 $Ρ (K_{1})$ 和属性幂集 $Ρ (K_{2})$ 应用命题1计算表1中的所有三元概念得：

\begin{array}{l} ℑ = \{(\emptyset, K_{2}, K_{3}), (K_{1}, \emptyset, K_{3}), (K_{1}, K_{2}, \emptyset), (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\}), (\{x_{1}\}, \{g_{2}, g_{6}\}, \{c_{1}, c_{3}\}), \\ (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\}), (\{x_{1}\}, \{g_{2}, g_{3}, g_{6}\}, \{c_{3}\}), (\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\}), (\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\}), \\ (\{x_{2}\}, \{g_{1}, g_{3}, g_{5}\}, \{c_{3}\}), (\{x_{2}\}, \{g_{1}\}, \{c_{1}, c_{3}\}), (\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\}), (\{x_{3}\}, \{g_{2}, g_{4}\}, K_{3}), \\ (\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{4}\}, \{c_{2}, c_{3}\}), (\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\}), \\ (\{x_{3}\}, \{g_{1}, g_{2}, g_{4}, g_{6}\}, \{c_{3}\}), (\{x_{1}, x_{2}\}, \{g_{3}\}, \{c_{3}\}), (\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}, c_{2}\}), \\ (\{x_{1}, x_{3}\}, \{g_{2}\}, K_{3}), (\{x_{1}, x_{3}\}, \{g_{2}, g_{6}\}, \{c_{3}\}), (\{x_{1}, x_{3}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{2}\}), (\{x_{2}, x_{3}\}, \{g_{1}\}, \{c_{3}\})\} \end{array}

2 新增条件对三元概念的影响

当三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 增加一个新的条件 $c_{0}$ 后原背景被更新为 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ ，其中， $Y_{0}$ 为 $K_{1}, K_{2}, \{c_{0}\}$ 之间的关系，即 $Y_{0} \subseteq K_{1} \times K_{2} \times \{c_{0}\}$ .下面考虑原背景的三元概念、新背景的三元概念以及 $(K_{1}, K_{2}, \{c_{0}\}, Y_{0})$ 的三元概念之间的关系.

对任意三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ ， $(X, B, C) \in$

$ℑ (K_{1}, K_{2}, K_{3}, Y)$ .显然有：若 $X = \emptyset$ 则

$(X, B, C) =$ $(\emptyset, K_{2}, K_{3})$ ；若 $B = \emptyset$ 则 $(X, B, C) = (K_{1}, \emptyset, K_{3})$ ；若 $C = \emptyset$ 则 $(X, B, C) =$

$(K_{1}, K_{2}, \emptyset)$ .于是，当增加一个条件 $c_{0} \notin K_{3}$ 时，若 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ， $X = \emptyset$ 或 $B = \emptyset$ ，则 $(X, B, C ⋃ \{c_{0}\}) \in$ $ℑ (K_{1}, K_{2},$ $K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ .

定理1

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增条件， $\forall (X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ， $X \neq \emptyset$ 且 $B \neq \emptyset$ .则 $(X, B, C) \in ℑ (K_{1}, K_{2},$

$K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ 当且仅当 $B ⋂ {(X \times \{c_{0}\})}^{(2)} \neq B$ .

证明

由于 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ， $X \neq \emptyset$ 且 $B \neq \emptyset$ ，则：

(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

当且仅当 $\exists x \in X, \exists g \in B$ 使 $(x, g, c_{0}) \notin Y_{0}$ ，由 $(i)$ ⁃诱导算子知，这等价于 $g \notin {(X \times \{c_{0}\})}^{(2)}$ .即此时：

(X, B, C) \in ℑ (K_{1}, K_{2},

K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

等价于 $B ⋂ {(X \times \{c_{0}\})}^{(2)} \neq B$ .

证毕.

定理1给出了三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 添加一个新的条件 $c_{0} \notin K_{3}$ 后，原背景 $(K_{1}, K_{2}, K_{3}, Y)$ 的三元概念 $(X, B, C)$ （ $X \neq \emptyset$ 且 $B \neq \emptyset$ ）不受影响，即它仍是新背景 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ 的三元概念的充要条件.

定理2

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增的条件， $\forall (X, B, C) \in ℑ (K_{1}, K_{2},$

K_{3}, Y)

，

X \neq \emptyset

且

B \neq \emptyset

.则：

(X, B, C ⋃ \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

当且仅当 $B ⋂ {(X \times \{c_{0}\})}^{(2)} = B$ .

证明

由于 $\forall (X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ，

$X \neq \emptyset$ 且 $B \neq \emptyset$ ，则：

(X, B, C ⋃ \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

当且仅当 $\forall x \in X, \forall g \in B$ 有 $(x, g, c_{0}) \in Y_{0}$ .

又因为 $B ⋂ {(X \times \{c_{0}\})}^{(2)} = B$ 当且仅当 $\forall g \in B$ ， $g \in {(X \times \{c_{0}\})}^{(2)}$ ，由 $(i)$ ⁃诱导算子知，这等价于 $\forall x \in X$ 有 $(x, g, c_{0}) \in Y_{0}$ .所以， $\forall (X, B, C) \in$

ℑ (K_{1}, K_{2}, K_{3}, Y)

，

X \neq \emptyset

且

B \neq \emptyset

时，

(X, B, C ⋃ \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

当且仅当 $B ⋂ {(X \times \{c_{0}\})}^{(2)} = B$ .

证毕.

定理2给出了三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 添加一个新的条件 $c_{0} \notin K_{3}$ 后，原背景 $(K_{1}, K_{2}, K_{3}, Y)$ 的三元概念 $(X, B, C)$ （ $X \neq \emptyset$ 且 $B \neq \emptyset$ ）被更改为 $(X, B, C ⋃ \{c_{0}\})$ 的充要条件，此时 $(X, B, C)$ 不再是新背景 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ 的三元概念.

定理3

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增的条件， $\forall (X, B, C) \in ℑ (K_{1},$

K_{2}, K_{3}, Y)

.若

B ⋂ {(X \times \{c_{0}\})}^{(2)} \neq \emptyset

且

B ⋂

{(X \times \{c_{0}\})}^{(2)} \neq B

，则：

\begin{array}{l} (X, B ⋂ {(X \times \{c_{0}\})}^{(2)}, C ⋃ \{c_{0}\}) \in \\ ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0}) \end{array}

当且仅当 $\forall x \in K_{1} \ X$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(\{x\} \times (C ⋃ \{c_{0}\}))}^{(2)}

且 $\forall c \in K_{3} \ C$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(X \times \{c_{0}\})}^{(2)}

证明

由于 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ，所以：

\begin{array}{l} (X, B ⋂ {(X \times \{c_{0}\})}^{(2)}, C ⋃ \{c_{0}\}) \in \\ ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0}) \end{array}

等价于

\begin{array}{l} {(X \times C ⋃ \{c_{0}\})}^{(2)} = \\ {(X \times C)}^{(2)} ⋂ {(X \times \{c_{0}\})}^{(2)} = B ⋂ {(X \times \{c_{0}\})}^{(2)} \end{array}

X = {\{(B ⋂ {(X \times \{c_{0}\})}^{(2)}) \times C ⋃ \{c_{0}\}\}}^{(1)}

C ⋃ \{c_{0}\} = {\{X \times (B ⋂ {(X \times \{c_{0}\})}^{(2)})\}}^{(3)}

而

X = {\{(B ⋂ {(X \times \{c_{0}\})}^{(2)}) \times C ⋃ \{c_{0}\}\}}^{(1)}

当且仅当 $\forall x \in K_{1} \ X$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(\{x\} \times (C ⋃ \{c_{0}\}))}^{(2)}

C ⋃ \{c_{0}\} = {\{X \times (B ⋂ {(X \times \{c_{0}\})}^{(2)})\}}^{(3)}

当且仅当 $\forall c \in K_{3} \ C$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(X \times \{c\})}^{(2)}

证毕.

定理4

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增的条件， $\forall (X, B, C) \in ℑ (K_{1},$

K_{2}, K_{3}, Y)

.若

B ⋂ {(X \times \{c_{0}\})}^{(2)} \neq \emptyset

且

B ⋂

{(X \times \{c_{0}\})}^{(2)} \neq B

，则：

\begin{array}{l} (X_{*}, B ⋂ {(X \times \{c_{0}\})}^{(2)}, C ⋃ \{c_{0}\}) \in \\ ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0}) \end{array}

当且仅当 $\forall c \in K_{3} \ C$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(X_{*} \times \{c\})}^{(2)}

其中，

X_{*} = {\{(B ⋂ {(X \times \{c_{0}\})}^{(2)}) \times (C ⋃ \{c_{0}\})\}}^{(1)}

证明由于 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ，所以

\begin{array}{l} (X_{*}, B ⋂ {(X \times \{c_{0}\})}^{(2)}, C ⋃ \{c_{0}\}) \in \\ ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0}) \end{array}

等价于

{(X \times (C ⋃ \{c_{0}\}))}^{(2)} = B ⋂ {(X \times \{c_{0}\})}^{(2)}

X_{*} = {\{(B ⋂ {(X \times \{c_{0}\})}^{(2)}) \times (C ⋃ \{c_{0}\})\}}^{(1)}

C ⋃ \{c_{0}\} = {\{X_{*} \times (B ⋂ {(X \times \{c_{0}\})}^{(2)})\}}^{(3)}

而：

C ⋃ \{c_{0}\} = {\{X_{*} \times (B ⋂ {(X \times \{c_{0}\})}^{(2)})\}}^{(3)}

当且仅当 $\forall c \in K_{3} \ C$ ，

B ⋂ {(X \times \{c_{0}\})}^{(2)} ⊄ {(X_{*} \times \{c\})}^{(2)}

证毕.

根据定理3和定理4容易得到下面结论成立.

定理5

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增的条件， $\forall (X, B, C) \in ℑ (K_{1},$

K_{2}, K_{3}, Y)

.若

B ⋂ {(X \times \{c_{0}\})}^{(2)} \neq \emptyset

且

B ⋂

{(X \times \{c_{0}\})}^{(2)} \neq B

，则：

\begin{array}{l} b_{23} (B \cap (X \times {c_{0} {})}^{(2)}, C \cup {c_{0}}) \in \\ ℑ (K_{1}, K_{2}, K_{3} \cup {c_{0}}, Y ⋃ Y_{0}) \end{array}

定理6

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元背景， $c_{0} \notin K_{3}$ 为新增的条件.则：

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

当且仅当：

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, \{c_{0}\}, Y_{0})

且 $\forall (X, B, C) \in ℑ (K_{1}, K_{2}, K_{3},$ $Y)$ ， $C \neq \emptyset$ 有 $X ⋂ X_{0} \neq X_{0}$ 或 $B ⋂ B_{0} \neq B_{0}$ .

证明

必要性若：

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

则 $X_{0} \neq \emptyset$ ， $B_{0} \neq \emptyset$ 且 ${(X_{0} \times B_{0})}^{(3) Y} = \emptyset$ ，

{(X_{0} \times B_{0})}^{(3) Y ⋃ Y_{0}} = {(X_{0} \times B_{0})}^{(3) Y_{0}} = \{c_{0}\}

{(X_{0} \times \{c_{0}\})}^{(2)} = B_{0}, {(B_{0} \times \{c_{0}\})}^{(1)} = X_{0}

于是，

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, \{c_{0}\}, Y_{0})

若存在 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ， $C \neq \emptyset$ 使得 $X ⋂ X_{0} =$ $X_{0}$ 且 $B ⋂ B_{0} = B_{0}$ ，则：

C = {(X \times B)}^{(3) Y} \subseteq {(X_{0} \times B_{0})}^{(3) Y} = \emptyset

矛盾！

充分性若

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, \{c_{0}\}, Y_{0})

则：

{(X_{0} \times \{c_{0}\})}^{(2)} = B_{0}

，

{(B_{0} \times \{c_{0}\})}^{(1)} = X_{0}

{(X_{0} \times B_{0})}^{(3) Y_{0}} = \{c_{0}\}

又因为 $\forall (X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ ， $C \neq \emptyset$ 有 $X ⋂ X_{0} \neq X_{0}$ 或 $B ⋂ B_{0} \neq B_{0}$ ，所以：

{(X_{0} \times B_{0})}^{(3) Y ⋃ Y_{0}} = {(X_{0} \times B_{0})}^{(3) Y_{0}} = \{c_{0}\}

且：

{(X_{0} \times \{c_{0}\})}^{(2)} = B_{0}

，

{(B_{0} \times \{c_{0}\})}^{(1)} = X_{0}

即：

(X_{0}, B_{0}, \{c_{0}\}) \in ℑ (K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})

证毕.

定理6给出了三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 添加一个新的条件 $c_{0} \notin K_{3}$ 后， $c_{0}$ 不借助原背景的三元概念生成新的三元概念的充要条件.

定理1至定理6说明：三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 添加一个新的条件 $c_{0} \notin K_{3}$ 后，原来的三元概念 $(X, B, C) \in ℑ (K_{1}, K_{2}, K_{3}, Y)$ 可能不受影响，仍旧是新背景 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\}, Y ⋃ Y_{0})$ 的三元概念； $(X, B, C)$ 也可能不再是新背景 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\},$ $Y ⋃ Y_{0})$ 的三元概念，而是被替换为 $(X, B, C ⋃ \{c_{0}\})$ ； $(X, B, C)$ 还可能与条件 $c_{0} \notin K_{3}$ 共同生成新背景的新概念 $b_{23} (B ⋂ {(X \times \{c_{0}\})}^{(2)}, C ⋃ \{c_{0}\})$ ；此外，条件 $c_{0} \notin K_{3}$ 也可能单独生成新背景 $(K_{1}, K_{2}, K_{3} ⋃ \{c_{0}\},$

$Y ⋃ Y_{0})$ 的三元概念 $(X_{0}, B_{0}, \{c_{0}\})$ .

3 三元概念的增量式构造算法

设 $(K_{1}, K_{2}, K_{3}, Y)$ 为三元形式背景，不妨设 $K_{3} = \{c_{1}, c_{2}, \dots, c_{n}\}$ .考虑条件逐个增加时三元概念的构造算法，称为三元概念的增量式构造算法.

算法

计算三元形式背景 $(K_{1}, K_{2}, K_{3}, Y)$ 所有三元概念

输入三元形式背景 $(K_{1}, K_{2}, K_{3}, Y)$ ；

输出所有三元概念 $ℑ$ ；

1.初始化 $ℑ = \emptyset$ ；

2. $ℑ \leftarrow \{(X, B, C)| (X, B, C) \in ℑ (K_{1}, K_{2}, \{c_{1}\}, Y_{1})\}$ ，并置i=2；

3.令 $S = ℑ$ ；

4.依次遍历 $S$ 中的每个元素 $(X, B, C)$ ；

5.若 $B ⋂ {(X \times \{c_{i}\})}^{(2)} = B$ ，则 $ℑ \leftarrow ℑ - \{(X, B, C)\}$ 且 $ℑ \leftarrow ℑ ⋃ \{(X, B, C ⋃ \{c_{i}\})\}$ ，并转至步骤7；否则转至步骤6；

6.若 $B ⋂ {(X \times \{c_{i}\})}^{(2)} \neq \emptyset$ 且 $B ⋂ {(X \times \{c_{i}\})}^{(2)} \neq B$ ，则 $ℑ \leftarrow ℑ ⋃ \{b_{23} (B ⋂ {(X \times \{c_{i}\})}^{(2)}, C ⋃ \{c_{i}\})\}$ ；

7.若 $S - \{(X, B, C)\} \neq \emptyset$ ，则 $S \leftarrow S - \{(X, B, C)\}$ 并返回步骤4；

8.若 $(X_{0}, B_{0}, \{c_{i}\}) \in ℑ (K_{1}, K_{2}, \{c_{i}\}, Y_{i})$ 且 $\forall (X, B, C) \in$

ℑ (K_{1}, K_{2}, \{c_{1}, \dots, c_{i - 1}\}, \cup_{j = 1}^{i - 1} Y_{j})

，

C \neq \emptyset

有

X ⋂ X_{0} \neq X_{0}

或

B ⋂ B_{0} \neq B_{0}

，则

ℑ \leftarrow ℑ ⋃ (X_{0}, B_{0}, \{c_{i}\})

；

9.若 $i < n$ ，则 $i \leftarrow i + 1$ ，并返回步骤3；

10.若 $\underset{(X, B, C) \in ℑ}{\cap} C = \emptyset$ ，则 $ℑ \leftarrow ℑ ⋃ \{(K_{1}, K_{2}, \emptyset)\}$ ；

11.若 $(\emptyset, K_{2}, K_{3})$ 是 $(K_{1}, K_{2}, K_{3}, Y)$ 的三元概念，则 $ℑ \leftarrow ℑ ⋃ \{(\emptyset, K_{2}, K_{3})\}$ ；

12.若 $(K_{1}, \emptyset, K_{3})$ 是 $(K_{1}, K_{2}, K_{3}, Y)$ 的三元概念，则 $ℑ \leftarrow ℑ ⋃ \{(K_{1}, \emptyset, K_{3})\}$ ；

13.输出 $ℑ$ .

三元概念的增量式构造方法考虑的是条件逐个增加时原有三元概念的更新、删减及新三元概念增加的情况.由于条件 $c_{1}$ 对应的三元背景 $(K_{1}, K_{2}, \{c_{1}\}, Y_{1})$ 生成所有三元概念的时间复杂度为 $O (|K_{1}|)$ ，结合三元概念的增量式构造算法可知本算法的时间杂度为 $O (|K_{3}| \times m a x \{|K_{1}|, |ℑ_{1}|\})$ .

关于三元概念的构造，Lehmann and Wille^［1］给出构造三元概念的枚举法.由定义1和命题1可知，该方法是对对象幂集、属性幂集和条件幂集中任意两个集合的全部元素逐一检查它们是否构成三元概念.以对象幂集和条件幂集为例采用枚举法生成所有的三元概念的时间复杂度为 $O (2^{|K_{1}|} \times 2^{|K_{3}|})$ .王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，生成所有对象⁃条件三元概念的时间复杂度为 $O (|K_{1}| \times |K_{3}|)$ ，若记 $O C$ 为所有对象⁃条件三元概念构成的集合，则通过对象⁃条件三元概念计算其余三元概念的时间复杂度为 $O (2^{|O C|} - |O C| - 1)$ .从时间复杂度的角度上看，三元概念的增量式构造方法及算法具有一定的优势.

例2 根据三元概念的增量式构造方法，计算表1中三元背景 $(K_{1}, K_{2}, K_{3}, Y)$ 的所有三元概念，具体步骤如下：

（1）初始状态只有 $c_{1}$ ，即初始三元背景为 $(K_{1}, K_{2}, \{c_{1}\}, Y_{1})$ ，故：

\begin{array}{l} ℑ_{1} = \{(\emptyset, K_{2}, \{c_{1}\}), (K_{1}, \emptyset, \{c_{1}\}), (K_{1}, K_{2}, \emptyset), \\ (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\}), (\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\}), \\ (\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}\}), (\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\}), \\ (\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}\}), (\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}\})\} \end{array}

（2）当条件 $c_{2}$ 加入时，原概念 $(\{x_{1}\},$

$\{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\})$ 的变化：

\begin{array}{l} \{g_{1}, g_{2}, g_{5}, g_{6}\} ⋂ {(\{x_{1}\} \times \{c_{2}\})}^{(2)} = \\ \{g_{1}, g_{2}, g_{5}\} \neq \{g_{1}, g_{2}, g_{5}, g_{6}\} \end{array}

所以 $(\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为：

{(\{g_{1}, g_{2}, g_{5}\} \times \{c_{1}, c_{2}\})}^{(1)} = \{x_{1}\}

所以新增三元概念 $(\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\})$ .

原概念 $(\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\})$ 的变化：

\begin{array}{l} \{g_{1}, g_{4}, g_{6}\} ⋂ {(\{x_{2}\} \times \{c_{2}\})}^{(2)} = \\ \{g_{4}, g_{6}\} \neq \{g_{1}, g_{4}, g_{6}\} \end{array}

所以 $(\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为：

{(\{g_{4}, g_{6}\} \times \{c_{1}, c_{2}\})}^{(1)} = \{x_{2}\}

所以新增三元概念 $(\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\})$ .

原概念 $(\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}\})$ 的变化：

\{g_{2}, g_{3}, g_{4}\} ⋂ {(\{x_{3}\} \times \{c_{2}\})}^{(2)} = \{g_{2}, g_{3}, g_{4}\}

所以 $(\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}\})$ 被更新为 $(\{x_{3}\},$

\{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\})

原概念 $(\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\})$ 的变化：

\{g_{1}, g_{6}\} ⋂ {(\{x_{1}, x_{2}\} \times \{c_{2}\})}^{(2)} = \emptyset \neq \{g_{1}, g_{6}\}

所以 $(\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\})$ 不被更新，它仍然是新背景的三元概念.

原概念 $(\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}\})$ 的变化：

\{g_{4}\} ⋂ {(\{x_{2}, x_{3}\} \times \{c_{2}\})}^{(2)} = \{g_{4}\}

所以 $(\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}\})$ 被更新为 $(\{x_{2}, x_{3}\}, \{g_{4}\},$

\{c_{1}, c_{2}\})

原概念 $(\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}\})$ 的变化：

\{g_{2}\} ⋂ {(\{x_{1}, x_{3}\} \times \{c_{2}\})}^{(2)} = \{g_{2}\}

所以 $(\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}\})$ 被更新为 $(\{x_{1}, x_{3}\}, \{g_{2}\},$

\{c_{1}, c_{2}\})

原概念 $(\emptyset, K_{2}, \{c_{1}\})$ 被更新为 $(\emptyset, K_{2}, \{c_{1}, c_{2}\})$ .

原概念 $(K_{1}, \emptyset, \{c_{1}\})$ 被更新为 $(K_{1}, \emptyset, \{c_{1}, c_{2}\})$ .

原概念 $(K_{1}, K_{2}, \emptyset)$ 不被更新，它仍然是新背景的三元概念.

由条件 $c_{2}$ 新增的三元概念如下：由于

(\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\}) \in ℑ (K_{1}, K_{2}, \{c_{2}\}, Y_{2})

且 $\forall (X, B, C) \in ℑ_{1}$ ， $C \neq \emptyset$ 有 $X ⋂ \{x_{3}\} \neq \{x_{3}\}$ 或 $B ⋂ \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\} \neq \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}$ ，所以 $(\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\})$ 为由条件 $c_{2}$ 新增的三元概念.

同样地，由于：

(\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}, c_{2}\}) \in ℑ (K_{1}, K_{2}, \{c_{2}\}, Y_{2})

且 $\forall (X, B, C) \in ℑ_{1}$ ， $C \neq \emptyset$ 有 $X ⋂ \{x_{1}, x_{3}\} \neq$

$\{x_{1}, x_{3}\}$ 或 $B ⋂ \{g_{2}\} \neq \{g_{2}\}$ ，所以 $(\{x_{1}, x_{3}\}, \{g_{2}\},$

$\{c_{1}, c_{2}\})$ 为由条件 $c_{2}$ 新增的三元概念.即，

\begin{array}{l} ℑ_{2} = \{(\emptyset, K_{2}, \{c_{1}, c_{2}\}), (K_{1}, \emptyset, \{c_{1}, c_{2}\}), (K_{1}, K_{2}, \emptyset), (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\}), (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\}), \\ (\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\}), (\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\}), (\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\}), \\ (\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\}), (\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}, c_{2}\}), (\{x_{1}, x_{2}\}, \{g_{2}\}, \{c_{1}, c_{2}\}), (\{x_{2}, x_{3}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{2}\})\} \end{array}

（3）当条件 $c_{3}$ 加入时，原概念 $(\{x_{1}\},$

$\{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\})$ 的变化：

\begin{array}{l} \{g_{1}, g_{2}, g_{5}, g_{6}\} ⋂ {(\{x_{1}\} \times \{c_{3}\})}^{(2)} = \\ \{g_{2}, g_{6}\} \neq \{g_{1}, g_{2}, g_{5}, g_{6}\} \end{array}

所以 $(\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为

{(\{g_{2}, g_{6}\} \times \{c_{1}, c_{3}\})}^{(1)} = \{x_{1}\}

且

\{g_{2}, g_{6}\} ⊄ {(\{x_{1}\} \times \{c_{2}\})}^{(2)} = \{g_{1}, g_{2}, g_{5}\}

所以新增三元概念 $(\{x_{1}\}, \{g_{2}, g_{6}\}, \{c_{1}, c_{3}\})$ .

原概念 $(\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\})$ 的变化：

\{g_{1}, g_{2}, g_{5}\} ⋂ {(\{x_{1}\} \times \{c_{3}\})}^{(2)} = \{g_{2}\} \neq \{g_{1}, g_{2}, g_{5}, g_{6}\}

所以 $(\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为 ${(\{g_{2}\} \times K_{3})}^{(1)} =$

$\{x_{1}, x_{3}\}$ ，所以新增三元概念 $(\{x_{1}, x_{3}\}, \{g_{2}\}, K_{3})$ .

原概念 $(\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\})$ 的变化：

\{g_{1}, g_{4}, g_{6}\} ⋂ {(\{x_{2}\} \times \{c_{3}\})}^{(2)} = \{g_{1}\} \neq \{g_{1}, g_{4}, g_{6}\}

所以 $(\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为

{(\{g_{1}\} \times \{c_{1}, c_{3}\})}^{(1)} = \{x_{2}\}

且

\{g_{1}\} ⊄ {(\{x_{2}\} \times \{c_{2}\})}^{(2)} = \{g_{4}, g_{6}\}

所以新增三元概念 $(\{x_{2}\}, \{g_{1}\}, \{c_{1}, c_{3}\})$ .

原概念 $(\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\})$ 的变化：

\{g_{4}, g_{6}\} ⋂ {(\{x_{2}\} \times \{c_{3}\})}^{(2)} = \emptyset \neq \{g_{4}, g_{6}\}

所以 $(\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\})$ 不被更新，它仍然是新背景的三元概念.

原概念 $(\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\})$ 的变化：

\{g_{2}, g_{3}, g_{4}\} ⋂ {(\{x_{3}\} \times \{c_{3}\})}^{(2)} = \{g_{2}, g_{4}\} \neq \{g_{2}, g_{3}, g_{4}\}

所以， $(\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为 ${(\{g_{2}, g_{4}\} \times K_{3})}^{(1)} = \{x_{3}\}$ ，所以新增三元概念 $(\{x_{3}\}, \{g_{2}, g_{4}\}, K_{3})$ .

原概念 $(\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\})$ 的变化：

\begin{array}{l} \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\} ⋂ {(\{x_{3}\} \times \{c_{3}\})}^{(2)} = \\ \{g_{1}, g_{2}, g_{4}\} \neq \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\} \end{array}

所以 $(\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为：

{(\{g_{1}, g_{2}, g_{4}\} \times \{c_{2}, c_{3}\})}^{(1)} = \{x_{3}\}

且

\{g_{1}, g_{2}, g_{4}\} ⊄ {(\{x_{3}\} \times \{c_{1}\})}^{(2)} = \{g_{2}, g_{3}, g_{4}\}

所以新增三元概念 $(\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}, c_{3}\})$ .

原概念 $(\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\})$ 的变化：

\{g_{1}, g_{6}\} ⋂ {(\{x_{1}, x_{2}\} \times \{c_{3}\})}^{(2)} = \emptyset \neq \{g_{1}, g_{6}\}

所以 $(\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\})$ 不被更新.

原概念 $(\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}, c_{2}\})$ 的变化：

\{g_{4}\} ⋂ {(\{x_{2}, x_{3}\} \times \{c_{3}\})}^{(2)} = \emptyset \neq \{g_{4}\}

所以 $(\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}, c_{2}\})$ 不被更新，它仍然是新背景的三元概念.

原概念 $(\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}, c_{2}\})$ 的变化：

\{g_{2}\} ⋂ {(\{x_{1}, x_{3}\} \times \{c_{3}\})}^{(2)} = \{g_{2}\}

所以 $(\{x_{1}, x_{3}\}, \{g_{2}\}, \{c_{1}, c_{2}\})$ 被更新为 $(\{x_{1}, x_{3}\},$

\{g_{2}\}, K_{3})

原概念 $(\{x_{1}, x_{3}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{2}\})$ 的变化：

\{g_{1}, g_{2}, g_{5}\} ⋂ {(\{x_{1}, x_{3}\} \times \{c_{3}\})}^{(2)} = \{g_{2}\} \neq \{g_{1}, g_{2}, g_{5}\}

所以 $(\{x_{1}, x_{3}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{2}\})$ 不被更新，它仍然是新背景的三元概念.同时，因为：

{(\{g_{2}\} \times \{c_{2}, c_{3}\})}^{(1)} = \{x_{1}, x_{3}\}

且

\{g_{2}\} \subseteq {(\{x_{1}, x_{3}\} \times \{c_{1}\})}^{(2)} = \{g_{2}\}

所以新增三元概念 $(\{x_{1}, x_{3}\}, \{g_{2}\}, K_{3})$ .

原概念 $(\emptyset, K_{2}, \{c_{1}, c_{2}\})$ 被更新为 $(\emptyset, K_{2}, K_{3})$ ；

原概念 $(K_{1}, \emptyset, \{c_{1}, c_{2}\})$ 被更新为 $(\emptyset, K_{2}, K_{3})$ ；原概念 $(K_{1}, K_{2}, \emptyset)$ 不被更新，它仍然是新背景的三元概念.

由条件 $c_{3}$ 新增的三元概念：

\begin{array}{l} L = \{(\{x_{1}\}, \{g_{2}, g_{3}, g_{6}\}, \{c_{3}\}), (\{x_{2}\}, \{g_{1}, g_{3}, g_{5}\}, \{c_{3}\}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{4}, g_{6}\}, \{c_{3}\}), \\ (\{x_{1}, x_{2}\}, \{g_{3}\}, \{c_{3}\}), (\{x_{1}, x_{3}\}, \{g_{2}, g_{6}\}, \{c_{3}\}), (\{x_{2}, x_{3}\}, \{g_{1}\}, \{c_{3}\})\} \subseteq ℑ (K_{1}, K_{2}, \{c_{3}\}, Y_{3}) \end{array}

由于 $\forall (X_{0}, Y_{0}, \{c_{3}\}) \in L$ 满足： $\forall (X, B, C) \in ℑ_{2}$ ， $C \neq \emptyset$ 有 $X ⋂ X_{0} \neq X_{0}$ 或 $B ⋂ B_{0} \neq B_{0}$ ，所以 $(X_{0}, Y_{0}, \{c_{3}\})$ 为由条件 $c_{3}$ 新增的三元概念.即：

\begin{array}{l} ℑ = \{(\emptyset, K_{2}, K_{3}), (K_{1}, \emptyset, K_{3}), (K_{1}, K_{2}, \emptyset), \\ (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}, g_{6}\}, \{c_{1}\}), (\{x_{1}\}, \{g_{2}, g_{6}\}, \{c_{1}, c_{3}\}), (\{x_{1}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{1}, c_{2}\}), (\{x_{1}\}, \{g_{2}, g_{3}, g_{6}\}, \{c_{3}\}), \\ (\{x_{2}\}, \{g_{1}, g_{4}, g_{6}\}, \{c_{1}\}), (\{x_{2}\}, \{g_{4}, g_{6}\}, \{c_{1}, c_{2}\}), (\{x_{2}\}, \{g_{1}, g_{3}, g_{5}\}, \{c_{3}\}), (\{x_{2}\}, \{g_{1}\}, \{c_{1}, c_{3}\}), \\ (\{x_{3}\}, \{g_{2}, g_{3}, g_{4}\}, \{c_{1}, c_{2}\}), (\{x_{3}\}, \{g_{2}, g_{4}\}, K_{3}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{3}, g_{4}, g_{5}\}, \{c_{2}\}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{4}\}, \{c_{2}, c_{3}\}), \\ (\{x_{1}, x_{2}\}, \{g_{1}, g_{6}\}, \{c_{1}\}), (\{x_{3}\}, \{g_{1}, g_{2}, g_{4}, g_{6}\}, \{c_{3}\}), (\{x_{1}, x_{2}\}, \{g_{3}\}, \{c_{3}\}), (\{x_{2}, x_{3}\}, \{g_{4}\}, \{c_{1}, c_{2}\}), \\ (\{x_{1}, x_{3}\}, \{g_{2}\}, K_{3}), (\{x_{1}, x_{3}\}, \{g_{2}, g_{6}\}, \{c_{3}\}), (\{x_{1}, x_{3}\}, \{g_{1}, g_{2}, g_{5}\}, \{c_{2}\}), (\{x_{2}, x_{3}\}, \{g_{1}\}, \{c_{3}\})\} \end{array}

与例1中所有三元概念一致.

4 结论

一个三元背景增加一个新的条件后，原背景的三元概念可能仍旧是新背景的三元概念，可能与新条件共同生成新背景的三元概念，也可能被替换掉，而新的条件也可能不借助原背景的三元概念而形成新的三元概念.本文分别给出了上述四种情况的充要条件，并得到了条件逐个增加时生成所有三元概念的增量式方法.同样地，在本文的基础上还可以考虑对象逐个增加时或属性逐个增加时生成所有三元概念的方法以及进行概念约简的相关问题.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Lehmann

，Wille

A triadic approach to formal concept analysis

∥Conceptual Structures：Applications，Implementation and Theory. Springer Berlin Heidelberg，1995：32-43.

[本文引用: 7]

[2]

Wille

Restructuring lattice theory：An approach based on hierarchies of concepts

∥Rival I. Ordered sets. Springer Berlin Heidelberg，1982：445-470.

[本文引用: 1]

[3]

Ganter

，Wille

. Formal concept analysis：Mathematical foundations. Berlin：Springer，1999，17-61.

[本文引用: 1]

[4]

魏玲，万青，钱婷，等.

三元概念分析综述

西北大学学报(自然科学版)，2014，44(5)：689-699.

[本文引用: 2]

Wei

，Wan

，Qian

，et al.

An overview of triadic concept analysis

Journal of Northwest University (Natural Science Edition)，2014，44(5)：689-699.

[本文引用: 2]

[5]

Wei

，Qian

，Wan

，et al.

A research summary about triadic concept analysis

International Journal of Machine Learning and Cybernetics，2018，9(4)：699-712.

[本文引用: 1]

[6]

Wille

The basic theorem of triadic concept analysis

Order，1995，12(2)：149-158.

[本文引用: 1]

[7]

Biedermann

Triadic Galois connections

∥Denecke K，Lüders O. General algebra and applications in discrete mathematics. Aachen：Shaker Verlag，1997：23-33.

[8]

Biedermann

An equational theory for trilattices

Algebra Universalis，1999，42(4)：253-268.

[9]

Groh

，Wille

Lattices of triadic concept graphs

∥8^th International Conference on Conceptual Structures. Springer Berlin Heidelberg，2000：332-341.

[10]

孙斌斌

. 概念三元格构造算法研究. 硕士学位论文. 西安：西安电子科技大学，2015.

[本文引用: 1]

Sun

B B

Study on the construction algorithm of concept trilattices

Master Dissertation. Xi'an：Xidian University，2015.

[本文引用: 1]

[11]

Biedermann

How triadic diagrams represent conceptual structures

∥5^th Conceptual Structures：Fulfilling Peirce's Dream. Springer Berlin Heidelberg，1997：304-317.

[本文引用: 1]

[12]

Ganter

，Obiedkov

S A

Implications in triadic formal contexts

∥12^th International Conference on Conceptual Structures. Springer Berlin Heidelberg，2004：186-195.

[13]

Missaoui

，Kwuida

Mining triadic association rules from ternary relations

∥9^th International Conference on Formal Concept Analysis. Springer Berlin Heidelberg，2011：204-218.

[本文引用: 1]

[14]

Dau

，Wille

On the modal understanding of triadic context

∥Decker R，Gaul W. Classification and information processing at the turn of the millennium. Springer Berlin Heidelberg，2000：83-94.

[本文引用: 1]

[15]

Jaschke

，Hotho

，Schmitz

，et al.

TRIAS：An algorithm for mining iceberg tri⁃lattices

∥6^th Inter⁃national Conference on Data Mining.Hong Kong，China：IEEE，2006：907-911.

[本文引用: 1]

[16]

Kavtoue

，Kuznetsov

，Macko

，et al.

Mining biclusters of similar values with triadic concept analysis

2011,arXiv:.

[17]

Kaytoue

，Kuznetsov

S O

，Macko

，et al.

Biclustering meets triadic concept analysis

Annals of Mathematics and Artificial Intelligence，2014，70(1/2)：55-79.

[本文引用: 1]

[18]

Belohlavek

，Vychodil

Optimal factorization of three⁃way binary data

∥2010 IEEE International Conference on Granular Computing. San Jose，CA，USA：IEEE，2010：61-66.

[本文引用: 1]

[19]

Glodeanu

Factorization methods of binary，triadic，real and fuzzy data

Informatica，2011，56(2)：81-86.

[20]

Belohlavek

，Glodeanu

，Vychodil

Optimal factorization of three⁃way binary data using triadic concepts

Order，2013，30(2)：437-454.

[21]

Glodeanu

C V

Tri⁃ordinal factor analysis

∥International Conference on Formal Concept Analysis. Springer Berlin Heidelberg，2013：125-140.

[本文引用: 1]

[22]

Belohlavek

，Osicka

Triadic concept analysis of data with fuzzy attributes

∥2010 IEEE International Conference on Granular Computing. San Jose，CA，USA：IEEE，2010：661-665.

[本文引用: 1]

[23]

Belohlavek

，Osicka

Triadic concept lattices of data with graded attributes

International Journal of General Systems，2012，41(2)：93-108.

[24]

Konecny

，Osicka

Triadic concept lattices in the framework of aggregation structures

Information Sciences，2014，279：512-527.

[25]

Glodeanu

C V

Fuzzy⁃Valued triadic implications

∥Proceedings of the 8th International Conference on Concept Lattices and Their Applications. Nancy，France：CEUR⁃WS.org，2011：159-173.

[26]

Belohlavek

，Osicka

Triadic fuzzy Galois connections as ordinary connections

Fuzzy Sets and Systems，2014(249)：83-99.

[本文引用: 1]

[27]

汤亚强，范敏，李金海.

三元形式概念分析下的认知系统模型及信息粒转化方法

山东大学学报(理学版)，2014，49(8)：102-106.

[本文引用: 1]

Tang

Y Q

，Fan

，Li

J H

Cognitive system model and approach to transformation of information granules under triadic formal concept analysis

Journal of Shandong University (Natural Science)，2014，49(8)：102-106.

[本文引用: 1]

[28]

祁建军，魏玲.

三元背景及概念三元格的简化

计算机科学，2017，44(9)：53-57.

[本文引用: 1]

J J

，Wei

Simplification of triadic contexts and concept trilattices

Computer Science，2017，44(9)：53-57.

[本文引用: 1]

[29]

魏玲，曹丽，祁建军.

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

西北大学学报(自然科学版)，2017，47(3)：313-320.

[本文引用: 1]

Wei

，Cao

，Qi

J J

Reduction based on the binary relations for triadic contexts

Journal of Northwest University (Natural Science Edition)，2017，47(3)：313-320.

[本文引用: 1]

[30]

王霞，张茜，李俊余，等.

基于粗糙集的三元概念分析

山东大学学报(理学版)，2017，52(7)：37-43.

[本文引用: 1]

Wang

，Zhang

，Li

J Y

，et al.

Triadic concept analysis based on rough set theory

Journal of Shandong University (Natural Science)，2017，52(7)：37-43.

[本文引用: 1]

[31]

Zhuk

，Ignatov

D I

，Konstantinova

Concept learning from triadic data

Procedia Computer Science，2014(31)：928-938.

[本文引用: 1]

[32]

Kumar

C A

，Mouliswaran

S C

，Li

J H

，et al.

Role based access control design using triadic concept analysis

Journal of Central South University，2016，23(12)：3183-3191.

[本文引用: 1]

[33]

李贞，张卓，王黎明.

基于三元概念分析的文本分类算法研究

计算机科学，2017，44(8)：207-215.

，Zhang

，Wang

L M

Research on text classification algorithm based on triadic concept analysis

.Computer Science，2017，44(8)：207-215.

[34]

薛金蓉，安秋生，郑军.

概念格的内涵缩减与数据库推理依赖

计算机研究与发展，2014，51(1)：96-103.

Xue

J R

，An

Q S

，Zheng

Intent reduction of concept lattice and database inference dependence

Journal of Computer Research and Development，2014，51(1)：96-103.

[35]

王霞，江山，李俊余，等.

三元概念的一种构造方法

计算机研究与发展，2019，56(4)：844-853.

[本文引用: 3]

Wang

，Jiang

，Li

J Y

，et al.

A construction method of triadic concepts

Journal of Computer Research and Development，2019，56(4)：844-853.

[本文引用: 3]

A triadic approach to formal concept analysis

1995

... 1995年，Lehmann and Wille^［1］基于皮尔斯范畴三分理论提出三元概念分析，它可以看作是形式概念分析^［2-3］的推广.三元概念分析的基本概念是三元背景和三元概念.三元背景^［1］是一个四元组

(K_{1}, K_{2}, K_{3}, Y)

，其中

K_{1}, K_{2}, K_{3}

为非空集合，

Y

为

K_{1}, K_{2}, K_{3}

之间的关系，即

Y \subseteq K_{1} \times K_{2} \times K_{3}

.分别称

K_{1}, K_{2}, K_{3}

为对象集、属性集和条件集，

K_{1}, K_{2}, K_{3}

的元素为对象、属性和条件.若对象x、属性b和条件c具有关系Y，则记为

(x, b, c) \in Y

，表示对象x在条件c下具有属性b，通常在三维交叉表的相应位置用“1”标出.若

(x, b, c) \notin Y

，则在三维交叉表的相应位置用“0”标出.三元概念是由外延、内涵和方式三部分构成的一个三元组.一个三元概念正好是

P (K_{1}) \times P (K_{2}) \times P (K_{3})

中（基于集合的包含关系）最大的三元组

(X, B, C) \subseteq Y

. ...

... ［1］是一个四元组

(K_{1}, K_{2}, K_{3}, Y)

，其中

K_{1}, K_{2}, K_{3}

为非空集合，

Y

为

K_{1}, K_{2}, K_{3}

之间的关系，即

Y \subseteq K_{1} \times K_{2} \times K_{3}

.分别称

K_{1}, K_{2}, K_{3}

为对象集、属性集和条件集，

K_{1}, K_{2}, K_{3}

的元素为对象、属性和条件.若对象x、属性b和条件c具有关系Y，则记为

(x, b, c) \in Y

，表示对象x在条件c下具有属性b，通常在三维交叉表的相应位置用“1”标出.若

(x, b, c) \notin Y

，则在三维交叉表的相应位置用“0”标出.三元概念是由外延、内涵和方式三部分构成的一个三元组.一个三元概念正好是

P (K_{1}) \times P (K_{2}) \times P (K_{3})

中（基于集合的包含关系）最大的三元组

(X, B, C) \subseteq Y

. ...

... 魏玲等^［4-5］对2014年以前三元概念分析的研究现状及发展趋势做了详细介绍.目前关于三元概念分析的研究主要集中在：概念三元格的构造及算法^{［1，6-10］}、三元蕴含及关联规则挖掘^［11-13］、三元模态算子^［14］、三元概念聚类^［15-17］、三元背景的因子分析^［18-21］、三元背景的模糊化^［22-26］、三元概念分析的认知系统模型^［27］、基于三元背景的约简^［28-29］、三元概念的推广^［30］、三元概念分析的分类问题^［31］、三元概念分析的应用^［32-35］等.在三元概念的构造方面，Lehmann and Wille^［1］给出了构造三元概念的枚举法，该方法对对象幂集、属性幂集和条件幂集的全部元素逐一检查是否构成三元概念，以此生成所有的三元概念.但利用这种方法处理规模较大的三元背景时计算量会很大.为了降低计算的复杂性，王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，该方法对对象集和条件集的全部元素逐一检查是否构成对象⁃条件三元概念，然后通过对象⁃条件三元概念计算其余三元概念.本文考虑增加一个新的条件后新背景的三元概念与原背景的三元概念之间的关系，并进一步探索构造三元概念的新方法. ...

... ［1］给出了构造三元概念的枚举法，该方法对对象幂集、属性幂集和条件幂集的全部元素逐一检查是否构成三元概念，以此生成所有的三元概念.但利用这种方法处理规模较大的三元背景时计算量会很大.为了降低计算的复杂性，王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，该方法对对象集和条件集的全部元素逐一检查是否构成对象⁃条件三元概念，然后通过对象⁃条件三元概念计算其余三元概念.本文考虑增加一个新的条件后新背景的三元概念与原背景的三元概念之间的关系，并进一步探索构造三元概念的新方法. ...

... 设

(K_{1}, K_{2}, K_{3}, Y)

为三元背景，

\{i, j, k\} = \{1,2, 3\}

且

j < k

，

X \subseteq K_{i}

，

Z \subseteq K_{j} \times K_{k}

.Lehmann and Wille^［1］定义了

(i)

⁃诱导算子： ...

... 定义1^［1］ ...

... 关于三元概念的构造，Lehmann and Wille^［1］给出构造三元概念的枚举法.由定义1和命题1可知，该方法是对对象幂集、属性幂集和条件幂集中任意两个集合的全部元素逐一检查它们是否构成三元概念.以对象幂集和条件幂集为例采用枚举法生成所有的三元概念的时间复杂度为

O (2^{|K_{1}|} \times 2^{|K_{3}|})

.王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，生成所有对象⁃条件三元概念的时间复杂度为

O (|K_{1}| \times |K_{3}|)

，若记

O C

为所有对象⁃条件三元概念构成的集合，则通过对象⁃条件三元概念计算其余三元概念的时间复杂度为

O (2^{|O C|} - |O C| - 1)

.从时间复杂度的角度上看，三元概念的增量式构造方法及算法具有一定的优势. ...

Restructuring lattice theory：An approach based on hierarchies of concepts

1982

(K_{1}, K_{2}, K_{3}, Y)

，其中

K_{1}, K_{2}, K_{3}

为非空集合，

Y

为

K_{1}, K_{2}, K_{3}

之间的关系，即

Y \subseteq K_{1} \times K_{2} \times K_{3}

.分别称

K_{1}, K_{2}, K_{3}

为对象集、属性集和条件集，

K_{1}, K_{2}, K_{3}

的元素为对象、属性和条件.若对象x、属性b和条件c具有关系Y，则记为

(x, b, c) \in Y

，表示对象x在条件c下具有属性b，通常在三维交叉表的相应位置用“1”标出.若

(x, b, c) \notin Y

，则在三维交叉表的相应位置用“0”标出.三元概念是由外延、内涵和方式三部分构成的一个三元组.一个三元概念正好是

P (K_{1}) \times P (K_{2}) \times P (K_{3})

中（基于集合的包含关系）最大的三元组

(X, B, C) \subseteq Y

. ...

1999

(K_{1}, K_{2}, K_{3}, Y)

，其中

K_{1}, K_{2}, K_{3}

为非空集合，

Y

为

K_{1}, K_{2}, K_{3}

之间的关系，即

Y \subseteq K_{1} \times K_{2} \times K_{3}

.分别称

K_{1}, K_{2}, K_{3}

为对象集、属性集和条件集，

K_{1}, K_{2}, K_{3}

的元素为对象、属性和条件.若对象x、属性b和条件c具有关系Y，则记为

(x, b, c) \in Y

，表示对象x在条件c下具有属性b，通常在三维交叉表的相应位置用“1”标出.若

(x, b, c) \notin Y

，则在三维交叉表的相应位置用“0”标出.三元概念是由外延、内涵和方式三部分构成的一个三元组.一个三元概念正好是

P (K_{1}) \times P (K_{2}) \times P (K_{3})

中（基于集合的包含关系）最大的三元组

(X, B, C) \subseteq Y

. ...

三元概念分析综述

2014

... 命题1^［4］ ...

三元概念分析综述

2014

... 命题1^［4］ ...

A research summary about triadic concept analysis

2018

The basic theorem of triadic concept analysis

1995

Triadic Galois connections

1997

An equational theory for trilattices

1999

Lattices of triadic concept graphs

2000

Study on the construction algorithm of concept trilattices

2015

Study on the construction algorithm of concept trilattices

2015

How triadic diagrams represent conceptual structures

1997

Implications in triadic formal contexts

2004

Mining triadic association rules from ternary relations

2011

On the modal understanding of triadic context

2000

TRIAS：An algorithm for mining iceberg tri?lattices

2006

Mining biclusters of similar values with triadic concept analysis

2011

Biclustering meets triadic concept analysis

2014

Optimal factorization of three?way binary data

2010

Factorization methods of binary，triadic，real and fuzzy data

2011

Optimal factorization of three?way binary data using triadic concepts

2013

Tri?ordinal factor analysis

2013

Triadic concept analysis of data with fuzzy attributes

2010

Triadic concept lattices of data with graded attributes

2012

Triadic concept lattices in the framework of aggregation structures

2014

Fuzzy?Valued triadic implications

2011

Triadic fuzzy Galois connections as ordinary connections

2014

三元形式概念分析下的认知系统模型及信息粒转化方法

2014

三元形式概念分析下的认知系统模型及信息粒转化方法

2014

三元背景及概念三元格的简化

2017

三元背景及概念三元格的简化

2017

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

2017

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

2017

基于粗糙集的三元概念分析

2017

基于粗糙集的三元概念分析

2017

Concept learning from triadic data

2014

Role based access control design using triadic concept analysis

2016

基于三元概念分析的文本分类算法研究

2017

基于三元概念分析的文本分类算法研究

2017

概念格的内涵缩减与数据库推理依赖

2014

概念格的内涵缩减与数据库推理依赖

2014

三元概念的一种构造方法

2019

... ［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，该方法对对象集和条件集的全部元素逐一检查是否构成对象⁃条件三元概念，然后通过对象⁃条件三元概念计算其余三元概念.本文考虑增加一个新的条件后新背景的三元概念与原背景的三元概念之间的关系，并进一步探索构造三元概念的新方法. ...

O (2^{|K_{1}|} \times 2^{|K_{3}|})

.王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，生成所有对象⁃条件三元概念的时间复杂度为

O (|K_{1}| \times |K_{3}|)

，若记

O C

为所有对象⁃条件三元概念构成的集合，则通过对象⁃条件三元概念计算其余三元概念的时间复杂度为

O (2^{|O C|} - |O C| - 1)

.从时间复杂度的角度上看，三元概念的增量式构造方法及算法具有一定的优势. ...

三元概念的一种构造方法

2019

O (2^{|K_{1}|} \times 2^{|K_{3}|})

.王霞等^［35］提出基于对象⁃条件三元概念构造所有三元概念的方法，生成所有对象⁃条件三元概念的时间复杂度为

O (|K_{1}| \times |K_{3}|)

，若记

O C

为所有对象⁃条件三元概念构成的集合，则通过对象⁃条件三元概念计算其余三元概念的时间复杂度为

O (2^{|O C|} - |O C| - 1)

.从时间复杂度的角度上看，三元概念的增量式构造方法及算法具有一定的优势. ...

〈

〉