·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