·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