为了方便描述, 下文将原形式背景记为(G, M^t, R^t), 其属性直观图记为 (HMt, ⩽), 对应的关系矩阵记为 Dt=(dijt)p×p.将删除属性后的形式背景记为(G, M^t-1, R^t-1), 其属性直观图记为 (HMt-1, ⩽), 对应的关系矩阵记为

Dt-1=(dijt-1)(p-1)×(p-1).

记属性m在 (HMt, ⩽)中的上近邻为U Nmt, 下近邻为L Nmt, R≺t为 (HMt, ⩽)中的上(下)近邻关系, R≺t-1为 (HMt-1, ⩽)中的上(下)近邻关系.

下面先给出从原形式背景的属性集M^t中删除属性m_k之后D^t和D^t-1之间的关系.

定理2 设 (HMt, ⩽)为(G, M^t, R^t)的属性直观图, Dt=(dijt)p×p为 (HMt, ⩽)的关系矩阵, m_k为删除属性,

Dt-1=(dijt-1)(p-1)×(p-1)

为 (HMt-1, ⩽)的关系矩阵.∀ m_i∈ M^t-{m_k}, 若 dikt=1, 且存在m_j∈ M^t-{m_k}有 dkjt=1, 而且满足

$U N_{m_{i}}^{t} \cap L N_{m_{j}}^{t}=\left\{m_{k}\right\}, $

则 dijt-1=1.

证明 ∀ m_i∈ M^t-{m_k}, 当 dikt=1且存在

m_j∈ M^t-{m_k}

有 dkjt=1时, 由定义6知在( HMt, ⩽)中有

< m_i, m_k> ∈ R≺t, < m_k, m_j> ∈ R≺t,

继而有

m'_i⊂m'_k⊂m'_j.

又由于

$U N_{m_{i}}^{t} \cap L N_{m_{j}}^{t}=\left\{m_{k}\right\}, $,

因此可知一定不存在

m∈ M^t-{m_k},

使得

m'_i⊂m'⊂m'_j,

所以当删除属性m_k后, 有

(m'_i, m_i)≺(m'_j, m_j),

于是根据定义6可得 dijt-1=1.

定理2揭示在形式背景中删除一个属性时, 属性集中其余属性上近邻的变化规律.基于定理2, 当删除属性m_k时, 记

Dt→t-1=(dijt→t-1)p×p

为由D^t到D^t-1的过渡矩阵, 其中

dijt→t-1=1, mi、mj满足定理2dijt, 其它

于是, 在过渡矩阵D^{t→ t-1}的基础上, 删除D^{t→ t-1}中的第k行与第k列便可得到删除属性m_k后的关系矩阵:

Dt-1=(dijt-1)(p-1)×(p-1).

注1 由于在从D^t得到D^t-1的过程中删除第k行和第k列, 此时, 对∀ m_i∈ M^t-1, 若i≥ k, 则D^t-1中的第i行(第i列)对应的属性与D^t的第i+1行(第i+1列)对应的属性一致.

下面举例解释当在属性集M^t中删除属性m_k时属性直观图的更新方法.

例3 当在例1所示的形式背景中删除属性m₂时, 获取( HMt-1, ⩽)的过程描述如下.

首先, 根据定理2对D^t中元素进行更新, 得到过渡矩阵

${{D}^{t}}^{\to t-1}={{(d_{ij}^{t\to t-1})}_{p\times p}}.$

因在D^t中只有 d42t=1, 且

d21t=1, d28t=1,

以及由

$UN_{{{m}_{4}}}^{t}=\{{{m}_{2}}, {{m}_{5}}\}, $

$LN_{{{m}_{1}}}^{t}=\{{{m}_{2}}, {{m}_{5}}\}, LN_{{{m}_{8}}}^{t}=\{{{m}_{2}}\}$

可得

$UN_{{{m}_{4}}}^{t}\cap LN_{{{m}_{1}}}^{t}=\{{{m}_{2}}, {{m}_{5}}\}, $

$UN_{{{m}_{4}}}^{t}\cap LN_{{{m}_{8}}}^{t}=\{{{m}_{2}}\}.$

故根据定理2可知, d48t→t-1=1.于是可得过渡矩阵:

Dt→t-1=00000000100000010000101001001000/110000100000000000000010000000000.

其次, 在D^{t→ t-1}中删除第2行和第2列, 可得

Dt-1=0000000000101000010011000100000000000001000000000.

最后, 根据定义6由D^t-1和 (HMt, ⩽)得到属性直观图 (HMt-1, ⩽)如图2所示.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 属性直观图 (HMt-1, ⩽)Fig.2 Property pictorial diagram (HMt-1, ⩽)

本文约定新增属性m_p+1∉M^t且不存在m_j∈ M^t有

m'_p+1=m'_j,

并将新增属性后的形式背景记为(G, M^t+1, R^t+1), 对应的属性直观图记为( HMt+1, ⩽), 关系矩阵记为

Dt+1=(dijt+1)(p+1)×(p+1),

上 (下)近邻关系记为 R≺t+1.

对于新增属性m_p+1, 类似于删除属性的情况, 根据D^t和D^t+1的特点, 先构造由D^t到D^t+1的过渡矩阵D^{t→ t+1}, 再由过渡矩阵D^{t→ t+1}得到D^t+1.下面给出D^t与D^t+1的前p行、前p列元素之间的关系.

引理1 设 (HMt, ⩽)为(G, M^t, R^t)的属性直观图, D^t= (dijt)p×p为 (HMt, ⩽)的关系矩阵, ${{m}_{p+1}}$为新增属性, D^t+1为 (HMt+1, ⩽)的关系矩阵.∀ m_l∈ M^t, 有如下结论成立:

1)若 dl(p+1)t+1=0, 则∀ j∈ {1, 2, …, p}, 有 dljt+1=dljt;

2)若 dl(p+1)t+1=1, 且对于m_s∈ M^t, 有 d(p+1)st+1=0, 则 dlst+1=dlst.

证明 先证1).若 dl(p+1)t+1=0, 则由定义6知

< m_l, m_p+1> ∉ R≺t+1,

进而可得

UNmlt+1=UNmlt,

即对∀ j∈ {1, 2, …, p}有 dljt+1=dljt.

再证2).由定义6知当 dl(p+1)t+1=1时

< m_l, m_p+1> ∈ R≺t+1,

当 d(p+1)st+1=0时

< m_p+1, m_s> ∉ R≺t+1,

此时分别针对 dlst=0和 dlst=1两种情况进行证明.

一方面, 当 dlst=0时, 由定义6得

< m_l, m_s> ∉ R≺t,

进而由定义5知m'_l⊄m'_s或存在m_v∈ M^t有

m'_l⊆m'_v⊆m'_s,

此时, 当增加属性 mp+1之后, m_l与m_s的上(下)近邻关系仍然保持不变, 即

< m_l, m_s> ∉ R≺t+1,

故有 dlst+1=0, 即 dlst+1=dlst.

另一方面, 由 dlst=1可知

< m_l, m_s> ∈ R≺t,

即m'_l⊆m'_s且不存在m_v∈ M^t有

m'_l⊆m'_v⊆m'_s.

当增加属性 mp+1之后, 假设 dlst+1=0, 则有m'_l⊄m'_s或存在m_w∈ M^t+1有

m'_l⊆m'_w⊆m'_s.

若m'_l⊄m'_s, 则与 dlst=1矛盾; 若存在m_w∈ M^t+1有

m'_l⊆m'_w⊆m'_s,

则根据 dlst=1可知m_w∉M^t, 此时m_w=m_p+1, 即

m'_l⊆m'_p+1⊆m'_s.

进一步, 由

< m_l, m_s> ∈ R≺t

可知, 不存在m∈ M^t有

m'_p+1⊆m'⊆m'_s,

故 d(p+1)st+1=1, 这与已知 d(p+1)st+1=0矛盾, 因此假设不成立, 即 dlst+1=1.于是可证 dlst+1= dlst.

引理1揭示在形式背景中增加一个属性时, 原属性集上属性上近邻的变化规律.基于引理1及关系矩阵的性质, 在新增属性m_p+1后, 记D^t到D^t+1的过渡矩阵为

Dt→t+1=(dijt→t+1)(p+1)×(p+1),

其中

dijt→t+1=dijt, i≤p, j≤p, 1, m'i⊆m'j, i=p+1或j=p+10, 其它

由过渡矩阵D^{t→ t+1}获取D^t+1的方法如定理3所示.

定理3 设 (HMt, ⩽)为(G, M^t, R^t)的属性直观图, Dt=(dijt)p×p为 (HMt, ⩽)的关系矩阵, mp+1为新增属性, D^{t→ t+1}为过渡矩阵.∀ m_l∈ M^t, 则有如下结论成立.

1)若 d(p+1)lt→t+1=1且存在m_s∈ M^t有 dlst→t+1=1, 则 d(p+1)st+1=0.

2)若存在m_s∈ M^t有 dlst→t+1=1且 ds(p+1)t→t+1=1, 则 dl(p+1)t+1=0.

3)若 dl(p+1)t→t+1=1且存在m_s∈ M^t有 d(p+1)st→t+1=1, 则 dlst+1=0.

证明 先证1).由 d(p+1)lt→t+1=1可得m'_p+1⊆m'_l.此时, 若存在m_s∈ M^t有 dlst→t+1=1, 则表明 dlst=1, 即m'_l⊆m'_s.于是, 由定义5和定义6可得在 (HMt+1, ⩽)中

< m_p+1, m_s> ∉ R≺t+1,

故 d(p+1)st+1=0.

2)和 3) 均可用类似于1)的证明过程得证.

例4 当在例1所示的形式背景中增加属性m₉(m'₉={3, 4})时, 获取( HMt+1, ⩽)的过程如下.

首先, 在D^t的基础上按照下述方法添加新的一行和新的一列元素得到D^{t→ t+1}.因为

m'₉⊆m'₁, m'₉⊆m'₅, m'₉⊆m'₆

且

m'₉⊈m'_i , i∈ {2, 3, 4, 7, 8},

故

d91t→t+1=d95t→t+1=d96t→t+1=1,

d92t→t+1=d93t→t+1=d94t→t+1=d97t→t+1=d98t→t+1=0.

又因m'₄⊆m'₉且m'_i⊈m'₉ , i∈ {1, 2, 3, 5, 6, 7, 8}, 故第9列中除了 d49t→t+1=1以外其余元素均为0.于是可得过渡矩阵:

Dt→t+1=000000000100000010000010100010010001100001000000000000000001000000000000100011000.

其次, 利用定理3对过渡矩阵D^{t→ t+1}中的元素进行更新.因

d95t→t+1=1, d51t→t+1=1, d56t→t+1=1,

故可得

d91t+1=d96t+1=0.

又因 d49t→t+1=1且

d91t→t+1=d95t→t+1=d96t→t+1=1,

故

d41t+1=d45t+1=d46t+1=0.

综上可得

Dt+1=00000000010000001000001010001001/000011000010000000000000000010000000000001/000011/0000.

最后, 根据定义6由关系矩阵D^t+1和( HMt, ⩽)可得属性直观图( HMt+1, ⩽)如图3所示.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 属性直观图 (HMt+1, ⩽)Fig.3 Property pictorial diagram (HMt+1, ⩽)

本节基于D^t-1的更新规律, 研究属性特征的更新规律, 进而得到属性约简的更新方法.

对于属性m_k, 若

$\sum_{i=1}^{p} d_{i k}^{t}=0$,

意味着m_k不是其它任何属性的上近邻, 此时删除属性m_k, 对其它属性而言定理4中的判定条件不发生改变, 那么其它属性的属性特征就不发生变化.基于此特点, 当删除属性m_k时, 可从D^t中第k列的值出发考虑其余属性的属性特征变化规律.

定理5 设 (HMt, ⩽)为(G, M^t, R^t)的属性直观图, Dt=(dijt)p×p为 (HMt, ⩽)的关系矩阵, C^t与I^t分别为(G, M^t, R^t)的核心和绝对不必要属性集, m_k为删除属性.∀ m_i∈ M^t-{m_k}, 有如下结论成立.

1)当 dikt=0时, 若m_i∈ C^t, 则m_i∈ C^t-1; 若m_i∈ I^t, 则m_i∈ I^t-1.

2)当 dikt=1时, 若m_i∈ C^t, 则m_i∈ C^t-1.

证明 先证1).因为 dikt=0, 故由定理2可知

$ \sum_{j=1}^{p-1} d_{i j}^{t-1}=\sum_{j=1}^{p} d_{i j}^{t} $

且

UNmit-1=UNmit,

进而由定理4可得m_i的属性特征保持不变, 即当m_i∈ C^t时, m_i∈ C^t-1; 当m_i∈ I^t时, m_i∈ I^t-1.

再证2).若 dikt=1且m_i∈ C^t, 则由定理4可知

$\sum_{j=1}^{p} d_{i j}^{t}=1 $

或

$\sum_{j=1}^{p} d_{i j}^{t}> 1 $

且

$\bigcap_{m_{s} \in U N_{m_{i}}^{t}} m_{s}^{\prime}-m_{i}^{\prime} \neq \emptyset $

当

$\sum_{j=1}^{p} d_{i j}^{t}=1 $

时, 则由定理2可知

$\overset{p-1}{\mathop{\underset{j=1}{\mathop \sum }\, }}\, d_{ij}^{t-1}=1$

或

$\overset{p-1}{\mathop{\underset{j=1}{\mathop \sum }\, }}\, d_{ij}^{t-1}=0, $

即

UNmit-1=1

或

UNmit-1=0,

因此由定理4可得m_i∈ C^t-1.当

$\overset{p}{\mathop{\underset{j=1}{\mathop \sum }\, }}\, d_{ij}^{t}> 1$

且

$\bigcap_{m_{s} \in U N_{m_{i}}^{t}} m_{s}^{\prime}-m_{i}^{\prime} \neq \emptyset$

时, 此时假设

$UN_{{{m}_{i}}}^{t}=\{{{m}_{k}}, {{m}_{r}}\}, $

则有

m'_i⊆m'_k, m'_i⊆m'_r

且

m'_k∩ m'_r-m'_i≠ Ø ,

于是可知

m'_i⊂m'_k∩ m'_r.

另外, 当删除属性m_k时, 由定理2可知

$UN_{{{m}_{i}}}^{t-1}\subseteq UN_{{{m}_{k}}}^{t}\cup \{{{m}_{r}}\}, $

于是

$\bigcap_{m_{l} \in U N_{m_{k}}^{t} \cup\left\{m_{r}\right\}} m_{l}^{\prime} \subseteq \bigcap_{m_{q} \in U N_{m_{i}}^{t-1}} m_{q}^{\prime}$

又因为

$m_{k}^{\prime} \subseteq \bigcap_{m_{i} \in U N_{m_{k}}^{t}} m_{i}^{\prime}$,

故有

$m_{i}^{\prime} \subset m_{k}^{\prime} \cap m_{r}^{\prime} \subseteq \bigcap_{m_{l} \in U N_{m_{k}}^{t} \cup\left\{m_{r}\right\}} m_{l}^{\prime} \subseteq \bigcap_{m_{q} \in U N_{m_{i}}^{t-1}} m_{q}^{\prime}$.

因此, 依据定理4可得m_i∈ C^t-1.

定理5说明在删除属性m_k之后, 原形式背景的剩余属性中核心属性仍是新形式背景的核心属性.因此, 基于定理5, 要获取新形式背景的属性约简, 仅需要对原形式背景绝对不必要属性集上的部分属性, 利用定理4在更新后的关系矩阵中对其进行判断即可.

例6 在表1的形式背景中, 已知核心

C^t={m₁, m₂, m₄, m₆, m₇, m₈},

绝对不必要属性集

I^t={m₃, m₅}.

在表1中, 当删除属性m₂时, 由例2中的D^t可知

d12t=d32t=d52t=d62t=d72t=d82t=0,

于是根据定理5中1)可得,

m₁∈ C^t-1, m₆∈ C^t-1, m₇∈ C^t-1, m₈∈ C^t-1,
m3_∈ It^-1, m5_∈ It^-1.

由于 d42t=1且m₄∈ C^t, 故由定理5中2)可得,

m₄∈ C^t-1.

综上所述, 当在表1所示形式背景中删除属性m₂后, 新形式背景的核心

C^t-1={m₁, m₄, m₆, m₇, m₈},

绝对不必要属性集

I^t-1={m₃, m₅},

属性约简

F^t-1={m₁, m₄, m₆, m₇, m₈}.

可验证该结论与定理4所得结果一致.

基于定理2、定理4和定理5, 在形式背景中删除属性m_k时, 获取属性约简的过程记为算法2, 时间复杂度为

O(|I^t-{m_k}-I₀||M^t-{m_k}||G|).

算法2 删除m_k时属性约简的更新算法

输入 ( HMt, ⩽), D^t= (dijt)p×p, m_k, I^t

输出 属性约简 F^t-1

initialize F^t-1← Ø , I₀← Ø , D^{t→ t-1}← zeros(p, p),

D^t-1← zeros(p-1, p-1), I₁← Ø

for m_i∈ I^t-{m_k}

if dikt=0

I₀← I₀∪ {m_i}

end if

end for

if I₀=I^t-{m_k}

return F^t-1← M^t-I^t-{m_k}

end if

for m_i∈ I^t-{m_k}-I₀

if dikt=1

for m_j∈ M^t-{m_k}

if dkjt=1∧ U Nmit∩ L Nmjt={m_k}

dijt→t-1← 1

else

dijt→t-1← dijt

end if

end for

end if

end for

D^{t→ t-1}← (dijt→t-1)p×p

D^t-1← 删除D^{t→ t-1}的第k行与第k列

for m_i∈ I^t-{m_k}-I₀

if $\sum_{j=1}^{p-1} d_{i j}^{t-1} \geqslant 2 \wedge \bigcap_{m_{s} \in U N_{m_{i}}^{t-1}} m_{s}^{\prime}-m_{i}^{\prime}=\emptyset$

I₁← I₁∪ {m_i}

end if

end for

F^t-1← M^t-{m_k}-I₀-I₁

return F^t-1

由于在基于属性直观图的属性特征的判别方法中, 关键在于求出属性的上近邻, 因此针对增加一个属性的情况, 下面仍借助 Dt+1的更新规律, 从关系矩阵 Dt+1的列出发分析属性特征的变化规律, 进一步得到属性约简的更新方法.

定理6 设( HMt, ⩽)为(G, M^t, R^t)的属性直观图, m_p+1为新增属性,

Dt+1=(dijt+1)(p+1)×(p+1)

为( HMt+1, ⩽)的关系矩阵, C^t与I^t分别为(G, M^t, R^t)的核心和绝对不必要属性集.∀ m_i∈ M^t, 有如下结论成立.

1)当 di(p+1)t+1=0时, 若m_i∈ C^t, 则m_i∈ C^t+1; 若m_i∈ I^t, 则m_i∈ I^t+1.

2)当 di(p+1)t+1=1时, 若m_i∈ I^t, 则m_i∈ I^t+1.

证明 类似于定理5可证.

定理6说明在增加属性${{m}_{p+1}}$时, 原形式背景的绝对不必要属性仍是新形式背景的绝对不必要属性.因此, 想要获取新形式背景的属性约简, 仅需对原形式背景核心中的部分属性及新增属性, 利用定理4在更新后的关系矩阵中对其进行判断即可.

例7 继续以例1的形式背景为例进行解释.

当在表1中增加属性m₉(m'₉={3, 4})时, 由例4中的D^t+1知

$\begin{aligned} d_{1(p+1)}^{t+1}= & d_{2(p+1)}^{t+1}=d_{3(p+1)}^{t+1}=d_{5(p+1)}^{t+1}=d_{6(p+1)}^{t+1}= \\ & d_{7(p+1)}^{t+1}=d_{8(p+1)}^{t+1}=0 \end{aligned}$

于是由

C^t={m₁, m₂, m₄, m₆, m₇, m₈},

I^t={m_3, m₅}

以及定理6中1)可得,

m₁∈ C^t+1, m₂∈ C^t+1, m₆∈ C^t+1, m₇∈ C^t+1, m₈∈ C^t+1,

m₃∈ I^t+1, m₅∈ I^t+1.

对于属性m₄, 由例4的D^t+1可知 d49t+1=1且m₄∉I^t, 因此进一步根据定理4判断m₄的属性特征.因

d42t+1=d49t+1=1,

故

UNm4t+1={m2, m9},

进而有

$\bigcap_{m_{s} \in U N_{m_{4}}^{t+1}} m_{s}^{\prime}-m_{4}^{\prime}=\{3\}-\{3\}=\emptyset, $

于是根据定理4可得m₄∈ I^t+1.

又因为

$\sum_{j=1}^{9} d_{9 j}^{t+1}=1< 2$,

故根据定理4可得新增属性m₉∉I^t+1.

综上所述, 在增加m₉(m'₉={3, 4})之后, 新形式背景的核心

C^t+1={m₁, m₂, m₆, m₇, m₈, m₉},

绝对不必要属性集

I^t+1={m₃, m₄, m₅},

属性约简

F^t+1={m₁, m₂, m₆, m₇, m₈, m₉}.

该结论可由定理4验证其正确性.

基于定理3、定理4和定理6, 在形式背景中增加属性${{m}_{p+1}}$时, 获取属性约简的过程记为算法3, 时间复杂度为

O(|C^t∪ {m_p+1}-C₀||M^t∪ {m_p+1}||G|).

算法3 增加${{m}_{p+1}}$时属性约简的更新算法

输入 ( HMt, ⩽), D^t= (dijt)p×p, (m'_p+1, m_p+1), C^t

输出 属性约简 F^t+1

initialize F^t+1← Ø , D^{t→ t+1}← zeros(p+1, p+1),

D^t+1← zeros(p+1, p+1), C₀← Ø , C₁← Ø

for m_i∈ M^t∪ {m_p+1}

for m_j∈ M^t∪ {m_p+1}

if i≤ p∧ j≤ p

dijt→t+1←dijt

else if m'_i⊆m'_j

dijt→t+1←1

else

dijt→t+1←0

end if

end for

end for

D^{t→ t+1}← (dijt→t+1)(p+1)×(p+1)

for m_l∈ M^t

for m_s∈ M^t

if d(p+1)lt→t+1=1∧dlst→t+1=1

d(p+1)st→t+1←0

end if

if dlst→t+1=1∧ds(p+1)t→t+1=1

dl(p+1)t→t+1←0

end if

if dl(p+1)t→t+1=1∧d(p+1)st→t+1=1

dlst→t+1← 0

end if

end for

end for

D^t+1← D^{t→ t+1}

for m_i∈ C^t

if di(p+1)t+1=0

C₀← C₀∪ {m_i}

end if

end for

for m_i∈ C^t∪ {m_p+1}-C₀

if $\overset{p+1}{\mathop{\underset{j=1}{\mathop \sum }\, }}\, d_{ij}^{t+1}< 2$

C₁← C₁∪ {m_i}

else if $\bigcap_{m_{s} \in U N_{m_{i}}^{t+1}} m_{s}^{\prime}-m_{i}^{\prime} \neq \emptyset$

C₁← C₁∪ {m_i}

end if

end for

F^t+1← C₀∪ C₁

return F^t+1