·446- 智能系统学报 第3卷 2)For every node C2 (A2.B2)in L2 17)C2(A2,B2)更新为(A2,B2U(B'-P)) 3)If Father(C2)= 18)增加边C'->C2(42,B2U(B'-P)) 4)调用函数Find1C2,C,)/根据外延寻找C2 19)End if 在L,中的对应概念C'(A,B,) 20)End or 5)C'(A1B,更新为C'(A,:(B,'-P)U 在此算法中，时间开销有2部分组成：L2的建 B2》 格时间和将L2插入到概念格L1中的时间.由于形 6)End if 式背景相对于K较小，所以L2的建格时间相对 7)If father(C2)≠G 于L较小.设L2的结点数为N2,则将L2插入L,中 8)调用函数Find()/在L!中寻找father(C) 的复杂度为ON2*0(Find())*0(Compare())) 的对应概念C'(A,B 其中，设L1中外延数为|A2的结点个数为N1,则 9)执行过程Compare(C,Child(c))/ 0(Find())=N1*422,设L,中和C2具有相同父 Child(C)=C (41.B) 结点父结点的外延相同的结点数为N,外延的最 10)next node 大个数为N4,则O(Compare))=N3*42|*N4, 11)End for 设N=N,*N2*N;*Na,则ON2*O(Fnd())* 12)If Intent(C1)=O/只判断L1的全概念 O(Compare()))=N*A2,算法的复杂度为多项 13)删除概念C1,更新父子关系 式级.而经典的Godin算法时间复杂度为 14)End if O(2IIG1I)(k为属性的个数)，复杂度是呈指数增 Fimd1C2,C1)/将L1的概念按外延排序，设 长的，显然本文算法较优由前面的分析可以看出， L,的任一概念为C1A1,B1) 分解得到的新属性个数越小，随着数据量的不断增 1)For every node C1 in lay(A2)/在，中，外 大，本文算法的优越性也越明显 延个数为42层次上的每个概念 2)fA1==A2 4举例分析 3)Retum C(A1.B) 表1为任意形式背景，图1是其构造出的概念 4)End if 格，将形式背景中的B属性分解为属性B1、B2、B3, 5)End for B1、B2、B,形成的形式背景及其构造出的概念格分 Compare (Ca.Child (C))/Child (C)= 别为表2和图2所示.采用本文的算法，更新构造新 C1(A1,B1 步骤如下 表2形式背景 1)For every Child(C) Table 2 Formal context 2)fA1==A2/若外延相同，只更新C,的内涵 8 3)C1A1,B1)更新为C(A1,(B1-P)UB2) 4)End if 5)Else ifA1sA2/将C,加入L1中 6)增加边C2->C #9(134,B) 7)C2(A2,B2)更新为42，B2U(B'-P) #10(13,BB,) #11(34,B,B,) 8)C1(A,B1)更新为(A1,(B1-P)UB2) 9)End if 10)Else ifA1∩42≠O/产生一特化概念C” #12(3,BBB》 11)生成特化概念C"(A∩42，(B1-P)UB2) 图2概念格的Hasse图 12)增加边C1(A1,B1)->C"(A1∩42，(B,-P) Fig 2 Hasse diagram of concept lattice UB,) 13)将概念C,加入L,中 首先在图1中找到图2中概念#9(134，B2)的 14)增加边C2->C”C'->C2 对应概念3(134，B),更新概念#3(134，B)为#3 15)End if (134,B2),由定义7，概念#3为更新概念.将概念#9 16)Else/A1≠A2,上述情况除外，若C2和C' 的每个子概念与概念#3的子概念做比较，首先，将 的每个子结点都不相同，将C,添加到L,中 #概念的子结点#10(13，B,B2)与概念#5(14，ABD) 做比较，概念#10与概念5的外延有交集1，又因为 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net2) For every node C2 (A2 , B2 ) in L2 3) If Father(C2 ) = ª 4)调用函数 Find (C2 , C1 ′) / /根据外延寻找 C2 在 L1 中的对应概念 C1 ′(A1 ′, B1 ′) 5) C1 ′(A1 ′, B1 ′)更新为 C1 ′(A1 ′, (B1 ′- P ) ∪ B2 ) 6) End if 7) If father(C2 ) ≠ª, 8)调用函数 Find ( ) / /在 L′1 中寻找 father(C2 ) 的对应概念 C′(A′, B ′) 9 ) 执 行 过 程 Compare ( C2 , Child ( C′) ) / / Child (C′) =C1 (A1 , B1 ) 10) next node 11) End for 12) If Intent(C′1 ) = ª/ /只判断 L′1 的全概念 13)删除概念 C′1 ,更新父子关系 14) End if Find (C2 , C′1 ) / /将 L1 的概念按外延排序 ,设 L1 的任一概念为 C′1 (A′1 , B ′1 ) 1) For every node C′1 in lay( |A2 | ) / /在 L1 中 ,外 延个数为 |A2 |层次上的每个概念 2) If A1 = =A2 3) Return C′1 (A′1 , B ′1 ) 4) End if 5) End for Compare ( C2 , Child ( C′) ) / /设 Child ( C′) = C1 (A1 , B1 ) 1) For every Child (C′) 2) If A1 = =A2 / /若外延相同 ,只更新 C1 的内涵 3) C1 (A1 , B1 )更新为 C1 (A1 , (B1 - P) ∪B2 ) 4) End if 5) Else if A1 Α A2 / /将 C2 加入 L1 中 6)增加边 C2 - >C1 7) C2 (A2 , B2 )更新为 (A2 , B2 ∪(B ′- P) ) 8) C1 (A1 , B1 )更新为 (A1 , (B1 - P) ∪B2 ) 9) End if 10) Else if A1 ∩A2 ≠ª/ /产生一特化概念 C″ 11)生成特化概念 C″( A1 ∩A2 , (B1 - P) ∪B2 ) 12)增加边 C1 (A1 , B1 ) - >C″( A1 ∩A2 , (B1 - P) ∪B2 ) 13)将概念 C2 加入 L1 中 14)增加边 C2 - >C″, C′- >C2 15) End if 16) Else / /A1 ≠A2 ,上述情况除外 ,若 C2 和 C′ 的每个子结点都不相同 ,将 C2 添加到 L1 中 17) C2 (A2 , B2 )更新为 (A2 , B2 ∪(B ′- P) ) 18)增加边 C′- >C2 (A2 , B2 ∪(B ′- P) ) 19) End if 20) End for 在此算法中 ,时间开销有 2部分组成 : L2 的建 格时间和将 L2 插入到概念格 L1 中的时间. 由于形 式背景 K2 相对于 K′较小 ,所以 L2 的建格时间相对 于 L′较小. 设 L2 的结点数为 N2 ,则将 L2 插入 L1 中 的复杂度为 O (N2 3 O (Find ( ) ) 3 O (Compare ( ) ) ). 其中 ,设 L1 中外延数为 | A2 |的结点个数为 N1 , 则 O (Find ( ) ) = N1 3 |A2 | 2 ,设 L1 中和 C2 具有相同父 结点 (父结点的外延相同 )的结点数为 N3 ,外延的最 大个数为 N4 ,则 O (Compare ( ) ) = N3 3 |A2 | 3 N4 , 设 N = N1 3 N2 3 N3 3 N4 ,则 O (N2 3 O (Find ( ) ) 3 O (Compare ( ) ) ) =N 3 |A2 | 3 ,算法的复杂度为多项 式级. 而 经 典 的 Godin 算 法 时 间 复 杂 度 为 O (2 2k | |G | | ) ( k为属性的个数 ) ,复杂度是呈指数增 长的 ,显然本文算法较优. 由前面的分析可以看出 , 分解得到的新属性个数越小 ,随着数据量的不断增 大 ,本文算法的优越性也越明显. 4 举例分析 表 1为任意形式背景 ,图 1是其构造出的概念 格 ,将形式背景中的 B 属性分解为属性 B1、B2、B3 , B1、B2、B3 形成的形式背景及其构造出的概念格分 别为表 2和图 2所示. 采用本文的算法 ,更新构造新 步骤如下. 表 2 形式背景 Table 2 Forma l con text B1 B2 B3 1 √ √ √ 3 √ √ √ 4 √ 图 2 概念格的 Hasse图 Fig. 2 Hasse diagram of concep t lattice 首先在图 1中找到图 2中概念 #9 ( 134, B2 )的 对应概念 #3 (134, B ) , 更新概念 #3 ( 134, B ) 为 #3 (134, B2 ) ,由定义 7,概念 #3为更新概念. 将概念 #9 的每个子概念与概念 #3的子概念做比较 ,首先 ,将 #9概念的子结点 #10 (13, B1B2 )与概念 #5 ( 14, ABD ) 做比较 ,概念 #10与概念 #5的外延有交集 1,又因为 ·446· 智 能 系 统 学 报 第 3卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net