第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