第1卷第2期 智能系统学报 Vol.1 Ng 2 2006年10月 CAAI Transactions on Intelligent Systems 0ct.2006 约束概念格及其构造方法 张继福2，张素兰，胡立华 (1.太原科技大学计算机科学与技术学院，山西太原030024,2.中国科学院自动化所模式识别国家重点实验室，北京100080) 摘要：概念格是一种有效的数据分析和知识提取的形式化工具.然而，随着要处理的数据量的剧增，基于原始形式 背景构造出的概念格结点数目庞大，占用大的存储空间，同时概念格结点中一些属性集形成的内涵，用户并不都感 兴趣，因而从中提取用户需求知识费时.为了降低概念格构造的时空复杂性，增强实用性和针对性，首先采用谓词逻 辑描述用户感兴趣的背景知识，并将背景知识引入到概念格结构中，提出了一种新的概念格：约束概念格.在此基础 上，提出了基于背景知识的约束概念格构造算法CCLA.理论分析表明，该算法能有效地减少概念格的存储空间和建 格时间.最后，采用恒星天体光谱数据作为形式背景，实验验证了该算法的有效性， 关键词：数据挖掘；约束概念格；谓词逻辑；背景知识；恒星光谱数据 中图分类号：TP311文献标识码：A文章编号：1673-4785(2006)02-0031-08 Constrained concept lattice and its construction method ZHAN GJi-fu'2,ZHAN G Su-lan',HU Li-hua' (1.School of Computer Science and Technology,Taiyuan University of Science and Technology,Taiyuan 030024,China; 2.National Laboratory of Pattern Recognition,Institute of Automation,Chinese Academy of Sciences,Beijing 100080,China) Abstract:Concept lattice is an effective formal tool for data analysis and knowledge mining.However, with the increase of data volume,the node number of the constructed concept lattice from the original for- mal context usually increases enormously,and large storage is required accordingly.Meantime,users are not interested in all intensions of attributes set,and more computational time is unnecessarily consumed as a result.In order to reduce time and storage complexity and improve the utility and pertinence to the con- cept lattice construction,predicate logic is used to describe the user interested background knowledge,and a new concept lattice structure-constrained concept lattice is presented.Then based on the background knowledge,a construction algorithm (CCLA)is also provided.Through some theoretical analysis,it is shown that the proposed algorithm can reduce the storage and time complexity of concept lattice construc- tion process.Finally,the experiments with celestial body spectra as the formal context validate the pro- posed algorithm. Key words:data mining;constrained concept lattice;predicate logic;background knowledge;star spectra data 概念格是一种有效的形式化数据分析工具，由和属性（特征、项目）之间的关系.概念内涵和外延的 德国的R.Wille教授在20世纪80年代初提出). 统一，生动而简洁地表明了概念之间的泛化和特化 概念格的每个结点是一个形式概念，由内涵（属性 关系，成为一种很有用的数据分析和知识提取工具. 集)和外延（拥有该属性集的实体集）两部分组成.这 这种形式概念分析工具己经被成功地用于数字图书 种格的结构及其相应的哈希图形式，反映了一种概 馆、文献检索、软件工程基于案例数据分析、知识发 念层次结构，本质上体现了实体（对象、记录、交易） 现等领域2.4. 目前，国内外学者对概念格进行了多方面深入 收稿日期：200602-15. 研究：概念格的构造算法研究；基于概念格的知识提 基金项目：因家自然科学基金资助项目(60573075) 取（数据分类、聚类及关联规则提取）；概念格与其他 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
第 1 卷第 2 期 智 能 系 统 学 报 Vol. 1 №. 2 2006 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2006 约束概念格及其构造方法 张继福1 ,2 , 张素兰1 ,胡立华1 (1.太原科技大学 计算机科学与技术学院 ,山西 太原 030024 ; 2.中国科学院自动化所 模式识别国家重点实验室 ,北京 100080) 摘 要 :概念格是一种有效的数据分析和知识提取的形式化工具. 然而 ,随着要处理的数据量的剧增 ,基于原始形式 背景构造出的概念格结点数目庞大 ,占用大的存储空间 ,同时概念格结点中一些属性集形成的内涵 ,用户并不都感 兴趣 ,因而从中提取用户需求知识费时. 为了降低概念格构造的时空复杂性 ,增强实用性和针对性 ,首先采用谓词逻 辑描述用户感兴趣的背景知识 ,并将背景知识引入到概念格结构中 ,提出了一种新的概念格 :约束概念格. 在此基础 上 ,提出了基于背景知识的约束概念格构造算法 CCLA. 理论分析表明 ,该算法能有效地减少概念格的存储空间和建 格时间. 最后 , 采用恒星天体光谱数据作为形式背景 ,实验验证了该算法的有效性. 关键词 :数据挖掘 ;约束概念格 ;谓词逻辑 ;背景知识 ;恒星光谱数据 中图分类号 : TP311 文献标识码 :A 文章编号 :167324785 (2006) 0220031208 Constrained concept lattice and its construction method ZHAN G Ji2fu 1 ,2 ,ZHAN G Su2lan 1 , HU Li2hua 1 (1. School of Computer Science and Technology , Taiyuan University of Science and Technology , Taiyuan 030024 , China ; 2. National Laboratory of Pattern Recognition , Institute of Automation , Chinese Academy of Sciences , Beijing 100080 , China) Abstract : Concept lattice is an effective formal tool for data analysis and knowledge mining. However , with the increase of data volume , t he node number of the constructed concept lattice from t he original for2 mal context usually increases enormously , and large storage is required accordingly. Meantime , users are not interested in all intensions of attributes set , and more comp utational time is unnecessarily consumed as a result. In order to reduce time and storage complexity and improve t he utility and pertinence to t he con2 cept lattice construction ,p redicate logic is used to describe t he user interested background knowledge , and a new concept lattice struct ure2constrained concept lattice is presented. Then based on t he background knowledge , a construction algorit hm (CCLA) is also provided. Through some t heoretical analysis , it is shown t hat t he proposed algorit hm can reduce t he storage and time complexity of concept lattice construc2 tion process. Finally , the experiments wit h celestial body spectra as t he formal context validate t he pro2 posed algorit hm. Keywords :data mining ; constrained concept lattice ; predicate logic ; background knowledge ; star spectra data 收稿日期 :2006202215. 基金项目 :国家自然科学基金资助项目(60573075) . 概念格是一种有效的形式化数据分析工具 ,由 德国的 R. Wille 教授在 20 世纪 80 年代初提出[1 ] . 概念格的每个结点是一个形式概念 ,由内涵 (属性 集) 和外延(拥有该属性集的实体集) 两部分组成. 这 种格的结构及其相应的哈希图形式 ,反映了一种概 念层次结构 ,本质上体现了实体 (对象、记录、交易) 和属性(特征、项目) 之间的关系. 概念内涵和外延的 统一 ,生动而简洁地表明了概念之间的泛化和特化 关系 ,成为一种很有用的数据分析和知识提取工具. 这种形式概念分析工具已经被成功地用于数字图书 馆、文献检索、软件工程、基于案例数据分析、知识发 现等领域[2 - 4 ] . 目前 ,国内外学者对概念格进行了多方面深入 研究 :概念格的构造算法研究 ;基于概念格的知识提 取(数据分类、聚类及关联规则提取) ;概念格与其他 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·32· 智能系统学报 第1卷 理论的融合（粗集遗传算法和模糊理论）等5·)：其 用知识（关联规则、分类规则、聚类规则等）费时，特 中，概念格的结构和构造效率始终是研究的重点，先 别随着要处理的数据量的激增，这些不足日益明显 后提出了许多种格结构及其构造算法o.12! 所以，基于背景知识的概念格构造研究无论在理论 为了提高概念格的构造效率，减少时空复杂性， 上还是在实际应用上都具有重要的意义 增强实用性和针对性，首先采用谓词逻辑作为用户 2一般概念格 感兴趣的背景知识，将背景知识引入到概念格结构 中，提出了一种新的概念格：约束概念格.在此基础 定义1给定一个形式背景为三元组T=(U 上，提出了一种基于背景知识的约束概念格构造算 I,),其中U为对象集，1为属性集，R是U与1之 法CCLA,理论证明了该算法能有效地节省概念格 间存在的一个二元偏序关系.由这个二元偏序关系 的存储空间和建格时间.最后采用天体专家知识作 可以形成一个概念格L. 为背景知识，恒星天体光谱数据作为形式背景，构造 定义2概念格的每一个结点为一个形式概念 了约束概念格，从而验证了约束概念格构造算法的 h=(O,D),其中，O∈P(U称为概念的外延，D∈ 有效性」 P()称为概念的内涵，D是由0中对象（记录、交 易)的共同特征（属性、项目）所组成的集合.具有这 1问题的提出 种结构的格称为一般概念格(General concept lat- 概念格是一种有效的数据挖掘和知识提取的形 tice) 式化分析工具，数据挖掘是在积累了巨量数据集后， 定义3(O,D)关于R满足完备性台0二U: 从中挖掘出有效的、新颖的、潜在有用的、最终可理 f(O)=fd∈I|Vx∈O:xRd和VD∈I:g(D)= 解并加以有目的的利用知识的过程，是从宏观角度 fx∈U|廿d∈I:xR同时成立. 利用积累的巨量数据进行知识抽象的高级阶段.可 定义4设h=(O,D)和加=(02，D2)是2 以看出数据挖掘是一项高级的智能活动，因此数据 个不同的结点，则m<加D2CD1OCO,如果 挖掘的过程离不开背景知识的支持.目前将背景知 不存在s=(O,D)有m<s<加成立，则加称 识融合在数据挖掘过程中的研究还处于初始阶段， 为的父结点父概念，直接前趋，m称为：的子 因而使得数据挖掘技术在实际应用中受到了一定的 结点子概念，直接后继) 限制2.).以用户提供的背景知识（感兴趣、不感 表1是一个形式背景，其中对象集U=1,2,3, 兴趣)为指导形成概念格，不仅有利于挖掘出用户感 4,5},属性集1={A,B,C,D,E母，R描述了U中所 兴趣的知识，而且也可以减少概念格构造的时空复 具有的1中的属性值集，该形式背景所构成的一般 杂性 概念格如图1所示 谓词逻辑是一种形式语言系统，它用逻辑方法 表1形式背景 研究推理的规律，适合于表示事物的状态、属性、概 Table 1 Formal context 念等事实性的知识，也可以用来表示事物之间确定 U A B C D E 的因果关系，即规则.因此具有自然性精确性、严密 性和容易实现等优点，是一种广泛使用的知识表示 技术.采用谓词逻辑作为表示指导概念格构造的用 3 户感兴趣的背景知识是可行的。 然而，一般概念格都是基于形式背景进行构造 的，一些属性组合成的概念格内涵，用户并不都感兴 趣，例如利用概念格从海量天体数据中挖掘分类知 ({123,45.Φ) 识时，从原始的形式背景（光度、温度）中由属性光 度、温度组合形成的概念格的内涵对7类恒星光谱 (1,4140(1,231.B)(2.4.D(3.5,C) 数据的分类就无任何指导意义，因此，在概念格的构 ({1},AB (4,AD)(3.BC)({2}.BDE) 造过程中，用户对含有这些属性组成的内涵是不感 兴趣的.同时，基于形式背景构造出含有所有属性组 (中，ABCDE) 合成内涵的结点明显存在以下不足：构造的结点数 图1一般概念格 目庞大，占用大的存储空间，基于这些概念格提取有 Fig 1 General concept lattice 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
理论的融合(粗集、遗传算法和模糊理论) 等[5 - 9 ] ;其 中 ,概念格的结构和构造效率始终是研究的重点 ,先 后提出了许多种格结构及其构造算法[10 - 12 ] . 为了提高概念格的构造效率 ,减少时空复杂性 , 增强实用性和针对性 ,首先采用谓词逻辑作为用户 感兴趣的背景知识 ,将背景知识引入到概念格结构 中 ,提出了一种新的概念格 :约束概念格. 在此基础 上 ,提出了一种基于背景知识的约束概念格构造算 法 CCLA ,理论证明了该算法能有效地节省概念格 的存储空间和建格时间. 最后采用天体专家知识作 为背景知识 ,恒星天体光谱数据作为形式背景 ,构造 了约束概念格 ,从而验证了约束概念格构造算法的 有效性. 1 问题的提出 概念格是一种有效的数据挖掘和知识提取的形 式化分析工具 ,数据挖掘是在积累了巨量数据集后 , 从中挖掘出有效的、新颖的、潜在有用的、最终可理 解并加以有目的的利用知识的过程 ,是从宏观角度 利用积累的巨量数据进行知识抽象的高级阶段. 可 以看出数据挖掘是一项高级的智能活动 ,因此数据 挖掘的过程离不开背景知识的支持. 目前将背景知 识融合在数据挖掘过程中的研究还处于初始阶段 , 因而使得数据挖掘技术在实际应用中受到了一定的 限制[ 12 - 13 ] . 以用户提供的背景知识 (感兴趣、不感 兴趣) 为指导形成概念格 ,不仅有利于挖掘出用户感 兴趣的知识 ,而且也可以减少概念格构造的时空复 杂性. 谓词逻辑是一种形式语言系统 ,它用逻辑方法 研究推理的规律 ,适合于表示事物的状态、属性、概 念等事实性的知识 ,也可以用来表示事物之间确定 的因果关系 ,即规则. 因此具有自然性、精确性、严密 性和容易实现等优点 ,是一种广泛使用的知识表示 技术. 采用谓词逻辑作为表示指导概念格构造的用 户感兴趣的背景知识是可行的. 然而 ,一般概念格都是基于形式背景进行构造 的 ,一些属性组合成的概念格内涵 ,用户并不都感兴 趣 ,例如利用概念格从海量天体数据中挖掘分类知 识时 ,从原始的形式背景 (光度、温度) 中由属性光 度、温度组合形成的概念格的内涵对 7 类恒星光谱 数据的分类就无任何指导意义 ,因此 ,在概念格的构 造过程中 ,用户对含有这些属性组成的内涵是不感 兴趣的. 同时 ,基于形式背景构造出含有所有属性组 合成内涵的结点明显存在以下不足 :构造的结点数 目庞大 ,占用大的存储空间 ,基于这些概念格提取有 用知识(关联规则、分类规则、聚类规则等) 费时 ,特 别随着要处理的数据量的激增 ,这些不足日益明显. 所以 ,基于背景知识的概念格构造研究无论在理论 上还是在实际应用上都具有重要的意义. 2 一般概念格 定义 1 给定一个形式背景为三元组 T = (U , I , R) ,其中 U 为对象集 , I 为属性集 , R 是 U 与 I 之 间存在的一个二元偏序关系. 由这个二元偏序关系 可以形成一个概念格 L . 定义 2 概念格的每一个结点为一个形式概念 h = ( O , D) , 其中 , O ∈ρ(U) 称为概念的外延 , D ∈ ρ( I) 称为概念的内涵 , D 是由 O 中对象 (记录、交 易) 的共同特征(属性、项目) 所组成的集合. 具有这 种结构的格称为一般概念格 ( General concept lat2 tice) . 定义 3 ( O , D) 关于 R 满足完备性 Ζ ΠO ΑU : f ( O) = { d ∈I ︱Πx ∈O : x R d} 和 ΠD Α I : g ( D) = { x ∈U ︱Πd ∈I : x R d}同时成立. 定义 4 设 h1 = ( O1 , D1 ) 和 h2 = ( O2 , D2 ) 是 2 个不同的结点 ,则 h1 < h2 Ζ D2 < D1 Ζ O1 < O2 ,如果 不存在 h3 = ( O3 , D3 ) 有 h1 < h3 < h2 成立 ,则 h2 称 为 h1 的父结点(父概念 ,直接前趋) , h1 称为 h2 的子 结点(子概念 ,直接后继) . 表 1 是一个形式背景 ,其中对象集 U = { 1 ,2 ,3 , 4 ,5} , 属性集 I = { A , B , C, D , E} , R 描述了 U 中所 具有的 I 中的属性值集 ,该形式背景所构成的一般 概念格如图 1 所示. 表 1 形式背景 Table 1 Formal context U I A B C D E 1 √ √ 2 √ √ √ 3 √ √ 4 √ √ 5 √ 图 1 一般概念格 Fig11 General concept lattice · 23 · 智 能 系 统 学 报 第 1 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第2期 张继福，等：约束概念格及其构造方法 ·33 3 面向概念格构造的背景知识 interest()为一谓词公式，乃(D表示一个格结点， 如果其内涵x是由用户关心的属性子集y%或Ⅵ组 在概念格的构造过程中，由所有属性组成的内 成，则该结点为关心结点 涵并非都是用户感兴趣的，同时一些属性组成的内 性质1谓词公式P、B和P描述了第I类 涵在实际应用中并无意义.因此，可以根据用户对数 背景知识. 据集的兴趣、了解、认识等作背景知识为指导来构成 证明通过∧（与）、V(或)运算所形成的谓词 概念格，从而使概念格的结构更具有针对性和实用 公式P、B和P描述了这样一类格结点，其内涵 性.采用谓词逻辑表示知识时，首先定义描述背景知 是由用户关心的含有某属性集合组成，因此描述了 识的谓词，并指出每个谓词的确切含义，然后再用连 第I类背景知识. 接词（人（与）、V(或)、（非）、（蕴含）、（全称量 以表1的形式背景为例，若用户关心的概念格 词)、3（存在量词）)把有关的谓词连接起来，形成一 结点的内涵含有属性A、属性A且B、属性A或B, 个谓词公式以表达一条完整的背景知识 则形成的概念格如图2~4所示 一个二维表可表示为一个n元有序组的集合， ({123,45,Φ) 一个集合可用一个特性谓词刻画，故一个n元有序 组的集合可用一个n元特性谓词刻画.基于一阶谓 词逻辑的概念格构造中所涉及到的背景知识描述如 ({1.41.A) 下： 定义5一个格结点集合G()为一个一元谓 ({1},AB) ({4},AD) 词，表示：是一个格结点 （Φ，ABD) 定义6 Concept(:,x,y)为一个三元谓词，表 示格结点：具有内涵x,外延y 图2属性A的概念格 定义7 Include(x,以表示由某属性集y组成 Fig 2 Concept lattice on attribute A 的内涵x. 定义8 Interest()为一个一元谓词，表示： ({12,34,5.Φ) 是一个关心结点. 概念格结点的内涵由属性组成，在实际的概念 ({1,4,A) (1,231,B) 格构造中，用户往往对含有某些属性组合的内涵和 不含有某些属性组合的内涵感兴趣，因此，可将背景 (1,AB) ({4},AD)({31,BC)({2,BDE) 知识分为2类知识：其中内涵由用户关心的含有某 些属性集合组成的知识定义为第【类背景知识，内 (中，ABCDE) 涵由用户关心的不含有某些属性集合组成的知识定 义为第类背景知识. 图3属性AVB的概念格 定义9设P(Z)=:(G(:)∧ Fig 3 Concept lattice on attribute A or B concept(=,x,y)Ainclude(x,yo))-interest(=)) 为一谓词公式，P()表示一个格结点，如果其内涵 ({1,2.3,4,5,Φ) x是由用户关心的属性子集组成，则该结点为关 心结点 ({1},AB) 定义10设B(Z)=:(G(:)∧ concept(=,x,y)A (include (x,yo)Ainclude (x. 图4属性A八B的概念格 n))interest()为一谓词公式，B(z表示一 Fig 4 Concept lattice on attribute A and B 个格结点，如果其内涵x是由用户关心的属性子集 定义12设P(z)=:((G(:)∧concept y”组成，则该结点为关心结点 (a,x,y)Ainclude(x,o)-interest()为一谓 定义11乃(Z)=:((G(:)∧concept 词公式，P:(刀表示一个格结点，如果其内涵是由用 (:,x,y)∧(include(x,w)Vinclude(x,n)→ 户关心的不含属性子集%组成，则该结点为关心结 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
3 面向概念格构造的背景知识 在概念格的构造过程中 ,由所有属性组成的内 涵并非都是用户感兴趣的 ,同时一些属性组成的内 涵在实际应用中并无意义. 因此 ,可以根据用户对数 据集的兴趣、了解、认识等作背景知识为指导来构成 概念格 ,从而使概念格的结构更具有针对性和实用 性. 采用谓词逻辑表示知识时 ,首先定义描述背景知 识的谓词 ,并指出每个谓词的确切含义 ,然后再用连 接词( ∧(与) 、∨(或) 、┓(非) 、→(蕴含) 、Π(全称量 词) 、ϖ (存在量词) ) 把有关的谓词连接起来 ,形成一 个谓词公式以表达一条完整的背景知识. 一个二维表可表示为一个 n 元有序组的集合 , 一个集合可用一个特性谓词刻画 ,故一个 n 元有序 组的集合可用一个 n 元特性谓词刻画. 基于一阶谓 词逻辑的概念格构造中所涉及到的背景知识描述如 下 : 定义 5 一个格结点集合 G( z) 为一个一元谓 词 ,表示 z 是一个格结点. 定义 6 Concept ( z , x , y ) 为一个三元谓词 ,表 示格结点 z 具有内涵 x ,外延 y. 定义 7 Include ( x , y) 表示由某属性集 y 组成 的内涵 x . 定义 8 Interest ( z) 为一个一元谓词 ,表示 z 是一个关心结点. 概念格结点的内涵由属性组成 ,在实际的概念 格构造中 ,用户往往对含有某些属性组合的内涵和 不含有某些属性组合的内涵感兴趣 ,因此 ,可将背景 知识分为 2 类知识 :其中内涵由用户关心的含有某 些属性集合组成的知识定义为第 Ⅰ类背景知识 ,内 涵由用户关心的不含有某些属性集合组成的知识定 义为第 Ⅱ类背景知识. 定 义 9 设 P1 ( Z ) = Πz ( ( G ( z ) ∧ concept ( z , x , y ) ∧include ( x , y0 ) ) →interest ( z) ) 为一谓词公式 , P1 ( Z) 表示一个格结点 ,如果其内涵 x 是由用户关心的属性子集 y 0 组成 ,则该结点为关 心结点. 定 义 10 设 P2 ( Z ) = Πz ( ( G ( z ) ∧ concept ( z , x , y ) ∧ (include ( x , y0 ) ∧include ( x , y1 ) ) ) →interest ( z) ) 为一谓词公式 , P2 ( Z) 表示一 个格结点 ,如果其内涵 x 是由用户关心的属性子集 y 0 、y1 组成 ,则该结点为关心结点. 定义 11 P3 ( Z) = Πz ( ( G ( z) ∧concept ( z , x , y ) ∧(include ( x , y0 ) ∨include ( x , y1 ) ) ) → interest ( z) ) 为一谓词公式 , P3 ( Z) 表示一个格结点 , 如果其内涵 x 是由用户关心的属性子集 y 0 或 y1 组 成 ,则该结点为关心结点. 性质 1 谓词公式 P1 、P2 和 P3 描述了第 Ⅰ类 背景知识. 证明 通过 ∧(与) 、∨(或) 运算所形成的谓词 公式 P1 、P2 和 P3 描述了这样一类格结点 ,其内涵 是由用户关心的含有某属性集合组成 ,因此描述了 第 Ⅰ类背景知识. 以表 1 的形式背景为例 ,若用户关心的概念格 结点的内涵含有属性 A 、属性 A 且 B 、属性 A 或 B , 则形成的概念格如图 2～4 所示. 图 2 属性 A 的概念格 Fig12 Concept lattice on attribute A 图 3 属性 A ∨B 的概念格 Fig13 Concept lattice on attribute A or B 图 4 属性 A ∧B 的概念格 Fig14 Concept lattice on attribute A and B 定义 12 设 P4 ( Z) = Πz ( ( G ( z) ∧concept ( z , x , y ) ∧┓include ( x , y0 ) ) →interest ( z) ) 为一谓 词公式 , P4 ( Z) 表示一个格结点 ,如果其内涵是由用 户关心的不含属性子集 y0 组成 ,则该结点为关心结 第 2 期 张继福 ,等 :约束概念格及其构造方法 · 33 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·34· 智能系统学报 第1卷 点 ({1,23,4,5,Φ) 定义13设P(Z)=:((G(z)∧concept (z,x,y)∧(include(x,o))∧7(include(x, (《1,4,0(12,3},B)241,D)(3.5}.C) )interest()为一谓词公式，P(z☑表示一 (4.AD)(《2,BDE)(3,BC) 个格结点，如果其内涵是由用户关心的不含属性子 集0且不含属性子集”组成，则该结点为关心结 (Φ，ABCDE) 点 定义14设PB%(Z)=廿：(G()∧concept 图7(1AVㄣB)概念格 (=x,y)A((include (x,yo)V include (x, Fig 7 Concept lattice on attribute 4 or B ))interest()为一谓词公式，P6(z)表示一 性质3由P(☑、…P6()所构成的合式逻 个格结点，如果其内涵是由用户关心的不含属性子 辑公式，描述了2类背景知识 集%或者不含属性子集Ⅵ组成，则该结点为关心 证明：由性质1和性质2可容易得证. 结点 性质2谓词公式P:、P和P描述了第Ⅱ类 4约束概念格及其构造 背景知识 4.1约束概念格 证明：通过∧（与）、V(或)、一（非）运算所形成 定义15概念格的每一个结点为一个形式概 的谓词公式P、P和P6描述了这样一类格结点， 念h=(O,D,P以，其中：P是由P、P、P所 其内涵是由用户关心的不含有某属性集合组成，因 构成的合式逻辑公式，且P(O,D)=,T.(逻辑值 此描述了第类背景知识. 为真)，O∈P(U)称为概念的外延，D∈P()称为概念 以表1形式背景为例，图5为用户关心的概念 的内涵，D是由O中满足P的所有对象（记录、交 格结点的内涵不含有属性A(A)的格结构，图6 易)的共同特征（属性、项目）组成的集合，具有这种 为用户关心的概念格结点的内涵不含有子集A且 不含有子集B(1A∧7B)的格结构，图7为用户关 结构的格称为约束概念格(constrained concept lat~ 心的概念格结点的内涵不含有属性子集A或者不 tice). 含有属性子集B(7AVㄣB)的格结构. 定义16设m=(O,D),p和加=(O ({123.4,5.Φ) D2),P)是约束概念格中的2个不同的结点，则 m<加台D2CD1→OCO,如果不存在B= ({1,2,31,B(2,4,D) ({3,5}.C0 (O3,D),P)有hm<s<成立，则m称为hi的 父结点（父概念，直接前趋），m称为：的子结点 ({2,BDE) ({31.BC) 子概念，直接后继). (Φ，BCDE) 定义17在同一形式背景下，设m= ((O,D),p是约束概念格中的一个结点，m= 图514概念格 (O,D)是一般概念格中的一个结点，如果D1C Fig 5 Concept lattice on attribute A D2,O1=O2=中，则称h、为2个等价结点. 定义18在同一形式背景下，如果约束概念格 ({1,23,4,51.) 中的任一结点都为一般概念格中的一个结点，任一 条边也都为一般概念格中的一条边，则称约束概念 (3,5.C) ({241.D) 格为一般概念格的子格 引理1当背景知识为第I类时，约束概念格 (Φ，CD) 为一般概念格的子格。 证明当背景知识为第I类时，约束概念格中 图6(7A∧7B)概念格 Fig 6 Concept lattice on attribute 4 and B 的任一结点内涵都是由用户关心的属性子集组成， 且为一般概念格中的一个结点，由定义4、定义16 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
点. 定义 13 设 P5 ( Z) = Πz ( ( G ( z) ∧concept ( z , x , y ) ∧ ( ┓(include ( x , y0 ) ) ∧┓(include ( x , y1 ) ) ) →interest ( z) ) 为一谓词公式 , P5 ( Z) 表示一 个格结点 ,如果其内涵是由用户关心的不含属性子 集 y0 且不含属性子集 y1 组成 ,则该结点为关心结 点. 定义 14 设 P6 ( Z) = Πz ( ( G ( z) ∧ concept ( z , x , y ) ∧( ┓( include ( x , y0 ) ∨ ┓include ( x , y1 ) ) ) →interest ( z) ) 为一谓词公式 , P6 ( Z) 表示一 个格结点 ,如果其内涵是由用户关心的不含属性子 集 y0 或者不含属性子集 y1 组成 ,则该结点为关心 结点. 性质 2 谓词公式 P4 、P5 和 P6 描述了第 Ⅱ类 背景知识. 证明 :通过 ∧(与) 、∨(或) 、┓(非) 运算所形成 的谓词公式 P4 、P5 和 P6 描述了这样一类格结点 , 其内涵是由用户关心的不含有某属性集合组成 ,因 此描述了第 Ⅱ类背景知识. 以表 1 形式背景为例 ,图 5 为用户关心的概念 格结点的内涵不含有属性 A ( ┓A) 的格结构 ,图 6 为用户关心的概念格结点的内涵不含有子集 A 且 不含有子集 B ( ┓A ∧┓B) 的格结构 ,图 7 为用户关 心的概念格结点的内涵不含有属性子集 A 或者不 含有属性子集 B ( ┓A ∨┓B) 的格结构. 图 5 ┓A 概念格 Fig15 Concept lattice on attribute ┓A 图 6 ( ┓A ∧┓B) 概念格 Fig16 Concept lattice on attribute ┓A and ┓B 图 7 ( ┓A ∨┓B) 概念格 Fig17 Concept lattice on attribute ┓A or ┓B 性质 3 由 P1 ( Z) 、…、P6 ( Z) 所构成的合式逻 辑公式 ,描述了 2 类背景知识. 证明 :由性质 1 和性质 2 可容易得证. 4 约束概念格及其构造 411 约束概念格 定义 15 概念格的每一个结点为一个形式概 念 h = ( ( O , D) , P) ,其中 : P 是由 P1 、P2 、…、P6 所 构成的合式逻辑公式 ,且 P( ( O , D) ) = . T. (逻辑值 为真) , O ∈ρ(U) 称为概念的外延 , D ∈ρ( I) 称为概念 的内涵 , D 是由 O 中满足 P 的所有对象 (记录、交 易) 的共同特征(属性、项目) 组成的集合 ,具有这种 结构的格称为约束概念格 (constrained concept lat2 tice) . 定义 16 设 h1 = ( ( O1 , D1 ) , p) 和 h2 = ( ( O2 , D2 ) , P) 是约束概念格中的 2 个不同的结点 , 则 h1 < h2 Ζ D2 < D1 Ζ O1 < O2 , 如 果 不 存 在 h3 = ( ( O3 , D3 ) , P) 有 h1 < h3 < h2 成立 ,则 h2 称为 h1 的 父结点(父概念 , 直接前趋) , h1 称为 h2 的子结点 (子概念 ,直接后继) . 定义 17 在 同 一 形 式 背 景 下 , 设 h1 = ( ( O1 , D1 ) , p) 是约束概念格中的一个结点 , h2 = ( O2 , D2 ) 是一般概念格中的一个结点 , 如果 D1 < D2 , O1 = O2 =Φ,则称 h1 、h2 为 2 个等价结点. 定义 18 在同一形式背景下 ,如果约束概念格 中的任一结点都为一般概念格中的一个结点 ,任一 条边也都为一般概念格中的一条边 ,则称约束概念 格为一般概念格的子格. 引理 1 当背景知识为第 Ⅰ类时 ,约束概念格 为一般概念格的子格. 证明 当背景知识为第 Ⅰ类时 ,约束概念格中 的任一结点内涵都是由用户关心的属性子集组成 , 且为一般概念格中的一个结点 ,由定义 4、定义 16 · 43 · 智 能 系 统 学 报 第 1 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第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