先给出形式背景及其算子的定义。

定义1^[1]   (G, M, I)为形式背景，其中G={x₁, x₂, …, x_n}，每个x_i(i≤n)称为对象；M={a₁, a₂, …, a_m}，每个a_j(j≤m)称为属性；对于x∈G与a∈M，如果(x, a)∈I，则称对象x拥有属性a。

定义2^[1]   (G, M, I)为形式背景，X $ \subseteq $ G，A$ \subseteq $M。一对算子定义如下：

*: P(G)→P(M)，X^*={a∈M |∀x∈X，(x, a)∈I}；

*: P(M)→P(G)，A^*={x∈G |∀a∈M，(x, a)∈I}。

基于形式背景的算子，可定义形式概念及其概念格。

定义3^[1]   (G, M, I)为形式背景，若X^*=A且A^*= X，则称(X, A)是一个概念。X称为该概念的外延，A称为该概念的内涵。

对于任意概念(X₁, A₁)，(X₂, A₂)，定义偏序关系为(X₁, A₁)≤(X₂, A₂) $ \Leftrightarrow $ X₁$ \subseteq $X₂$ \Leftrightarrow $A₂$ \subseteq $A₁，则形式背景(G, M, I)的所有概念在该偏序关系下是完备格，称为概念格，记为L(G, M, I)。

以下给出概念格之间的细于关系以及决策形式背景及其协调性的定义。

定义4^[8]    L(G, M, I)与L(G, N, J)是两个概念格，若对∀(Y, B)∈L(G, N, J)，存在(X, A)∈L(G, M, I)，使得X=Y，则称L(G, M, I)细于L(G, N, J)，记作L(G, M, I)≤L(G, N, J)。

定义5^[8]    (G, M, I)与(G, N, J)是两个形式背景，则称(G, M, I, N, J)是决策形式背景。若L(G, M, I)≤L(G, N, J)，则称该决策形式背景是协调的。

为了在形式概念分析中引入三支决策的思想，给出形式背景负算子的定义：

定义6^[14]    (G, M, I)是形式背景，对于X$ \subseteq $G，A$ \subseteq $M，一对负算子定义如下：

*^－: P(G)→P(M)：X^*－= {a∈M|∀x∈X， $\neg $ (xIa)}={a∈M|∀x∈X，xI ^ca}，其中I^c =(G×M)-I。

*^－: P(M)→P(G)：A^*－={x∈G|∀a∈A，$\neg $(xIa)}={x∈G|∀a∈A，xI ^ca}。

在形式背景算子及负算子的基础上，可定义形式背景的三支算子：

定义7^[14]   (G, M, I)是形式背景，X$ \subseteq $G，A$ \subseteq $M，一对三支算子定义如下：

≤: P(G)→DP(M)：X^≤=(X^*，X^*－)

≤: P(M)→DP(G)：A^≤=(A^*，A^*－)

进一步地，可定义上述三支算子的逆运算：

≥: DP(M)→P(G)：(A, B)^≥={x∈G|x∈A^*且x∈B^*－}=A^*∩B^*－

≥: DP(G)→P(M)：(X, Y)^≥={a∈M|a∈X^*且a∈Y^*－}=X^*∩Y^*－

基于形式背景的三支算子，可定义对象导出三支概念和对象导出三支概念格。

定义8^[14]  设(G, M, I)是形式背景，(X, (A, B))称为对象导出三支概念，简称OE-概念，这里X^≤=(A, B)且(A, B)^≥=X，其中X$ \subseteq $G，A、B$\subseteq $M。X和(A, B)分别称为OE-概念的外延和内涵。

对于(X, (A, B))，(Y, (C, D))，定义偏序关系(X, (A, B)) ≤(Y, (C, D))$ \Leftrightarrow $X$\subseteq $Y$ \Leftrightarrow $(C, D)$\subseteq $(A, B)，形式背景(G, M, I)的所有OE-概念在该偏序关系下是完备格，称为对象导出三支概念格，记为OEL(G, M, I)。

类似地，可定义属性导出三支概念及属性导出三支概念格。

定义9^[14]  设(G, M, I)是形式背景，则称((X, Y), A)为属性导出三支概念，简称AE-概念，这里(X, Y)^≥=A且A^≤=(X, Y)，其中X、Y$\subseteq $G，A$ \subseteq $M。(X, Y)和A分别称为AE-概念的外延和内涵。

对于((X, Y), A), ((Z, W), B)，定义偏序关系((X, Y), A) ≤((Z, W), B)$ \Leftrightarrow $(X, Y)$\subseteq $(Z, W) $ \Leftrightarrow $B$\subseteq $A，形式背景(G, M, I)的所有AE-概念在该偏序关系下是完备格，称为属性导出三支概念格，记AEL(G, M, I)。

文献[18]定义了属性导出三支概念格之间的细于关系，以及决策背景基于属性导出三支概念格的协调性。

定义10^[18]  设AEL(G, M, I)与AEL(G, N, J)是属性导出三支概念格。若对于任意((Z, W), B)∈AEL(G, N, J)，存在((X, Y), A)∈AEL(G, M, I)，使得X=Z且Y=W，则称AEL(G, M, I)细于AEL(G, N, J)，记作AEL(G, M, I)≤AEL(G, N, J)，并称决策背景(G, M, I, N, J)是基于属性导出三支概念格协调的。

文献[18]比较了属性导出三支概念格和经典概念格下的规则提取。

定理1^[18]  设(G, M, I, N, J)是决策形式背景，且AEL(G, M, I)≤AEL(G, N, J)。R表示经典概念格下的生成规则集合，TR_a表示属性导出三支概念格下的生成规则集合，则R$\subseteq $TR_a。

定理2^[18]  设(G, M, I, N, J)是决策形式背景，且AEL(G, M, I)≤AEL(G, N, J)，R表示经典概念格下的生成规则集合，TR_a表示属性导出三支概念格下的生成规则集合，则对于A→B∈R，总存在C→B∈TR_a，且C$\subseteq $A。

文献[18]给出基于属性导出三支概念格的决策背景规则提取方法，本文在其基础上进一步研究基于对象导出三支概念格的规则提取，并与经典概念格及属性导出三支概念格下的规则提取进行比较。

先定义对象导出三支概念格之间的细于关系，以及决策背景基于对象导出三支概念格的协调性。

定义11   设OEL(G, M, I)与OEL(G, N, J)是对象导出三支概念格，若对于任意(Y, (C, D))∈OEL(G, N, J)，存在(X, (A, B))∈OEL(G, M, I)，使得X=Y，则称OEL(G, M, I)细于OEL(G, N, J)，记作OEL(G, M, I)≤ OEL(G, N, J)，并称决策背景(G, M, I, N, J)是基于对象导出三支概念格协调的。

例1：表 1是一个决策形式背景^[18]，G={1, 2, 3, 4}，M={a, b, c, d, e, f}，N={g, h, k}，其对象导出三支概念格OEL(G, M, I)和OEL(G, N, J)分别如图 1、图 2所示。

图  1  对象导出三支概念格OEL(G, M, I)

图  2  对象导出三支概念格OEL(G, N, J)

由图 1、图 2可以看出，OEL(G, M, I)≤OEL (G, N, J)，所以表 1所示决策背景是基于对象导出三支概念格协调的。

接着定义对象导出三支概念格下的生成规则。

定义12   设决策背景(G, M, I, N, J)是基于对象导出三支概念格协调的，若对于X、Y≠ $ \mathit{\emptyset} $ ，G，有(X, (A, B))∈OEL(G, M, I), (Y, (C, D))∈OEL(G, N, J), 且X=Y，则称A→C和B→D分别是一个规则。

例2：根据定义12，表 1所示决策背景在对象导出三支概念格下的生成规则集合TR_o为：

d→g；de→g；ab→h；abc→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

定义13   设决策背景(G, M, I, N, J)是协调的，若对于X, Y≠$ \mathit{\emptyset} $, G，有(X, A)∈L(G, M, I)，(Y, B)∈L(G, N, J)，且X=Y，则称A→B是一个规则。

例3：表 1所示决策背景的概念格L(G, M, I)和L(G, N, J)分别如图 3、图 4所示。

图  3  概念格L(G, M, I)

图  4  概念格L(G, N, J)

根据定义13，表 1所示决策背景在经典概念格下的生成规则集合R为：de→g；f→k；def→gk；abcef→hk

定理3   设(G, M, I, N, J)是决策形式背景，且OEL(G, M, I)≤OEL(G, N, J)。R表示经典概念格下的生成规则集合，TR_o表示对象导出三支概念格下的生成规则集合，则R$\subseteq $TR_o

证明：对任意A→B∈R，由定义13，存在(X, A)∈L(G, M, I)，(Y, B)∈L(G, N, J)，且X=Y。又因为OEL(G, M, I)≤OEL(G, N, J)，由定义11，对于(Y, (B, Y^*-J))∈OEL(G, N, J)，存在(X, (C, X^*-I))∈OEL(G, M, I)。由于C=X^{* I}=A，所以(X, (C, X^*-I))即(X, (A, X^*-I))。由定义12，A→B∈TR_o，因此R$\subseteq $TR_o

例4：比较表 1所示决策背景分别在对象导出三支概念格及经典概念格下的生成规则集合TR_o和R，可以看出，TR_o不仅包含了R中每条规则，还包含了ab→h；abde→gh等其他更多规则。

定理4  设(G, M, I, N, J)是决策形式背景，且OEL(G, M, I)≤OEL(G, N, J)，R表示经典概念格下的生成规则集合，TR_o表示对象导出三支概念格下的生成规则集合，则对于A→B∈R，总存在C→B∈TR_o，且C$\subseteq $A。

证明：对任意A→B∈R，由定义13，存在(X, A)∈L(G, M, I)，(Y, B)∈L(G, N, J)，且X=Y。由于存在保序嵌入^[15] $\varphi $ :L(G, M, I)→OEL(G, M, I)，$\varphi $:L(G, N, J)→ OEL(G, N, J)，使$\varphi $((X, A))=(X, (A, X^*-I))，$\varphi $((Y, B))= (Y, (B, Y^*-J))，且OEL(G, M, I)≤OEL(G, N, J)，因此对于(Y, (B, Y^*-J))∈OEL(G, N, J)，存在(Y, (C, Y^*-I))∈OEL (G, M, I)，使得C→B∈TR_a。又因为Y=C^{* I}$ \cap $Y^{*- I *-I} ，所以Y$\subseteq $C^{* I}，进而C$\subseteq $Y^{* I}=X^{* I}=A，即C$\subseteq $A。

例5：比较表 1所示决策背景分别在对象导出三支概念格及经典概念格下的生成规则集合TR_o和R，可以看出，对于R中的每条规则A→B，在TR_o中总存在相应的规则C→B，且C$\subseteq $A。

与经典概念格下的生成规则比较，对象导出三支概念格下的生成规则更为丰富也更为精炼。但是，由于对象导出三支概念格比经典概念格的概念数量更多，结构也更为复杂，因此构建对象导出三支概念格比构建经典概念格要付出更多的时间开销。

定义14  设决策背景(G, M, I, N, J)是基于属性导出三支概念格协调的，若(X, Y)、(Z, W) ≠($ \mathit{\emptyset} $, $ \mathit{\emptyset} $)、(G, G)，有((X, Y), A)∈AEL(G, M, I)，((Z, W), B)∈AEL(G, N, J)，且X=Z、Y$\subseteq $W，则称A→B是一个规则。

例6：表 1所示决策背景的属性导出三支概念格AEL(G, M, I)和AEL(G, N, J)如图 5、图 6所示。

图  5  属性导出三支概念格AEL(G, M, I)

图  6  属性导出三支概念格AEL(G, N, J)

根据定义14，表 1所示决策背景在属性导出三支概念格下的生成规则集合TR_a为：

d→g；de→g；ab→h；abe→h；abc→h；abcf→h；abcef→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

先定义对象导出三支概念格与属性导出三支概念格之间的细于关系，以及决策背景基于对象导出三支概念格和属性导出三支概念格的协调性。

定义15   设(G, M, I)是形式背景，若对于任意(X, (A, B))∈OEL(G, M, I)，存在((Y, Z), C)∈AEL (G, M, I)，使得X=Y或Z，则称AEL(G, M, I)细于OEL(G, M, I)，记作AEL(G, M, I)≤OEL(G, M, I)，并称形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的。

例7：由定义15，对于图 1所示对象导出三支概念格OEL(G, M, I)，图 5所示属性导出三支概念格AEL(G, M, I)，有AEL(G, M, I)≤OEL(G, M, I)，所以形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的；类似地，对于图 2所示对象导出三支概念格OEL(G, N, J)，图 4所示属性导出三支概念格AEL(G, N, J)，有AEL(G, N, J)≤OEL(G, N, J)，所以形式背景(G, N, J)是基于AEL(G, N, J)和OEL(G, N, J)协调的。

接下来，给出相应的规则定义。

定义16  设形式背景(G, M, I)是基于AEL(G, M, I)和OEL(G, M, I)协调的，若对于X≠$ \mathit{\emptyset} $、G，(Y, Z)≠($ \mathit{\emptyset} $, $ \mathit{\emptyset} $)、(G, G)，有(X, (A, B))∈OEL(G, M, I)，((Y, Z), C)∈AEL(G, M, I)，且X=Y或Z，则称A→B是一个规则。

在上述定义的基础上，以下比较对象导出三支概念格与属性导出三支概念格下的生成规则。

定理5  设(G, M, I, N, J)是决策背景，且AEL (G, M, I)≤AEL(G, N, J)，OEL(G, M, I)≤OEL(G, N, J), AEL(G, M, I)≤OEL(G, N, J)，则TR_o$\subseteq $TR_a

证明：对于任意A→B∈TR_o，由定义12，存在(X, (A, C)∈OEL(G, M, I)，(X, (B, D)∈OEL(G, N, J)。因为AEL(G, M, I)≤OEL(G, N, J)，因此对于(X, (B, D)∈OEL(G, N, J)，存在((X, Z), A)或((Y, X), A)∈AEL(G, M, I)。又因为AEL(G, N, J)≤OEL(G, N, J)，所以(X, (B, D)∈OEL(G, N, J)等价于((X, Z), A)或((Y, X), A)∈AEL(G, N, J)，因此对于((X, Z), A)或((Y, X), A)∈AEL(G, N, J)，存在((X, Z), A)或((Y, X), A)∈AEL(G, M, I)。因此A→B∈TR_a，即TR_{o$\subseteq $}TR_a

例8：比较表 1所示决策背景分别在对象导出三支概念格及属性导出三支概念格下的生成规则集合TR_o和TR_a，可以看出，TR_a不仅包含了TR_o中每条规则，还包含了abe→h；abcf→h；abcef→h等规则。

通过与属性导出三支概念格下的生成规则进行比较，可以看出，属性导出三支概念格下的生成规则更为丰富。但是，属性导出三支概念格比对象导出三支概念格生成了更多的冗余规则，如图 5、图 6所示属性导出三支概念格生成了de→g、abc→h、abe→h、abcf→h、abcef→h、abcef→hk等6条冗余规则，而图 1、图 2所示对象导出三支概念格只生成了de→g、abc→h、abcef→hk等3条冗余规则。因此，在支持决策分析方面，属性导出三支概念格的能力要稍弱于对象导出三支概念格。

与属性导出三支概念格类似，对象导出三支概念格下的生成规则中也引入了一些冗余规则。冗余规则是指^[18]，对规则B→C和B'→C'，若B$\subseteq $B'且C'$\subseteq $C，则称规则B'→C'是冗余的。例如，由图 5、图 6，属性导出三支概念格下的生成规则中de→g、abc→h、abe→h、abcf→h、abcef→h、abcef→hk均为冗余规则；由图 1、图 2，对象导出三支概念格下的生成规则中de→g、abc→h、abcef→hk均为冗余规则。

进一步分析原因，主要是因为基于对象导出三支概念格的规则提取时考虑的是对象特性，而基于属性导出三支概念格的规则提取时考虑的是属性特性。因此单纯基于对象导出或属性导出三支概念格进行规则提取时，就会生成一些冗余规则。

为进一步消除对象导出三支概念格或属性导出三支概念格下生成的冗余规则，以下通过对象导出三支概念格与属性导出三支概念格的合并，使得在进行规则提取时受双重特性(对象特性和属性特性)约束，从而进一步减少冗余规则的生成。为此，先给出对象/属性导出合并三支概念格的定义。

定义17    (G, M, I, N, J)是形式背景，若((X, Y), A) $ \in $ AEL(G, M, I)，(X, (A, B))或(Y, (B, A)) $ \in $OEL(G, M, I)，则((X, Y), (A, B))称为对象/属性导出合并三支概念，简称OAE-概念，这里(X, Y)^≥=A且A^≤=(X, Y)，X^≤=(A, B)且(A, B)^≥=X；或(X, Y)^≥=A且A^≤=(X, Y)，Y^≤=(B, A)且(B, A)^≥=Y。其中X、Y $\subseteq $G，A、B$\subseteq $M。(X, Y)和(A, B)称为OAE-概念的外延和内涵。

对于((X, Y), (A, B))，((Z, W), (C, D))，定义其偏序关系((X, Y), (A, B))≤((Z, W), (C, D))$ \Leftrightarrow $(X, Y)$\subseteq $(Z, W)$ \Leftrightarrow $ (C, D)$\subseteq $(A, B)，形式背景(G, M, I)的所有OAE-概念在上面定义的偏序关系下是完备格，称为对象/属性导出合并三支概念格，记为OAEL(G, M, I)。

例9：合并图 1的OEL(G, M, I)和图 5的AEL(G, M, I)，以及图 2的OEL(G, N, J)和图 6的AEL(G, N, J)，所得对象/属性导出合并三支概念格OAEL(G, M, I)和OAEL(G, N, J)如图 7、图 8所示。

图  7  对象/属性导出合并三支概念格OAEL(G, M, I)

图  8  对象/属性导出合并三支概念格OAEL(G, N, J)

接下来，定义对象/属性导出合并三支概念格之间的细于关系，以及决策背景基于对象/属性导出合并三支概念格的协调性。

定义18  设OAEL(G, M, I)与OAEL(G, N, J)是对象/属性导出合并三支概念格, 若对于任意((Z, W), (C, D))∈OAEL(G, N, J)，存在((X, Y), (A, B))∈OAEL (G, M, I)，使得X=Z且Y=W，则称OAEL(G, M, I)细于OAEL(G, N, J)，记作OAEL(G, M, I)≤OAEL(G, N, J)，并称决策背景(G, M, I, N, J)是基于对象/属性导出合并三支概念格协调的。

例10：表 1所示决策背景的对象/属性导出合并三支概念格OAEL(G, M, I)≤OAEL(G, N, J)，所以该决策背景是基于对象/属性导出合并三支概念格协调的。

在上述定义的基础上，进一步定义对象/属性导出合并三支概念格下的生成规则。

定义19   设决策背景(G, M, I, N, J)是基于对象/属性导出合并三支概念格协调的，若对于(X, Y)、(Z, W)≠($ \mathit{\emptyset} $, $ \mathit{\emptyset} $)、(G, G)，有((X, Y), (A, B))∈OAEL(G, M, I), ((Z, W), (C, D))∈OAEL(G, N, J)且X=Z、Y=W，则称A→C，B→D分别是一个规则。

例11：由图 7、图 8可以看出，因为(($ \mathit{\emptyset} $, 1), (gh, $ \mathit{\emptyset} $))∈OAEL(G, N, J)，(($ \mathit{\emptyset} $, 1), (abde, $ \mathit{\emptyset} $))∈OAEL(G, M, I)，根据定义19，可得规则abde→gh, $ \mathit{\emptyset} $→$ \mathit{\emptyset} $(舍去)。

以下给出基于对象/属性导出合并三支概念格的规则提取算法。

算法1基于合并三支概念格的规则提取算法

输入：决策形式背景(G, M, I, N, J)；

输出：决策规则集合C；

1) C=$ \mathit{\emptyset} $；

2) 构建对象导出三支概念格OEL(G, M, I)和OEL(G, N, J)；

3) 构建属性导出三支概念格AEL(G, M, I)和AEL(G, N, J)；

4) 合并OEL(G, M, I)和AEL(G, M, I)，构建对象/属性导出合并三支概念格OAEL(G, M, I)；

① 对于AEL(G, M, I)中每个概念((X, Y), A))，若OEL(G, M, I)中存在对应概念(X, (A, B))或(Y, (B, A))，则生成新概念((X, Y), (A, B))；

② 由所有概念((X, Y), (A, B))生成对象/属性导出合并三支概念格OAEL(G, M, I)；

5) 合并OEL(G, N, J)和AEL(G, N, J)，构建对象/属性导出合并三支概念格OAEL(G, N, J)：

① 对于AEL(G, N, J)中每个概念((X, Y), A))，若OEL(G, N, J)中存在对应概念(X, (A, B))或(Y, (B, A))，则生成新概念((X, Y), (A, B))；

② 由所有概念((X, Y), (A, B))生成对象/属性导出合并三支概念格OAEL(G, N, J)；

6) 对于OAEL(G, N, J)中每个概念((X, Y), (C, D))，重复下列操作：

若OAEL(G, M, I)中存在对应概念((X, Y), (A, B))，则C = C$ \cup ${A→C，B→D}；

7) 舍去C中所有前提或结论为 ϕ的规则，输出C。

该算法综合利用了对象导出三支概念格所包含的对象信息和属性导出三支概念格所包含的属性信息，这是因为OE概念(X, (A, B))刻画了对象子集X共同具有的属性子集A和共同不具有的属性子集B，而AE概念((X, Y), A)刻画了共同具有属性子集A的对象子集X 和共同不具有属性子集A的对象子集Y，因此相对于单纯的对象导出三支概念格或属性导出三支概念格，所得的对象/属性导出合并三支概念格同时包含了对象和属性信息，进而也使得所生成的规则在冗余性方面得到一定程度的降低。

另外，该算法的实现效率主要取决于对象导出三支概念格和属性导出三支概念格中的三支概念构建算法。关于三支概念的构建，文献[19]通过对形式背景及其补背景的变换和并置，提出一种基于二支算子的三支概念构建算法。文献[20]针对三支概念分析理论中三支概念数量庞大、构建耗时的问题，提出一种三支概念的并行构建算法。考虑到本文示例中的形式背景比较简单，因此借鉴的是一般形式概念的构建方法，在后续研究中将结合具体的应用，尝试采用上述两类新的三支概念构建算法。

例12：应用上述算法，由图 7、图 8的对象/属性导出合并三支概念格OAEL(G, M, I)和OAEL(G, N, J)所得的生成规则集合如下：

d→g；ab→h；f→k；def→gk；abde→gh；abcf→hk

比较前面的属性导出三支概念格下的生成规则集合：

d→g；de→g；ab→h；abe→h；abc→h；abcf→h；abcef→h；f→k；def→gk；abde→gh；

abcf→hk；abcef→hk

以及对象导出三支概念格下的生成规则集合：

d→g；de→g；ab→h；abc→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

可以看出，对属性导出三支概念格和对象导出三支概念格进行合并以后，进一步消除了原来的冗余规则。

在决策背景的规则提取方面，现有文献基于属性导出三支概念格进行规则提取，并取得了较好的效果。本文在其基础上进一步研究了基于对象导出三支概念格的规则提取，并与经典概念格及属性导出三支概念格下的规则提取进行了比较；同时通过对象导出三支概念格和属性导出三支概念格的合并，定义了对象/属性导出合并三支概念格，并提出了基于对象/属性导出合并三支概念格的规则提取算法。理论分析和实例结果也表明了本文工作的有效性。下一步将本文提出的决策规则提取算法应用到地理课程自动解题研究，以自动获取用于地理试题解答的隐式解题规则。