第5期 杜秋香，等：概念特化的概念格更新构造算法 ·447· #5的子概念中没有外延为1的子概念，由定义8产 背景：1)选定间隔为20的150个波长S3810, 生一特化概念#13(1，AB1B2D),再将概念#10(13， S3830,…,S6810作为属性集，2)依据每一波长处的 B1B2与概念#7(3，BC)做比较，因为概念#7的外延 流量、峰宽和形状，将其离散化为13种数值之一，并 3为概念#10外延1,3的子集，由定义9，概念 作为该波长处取值.实验中将波长为S3850处的属 #10(13,B,B2)添加到概念格L1中.将概念#7、#5作 性分解为S6830、S6850、S6870、S6890、S6910等5种 为它的子结点，并将#7更新为(3，B,B2C).再将#9 波长，实验结果与Godin算法比较的结果如表4所 的第2个子结点#11(34，B2B3)与#3(134，B2)的每 示： 个子结点#5、#7作比较，产生特化概念#14(4， 表4不同对象的God in算法与UCCS算法实验比较 AB2B3D),#7(3,B1B2C)又被更新为(3，B1B2B3C) Table 4 Experimen tal com parison between Godin a lgo 最后将概念#12(3，B1B2B3)与L1中的下一层上的 rithm and UCCS a lgorithm of differen t objects 结点做比较，#8更新为(GAB,B2B,CD).综上所述 对象数 Godin/s UCCS/s生成结点数 在此更新过程中的特化概念有#13(1，ABB,D)、 2000 523 19 12221 #14(4,AB2B3D),新增概念有#11(34，B2B3)、#10 3000 1250 44 19155 4000 2239 25077 (13,B1B2),更新概念有#3(134，B2)、#5(14, 81 6000 4579 122 30314 AB2D)、#73,B1B2B3C、#8(GAB1B2B3CD),而概 8315 4649 275 42679 念#1(12345,0、#2(1245，A)、#4(23,C)则为不变 从实验结果可以看出，UCCS算法更新构造概 概念.可以很容易看出此算法与在表3的形式背景 念格的结点数和Godin算法生成的结点数是相同 重新构造的概念格是相同的，进而证明了此算法的 的，从而验证了本文算法的正确性.采用基于链表结 正确性」 构的概念格渐进式构造算法大大提高了寻找相应概 表3形式背景 Table 3 Fommal con text 念的效率1.当分解后的新属性的个数远小于形式 背景中属性的个数时，UCCS算法更新构造概念格 A B2 B3 C D 的效率远高于利用God in算法重新构造概念格的效 2 率.若新属性和原形式背景中的属性相当，退化为两 概念格的合并问题，由文献[17]知，其效率也明显 高于利用传统算法重新构造概念格的效率 #1(12345,☑ 6结束语 #2(1245,A) 3(134,B) #4(23,C) 本文利用概念格概念间的泛化与例化关系，给 出了一种基于概念特化的概念格更新构造算法 UCCS,当形式背景中某个属性分解，新的概念格产 #5(14,AB,D)#11(34,B,B)#10(13,BB,) #6(2,AC) 生较之原格更加特化的概念，利用较高层的概念格， 只对原格的某个子格进行更新处理，得到了概念较 为特化的概念格.最后，通过与Godin算法重新构造 #13(1,ABB,D)#14(4,AB,B,D) 7(3,BB,B.C 概念格作比较，实验验证了算法的正确性和有效性 参考文献： #8(,AB B,BCD) [1 W LLE R Restructuring lattice theory:an app roach based 图3概念格的Hase图 on hierarchies of concepts [M ]Dordrecht Reidel,1982: Fig 3 Hasse diagram of concept lattice 415-470 [2 CHR ISTAN N,KENT R E Conceptual analysis of re- 5实验分析 source meta-infomation[J ]Computer Neworks and ISDN System,1995,27(6):973984 在W indows XP操作系统，数据库为Oracle9i, [3 ]EKLUND P W,MARTN P.WWW indexaton and docu- 采用Visual C++6.0实现了Godin算法和UCCS ment navigation using conceptual structures [C]//2nd 算法.实验数据采用国家天文台提供的恒星光谱数 IEEE Conference on Intelligent Infomation Processing Sys- 据，将这些数据经过以下处理构成本实验中的形式 tems(C IPS98).S 1 1.IEEE Press,1998:217-221 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net#5的子概念中没有外延为 1的子概念 ,由定义 8产 生一特化概念 #13 ( 1, AB1B2D ) ,再将概念 #10 ( 13, B1B2 )与概念 #7 (3, BC)做比较 ,因为概念 #7的外延 { 3}为概念 #10外延 { 1, 3}的子集 , 由定义 9, 概念 #10 (13, B1B2 )添加到概念格 L1 中 ,将概念 #7、#5作 为它的子结点 ,并将 #7更新为 ( 3, B1B2 C). 再将 #9 的第 2个子结点 #11 ( 34, B2B3 )与 #3 ( 134, B2 )的每 个子结点 # 5、# 7 作比较 , 产生特化概念 # 14 ( 4, AB2B3D ) , #7 (3, B1B2 C)又被更新为 ( 3, B1B2 B3 C). 最后将概念 #12 ( 3, B1B2 B3 )与 L1 中的下一层上的 结点做比较 , #8更新为 ( ª, AB1B2B3 CD ). 综上所述 , 在此更新过程中的特化概念有 #13 ( 1, AB1B2D ) 、 #14 (4, AB2B3D ) ,新增概念有 #11 ( 34, B2B3 )、#10 (13, B1B2 ) , 更新概 念有 # 3 ( 134, B2 )、# 5 ( 14, A B2D )、#7 (3, B1B2B3 C) 、#8 ( ª, AB1B2B3 CD ) , 而概 念 #1 (12345, ª) 、#2 (1245, A )、#4 ( 23, C)则为不变 概念. 可以很容易看出此算法与在表 3的形式背景 重新构造的概念格是相同的 ,进而证明了此算法的 正确性. 表 3 形式背景 Table 3 Forma l con text A B1 B2 B3 C D 1 √ √ √ √ 2 √ √ 3 √ √ √ √ 4 √ √ √ √ 5 √ 图 3 概念格的 Hasse图 Fig. 3 Hasse diagram of concep t lattice 5 实验分析 在 W indows XP操作系统 ,数据库为 O racle 9 i, 采用 V isual C + + 6. 0实现了 Godin算法和 UCCS 算法. 实验数据采用国家天文台提供的恒星光谱数 据 ,将这些数据经过以下处理构成本实验中的形式 背景 : 1 ) 选定间 隔 为 20 的 150 个 波 长 S3810, S3830, …, S6810作为属性集 ; 2)依据每一波长处的 流量、峰宽和形状 ,将其离散化为 13种数值之一 ,并 作为该波长处取值. 实验中将波长为 S3850处的属 性分解为 S6830、S6850、S6870、S6890、S6910等 5种 波长 ,实验结果与 Godin算法比较的结果如表 4所 示 : 表 4 不同对象的 Godin算法与 UCCS算法实验比较 Table 4 Exper im en ta l com par ison between God in a lgo2 r ithm and UCCS a lgor ithm of d ifferen t objects 对象数 Godin /s UCCS/s 生成结点数 2 000 523 19 12 221 3 000 1 250 44 19 155 4 000 2 239 81 25 077 6 000 4 579 122 30 314 8 315 4 649 275 42 679 从实验结果可以看出 , UCCS算法更新构造概 念格的结点数和 Godin算法生成的结点数是相同 的 ,从而验证了本文算法的正确性. 采用基于链表结 构的概念格渐进式构造算法大大提高了寻找相应概 念的效率 [ 18 ] . 当分解后的新属性的个数远小于形式 背景中属性的个数时 , UCCS算法更新构造概念格 的效率远高于利用 Godin算法重新构造概念格的效 率. 若新属性和原形式背景中的属性相当 ,退化为两 概念格的合并问题 ,由文献 [ 17 ]知 ,其效率也明显 高于利用传统算法重新构造概念格的效率. 6 结束语 本文利用概念格概念间的泛化与例化关系 ,给 出了一种基于概念特化的概念格更新构造算法 UCCS,当形式背景中某个属性分解 ,新的概念格产 生较之原格更加特化的概念 ,利用较高层的概念格 , 只对原格的某个子格进行更新处理 ,得到了概念较 为特化的概念格. 最后 ,通过与 Godin算法重新构造 概念格作比较 ,实验验证了算法的正确性和有效性. 参考文献 : [ 1 ]W ILLE R. Restructuring lattice theory: an app roach based on hierarchies of concep ts[M ]. Dordrecht: Reidel, 1982: 4152470. [ 2 ] CHR ISTIAN N, KENT R E. Concep tual analysis of re2 source meta2information[J ]. Computer Networks and ISDN System, 1995, 27 (6) : 9732984. [ 3 ] EKLUND P W , MARTIN P. WWW indexation and docu2 ment navigation using concep tual structures [ C ] / / 2nd IEEE Conference on Intelligent Information Processing Sys2 tem s( IC IPS’98). [ S. l. ]. IEEE Press, 1998: 2172221. 第 5期 杜秋香 ,等 :概念特化的概念格更新构造算法 ·447· © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net