第2期 张继福，等：约束概念格及其构造方法 ·35· 和定义17可知，约束概念格中的任一边也都为一般 造 概念格中的一条边，由定义18可知，背景知识为第 当为第类背景知识时，即用户不关心的属性 一类时，约束概念格为一般概念格的子格 集为X、XVY(X或者Y)或者X∧Y(X且y),则概 引理2当背景知识为第Ⅱ类时，约束概念格 念格结点的内涵为不含有X、Y、或者XY的属性 减少了一般概念格的中的节点数和边数 集，可用如下方法构造： 证明当背景知识为第Ⅱ类时，约束概念格中 1)将含有不关心属性的对象做上删除标志，不 的任一结点内涵都是由用户关心的不含有某属性子 关心的属性值记为空值； 集的集合组成，而一般概念格中的节点是所有原始 2)渐进式生成概念格时，如果结点为空时，先生 形式背景中的属性集合，所以，约束概念格中的节点 成不含有删除标志的对象的格结点： 比一般概念格的节点少，同样由定义4、定义16和 3)然后求解其与前面有删除标志对象结点的关 定义17可知，约束概念格中的边也比一般概念格中 系（交集）.由交的结果决定是否生成新结点若交集 的边少.因此，当背景知识为第类时，约束概念格 不为空时，则生成新结点，否则不做任何处理， 减少了一般概念格中的节点数和边数. 4)再求解带删除标志对象结点间的关系（交 定理1约束概念格比一般概念格的格结构的 集).由交集的结果决定是否生成新结点.若交集不 复杂性要低 为空时，则生成新结点，否则不做任何处理 证明：由引理1和2容易得证 由上述算法的构造思想及相关定理，可给出如 定理2当P(O,D)为空时，约束概念格退 下约束概念格构造算法CCLA」 化为一般概念格 算法CCLA(constrained concept lattice algo 证明给定一个形式背景T=(U,1,),一般概 rithm) 念格的任意结点h=(O,D),由于P为空，则P(hM 输入：原约束概念格L",用户关心的属性子集 为真，因而(O,D),P)也是约束概念格的一个结 X、XVY(X或者)、X∧Y(X且)，用户不关心 点.另外设h=(O,D)和m=(O2,D2)是一般概 的属性子集7X、XVY(非X或者非Y)、 念格2个不同的结点，而且h<,由于P为空， X∧7Y(非X且非) (O,D),P)和(O2,D2),)也是约束概念格中的 输出：更新后的约束概念格L, 两个不同的结点，由定义4和16可得 l)Mark:=中：/*Mark约束概念格结点集合 (O,D),)<(O,D),P).因此，约束概念格退 */ 化为一般概念格. 2)对渐进式追加的每个对象x, 定理3约束概念格是完备的， 3)F输入用户关心的属性子集X、X∧Y或者 证明：对一般概念格中的一个点，凡是满足P X VY Then 的点都在约束概念格中，那么h=(O,D,P)关于 4)f关心的属性子集为X、或者X∧Y Then R满足完备性O三U:f(O)=fd∈1|廿x∈O: 5)fX∈f(x)or Xy∈写f(x)Then xRd且P(O,D)=,T.和D∈I:g(D)= 6)Generate( {x∈U|d∈1：xRd且P(O,D)=.T.同时成 7)Else 立，显然约束概念格是完备的 8)IfX∈f(x)orY∈f(x)Then 4.2基于背景知识的约束概念格构造 9)Generate() 当为第I类背景知识时，即用户关心的属性集 10)End if 为X、XVY(x或者Y)或者X∧Y(X且)，则概念 11)End if 格结点的内涵只能为含有X、Y、或者XY的属性 12)End if 集.由引理1可知，由用户关心的属性集形成的概念 13)Else 格为原概念格的子格，那么在概念格构造过程中，只 14)f不关心的属性子集为7X、或者7XV 需要对含有关心属性的对象进行概念格的渐进式构 Y Then 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net和定义 17 可知 ,约束概念格中的任一边也都为一般 概念格中的一条边 ,由定义 18 可知 ,背景知识为第 一类时 ,约束概念格为一般概念格的子格. 引理 2 当背景知识为第 Ⅱ类时 ,约束概念格 减少了一般概念格的中的节点数和边数. 证明 当背景知识为第 Ⅱ类时 ,约束概念格中 的任一结点内涵都是由用户关心的不含有某属性子 集的集合组成 ,而一般概念格中的节点是所有原始 形式背景中的属性集合 ,所以 ,约束概念格中的节点 比一般概念格的节点少 ,同样由定义 4、定义 16 和 定义 17 可知 ,约束概念格中的边也比一般概念格中 的边少. 因此 ,当背景知识为第 Ⅱ类时 , 约束概念格 减少了一般概念格中的节点数和边数. 定理 1 约束概念格比一般概念格的格结构的 复杂性要低. 证明 :由引理 1 和 2 容易得证. 定理 2 当 P ( ( O , D) ) 为空时 ,约束概念格退 化为一般概念格. 证明 :给定一个形式背景 T = (U , I , R) ,一般概 念格的任意结点 h = ( O , D) ,由于 P 为空 ,则 P( h) 为真 ,因而 ( ( O , D) , P) 也是约束概念格的一个结 点. 另外设 h1 = ( O1 , D1 ) 和 h2 = ( O2 , D2 ) 是一般概 念格 2 个不同的结点 ,而且 h1 < h2 , 由于 P 为空 , ( ( O1 , D1 ) , P) 和( ( O2 , D2 ) , P) 也是约束概念格中的 两 个 不 同 的 结 点 , 由 定 义 4 和 16 可 得 ( ( O1 , D1 ) , P) < ( ( O2 , D2 ) , P) . 因此 ,约束概念格退 化为一般概念格. 定理 3 约束概念格是完备的. 证明 :对一般概念格中的一个点 ,凡是满足 P 的点都在约束概念格中 ,那么 h = ( ( O , D) , P) 关于 R 满足完备性 Ζ O ΑU : f ( O) = { d ∈I ︱Πx ∈O : x R d} 且 P ( ( O , D) ) = . T. 和 ΠD Α I : g ( D) = { x ∈U ︱Πd ∈I : x R d}且 P ( ( O , D) ) = . T. 同时成 立 ,显然约束概念格是完备的. 412 基于背景知识的约束概念格构造 当为第 Ⅰ类背景知识时 ,即用户关心的属性集 为 X 、X ∨Y ( X 或者 Y) 或者 X ∧Y ( X 且 Y) ,则概念 格结点的内涵只能为含有 X 、Y 、或者 X Y 的属性 集. 由引理 1 可知 ,由用户关心的属性集形成的概念 格为原概念格的子格 ,那么在概念格构造过程中 ,只 需要对含有关心属性的对象进行概念格的渐进式构 造. 当为第 Ⅱ类背景知识时 ,即用户不关心的属性 集为 X 、X ∨Y ( X 或者 Y) 或者 X ∧Y ( X 且 Y) ,则概 念格结点的内涵为不含有 X 、Y 、或者 X Y 的属性 集 ,可用如下方法构造 : 1) 将含有不关心属性的对象做上删除标志 ,不 关心的属性值记为空值; 2) 渐进式生成概念格时 ,如果结点为空时 ,先生 成不含有删除标志的对象的格结点; 3) 然后求解其与前面有删除标志对象结点的关 系(交集) . 由交的结果决定是否生成新结点. 若交集 不为空时 ,则生成新结点 ,否则不做任何处理. 4) 再求解带删除标志对象结点间的关系 (交 集) . 由交集的结果决定是否生成新结点. 若交集不 为空时 ,则生成新结点 ,否则不做任何处理. 由上述算法的构造思想及相关定理 ,可给出如 下约束概念格构造算法 CCLA. 算法 CCLA (constrained concept lattice algo2 rit hm) 输入 :原约束概念格 L w ,用户关心的属性子集 X 、X ∨Y ( X 或者 Y) 、X ∧Y ( X 且 Y) ,用户不关心 的属性子集 ┓X 、┓X ∨┓Y (非 X 或者非 Y ) 、 ┓X ∧┓Y (非 X 且非 Y) . 输出 : 更新后的约束概念格 L r . 1) Mark : =Φ;/ 3 Mark 约束概念格结点集合 3 / 2) 对渐进式追加的每个对象 x , 3) If 输入用户关心的属性子集 X 、X ∧Y 或者 X ∨Y Then 4) If 关心的属性子集为 X 、或者 X ∧Y Then 5) If X ∈f ( x) or X Y ∈f ( x) Then 6) Generate () 7) Else 8) If X ∈f ( x) or Y ∈f ( x) Then 9) Generate () 10) End if 11) End if 12) End if 13) Else 14) If 不关心的属性子集为 ┓X 、或者 ┓X ∨ ┓Y Then 第 2 期 张继福 ,等 :约束概念格及其构造方法 · 53 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net