第3卷第5期 智能系统学报 Vol 3 Na 5 2008年10月 CAA I Transactions on Intelligent Systems Oct 2008 概念特化的概念格更新构造算法 杜秋香，张继福，张素兰 (太原科技大学计算机科学与技术学院，山西太原030024) 摘要：概念格是形式概念分析中的核心数据结构，概念格应用的瓶颈之一是其构造效率.针对形式背景的某个属 性分解为多个新属性得到更加特化的概念给出了一种基于概念特化的渐进式更新构造算法.该算法利用分解后的 新属性及其相应的形式背景，构造出的概念格与原概念格的某个子概念格作比较，来更新构造概念格，从而减少了 比较次数，提高了更新构造的效率.以天体光谱数据作为形式背景，实验验证了该算法的正确性和有效性 关键词：概念格：渐进式构造：概念特化：更新构造 中图分类号：TP311文献标识码：A文章编号：1673-4785(2008)05-0443-06 An i proved a lgorithm based on concept spec alization for constructing concept aattices DU Q iu-xiang,ZHANG Ji-fu,ZHANG Su-lan School of Computer Science and Technolgy,Taiyuan University of Science and Technology,Taiyuan 030024,China) Abstract:Concept lattices are the core data structures in fomal concept analysis The widesp read application of con- cept analysis is li ited by the difficulty of constructing a concept lattice An incrementally updating construction algo- rithm based on concept spcialization was devebped after it was realized that the attributes in the omal context can be decomposed into several new attributes,ormore specialized concepts The algorithm,with decomposed attributes and a corresponding fomal context,compares the concept lattice fomed with the new attributes and one of the sub-lattices of the original concept lattice,then upgrades the concept lattice according to results from the comparisons In this way the number of comparisons is reduced and the efficiency of constructing the concept lattice is mproved Experi- ment results,with celestial spectrum data as the fomal context,verified the validity of the algorithm. Keywords:concept lattice;incremental constructing concept specialization;updating construction “概念的基本观点是由哲学理论中的概念发 重用I1:Gord in等人还将概念格应用于类层次(class 展而来，是反应事物本质属性的思维产物.形式概念 hierarchy)的设计上ts) 理论是20世纪80年代初由德国教授R W ille:提出 概念格构造效率一直是概念格应用的主要瓶颈 的l山，并通过Hase图生动简洁地体现了概念间的 之一.目前，概念格的构造算法主要分为批处理算法 泛化和特化关系，提供了一种数据分析和知识处理 和渐进式算法两大类，典型的批处理算法有Bordat 的有力工具，被广泛应用于知识工程、数据挖掘、信 算法、Ganter算法、Nourine?算法等I6,其存在的问题 息检索和软件工程等领域，典型的应用有：Neuss和 是当形式背景发生变化时就要重新构造概念格.渐 Kent使用概念格进行Intemet_上文档元信息的自动 进式算法被认为是比较有前途的一类算法，可分为 分类和分析，Eklund和Martin展示了概念层次进 增加对象和增加属性2类概念格的渐进式构造.增 行Web文档索引和导航的能力；Corbetti和Burow 加对象的经典算法是Godin算法)，以及Godin算 提出使用概念格表示建筑早期设计软件支持环境 法的改进，例如，采用树结构组织格结点进行概念格 (SED)中的状态图，使得设计中获得的知识可以 的构造1：增加属性的典型算法是基于属性的概念 格渐进式生成算法，以及Add ntent算法io,.此 收稿日期：2008-03-21 基金项目：山西省自然科学基金资助项目(2006011041). 外，对概念格的研究热点还包括：规则提取、概 通信作者：杜秋香.Emai让anny1l23@163.com 念格的扩展以及与其他理论的融合35)、概念格的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 概念特化的概念格更新构造算法 杜秋香 ,张继福 ,张素兰 (太原科技大学 计算机科学与技术学院 ,山西 太原 030024) 摘 要 :概念格是形式概念分析中的核心数据结构 ,概念格应用的瓶颈之一是其构造效率. 针对形式背景的某个属 性分解为多个新属性得到更加特化的概念 ,给出了一种基于概念特化的渐进式更新构造算法. 该算法利用分解后的 新属性及其相应的形式背景 ,构造出的概念格与原概念格的某个子概念格作比较 ,来更新构造概念格 ,从而减少了 比较次数 ,提高了更新构造的效率. 以天体光谱数据作为形式背景 ,实验验证了该算法的正确性和有效性. 关键词 :概念格 ;渐进式构造 ;概念特化 ;更新构造 中图分类号 : TP311 文献标识码 : A 文章编号 : 167324785 (2008) 0520443206 An improved algor ithm based on concept spec ialization for constructing concept lattices DU Q iu2xiang, ZHANG Ji2fu, ZHANG Su2lan ( School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China) Abstract:Concep t lattices are the core data structures in formal concep t analysis. The widesp read app lication of con2 cep t analysis is limited by the difficulty of constructing a concep t lattice. An incrementally updating construction algo2 rithm based on concep t spcialization was developed after itwas realized that the attributes in the formal context can be decomposed into several new attributes, ormore specialized concep ts. The algorithm, with decomposed attributes and a corresponding formal context, compares the concep t lattice formed with the new attributes and one of the sub2lattices of the original concep t lattice, then upgrades the concep t lattice according to results from the comparisons. In this way the number of comparisons is reduced and the efficiency of constructing the concep t lattice is imp roved. Experi2 ment results, with celestial spectrum data as the formal context, verified the validity of the algorithm. Keywords: concep t lattice; incremental constructing; concep t specialization; updating construction 收稿日期 : 2008203221. 基金项目 :山西省自然科学基金资助项目 (2006011041). 通信作者 :杜秋香. E2mail: janny123@163. com. “概念 ”的基本观点是由哲学理论中的概念发 展而来 ,是反应事物本质属性的思维产物. 形式概念 理论是 20世纪 80年代初由德国教授 R. W ille提出 的 [ 1 ] ,并通过 Hasse图生动简洁地体现了概念间的 泛化和特化关系 ,提供了一种数据分析和知识处理 的有力工具 ,被广泛应用于知识工程、数据挖掘、信 息检索和软件工程等领域 ,典型的应用有 : Neuss和 Kent使用概念格进行 Internet上文档元信息的自动 分类和分析 [ 2 ] ; Eklund和 Martin展示了概念层次进 行 Web文档索引和导航的能力 [ 3 ] ; Corbett和 Burrow 提出使用概念格表示建筑早期设计软件支持环境 (SEED)中的状态图 ,使得设计中获得的知识可以 重用 [ 4 ] ; Gordin等人还将概念格应用于类层次 ( class hierarchy)的设计上 [ 5 ] . 概念格构造效率一直是概念格应用的主要瓶颈 之一. 目前 ,概念格的构造算法主要分为批处理算法 和渐进式算法两大类 ,典型的批处理算法有 Bordat 算法、Ganter算法、Nourine算法等 [ 6 ] ,其存在的问题 是当形式背景发生变化时就要重新构造概念格. 渐 进式算法被认为是比较有前途的一类算法 ,可分为 增加对象和增加属性 2类概念格的渐进式构造. 增 加对象的经典算法是 Godin算法 [ 7 ] ,以及 Godin算 法的改进 ,例如 ,采用树结构组织格结点进行概念格 的构造 [ 8 ] ;增加属性的典型算法是基于属性的概念 格渐进式生成算法 [ 9 ] ,以及 Add Intent算法 [ 10 ] . 此 外 ,对概念格的研究热点还包括 :规则提取 [ 11212 ]、概 念格的扩展以及与其他理论的融合 [ 13215 ]、概念格的 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·444- 智能系统学报 第3卷 更新与维护167等方面. 来，图1就是表1的形式背景对应概念格的Hasse 概念是语义描述的基本单位，在数据库中，概念 图形式.其中，图1中的每个结点表示一个形式概 描述了各个对象的基本特征.各属性值以及概念依 念，结点间的连线表示概念间的父子关系 据抽象程度不同可构成一个层次结构，通常称为概 #(12345,0) 念树或概念层次树.在概念层次树中，不同的层次表 示概念不同的抽象级别.层次越高，表示概念的抽象 #2(1245,A) #3(134,B) #4(23,C) 级别越高，概念也越泛化；层次越低，表示概念的抽 象级别越低，概念也越特化.概念分层为在各种抽象 级别处理数据提供了方便.概念格的Hasse图形象 #5(14,ABD #6(2,AC) #7(3,BC) 地体现了格中概念间的泛化特化关系.当形式背 景中若干属性合并时，概念格中的部分概念提升到 #8(.ABCD) 一个较高层次，得到较为泛化的概念，相反，当形式 背景中某个属性分解为若干个新属性时，就会得到 图1概念格的Hasse图 Fig 1 Hasse diagram of concept lattice 更加特化的概念.针对形式背景中的概念特化，即属 性分解问题，本文给出了一种基于概念特化的概念 2 基于概念特化的概念格更新构造 格渐进式更新构造算法UCCS,从而提高了概念格 更新构造的效率」 对于任意给定的形式背景，一个属性分解为若 干个新属性，即形式背景中的高层概念属性特化为 1基本概念 多个底层概念属性，使得形式背景发生变化，因此如 一个二维数据表(G,M),其中G的元素称为对 何利用原形式背景已构造出的概念格，来快速更新 象，M的元素称为属性，若G与M之间存在二元偏 构造新形式背景的概念格，对于提高概念格构造效 序关系GM=1在形式概念理论中称K= 率具有重要意义，该问题可以描述如下： (G,M,D为一个形式背景，则(gm)∈或gm表示 设形式背景K=(G,M1,),由K构造的概 对象g具有属性m.设A是对象集合G的一个子集， 念格为L1,P∈M,若属性P分解为属性集合P'= B是属性集合M的一个子集，若A、B满足：1) {P,P2,Pn},则形式背景由K变为K'=(G, fA)=fm∈M|廿g∈A,gm}(A中对象共同属性的 M1-P)U{P,P,Pn/,I),且由K构造的概 集合：2)g(B)=1g∈G1廿m∈B,gm}俱有B中 念格为L!如何利用原格L,通过快速更新构造得到 所有属性的对象的集合)，则称C(A,B)为概念格 概念格L,是本文要解决和研究的问题.利用L,更 L(K)的一个形式概念，其中，A为该概念的外延，记 新构造出的概念格设为L,则L'=L 为A=Extent(C),B为该概念的内涵，记为B= 定义2设K=(G,M1,)为形式背景，P∈ Intent(C).6 M1,若属性P分解为属性集合P,P,Pn,称P 定义1L61设C(A1,B1),C(A2,B2)为概念 为分解属性 格L的2个不同概念，若C<C2台A,CA282C 在形式背景K=(G,M1,4)中，若g(P)=Q, B1,并且不存在C3(A,B)有C<C<C成立，则 则由形式背景飞=(Q,{P,乃，Pn,)构造的 称C为C,的父概念或父结点，记为C2= 概念格设为L2,更新构造概念格L的过程是利用L2 Father(C),若Father(C)不存在，则称概念C,为 的概念与L,的部分概念做比较得到的 全概念；C为C2的子概念或子结点，记为C= 定义3设概念C(A1,B)∈L1,C(A42,B,)∈ Child1C2),若Chid(C2)不存在，则称C2为零概念. L2,若概念C与C2具有相同的外延，即A1=A2,则 表1形式背景 称概念C与概念C2互为对应概念 Table 1 Fommal con text 定义4设L1=(G1,M1,)为任一概念格 D 若C(A1,B1)∈L1,都有C'(A1,B1)∈L1成立 并且L,的二元关系关于概念格L,也成立，则称 L,为L1的子概念格，简称子格 定理1利用概念格L,更新构造概念格L的过 程中，若L2的全概念C2(42,B2)与L1的子格L1的 概念格可以用Hase图的形式可视地表现出 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved htp://www.cnki.net
更新与维护 [ 16217 ]等方面. 概念是语义描述的基本单位 ,在数据库中 ,概念 描述了各个对象的基本特征. 各属性值以及概念依 据抽象程度不同可构成一个层次结构 ,通常称为概 念树或概念层次树. 在概念层次树中 ,不同的层次表 示概念不同的抽象级别. 层次越高 ,表示概念的抽象 级别越高 ,概念也越泛化 ;层次越低 ,表示概念的抽 象级别越低 ,概念也越特化. 概念分层为在各种抽象 级别处理数据提供了方便. 概念格的 Hasse图形象 地体现了格中概念间的泛化 —特化关系. 当形式背 景中若干属性合并时 ,概念格中的部分概念提升到 一个较高层次 ,得到较为泛化的概念 ;相反 ,当形式 背景中某个属性分解为若干个新属性时 ,就会得到 更加特化的概念. 针对形式背景中的概念特化 ,即属 性分解问题 ,本文给出了一种基于概念特化的概念 格渐进式更新构造算法 UCCS,从而提高了概念格 更新构造的效率. 1 基本概念 一个二维数据表 (G, M ) ,其中 G的元素称为对 象 , M 的元素称为属性 ,若 G与 M 之间存在二元偏 序关系 G ×M = I, 在形式概念理论中称 K = (G, M , I)为一个形式背景 ,则 ( g, m ) ∈I或 gIm 表示 对象 g具有属性 m. 设 A是对象集合 G的一个子集 , B 是属性集合 M 的一个子集 , 若 A、B 满足 : 1 ) f (A ) = {m ∈M | Π g∈A, gIm } (A中对象共同属性的 集合 ) ; 2) g (B ) = { g∈G | Π m ∈B , g Im } (具有 B 中 所有属性的对象的集合 ) , 则称 C (A, B )为概念格 L ( K)的一个形式概念 ,其中 , A为该概念的外延 ,记 为A = Extent(C) , B 为该概念的内涵 , 记为 B = Intent(C) [ 1, 6 ] . 定义 1 [ 1, 6 ] 设 C1 (A1 , B1 ) , C2 (A2 , B2 )为概念 格 L的 2个不同概念 ,若 C1 < C2 Ζ A1 < A2 Ζ B2 < B1 ,并且不存在 C3 (A3 , B3 )有 C1 < C3 < C2 成立 ,则 称 C2 为 C1 的 父 概 念 或 父 结 点 , 记 为 C2 = Father(C1 ) ,若 Father (C1 )不存在 ,则称概念 C1 为 全概念; C1 为 C2 的子概念或子结点 , 记为 C1 = Child (C2 ) ,若 Child (C2 )不存在 ,则称 C2 为零概念. 表 1 形式背景 Table 1 Forma l con text A B C D 1 √ √ √ 2 √ √ 3 √ √ 4 √ √ √ 5 √ 概念格可以用 Hasse图的形式可视地表现出 来 ,图 1就是表 1的形式背景对应概念格的 Hasse 图形式. 其中 ,图 1中的每个结点表示一个形式概 念 ,结点间的连线表示概念间的父子关系. 图 1 概念格的 Hasse图 Fig. 1 Hasse diagram of concep t lattice 2 基于概念特化的概念格更新构造 对于任意给定的形式背景 ,一个属性分解为若 干个新属性 ,即形式背景中的高层概念属性特化为 多个底层概念属性 ,使得形式背景发生变化 ,因此如 何利用原形式背景已构造出的概念格 ,来快速更新 构造新形式背景的概念格 ,对于提高概念格构造效 率具有重要意义 ,该问题可以描述如下 : 设形式背景 K1 = (G1 , M1 , I1 ) ,由 K1 构造的概 念格为 L1 , P∈M1 ,若属性 P分解为属性集合 P′= { P1 , P2 , …, Pn },则形式背景由 K1 变为 K′= ( G1 , (M1 - P) ∪{ P1 , P2 , …, Pn }, I′) ,且由 K′构造的概 念格为 L′. 如何利用原格 L1 通过快速更新构造得到 概念格 L′,是本文要解决和研究的问题. 利用 L1 更 新构造出的概念格设为 L,则 L′=L. 定义 2 设 K1 = ( G1 , M1 , I1 )为形式背景 , P∈ M1 ,若属性 P分解为属性集合 { P1 , P2 , …, Pn },称 P 为分解属性. 在形式背景 K1 = (G1 , M1 , I1 )中 ,若 g ( P) =Q, 则由形式背景 K2 = (Q, { P1 , P2 , …, Pn }, I2 )构造的 概念格设为 L2 ,更新构造概念格 L 的过程是利用 L2 的概念与 L1 的部分概念做比较得到的. 定义 3 设概念 C1 (A1 , B1 ) ∈L1 , C2 (A2 , B2 ) ∈ L2 ,若概念 C1 与 C2 具有相同的外延 ,即 A1 =A2 ,则 称概念 C1 与概念 C2 互为对应概念. 定义 4 设 L′1 = (G′1 , M ′1 , I′1 )为任一概念格 , 若 C′1 (A′1 , B ′1 ) ∈L′1 ,都有 C1 ′(A′1 , B ′1 ) ∈L1 成立 并且 L1 ′的二元关系 I1 ′关于概念格 L1 也成立 ,则称 L1 ′为 L1 的子概念格 ,简称子格. 定理 1 利用概念格 L1 更新构造概念格 L的过 程中 ,若 L2 的全概念 C2 (A2 , B2 )与 L1 的子格 L′1 的 ·444· 智 能 系 统 学 报 第 3卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第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
·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.net
2) 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
第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
·448· 智能系统学报 第3卷 [4 ]CORBETT D,BURROW A L.Knowledge reuse in SEED 智能系统学报，2006,1(2)：31-38 exp biting concep tual graphs[C]//Intemational Conference ZHANG Jifu,ZHANG Sulan,HU L ihua Constrained con- on Concep tual Graphs(ICC96).Sydney,1996:56-60 cept lattice and its construction method [J ]CAA I Trans- [5 ]GOD N R,HAFEDH M H,M NEAU GW,et al Design actions on Intelligent Systems,2006,1(2):31-38 of class hierarchies based on concept(Galois)lattices[J [15战立强，刘大昕.基于概念格的频繁闭项集增量挖掘算 Theory and Application of Object Systems,1998,4(2): 法研究[J].哈尔滨工程大学学报，2007,28(2)：194 117-134 198 [6湖可云，陆玉昌，石纯一.概念格及其应用进展J]清华 ZHANG Liqiang.L U Daxin Study on FCI m ining algo- 大学学报（自然科学版），2000,40(9)：77-81 rithm based on concept lattice[J].Joumal of Harbin Engi- HU Keyun,LU Yuchang.SHI Chunyi Advances in con- neering University,2007,28(2):194-198 cept lattice and its application[J]J Tsinghua Univ(Sci& [16屠莉，陈峻，李云.一种基于属性的概念格生成 Tech),2000,40(9):77-81 及维护算法[J]计算机应用，2004,24(10)：116-118 [7]GOD N R.Incremental concept fomatin algorithm based TU Li,CHENG L ing.LI Yun Attribute-based algorithm on Galois concept)lattices J ]Computational Intelli- for constructing and maintenance of concept lattice [J ] gence,1995,11(2):246-267 Computer Applications,2004,24(10):116-118 [8谢志鹏，刘宗田.概念格的快速渐进式构造算法[J]计 [17李云，刘宗田，陈崚，等.多概念格的横向合并算法 算机学报，2002,25(5)：490-496 [J]电子学报，2004,32(11)：1849-1854 XIE ZhiPeng.LU ZongTian A fast incremental algorithm LI Yun,LU Zongtian,CHEN L ing.et al Horiontal u- for building concept lattice [J ]Chinese J Computers, nion algorithm of multiple concept lattices[J ]Acta Elec- 2002,25(5):490-496 tronica Sinica,2004,32(11):1849-1854 [9李云，刘宗田，陈崚，等.基于属性的概念格渐进式 [18蒋义勇，张继福，张素兰，基于链表结构的概念格渐进 生成算法[J]小型微型计算机系统，2004,25(10)：1768- 式构造[J]计算机工程与应用，2007,43(11)：178-180 1771 JANG Yiyong,ZHANG Jifu,ZHANG Sulan Incremental L I Yun,L U Zongtian,CHEN Ling,et al A ttribute-based construction of concept lattice based on linked list structure incremental fomation algorithm of concept lattice[J].Mini- [J].Computer Engineering and Applications,2007,43 Mico Systems,2004,25(10):1768-1771. (11):178-180 [10]Van MERW E D,OB IEDKOV S,KOUR IE D.AddIntent 作者简介： a new incremental algorithm for constructing concept lat- 杜秋香，女，1982年生，硕士研究 tices[C]//Poc of the Second Intemational Conference on 生，主要研究方向为概念格与数据挖 Fomal Concept Analysis Sydney,2004:372-385. [11 WANG Zhihai,HU Keyun,HU Xuegang General and in- cremental algorithms of rule extraction based on concept lattice J].Chinese J Computers,1999,22(1):66-70. [12胡可云，陆玉昌，石纯一.基于概念格的分类和关联规 则的集成挖掘方法[J]软件学报，2000,11(11)：1478- 张继福，男，1963年生，教授，博士， 1483 主要研究方向为数据挖掘、模式识别与 HU Keyun,LU Yuchang,SHIChunyi An integrated m in- 智能信息系统.已发表学术论文60余 ing approach for classification and association rule based on 篇，其中被SC1E收录20余篇. concept lattice J ]Joumal of Softare,2000,11 (11): 1478-1483 [13刘宗田，强宇，周文，等.一种模糊概念格模型及其 渐进式构造算法[J]计算机学报，2007,30(2)：184- 张素兰，女，1971年生，副教授，主 188 要研究方向为概念格与数据挖掘.己发 LU Zongtian,QANG Yu,ZHOU Wen,et al A fuzzy 表学术论文20余篇，其中被SCkE收 concept lattice model and its incremental construction algo- 录10余篇 rithm [J ]Chinese J Computers,2007,30(2):184-188 [14张继福，张素兰，胡立华，约束概念格及其构造方法[J] 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
[ 4 ] CORBETT D, BURROW A L. Knowledge reuse in SEED exp loiting concep tual graphs[ C ] / / International Conference on Concep tual Graphs( ICC’96). Sydney, 1996: 56260. [ 5 ] GOD IN R, HAFEDH M H, M INEAU G W , et al. Design of class hierarchies based on concep t( Galois) lattices[J ]. Theory and App lication of Object System s, 1998, 4 ( 2 ) : 1172134. [ 6 ]胡可云 ,陆玉昌 ,石纯一. 概念格及其应用进展 [J ]. 清华 大学学报 (自然科学版 ) , 2000, 40 (9) : 77281. HU Keyun, LU Yuchang, SH I Chunyi. Advances in con2 cep t lattice and its app lication[J ]. J Tsinghua Univ ( Sci & Tech) , 2000, 40 (9) : 77281. [ 7 ] GOD IN R. Incremental concep t formation algorithm based on Galois ( concep t) lattices [ J ]. Computational Intelli2 gence, 1995, 11 (2) : 2462267. [ 8 ]谢志鹏 ,刘宗田. 概念格的快速渐进式构造算法 [J ]. 计 算机学报 , 2002, 25 (5) : 4902496. X IE ZhiPeng, L IU ZongTian. A fast incremental algorithm for building concep t lattice [ J ]. Chinese J Computers, 2002, 25 (5) : 4902496. [ 9 ]李 云 ,刘宗田 ,陈 崚 ,等. 基于属性的概念格渐进式 生成算法 [J ]. 小型微型计算机系统 , 2004, 25 (10) : 17682 1771. L I Yun, L IU Zongtian, CHEN L ing, et al. A ttribute2based incremental formation algorithm of concep t lattice[J ]. M ini2 M icro System s, 2004, 25 (10) : 176821771. [ 10 ]Van MERW E D, OB IEDKOV S, KOUR IE D. Add Intent: a new incremental algorithm for constructing concep t lat2 tices[C ] / /Proc of the Second International Conference on Formal Concep t Analysis. Sydney, 2004: 3722385. [ 11 ]WANG Zhihai, HU Keyun, HU Xuegang. General and in2 cremental algorithm s of rule extraction based on concep t lattice[J ]. Chinese J Computers, 1999, 22 (1) : 66270. [ 12 ]胡可云 ,陆玉昌 ,石纯一. 基于概念格的分类和关联规 则的集成挖掘方法 [J ]. 软件学报 , 2000, 11 ( 11) : 14782 1483. HU Keyun, LU Yuchang, SH IChunyi. An integrated m in2 ing app roach for classification and association rule based on concep t lattice [ J ]. Journal of Software, 2000, 11 ( 11 ) : 147821483. [ 13 ]刘宗田 ,强 宇 ,周 文 ,等. 一种模糊概念格模型及其 渐进式构造算法 [J ]. 计算机学报 , 2007, 30 ( 2 ) : 1842 188. L IU Zongtian, Q IANG Yu, ZHOU W en, et al. A fuzzy concep t lattice model and its incremental construction algo2 rithm [J ]. Chinese J Computers, 2007, 30 (2) : 1842188. [ 14 ]张继福 ,张素兰 ,胡立华. 约束概念格及其构造方法 [J ]. 智能系统学报 , 2006, 1 (2) : 31238. ZHANG Jifu, ZHANG Sulan, HU L ihua. Constrained con2 cep t lattice and its construction method [J ]. CAA I Trans2 actions on Intelligent Systems, 2006, 1 (2) : 31238. [ 15 ]战立强 ,刘大昕. 基于概念格的频繁闭项集增量挖掘算 法研究 [J ]. 哈尔滨工程大学学报 , 2007, 28 ( 2) : 1942 198. ZHANG L iqiang, L IU Daxin. Study on FCI m ining algo2 rithm based on concep t lattice[J ]. Journal of Harbin Engi2 neering University, 2007, 28 (2) : 1942198. [ 16 ]屠 莉 ,陈 崚 ,李 云. 一种基于属性的概念格生成 及维护算法 [J ]. 计算机应用 , 2004, 24 (10) : 1162118. TU L i, CHENG L ing, L I Yun. A ttribute2based algorithm for constructing and maintenance of concep t lattice [ J ]. Computer App lications, 2004, 24 (10) : 1162118. [ 17 ]李 云 ,刘宗田 ,陈 崚 ,等. 多概念格的横向合并算法 [J ]. 电子学报 , 2004, 32 (11) : 184921854. L I Yun, L IU Zongtian, CHEN L ing, et al. Horizontal u2 nion algorithm of multip le concep t lattices[J ]. Acta Elec2 tronica Sinica, 2004, 32 (11) : 184921854. [ 18 ]蒋义勇 ,张继福 ,张素兰. 基于链表结构的概念格渐进 式构造 [J ]. 计算机工程与应用 , 2007, 43 (11) : 1782180. J IANG Yiyong, ZHANG Jifu, ZHANG Sulan. Incremental construction of concep t lattice based on linked list structure [J ]. Computer Engineering and App lications, 2007, 43 (11) : 1782180. 作者简介 : 杜秋香 ,女 , 1982 年生 ,硕士研究 生 ,主要研究方向为概念格与数据挖 掘. 张继福 ,男 , 1963年生 ,教授 ,博士 , 主要研究方向为数据挖掘、模式识别与 智能信息系统. 已发表学术论文 60余 篇 ,其中被 SCI、EI收录 20余篇. 张素兰 ,女 , 1971年生 ,副教授 ,主 要研究方向为概念格与数据挖掘. 已发 表学术论文 20余篇 ,其中被 SCI、EI收 录 10余篇. ·448· 智 能 系 统 学 报 第 3卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net