定义1^[1] 称(G, M, I)为形式背景, 其中

G={x₁, x₂, ···, x_p}

为对象集, 每个x_i(i≤ p)称为一个对象,

M={a₁, a₂, ···, a_q}

为属性集, 每个a_j(j≤ q)称为一个属性, I为G和M之间的二元关系, I⊆G× M.若(x, a)∈ I, 则表示对象x具有属性a, 记为xIa.

在形式背景(G, M, I)中, 对于任意对象子集X⊆G和属性子集B⊆M, Wille^[1]定义一对导出算子如下:

${{X}^{* }}=\left\{ a\in M\left| \forall x\in X \right., xIa \right\}$

${{B}^{* }}=\left\{ x\in G\left| \forall a\in B \right., xIa \right\}$

其中, X^* 表示X中所有对象共同具有的属性集合, B^* 表示共同具有B中所有属性的对象集合.若二元组(X, B)满足X^* =B且X=B^* , 则称(X, B)为形式概念, 简称概念, 其中X称为概念的外延, B称为概念的内涵, 使用L(G, M, I)表示形式背景(G, M, I)的全体概念.

性质1^[2] 设(G, M, I)为形式背景, ∀ X⊆G, X₁⊆G, X₂⊆G且∀ B⊆M, B₁⊆M, B₂⊆M, 如下性质成立:

1)X₁⊆X₂⇒ X2*⊆ X1*, B₁⊆B₂⇒ B2*⊆ B1*;

2)X⊆X^{* *} , B⊆B^{* *} ;

3)X^* =X^{* * *} , B=B^{* * *} ;

4)X⊆B^* ⇔ B⊆X^* ;

5)(X₁∪ X₂)^* = X1*∩ X2*, (B₁∪ B₂)^* = B1*∩ B2*;

6)(X₁∩ X₂)^* ⊇ X1*∪ X2*, (B₁∩ B₂)^* ⊇ B1*∪ B2*.

定义2^[8] 称(K₁, K₂, K₃, Y)为一个三元背景, 其中:

K₁={g₁, g₂, ···, g_p}

为对象集, 每个g_i(i≤ p)称为一个对象;

K₂={m₁, m₂, ···, m_q}

为属性集, 每个m_j(j≤ q)称为一个属性;

K₃={b₁, b₂, ···, b_r}

为条件集, 每个b_k(k≤ r)称为一个条件; Y为K₁、K₂和K₃之间的三元关系,

Y⊆K₁× K₂× K₃.

若(g, m, b)∈ Y, 则表示对象g在条件b下具有属性m.

定义3^[16] 设K=(K₁, K₂, K₃, Y)为三元背景, 称

$\begin{array}{l} K^{(1)}=\left(K_{1}, K_{2} \times K_{3}, Y^{(1)}\right), \\ K^{(2)}=\left(K_{2}, K_{1} \times K_{3}, Y^{(2)}\right), \\ K^{(3)}=\left(K_{3}, K_{1} \times K_{2}, Y^{(3)}\right) \end{array}$

为K诱导的三个形式背景.K诱导的形式背景K⁽ⁱ⁾(i∈ {1, 2, 3})上的* 算子记为* Y⁽ⁱ⁾.

定义4^[8] 设K=(K₁, K₂, K₃, Y)为三元背景, {i, j, k}={1, 2, 3}且j< k.对于∀ X⊆K_i, Z⊆K_j× K_k.定义(i)-诱导算子如下:

${{X}^{\left( i \right)}}=\left\{ ({{a}_{j}}, {{a}_{k}})\in {{K}_{j}}\times {{K}_{k}}\left| \left( {{a}_{i}}, {{a}_{j}}, {{a}_{k}} \right)\in Y \right., \forall {{a}_{i}}\in X \right\}$,

${{Z}^{\left( i \right)}}=\left\{ {{a}_{i}}\in {{K}_{i}}\left| \left( {{a}_{i}}, {{a}_{j}}, {{a}_{k}} \right)\in Y \right., \forall ({{a}_{j}}, {{a}_{k}})\in Z \right\}$.

实际上, (i)-诱导算子相当于形式背景

${{K}^{\left( 1 \right)}}=\left( {{K}_{1}}, {{K}_{2}}\times {{K}_{3}}, {{Y}^{\left( 1 \right)}} \right)$,

${{K}^{\left( 2 \right)}}=\left( {{K}_{2}}, {{K}_{1}}\times {{K}_{3}}, {{Y}^{\left( 2 \right)}} \right)$,

${{K}^{\left( 3 \right)}}=\left( {{K}_{3}}, {{K}_{1}}\times {{K}_{2}}, {{Y}^{\left( 3 \right)}} \right)$

上的* 算子.

定义5^[8] 设K=(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}}^{\left( i, j, {{X}_{k}} \right)}=\left\{ {{a}_{j}}\in {{K}_{j}}\left| \left( {{a}_{i}}, {{a}_{j}}, {{a}_{k}} \right)\in Y, \forall \left( {{a}_{i}}, {{a}_{k}} \right)\in {{X}_{i}}\times {{X}_{k}} \right. \right\}$,

${{X}_{j}}^{\left( i, j, {{X}_{k}} \right)}=\left\{ {{a}_{i}}\in {{K}_{i}}\left| \left( {{a}_{i}}, {{a}_{j}}, {{a}_{k}} \right)\in Y, \forall \left( {{a}_{j}}, {{a}_{k}} \right)\in {{X}_{j}}\times {{X}_{k}} \right. \right\}$.

定义6^[8] 设K=(K₁, K₂, K₃, Y)为三元背景, A_i⊆K_i, i=1, 2, 3.若满足

A_i=(A_j× A_k)⁽ⁱ⁾,

其中{i, j, k}={1, 2, 3}且j< k, 则称(A₁, A₂, A₃)为三元背景K的三元概念, 并称A₁为外延, A₂为内涵, A₃为方式.记K中所有三元概念构成的集合为T(K).

引理1^[8] 设K=(K₁, K₂, K₃, Y)为三元背景, X_i⊆K_i, X_k⊆K_k, {i, j, k}={1, 2, 3}.记

${{A}_{j}}={{X}_{i}}^{\left( i, j, {{X}_{k}} \right)}$,

${{A}_{i}}={{A}_{j}}^{\left( i, j, {{X}_{k}} \right)}$,

${{A}_{k}}={{({{A}_{i}}\times {{A}_{j}})}^{\left( k \right)}}, \left( i< j \right) $

则(A₁, A₂, A₃)为三元概念.

为了简化三元概念的书写, 本文将一般集合写成其元素的序列.例如, 对象集{2, 4}简写为24, 属性集{c, d}简写为cd, 条件集{A, B, C}简写为ABC.

例1 表1是一个三元背景K=(K₁, K₂, K₃, Y), 其中, 对象集K₁={1, 2, 3, 4}, 属性集K₂={a, b, c, d, e}, 条件集K₃={A, B, C}.

表1

Table 1

表1(Table 1)

表1 三元背景K=(K1, K2, K3, Y) Table 1 Triadic context K=(K1, K2, K3, Y) A B C a b c d e a b c d e a b c d e 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 2 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 3 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 4 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0

表1 三元背景K=(K1, K2, K3, Y) Table 1 Triadic context K=(K1, K2, K3, Y)

由定义6可求得该三元背景的所有三元概念如下:

$\begin{array}{l} (124, a, A), (1, a, A B C), (1, a e, A B), \\ (1, a b e, A), (24, a c d, A), (24, c d, A B C), \\ (24, b c d, C), (13, b, A), (13, a e, B), \\ (3, b, A B), (3, e, B C), (3, a b e, B), \\ (3, c d e, C), (234, c d, C), \left(K_{1}, K_{2}, \varnothing\right), \\ \left(K_{1}, \varnothing, K_{3}\right), \left(\varnothing, K_{2}, K_{3}\right) . \end{array}$

定义9 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽¹⁾=(K₁, K₂× K₃, Y⁽¹⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽¹⁾), BK3X为(X, B)中B按条件分类的属性集的集合, 称

$EC\left( X \right)=\left\{ \underset{E\in A}{\mathop{\bigcap }}\, E\left| A\subseteq B_{{{K}_{3}}}^{X} \right., A\ne \varnothing \right\}$

为X的外延待选集.

由于(X, B)为K⁽¹⁾上的形式概念, 故也可记

$B_{{{K}_{3}}}^{X}=\left\{ {{\left( X\times k \right)}^{\left( 2 \right)}}, k\in {{K}_{3}} \right\}$,

类似地, 也可记X的外延待选集

$EC\left( X \right)=\left\{ \underset{i\subseteq I}{\mathop{\bigcap }}\, {{\left( X\times i \right)}^{\left( 2 \right)}}, I\subseteq {{K}_{3}}, I\ne \varnothing \right\}$.

设K为三元背景, 记T(K)中所有三元概念外延的集合为

$E\left( K \right)=\left\{ \left. {{A}_{1}} \right|\left( {{A}_{1}}, \right.\left. {{A}_{2}}, {{A}_{3}} \right)\in T\left( K \right) \right\}$,

T(K)中所有三元概念内涵的集合为

$I\left( K \right)=\left\{ \left. {{A}_{2}} \right| \right.\left( {{A}_{1}}, {{A}_{2}}, {{A}_{3}} \right)$$\left. \in T\left( K \right) \right\}$,

T(K)中所有三元概念方式的集合为

$M\left( K \right)=\left\{ \left. {{A}_{3}} \right|\left( {{A}_{1}}, {{A}_{2}}, {{A}_{3}} \right) \right.\left. \in T\left( K \right) \right\}$.

K⁽ⁱ⁾为K诱导的形式背景, 其中i=1, 2, 3.记K⁽ⁱ⁾的所有形式概念外延的集合为

$E\left( {{K}^{\left( i \right)}} \right)=\left\{ \left. X \right|\left( X, B \right)\in L\left( {{K}^{\left( i \right)}} \right) \right\}$.

例4 (续例3) 例3中的净化三元背景

K'=(K'₁, K'₂, K'₃, Y),

其诱导的形式背景K'⁽¹⁾如表6所示.

表6

Table 6

表6(Table 6)

表6 K'诱导的形式背景K'(1)=(K'1, K'2× K'3, Y'(1)) Table 6 Formal context K'(1)=(K'1, K'2× K'3, Y'(1)) induced by K' 1 2 3 1 2 3 (a, A) 1 1 0 (c, B) 0 1 0 (b, A) 1 0 1 (e, B) 1 0 1 (c, A) 0 1 0 (a, C) 1 0 0 (e, A) 1 0 0 (b, C) 0 1 0 (a, B) 1 0 1 (c, C) 0 1 1 (b, B) 0 0 1 (e, C) 0 0 1

表6 K'诱导的形式背景K'(1)=(K'1, K'2× K'3, Y'(1)) Table 6 Formal context K'(1)=(K'1, K'2× K'3, Y'(1)) induced by K'

K'⁽¹⁾的形式概念如下:

$\begin{array}{l} (12, (A, a)), (23, (C, c)), \\ (1, (A, a)(A, b)(A, e)(B, a)(B, e)(C, a)), \\ (3, (A, b)(B, a)(B, b)(B, e)(C, c)(C, e)), \\ (13, (A, b)(B, a)(B, e)), \\ (2, (A, a)(A, c)(B, c)(C, b)(C, c)), \\ \left(K_{1}^{\prime}, \varnothing\right), \left(\varnothing, K_{2}^{\prime} \times K_{3}^{\prime}\right) . \end{array}$

由定义9知外延2对应的外延待选集为{ac, c, bc}, 外延3对应的外延待选集为{Ø , b, abe, ce, e}.

定理1 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽¹⁾=(K₁, K₂× K₃, Y⁽¹⁾)

为K诱导的形式背景, 则有

E(K)⊆E(K⁽¹⁾).

证明 取(A₁, A₂, A₃)∈ T(K), 则有

A₁=(A₂× A₃)⁽¹⁾,

其在形式背景K⁽¹⁾上等价于

A₁=(A₂× A₃)^* ,

故由性质1知,

A₂× A₃⊆ A1*.

首先, 若

A₂× A₃= A1*,

则显然有

(A₁, (A₂× A₃))∈ L(K⁽¹⁾).

其次, 若

A₂× A₃⊂ A1*,

则存在

Q∈ K₂× K₃\A₂× A₃,

使得

A1*=(A₂× A₃)∪ Q.

故若

A₁=((A₂× A₃)∪ Q)^* ,

则

(A₁, (A₂× A₃)∪ Q)

为形式概念.

下证

A₁=((A₂× A₃)∪ Q)^* .

假设

A₁≠ ((A₂× A₃)∪ Q)^* ,

即

A₁≠ (A₂× A₃)^* ∩ Q^* ,

又因为

A₁=(A₂× A₃)^* ,

故有Q^* ⊂A₁.又由

A1*=(A₂× A₃)∪ Q

知Q⊆ A1*, 且

Q⊆ A1*⇔ A₁⊆Q^* .

而A₁⊆Q^* 与Q^* ⊂A₁矛盾, 因此假设不成立, 故一定有

A₁=((A₂× A₃)∪ Q)^* .

综上所述, A₁一定为形式背景K⁽¹⁾的某个形式概念的外延, 即E(K)⊆E(K⁽¹⁾).

定理1表明三元背景K诱导的形式背景K⁽¹⁾的所有形式概念的外延集包含三元背景K的所有三元概念的外延集, 从而提供利用形式背景K⁽¹⁾的形式概念构造三元概念的基础.

定理2 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽¹⁾ =(K₁, K₂× K₃, Y⁽¹⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽¹⁾).若

(A× (X× A)⁽³⁾)⁽¹⁾=X,

则

(X, A, (X× A)⁽³⁾)∈ T(K),

其中A∈ EC(X).

证明 因为

(A× (X× A)⁽³⁾)⁽¹⁾=X,

故只需证

(X× (X× A)⁽³⁾)⁽²⁾=A.

令Z=(X× A)⁽³⁾, 即证(X× Z)⁽²⁾=A.假设存在

u∈ (X× Z)⁽²⁾\A,

即u∈ (X× Z)⁽²⁾且u∉A.又因为A∈ EC(X), 故存在I⊆K₃, 使得

A= ∩i∈I(X× i)⁽²⁾,

因此有

u∉ ∩i∈I(X× i)⁽²⁾,

即u∉(X× I)⁽²⁾.若I⊆Z, 则有

(X× Z)⁽²⁾⊆(X× I)⁽²⁾,

又因为u∉(X× I)⁽²⁾, 故u∉(X× Z)⁽²⁾, 与

u∈ (X× Z)⁽²⁾

矛盾.因此不存在

u∈ (X× Z)⁽²⁾\A,

也即

(X× Z)⁽²⁾=A.

下证I⊆Z.假设Z⊂I, 即存在k∈ I\Z, 又因为

A= ∩i∈I(X× i)⁽²⁾,

有A∈ (X× k)⁽²⁾, 故对于∀ x∈ X, a∈ A, 有(x, a, k)∈ Y, 因此有

(X× A)⁽³⁾=Z∪ {k},

与

(X× A)⁽³⁾=Z

矛盾, 故I⊆Z.

综上所述, (X, A, (X× A)⁽³⁾)为三元概念.

定理2给出基于外延待选集的三元概念构造方法, 即利用形式背景K⁽¹⁾的形式概念外延和其外延待选集相结合构造三元概念, 同时说明该构造方法的可行性.

定理3 设K=(K₁, K₂, K₃, Y)为三元背景,

$\begin{array}{l} \left(A_{1}, A_{2}, A_{3}\right) \in T(K) \\ K^{(1)}=\left(K_{1}, K_{2} \times K_{3}, Y^{(1)}\right) \end{array}$

为K诱导的形式背景, 则存在(X, B)∈ L(K⁽¹⁾)使得

(X, A, (X× A)⁽³⁾)=(A₁, A₂, A₃),

其中A∈ EC(X).

证明 由定理1知, 对于三元概念(A₁, A₂, A₃)一定存在一个形式概念(X, B)与其外延相等, 取X=A₁.因为(A₁, A₂, A₃)∈ T(K), 有

(A₁× A₃)⁽²⁾=A₂.

在三元背景K诱导的形式背景K⁽²⁾上取

A₁× A₃∈ K₁× K₃,

有

${{\left( {{A}_{1}}\times {{A}_{3}} \right)}^{* }}=\bigcap\limits_{i\subseteq {{A}_{3}}}{{{\left( {{A}_{1}}\times i \right)}^{\left( 2 \right)}}}={{\bigcap\limits_{i\subseteq {{A}_{3}}}{\left( X\times i \right)}}^{\left( 2 \right)}}\in EC\left( X \right)$

又因为

A₂=(A₁× A₃)⁽²⁾,

故A₂∈ EC(X), 因此一定存在A∈ EC(X), 使得A=A₂.

综上所述, 一定存在(X, B)∈ L(K⁽¹⁾)使得

(X, A, (X× A)⁽³⁾)=(A₁, A₂, A₃).

定理3表明, 任何一个三元概念都可通过某个形式概念依据定理2的构造方法得到, 即证明该构造方法的完备性.

定理2和定理3两者结合就可确保基于外延待选集的三元概念构造方法能获取三元概念, 且能获取所有的三元概念.

基于外延待选集的三元概念构造方法是将三元背景K诱导为形式背景K⁽¹⁾, 从K⁽¹⁾的形式概念出发构造三元概念.由于K₁、K₂和K₃在三元背景上地位的平等性, 故将上述方法推广到三元背景诱导的另外两个形式背景K⁽²⁾和K⁽³⁾上.

首先在形式背景K⁽²⁾上定义内涵待选集, 并在形式背景K⁽²⁾上给出基于内涵待选集的三元概念构造方法.由于K₁和K₂地位的平等性, 后文定理4、定理5和定理6的证明与定理1、定理2和定理3的证明类似, 故省略.

类似地, 在三元背景诱导的形式背景K⁽³⁾上也可给出方式待选集的定义和基于方式待选集的三元概念构造方法.由于K₁和K₃地位的平等性, 故后文定理7、定理8和定理9也不再进行证明.

定义10 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽²⁾=(K₂, K₁× K₃, Y⁽²⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽²⁾), BK1X为(X, B)中B按对象分类的条件集的集合, 称

$IC\left( X \right)=\left\{ \underset{I\in C}{\mathop{\bigcap }}\, I\left| C\subseteq B_{{{K}_{1}}}^{X} \right., C\ne \varnothing \right\}$

为X的内涵待选集.

定理4 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽²⁾= (K₂, K₁× K₃, Y⁽²⁾)

为K诱导的形式背景, 则有

I(K)⊆E(K⁽²⁾).

定理5 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽²⁾=(K₂, K₁× K₃, Y⁽²⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽²⁾).若

((X× A)⁽¹⁾× A)⁽²⁾=X,

则

((X× A)⁽¹⁾, X, A)∈ T(K),

其中A∈ IC(X).

定理6 设K=(K₁, K₂, K₃, Y)为三元背景,

$\begin{array}{l} \left(A_{1}, A_{2}, A_{3}\right) \in T(K) \\ K^{(2)}=\left(K_{2}, K_{1} \times K_{3}, Y^{(2)}\right) \end{array}$

为K诱导的形式背景, 则存在(X, B)∈ L(K⁽²⁾)使得

((X× A)⁽¹⁾, X, A)=(A₁, A₂, A₃),

其中A∈ IC(X).

定理4表明, 形式背景K⁽²⁾的形式概念的外延集包含K的三元概念的内涵集.定理5给出基于内涵待选集的三元概念构造方法.定理6在此基础上确保基于内涵待选集的三元概念构造方法的完备性.

定义11 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽³⁾=(K₃, K₁× K₂, Y⁽³⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽³⁾), BK2X为(X, B)中B按属性分类的对象集的集合, 称

$MC\left( X \right)=\left\{ \underset{M\in O}{\mathop{\bigcap }}\, M\left| O\subseteq B_{{{K}_{2}}}^{X} \right., O\ne \varnothing \right\}$

为X的方式待选集.

定理7 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽³⁾=(K₃, K₁× K₂, Y⁽³⁾)

为K诱导的形式背景, 则有

M(K)⊆E(K⁽³⁾).

定理8 设K=(K₁, K₂, K₃, Y)为三元背景,

K⁽³⁾=(K₃, K₁× K₂, Y⁽³⁾)

为K诱导的形式背景, (X, B)∈ L(K⁽³⁾).若

(A× (A× X)⁽²⁾)⁽³⁾=X,

则

(A, (A× X)⁽²⁾, X)∈ T(K),

其中A∈ MC(X).

定理9 设K=(K₁, K₂, K₃, Y)为三元背景,

$\begin{array}{l} \left(A_{1}, A_{2}, A_{3}\right) \in T(K) \\ K^{(3)}=\left(K_{3}, K_{1} \times K_{2}, Y^{(3)}\right) \end{array}$

为K诱导的形式背景, 则存在(X, B)∈ L(K⁽³⁾)使得

(A, (A× X)⁽²⁾, X)=(A₁, A₂, A₃),

其中A∈ MC(X).

定理7表明, 形式背景K⁽³⁾的形式概念的外延集包含K的三元概念的方式集.定理8给出基于方式待选集的三元概念方法.定理9在此基础上确保基于方式待选集的构造方法的完备性.

基于外延待选集的三元概念构造方法是利用三元背景K诱导的形式背景K⁽¹⁾的形式概念和其外延待选集来构造三元概念, 其速度主要取决于形式概念和外延待选集的数量.

上述三种三元概念构造方法的原理相同, 主要区别在于通过诱导得到的每个形式背景的形式概念和待选集的数量不同, 这些差异直接影响构造三元概念的速度.因此针对不同的三元背景, 可选择最合适的三元概念构造方法, 加快获取三元概念的速度.

首先分析对象个数对算法运行时间的影响.设置属性个数为10, 20, 条件个数为5, 三元背景密度为0.3, 当对象个数从10增至90时, 运行时间如图2所示.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 对象个数对算法运行时间的影响Fig.2 Impact of the number of objects on algorithm runtime

由图2可看出, 随着对象个数的增加, 运行时间也在增加, 在对象个数达到60之后, 运行时间的增加更明显.原因是此时对象对待选集数量的影响变大, 使三元概念数量的增幅变大, 导致算法的运行时间增幅变大.当属性个数从10增至20, 算法运行时间的倍数由最初的1~2倍, 慢慢增至4倍.

下面分析属性个数对算法运行时间的影响.设置对象个数为10, 20, 条件个数为5, 三元背景密度为0.3, 当属性个数从10增至90时, 运行时间如图3所示.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 属性个数对算法运行时间的影响Fig.3 Impact of the number of attributes on algorithm runtime

由图3可看出, 随着属性个数的增加, 算法的运行时间不断增加, 但慢慢趋于平缓.主要原因是对象个数和条件个数固定, 属性个数的增加不会导致待选集数量的明显增加, 使三元概念数量的增加也相对平缓, 因此算法运行时间的增加趋于平缓.当对象个数从10增至20, 算法运行时间的倍数由最初的2倍, 慢慢增至4倍.

再分析条件个数对算法运行时间的影响, 设置对象个数为10, 20, 属性个数为5, 三元背景密度为0.3, 当条件个数从10增至90, 运行时间如图4所示.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 条件个数对算法运行时间的影响Fig.4 Impact of the number of conditions on algorithm runtime

由图4可看出, 随着条件个数的增加, 算法的运行时间不断增加, 最初的时间增加较明显, 但在条件个数到达80之后趋于平缓.原因是此时条件个数增加对待选集数量的影响降低, 使三元概念数量的增加趋于平缓, 因此算法运行时间的增加趋于平缓.当对象个数从10增至20, 运行时间的倍数由最初的1~2倍, 慢慢增至4倍.

最后分析三元背景密度对算法运行时间的影响.设置对象个数为10, 属性个数为10, 条件个数为10, 三元背景密度从10%增至90%时, 运行时间如图5所示.由图可看出, 在三元背景密度小于50%时, 其对算法运行时间的影响较小, 但三元背景密度超过50%后, 算法运行时间大幅增加.主要原因是, 在低密度阶段三元背景中的三元关系较少, 使待选集的增量较少, 因此运行时间增幅较小, 但随着三元背景密度的增加, 待选集的增量也逐渐变多, 从而使运行时间大幅增加.

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 三元背景密度对算法运行时间的影响Fig.5 Impact of triadic context density on algorithm runtime

为了进一步验证本文算法的性能, 在不同的三元背景上与文献[8]算法、文献[25]算法进行对比实验.

首先考察对象个数对3种算法运行时间的影响.设置三元背景对象个数分别为100, 500, 1 000, 2 000, 属性个数为10, 条件个数为10, 三元背景密度为0.3.具体运行时间如图6(a)所示.

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 参数改变时各算法运行时间对比Fig.6 Runtime comparison of different algorithms with varying parameters

再考察属性个数对3种算法运行时间的影响.设置三元背景对象个数为10, 属性个数分别为100, 500, 1 000, 2 000, 条件个数为10, 三元背景密度为0.3.具体运行时间如图6(b)所示.

最后考察条件个数对3种算法运行时间的影响.设置三元背景对象个数为10, 属性个数为10, 条件个数分别为100, 500, 1 000, 2 000, 三元背景密度为0.3.具体运行时间如图6(c)所示.

由图6可见, 本文算法都保持最短的运行时间, 这充分说明本文算法获取三元概念的有效性.

从图6可看出, 本文算法运行时间明显低于文献[8]算法, 原因在于文献[8]算法要考虑两个幂集, 而本文算法只考虑一个幂集, 因此运行时间较短.

从图6还可看出, 在(a)、(b)中本文算法稍快于文献[25]算法, 但在(c)中文献[25]算法的运行时间大约是本文算法的3~5倍, 并且随着条件个数的增加, 文献[25]算法与本文算法运行时间的差距越来越大.主要原因在于文献[25]算法需要计算每个单条件下的三元概念, 并重复遍历, 而本文算法是考虑条件集的整体, 因此当条件个数不断增加时, 本文算法依然保持较低的运行时间.

综合分析, 本文算法的性能最佳.