第5期 杜秋香，等：概念特化的概念格更新构造算法 ·445. 全概念C(41,B1)互为对应概念，则L2只需与概念 证明因为廿CA,B)∈L,1)若概念C为L的 格L1做比较.即L2无需与L,的所有概念都做比 不变概念，则C∈L1.说明概念C(A,B)与分解属性 较，也就是L2仅与L,的一个子概念格做比较 P无关，所以在形式背景K、K中，概念C(A,B均满 证明设C'(A!B)为概念格L,中除C及其 足fA)=B,gB)=A成立，所以C(A,B)∈L2)若 子孙结点以外的其他任一概念：1)若C为C的父 概念C为特化概念，则有：C1=(AUA1,B1)∈L1, 结点或祖先结点，则有A1CA成立，因为C2与C,互 C2=(AUA2,B2)∈L2,并且A1∩A2=G(B1-P)U 为对应概念，根据定义5有A1=A2,所以A2CA成 B2=B.那么在K中有B1使得：g(B1)=AUA1, 立，概念C2应作为C的子结点，这时概念C就会有 fA)2f(AUA1)=B1,这时，若A1=G则f(A)= 2个外延相同的子结点，所以C,不与C,的父概念 fAUA)=B1,若A1≠G由定义6，只能有f(A)= 及其祖先概念做比较：2)若C'(A:B)为除其父结 fAUA1)=B1,这时概念(A,B1)不满足概念的完备 点及其祖先结点外的其他结点，又分为2种情况：如 性，因为A≠gfA)=AUA1,所以(A,B)年L.同 果A与A,没有任何关系，则C显然没有必要与 理可证在形式背景中有B,使得g(B2)=AU C'(A,B)做比较.如果A'∩A1≠O又因为A:= A2,f4)=B2,即(A,B2)年L2.因此，在K中有 A2,则C'(A,B)与C(A1,B1)必有相同的子结点， (B,-P)UB2=B满足g(B)=A和f(A)=B,即 这时L2中的结点只与C'(A,B)的子结点做比较 C(A,B)∈L!同理可证，当概念C为L的新增概念 就可以，而没有必要与C做比较： 和更新概念时，C(A,B)∈L成立. 所以，将L2中的概念插入L中更新构造概念 定理3若概念C(A,B)为重构概念格L的任 格L时，L2只需与，中以C,为全概念的子格L: 一概念，则概念C也为更新概念格L的一个概念， 做比较 即若C(A,B)∈L,则C(A,B)∈L 在利用概念格L1、L2更新构造概念格L的过程 证明因为C(A,B)∈L,假设B=B1UB2,并 中，L2的每一概念C2与L1中具有相同父概念的结且B,∈K和B,∈K,则在概念格L,中有：gB,U 点C,进行比较，根据外延之间关系的不同采取不同 P)=AUA1,fAUA1)=B,UP,在概念格L2中有： 的措施，删除概念C内涵中的分解属性P,添加新 g(B2)=AUA2,fAUA2)=B2,并且A1∩A2=0即 的属性，更新父子关系.这样逐层自顶向下进行比 有：C1AUA1,B1UP)∈L1,C2(AUA2,B2)∈L2.又 较，直到L2的所有概念比较完毕.在此过程中，根据 因为在形式背景K中，f(A)=B=B,UB2,则在K 概念外延关系的不同会产生以下几类概念： 中有fA)=B,UP,又因为A≠g(f(A)),所以(A, 定义5设概念C141,B1)∈L1,C(42,B2)∈ B,UP)年L.同理可证，(A,B2)年L2.根据以上生 L2,若A1=A,并且P∈B1,C,变为(A1,(B,·P)U成概念的定义，概念CA,B)∈L B2),则称概念C为概念格L的更新概念. 定理2与定理3证明了利用概念格L2插入概 定义6设概念C1(A1,B1)∈L1,C2(42,B2)∈ 念格L,中更新构造的概念格L与直接在新的形式 L2,若A,∩A2≠0则产生一新概念C(A1∩42， 背景下生成的概念格L的概念是相同的，在更新构 B,UB2)·P),称概念C为L的特化概念 造L的过程中，格中的父子关系也随着概念的变化 定义7设概念C(A1,B1)∈L1,C2(A2,B2)∈ 进行更新，L中概念和L中概念有着相同的父子关 L2,若A2CA1,则将概念C2(A2,B2插入到概念格L1 系，所以概念格L与概念格L为同一概念格 中，C、C分别变为(A,(B,-P)、(A2,B1-P)U 3基于概念特化的概念格更新构造算法 B2),则概念C、C分别称为概念格L的更新概念和 新增概念 基于上述分析，基于概念特化的概念格更新构 定义8设L,的任一概念C(A,B),若A三Q不 造算法如下： 成立或P年B,则称概念C为概念格L的不变概念. 算法UCCS(updating constructing based on con 根据文献17)，可以证明如下定理，即利用概 cept specialization) 念格L,与L2更新构造的概念格L与在形式背景K 输入：概念格L,对象集合Q,分解属性P及其 上重新构造的概念格L为同一概念格 分解后的属性集合P,P,…Pn 定理2若概念CA,B)为更新构造的概念格L 输出：概念格L 的任一概念，则概念C(A,B也为重新构造的概念格 1)在形式背景飞=(Q,{P,P2,,Pn,)上 L的一个概念，即若廿CA,B)∈L则CA,B)∈L! 生成概念格L2 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net全概念 C1 (A1 , B1 )互为对应概念 ,则 L2 只需与概念 格 L′1 做比较. 即 L2 无需与 L1 的所有概念都做比 较 ,也就是 L2 仅与 L1 的一个子概念格做比较. 证明 设 C′(A′, B ′)为概念格 L1 中除 C1 及其 子孙结点以外的其他任一概念 : 1)若 C′为 C1 的父 结点或祖先结点 ,则有 A1 < A′成立 ,因为 C2 与 C1 互 为对应概念 ,根据定义 5有 A1 =A2 ,所以 A2 < A′成 立 ,概念 C2 应作为 C′的子结点 ,这时概念 C′就会有 2个外延相同的子结点 ,所以 C2 不与 C1 的父概念 及其祖先概念做比较; 2)若 C′(A′, B ′)为除其父结 点及其祖先结点外的其他结点 ,又分为 2种情况 :如 果 A′与 A1 没有任何关系 ,则 C2 显然没有必要与 C′(A′, B ′)做比较. 如果 A′∩A1 ≠ ª, 又因为 A1 = A2 ,则 C′(A′, B ′)与 C1 (A1 , B1 )必有相同的子结点 , 这时 L2 中的结点只与 C′(A′, B ′)的子结点做比较 就可以 ,而没有必要与 C′做比较. 所以 ,将 L2 中的概念插入 L1 中更新构造概念 格 L时 , L2 只需与 L1 中以 C1 为全概念的子格 L′1 做比较. 在利用概念格 L1、L2 更新构造概念格 L的过程 中 , L2 的每一概念 C2 与 L1 中具有相同父概念的结 点 C1 进行比较 ,根据外延之间关系的不同采取不同 的措施 ,删除概念 C1 内涵中的分解属性 P,添加新 的属性 ,更新父子关系. 这样逐层自顶向下进行比 较 ,直到 L2 的所有概念比较完毕. 在此过程中 ,根据 概念外延关系的不同会产生以下几类概念 : 定义 5 设概念 C1 (A1 , B1 ) ∈L1 , C2 (A2 , B2 ) ∈ L2 ,若 A1 =A2 并且 P∈B1 , C1 变为 (A1 , (B1 - P) ∪ B2 ) ,则称概念 C1 为概念格 L的更新概念. 定义 6 设概念 C1 (A1 , B1 ) ∈L1 , C2 (A2 , B2 ) ∈ L2 ,若 A1 ∩A2 ≠ª, 则产生一新概念 C (A1 ∩A2 , (B1 ∪B2 ) - P) ,称概念 C为 L的特化概念. 定义 7 设概念 C1 (A1 , B1 ) ∈L1 , C2 (A2 , B2 ) ∈ L2 ,若 A2 < A1 ,则将概念 C2 (A2 , B2 )插入到概念格 L1 中, C1、C2 分别变为 (A1 , (B1 - P) )、(A2 , (B1 - P) ∪ B2 ) ,则概念 C1、C2 分别称为概念格 L 的更新概念和 新增概念. 定义 8 设 L1 的任一概念 C (A, B ) ,若 A Α Q不 成立或 P| B ,则称概念 C为概念格 L的不变概念. 根据文献 [ 17 ],可以证明如下定理 ,即利用概 念格 L1 与 L2 更新构造的概念格 L与在形式背景 K′ 上重新构造的概念格 L′为同一概念格. 定理 2 若概念 C (A, B )为更新构造的概念格 L 的任一概念,则概念 C (A, B )也为重新构造的概念格 L′的一个概念,即若 ΠC (A, B ) ∈L,则 C (A, B ) ∈L′. 证明 因为 Π C (A, B ) ∈L, 1)若概念 C为 L 的 不变概念 ,则 C∈L1 . 说明概念 C (A, B )与分解属性 P无关 ,所以在形式背景 K、K′中 ,概念 C (A, B )均满 足 f (A ) =B , g (B ) =A成立 ,所以 C (A, B ) ∈L′; 2)若 概念 C 为特化概念 , 则有 : C1 = (A ∪A1 , B1 ) ∈L1 , C2 = (A∪A2 , B2 ) ∈L2 ,并且 A1 ∩A2 = ª, (B1 - P) ∪ B2 =B. 那么在 K1 中有 B1 使得 : g (B1 ) = A ∪A1 , f (A ) Β f (A ∪A1 ) = B1 ,这时 ,若 A1 = ª,则 f (A ) = f (A∪A1 ) =B1 ,若 A1 ≠ª,由定义 6,只能有 f (A ) = f (A∪A1 ) =B1 ,这时概念 (A, B1 )不满足概念的完备 性 ,因为 A≠g ( f (A ) ) =A∪A1 ,所以 (A, B1 ) | L1 . 同 理可证在形式背景 K2 中有 B2 使得 g (B2 ) = A ∪ A2 , f (A ) = B2 , 即 (A, B2 ) | L2 . 因此 , 在 K′中有 (B1 - P) ∪B2 = B 满足 g (B ) = A 和 f (A ) = B , 即 C (A, B ) ∈L′. 同理可证 ,当概念 C为 L 的新增概念 和更新概念时 , C (A, B ) ∈L′成立. 定理 3 若概念 C (A, B )为重构概念格 L′的任 一概念 ,则概念 C也为更新概念格 L 的一个概念 , 即若 C (A, B ) ∈L′,则 C (A, B ) ∈L. 证明 因为 C (A, B ) ∈L′,假设 B = B1 ∪B2 ,并 且 B1 ∈K1 和 B2 ∈K2 ,则在概念格 L1 中有 : g (B1 ∪ P) =A∪A1 , f (A ∪A1 ) = B1 ∪P,在概念格 L2 中有 : g (B2 ) =A∪A2 , f (A ∪A2 ) =B2 ,并且 A1 ∩A2 = ª,即 有 : C1 (A∪A1 , B1 ∪P) ∈L1 , C2 (A ∪A2 , B2 ) ∈L2 . 又 因为在形式背景 K′中 , f (A ) =B =B1 ∪B2 ,则在 K1 中有 f (A ) =B1 ∪P,又因为 A ≠g ( f (A ) ) ,所以 (A, B1 ∪P) | L1 . 同理可证 , (A, B2 ) | L2 . 根据以上生 成概念的定义 ,概念 C (A, B ) ∈L. 定理 2与定理 3证明了利用概念格 L2 插入概 念格 L1 中更新构造的概念格 L 与直接在新的形式 背景下生成的概念格 L′的概念是相同的 ,在更新构 造 L的过程中 ,格中的父子关系也随着概念的变化 进行更新 , L中概念和 L′中概念有着相同的父子关 系 ,所以概念格 L与概念格 L′为同一概念格. 3 基于概念特化的概念格更新构造算法 基于上述分析 ,基于概念特化的概念格更新构 造算法如下 : 算法 UCCS( updating constructing based on con2 cep t specialization) 输入 :概念格 L1 ,对象集合 Q,分解属性 P及其 分解后的属性集合 { P1 , P2 , …, Pn }. 输出 :概念格 L. 1)在形式背景 K2 = (Q, { P1 , P2 , …, Pn }, I2 )上 生成概念格 L2 第 5期 杜秋香 ,等 :概念特化的概念格更新构造算法 ·445· © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net