第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
·36· 智能系统学报 第1卷 l5)fX∈f(x)orXy∈f(x)Then 51)End if 16)f(x)的属性值X或者XY记为空值，原 52)For对于Mark中的每个格结点hm=(O, f(x一f(x) D',w)按D1降序排列Do 17)Generate() 53)If存在h EMark使得D'Cinter Then增 18)End if 加边Nw-hm: 19)Else 54)f存在hm是h.的双亲Then删去边ha 20)fX∈f(xW、Y∈f(x)Then +hm i 21)f(x)的属性值X、Y记为空值，原f(x)→ 55)End if f(x‘) 56)End for 22)Generate() 57)End if 23)End if 58)End Gennew() 24)End if 算法分析： 25)End if 在上述CCLA算法中，不但只根据新追加对象 26)End CCLA 内涵与原格内涵的交集结果，而且还要根据用户关 27)(Generate() 心和不关心的属性子集的组合决定格节点的生成， 28)ForL,中的每个格结点h,=((O,D),P列 用户不感兴趣的属性子集的内涵的格结点将不被生 按！Dl升序排列Da*更新约束概念*/ 成 29)IfD∈f(x)Then 对于一个新对象h:={x,f(x,w子，最多可能 30)0:=0U{x}; 存在2个内涵包含于f(x)的概念.因此，当所有 31)MarkMark U(h) 原始形式背景的行对象的属性都包含用户关心的属 32)IfD=f(x)Then退出For循环；Else 性集时，无节点被删除.根据文献[8]建格算法分析 33)调用过程Gennew0; 可知，若设1∫(x)丨=k,则算法的复杂度为 34)End if O21U1).而在实际应用中，对象x具有的属性内 35)End for 涵并不都是用户感兴趣的，不包含用户关心的属性 36)End Generate() 集的对象不进行渐进式构造，在实际概念格的构造 37)Gennew() 中，随着要处理数据量的增大，」U川的量减少，生成 38)f输入用户关心的属性子集X、X八Y或者 的节点数将明显减少，算法的复杂度要小于 XVy Then O21U1).同样地，在实际应用中，当生成用户定 39)inter:=Dnf(x划： 义的不含有某属性子集的内涵的格结点时，含有某 40)Else 属性子集的内涵的格结点将不被生成，随着要处理 41)inter:=D nf(x 数据量的增大，f(x)即k的量减少，因此，算法的复 42)Endif 杂度远小于021U1).所以，该算法能有效地节省 43)If inter≠Φ 概念格的存储空间和建格时间 44)f用户输入的子集为XVY,Then 5实验分析 45)If X Einter or y Einter Then/*约束新增 概念*1 当前我国正在建造一台大天区面积多目标光纤 46)f不存在h:∈Mark使得Dk:=inter Then 光谱望远镜（简称LAMOST),它是国家“九五”计 47)N,=(OUyx,inter);/*N,新增结点*/ 划重大工程项目，总投资达235亿人民币.由于 48)End if LAMOST具有以较高效率大规模测量天体光谱的 49)Mark:Mark UN,: 能力，可提供的研究课题将遍及天文学多个层次，从 50)增加边h.-N,: 恒星、银河系、星系、星系团、活动星系核，直到宇宙 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
15) If X ∈f ( x) or X Y ∈f ( x) Then 16) f ( x) 的属性值 X 或者 XY 记为空值 , 原 f ( x) →f ( x 3 ) 17) Generate () 18) End if 19) Else 20) If X ∈f ( x) 、Y ∈f ( x) Then 21) f ( x) 的属性值 X 、Y 记为空值 ,原 f ( x) → f ( x 3 ) 22) Generate () 23) End if 24) End if 25) End if 26) End CCLA 27) ( Generate () 28) For L r 中的每个格结点 h r = ( ( O , D) , P) 按| D| 升序排列 Do/ 3 更新约束概念 3 / 29) If D Α f ( x) Then 30) O : = O ∪{ x} ; 31) Mark : = Mark ∪{ hr} ; 32) If D = f ( x) Then 退出 For 循环 ; Else 33) 调用过程 Gennew () ; 34) End if 35) End for 36) End Generate () 37) Gennew () 38) If 输入用户关心的属性子集 X 、X ∧Y 或者 X ∨Y Then 39) inter : = D ∩f ( x) ; 40) Else 41) inter : = D ∩ f ( x 3 ) ; 42) Endif 43) If inter ≠Φ 44) If 用户输入的子集为 X ∨Y , Then 45) If X ∈inter or Y ∈inter Then/ 3 约束新增 概念 3 / 46) If 不存在 hk ∈Mark 使得 Dk : = inter Then 47) N r = ( O ∪{ x} ,inter) ;/ 3 N r 新增结点 3 / 48) End if 49) Mark : = Mark ∪N r ; 50) 增加边 hx ←N r ; 51) End if 52) For 对于 Mark 中的每个格结点 hm = ( O′, D′, w′) 按| D′| 降序排列 Do 53) I f 存在 h m ∈Mark 使得 D′< inter Then 增 加边 N w ←hm ; 54) If 存在 hm 是 h x 的双亲 Then 删去边 hx ←hm ; 55) End if 56) End for 57) End if 58) End Gennew () 算法分析 : 在上述 CCLA 算法中 ,不但只根据新追加对象 内涵与原格内涵的交集结果 ,而且还要根据用户关 心和不关心的属性子集的组合决定格节点的生成 , 用户不感兴趣的属性子集的内涵的格结点将不被生 成. 对于一个新对象 hx = { x , f ( x) , w′} ,最多可能 存在 2 f ( x) 个内涵包含于 f ( x) 的概念. 因此 ,当所有 原始形式背景的行对象的属性都包含用户关心的属 性集时 ,无节点被删除. 根据文献[8 ]建格算法分析 可知 , 若 设 | f ( x ) | = k , 则 算 法 的 复 杂 度 为 O(2 2 k | U| ) . 而在实际应用中 ,对象 x 具有的属性内 涵并不都是用户感兴趣的 ,不包含用户关心的属性 集的对象不进行渐进式构造 ,在实际概念格的构造 中 ,随着要处理数据量的增大 , | U| 的量减少 ,生成 的节 点 数 将 明 显 减 少 , 算 法 的 复 杂 度 要 小 于 O(2 2 k | U| ) . 同样地 ,在实际应用中 , 当生成用户定 义的不含有某属性子集的内涵的格结点时 ,含有某 属性子集的内涵的格结点将不被生成 ,随着要处理 数据量的增大 , f ( x) 即 k 的量减少 ,因此 ,算法的复 杂度远小于O(2 2 k | U| ) . 所以 ,该算法能有效地节省 概念格的存储空间和建格时间. 5 实验分析 当前我国正在建造一台大天区面积多目标光纤 光谱望远镜 (简称 LAMOST) ,它是国家“九五”计 划重大工程项目 ,总投资达 2135 亿人民币. 由于 LAMOST 具有以较高效率大规模测量天体光谱的 能力 ,可提供的研究课题将遍及天文学多个层次 ,从 恒星、银河系、星系、星系团、活动星系核 ,直到宇宙 · 63 · 智 能 系 统 学 报 第 1 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第2期 张继福，等：约束概念格及其构造方法 ·37· 大尺度结构.LAMOST计划的主要目标是用来进 由表23中的实验结果可以看出，1)在相同形 行大规模光谱巡天，预计从2006年底起，每个观测 式背景下，约束概念格比一般概念格的结点数少，建 夜晚将收集2~4万条光谱的数据，LAMOST所观 格时间短.所以，利用背景知识，算法CCLA可以有 测到的光谱数据容量可达4TG1.如何利用数据挖 效地减少概念格结点数，节省概念格构造所用的时 掘技术从海量天体光谱数据中发现未知的、特殊的 间.因此，约束概念格利用用户提供的背景知识，可 天体和天体规律是值得研究和探索的新应用领域. 以降低概念格的时空复杂性.2)随着背景知识对概 在PentiumII-1.0GCPU,256MB内存，Win- 念格结点约束程度的加大，其满足约束的格结点个 dows2000操作系统，DBMS为ORACL E9i,用Vis 数和相应的建格时间将明显减低.3)由于背景知识 ual Basice6.0实现了CCLA算法.选用2500条M、 描述了用户感兴趣或不感兴趣的内涵，因此约束概 K、G、F、AB、O等类恒星光谱数据为数据集，经过 念格提高了概念格的针对性和实用性 以下预处理后构成该实验中的形式背景：1)选定间 隔为40的100个波长3510,3550，…，8330A,依 6结束语 据流量、峰宽和形状，将每个波长离散化为13种值； 在应用概念格进行知识提取时，一些概念格内 2)恒星的任意类型温度等间隔离散化为3种，7类 涵的属性组合，并非用户都感兴趣.同时，随着要处 恒星温度被离散化为21种值：3)根据恒星的光度、 理的数据量的激增，概念格的构造时间长，占用大的 化学丰度、微湍流、其他参数等间隔离散化为3种 存储空间.因此，为了提高概念格的构造效率，减少 值：4)根据恒星的物理参数，等间隔离散化为5种 建格的时间复杂度和空间复杂度，提出了一种全新 值 的概念格结构：基于背景知识的约束概念格.利用背 如果用户对恒星温度和化学分度组成的内涵感 景知识来指导概念格的构造，使构造出的概念格更 兴趣，对物理4和微湍流1组成的内涵不感兴趣，其 具有针对性和实用性.进一步工作是基于约束概念 约束概念格的结点个数和建格时间如表23所示 格的知识提取及在天体光谱数据知识发现中的应 用 表2CLA算法实验结果1 Table 2 The experiment result 1 of CCLA algorithm 参考文献： 背景知识 结点数 建格时间/s [1]WILLE R.Restructuring lattice theory:an approaches 中一般概念格) 6713 2823 based on hierarchies of concepts[A].In:Rival I ed.Or- 温度aV化学丰度2 3860 949 dered Sets[M].Dordrecht Reideal,1982. 温度a 1002 121 [2]GODIN R,MISSAOUI R.An Incremental concept for- mation approach for learning from databases [J].Theo- 化学丰度2 3351 851 retical Computer Science,1994,133(2):387-419. 温度a化学丰度2 473 71 [3]BEL EN D A,PEDRO A.Formal concept analysis as a support technique for CBR [J ]Knowledge-based Sys- 表3 CA算法实验结果2 tems,2001,14(3):163-171. Table 3 The experiment result 2 of CCLA algorithm [4]YOUNG P.Software retrieval by samples using concept 背景知识 结点数 建格时间/s analysis [J].The Journal of Systems and Computer, 中一般概念格)】 2000,54(3):179-183. 6713 2823 7物理4Vㄣ微湍流 [5]CHU S,CESNIK B.Knowledge representation and re- 16319 2760 trieval using conceptual graphs and free document self- 微湍流1 6090 2479 organisation techniques[J ]International Journal of Med- 7物理4 4122 879 ical Informatics,2001,62(2/3):121-33. 7物理4八7微湍流1 3665 732 [6]KENT R E.Rough concept analysis[A].In:Ziarko W P ed.Rough Sets,Fuzzy Sets and Knowledge Discovery 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
大尺度结构. LAMOST 计划的主要目标是用来进 行大规模光谱巡天 ,预计从 2006 年底起 ,每个观测 夜晚将收集 2～4 万条光谱的数据 ,LAMOST 所观 测到的光谱数据容量可达 4 T G [15 ] . 如何利用数据挖 掘技术从海量天体光谱数据中发现未知的、特殊的 天体和天体规律是值得研究和探索的新应用领域. 在 PentiumIII2110 G CPU , 256MB 内存 , Win2 dows2000 操作系统 ,DBMS 为 ORACL E9i ,用 Vis2 ual Basic610 实现了 CCLA 算法. 选用 2 500 条 M、 K、G、F、A 、B、O 等类恒星光谱数据为数据集 ,经过 以下预处理后构成该实验中的形式背景 :1) 选定间 隔为 40 的 100 个波长 3 510 ,3 550 , …, 8 330 A ° ,依 据流量、峰宽和形状 ,将每个波长离散化为 13 种值 ; 2) 恒星的任意类型温度等间隔离散化为 3 种 ,7 类 恒星温度被离散化为 21 种值 ;3) 根据恒星的光度、 化学丰度、微湍流、其他参数等间隔离散化为 3 种 值 ;4) 根据恒星的物理参数 ,等间隔离散化为 5 种 值. 如果用户对恒星温度和化学分度组成的内涵感 兴趣 ,对物理 4 和微湍流 1 组成的内涵不感兴趣 ,其 约束概念格的结点个数和建格时间如表 2、3 所示. 表 2 CCLA算法实验结果 1 Table 2 The experiment result 1 of CCLA algorithm 背景知识 结点数 建格时间/ s Ф(一般概念格) 6 713 2 823 温度 a ∨化学丰度 2 3 860 949 温度 a 1 002 121 化学丰度 2 3 351 851 温度 a ∧化学丰度 2 473 71 表 3 CCLA算法实验结果 2 Table 3 The experiment result 2 of CCLA algorithm 背景知识 结点数 建格时间/ s Ф(一般概念格) 6 713 2 823 ┓物理 4 ∨┓微湍流 16 319 2 760 ┓微湍流 1 6 090 2 479 ┓物理 4 4 122 879 ┓物理 4 ∧┓微湍流 1 3 665 732 由表 2、3 中的实验结果可以看出 ,1) 在相同形 式背景下 ,约束概念格比一般概念格的结点数少 ,建 格时间短. 所以 ,利用背景知识 ,算法 CCLA 可以有 效地减少概念格结点数 ,节省概念格构造所用的时 间. 因此 ,约束概念格利用用户提供的背景知识 ,可 以降低概念格的时空复杂性. 2) 随着背景知识对概 念格结点约束程度的加大 ,其满足约束的格结点个 数和相应的建格时间将明显减低. 3) 由于背景知识 描述了用户感兴趣或不感兴趣的内涵 ,因此约束概 念格提高了概念格的针对性和实用性. 6 结束语 在应用概念格进行知识提取时 ,一些概念格内 涵的属性组合 ,并非用户都感兴趣. 同时 ,随着要处 理的数据量的激增 ,概念格的构造时间长 ,占用大的 存储空间. 因此 ,为了提高概念格的构造效率 ,减少 建格的时间复杂度和空间复杂度 ,提出了一种全新 的概念格结构 :基于背景知识的约束概念格. 利用背 景知识来指导概念格的构造 ,使构造出的概念格更 具有针对性和实用性. 进一步工作是基于约束概念 格的知识提取及在天体光谱数据知识发现中的应 用. 参考文献 : [ 1 ] WILL E R. Restructuring lattice theory : an approaches based on hierarchies of concepts[ A ]. In :Rival I ed. Or2 dered Sets[ M]. Dordrecht : Reideal ,1982. [2 ] GODIN R , MISSAOU I R. An Incremental concept for2 mation approach for learning from databases [J ] . Theo2 retical Computer Science , 1994 ,133 (2) :387 - 419. [3 ]BEL EN D A , PEDRO A. Formal concept analysis as a support technique for CBR [J ]. Knowledge2based Sys2 tems ,2001 ,14 (3) :163 - 171. [4 ] YOUN G P. Software retrieval by samples using concept analysis [J ] . The Journal of Systems and Computer , 2000 ,54 (3) :179 - 183. [5 ]CHU S , CESNIK B. Knowledge representation and re2 trieval using conceptual graphs and free document self2 organisation techniques[J ]. International Journal of Med2 ical Informatics ,2001 ,62 (2/ 3) :121 - 33. [6 ] KEN T R E. Rough concept analysis[ A ]. In : Ziarko W P ed. Rough Sets , Fuzzy Sets and Knowledge Discovery 第 2 期 张继福 ,等 :约束概念格及其构造方法 · 73 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·38· 智能系统学报 第1卷 (RSKD,93)[C].London Springer-Verlag 1994. [14]张凯，胡运发，王瑜.基于互关联后继树的概念格 [7]CARPIN ETO C,ROMANO G.A lattice conceptual 构造算法U].计算机研究与发展，2004,41(9)：1493. clustering system and its application to browsing retriev- 1499. al [J].Maching Learning,1996,24(2):95-122. ZHANG Kai,HU Yunfa,WAN G Yu.An IRST-based [8]王志海，胡可云，胡学钢，等.概念格上规则提取的一般 algorithm for construction of concept lattices[J].Jour- 算法与渐进式算法[0].计算机学报，1999,22(1)：66- nal of Computer Research and Development,2004,41 70. (9):1493.1499 WAN G Zhihai,HU Keyun,HU Xuegang ,et al.General [15]罩冬梅.天体光谱信号的自动识别方法研究D].北京： and incremental algorithms of rule extraction based on 中国科学院自动化研究所，2003， concept lattice[J].Chinese Journal of Computers,1999, QIN Dongmei.The research on automatic recognition of 22(1):66-70. astronomical spectra data [D].Beijing:Institute of Au [9]陈世权，程里春.模糊概念格」].模糊系统与数学， tomation Chinese Academy of Sciences,2003 2002,16(4):12-18. 作者简介： CHEN Shiquan,CHENG Lichun.Fuzzy concept lattice 张继福，男，教授，2005年毕业于北京 [J ]Fuzzy Systems and Mathematics,2002,16(4):12 理工大学，获工学博士学位，CCF高级会 -18. 员，主要研究方向：数据仓库与数据挖掘、 [10]NOURINE L,RA YNAUD O.A fast algorithm for 人工智能及应用.已发表学术论文50余 building lattices [J ]Information Processing Letters, 篇，其中被SCl、EI收录20余篇.Email:jr 1999,71(5.6):199.204. fuzh @sina.com [11]谢志鹏，刘宗田.概念格的快速渐进式构造算法卫].计 算机学报，2002,25(5)：490.495. 张素兰，女，副教授，2003年毕业于太 XIE Zhipeng,LIU Zongtian.A fast incremental algo- 原科技大学，获工学硕士学位，主要研究 rithm for building concept lattice[J].Chinese Journal of 方向：概念格与数据挖掘.已发表学术论 Computers,2002,25(5):490.495, 文10余篇 [12]HAN J,KAMBR M.Data mining concepts and tech- niques [M].San Fransisco:Morgan Kaufmann Publish- ers,2000 胡立华，女，助教，2006年毕业于太原 [13 HAN J,LAKS V S,Raymond T.Constraint-Based 科技大学，获工学硕士学位，主要研究方 Multidimensional data Mining [J ]Compuer,1999,32 向：概念格与数据挖掘.已发表学术论文 (8):46-50. 3篇 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
(RSKD ,93) [C]. London : Springer2Verlag , 1994. [7 ] CARPINETO C , ROMANO G. A lattice conceptual clustering system and its application to browsing retriev2 al [J ] . Maching Learning , 1996 ,24 (2) :95 - 122. [8 ]王志海 ,胡可云 ,胡学钢 ,等. 概念格上规则提取的一般 算法与渐进式算法[J ]. 计算机学报 ,1999 ,22 (1) : 66 - 70. WAN G Zhihai , HU Keyun , HU Xuegang ,et al. General and incremental algorithms of rule extraction based on concept lattice[J ]. Chinese Journal of Computers , 1999 , 22 (1) :66 - 70. [9 ]陈世权 ,程里春. 模糊概念格 [J ]. 模糊系统与数学 , 2002 , 16 (4) :12 - 18. CHEN Shiquan , CHEN G Lichun. Fuzzy concept lattice [J ]. Fuzzy Systems and Mathematics , 2002 , 16 (4) : 12 - 18. [10 ] NOURIN E L , RA YNAUD O. A fast algorithm for building lattices [J ]. Information Processing Letters , 1999 ,71 (5 - 6) :199 - 204. [11 ]谢志鹏 ,刘宗田. 概念格的快速渐进式构造算法[J ]. 计 算机学报 , 2002 , 25 (5) :490 - 495. XIE Zhipeng ,L IU Zongtian. A fast incremental algo2 rithm for building concept lattice[J ]. Chinese Journal of Computers , 2002 , 25 (5) :490 - 495. [12 ] HAN J , KAMBR M. Data mining concepts and tech2 niques [ M]. San Fransisco :Morgan Kaufmann Publish2 ers ,2000. [ 13 ] HAN J , LA KS V S , Raymond T. Constraint2Based Multidimensional data Mining [J ] . Compuer ,1999 ,32 (8) :46 - 50. [14 ]张 凯 ,胡运发 ,王 瑜. 基于互关联后继树的概念格 构造算法[J ]. 计算机研究与发展 , 2004 ,41 (9) :1493 - 1499. ZHAN G Kai , HU Yunfa ,WAN G Yu. An IRST2based algorithm for construction of concept lattices[J ]. Jour2 nal of Computer Research and Development , 2004 , 41 (9) :1493 - 1499. [15 ]覃冬梅. 天体光谱信号的自动识别方法研究[D ]. 北京 : 中国科学院自动化研究所 ,2003. QIN Dongmei. The research on automatic recognition of astronomical spectra data [ D ]. Beijing : Institute of Au2 tomation Chinese Academy of Sciences ,2003. 作者简介 : 张继福 ,男 ,教授 ,2005 年毕业于北京 理工大学 ,获工学博士学位 ,CCF 高级会 员 ,主要研究方向 :数据仓库与数据挖掘、 人工智能及应用. 已发表学术论文 50 余 篇 ,其中被 SCI、EI 收录 20 余篇. E2mail :ji2 fuzh @sina. com. 张素兰 ,女 ,副教授 ,2003 年毕业于太 原科技大学 ,获工学硕士学位 ,主要研究 方向 :概念格与数据挖掘. 已发表学术论 文 10 余篇. 胡立华 ,女 ,助教 ,2006 年毕业于太原 科技大学 ,获工学硕士学位 ,主要研究方 向 :概念格与数据挖掘. 已发表学术论文 3 篇. · 83 · 智 能 系 统 学 报 第 1 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net