第3卷第5期 智能系统学报 Vol 3 Na 5 2008年10月 CAA I Transactions on Intelligent Systems Oct 2008 概念特化的概念格更新构造算法 杜秋香，张继福，张素兰 (太原科技大学计算机科学与技术学院，山西太原030024) 摘要：概念格是形式概念分析中的核心数据结构，概念格应用的瓶颈之一是其构造效率.针对形式背景的某个属 性分解为多个新属性得到更加特化的概念给出了一种基于概念特化的渐进式更新构造算法.该算法利用分解后的 新属性及其相应的形式背景，构造出的概念格与原概念格的某个子概念格作比较，来更新构造概念格，从而减少了 比较次数，提高了更新构造的效率.以天体光谱数据作为形式背景，实验验证了该算法的正确性和有效性 关键词：概念格：渐进式构造：概念特化：更新构造 中图分类号：TP311文献标识码：A文章编号：1673-4785(2008)05-0443-06 An i proved a lgorithm based on concept spec alization for constructing concept aattices DU Q iu-xiang,ZHANG Ji-fu,ZHANG Su-lan School of Computer Science and Technolgy,Taiyuan University of Science and Technology,Taiyuan 030024,China) Abstract:Concept lattices are the core data structures in fomal concept analysis The widesp read application of con- cept analysis is li ited by the difficulty of constructing a concept lattice An incrementally updating construction algo- rithm based on concept spcialization was devebped after it was realized that the attributes in the omal context can be decomposed into several new attributes,ormore specialized concepts The algorithm,with decomposed attributes and a corresponding fomal context,compares the concept lattice fomed with the new attributes and one of the sub-lattices of the original concept lattice,then upgrades the concept lattice according to results from the comparisons In this way the number of comparisons is reduced and the efficiency of constructing the concept lattice is mproved Experi- ment results,with celestial spectrum data as the fomal context,verified the validity of the algorithm. Keywords:concept lattice;incremental constructing concept specialization;updating construction “概念的基本观点是由哲学理论中的概念发 重用I1:Gord in等人还将概念格应用于类层次(class 展而来，是反应事物本质属性的思维产物.形式概念 hierarchy)的设计上ts) 理论是20世纪80年代初由德国教授R W ille:提出 概念格构造效率一直是概念格应用的主要瓶颈 的l山，并通过Hase图生动简洁地体现了概念间的 之一.目前，概念格的构造算法主要分为批处理算法 泛化和特化关系，提供了一种数据分析和知识处理 和渐进式算法两大类，典型的批处理算法有Bordat 的有力工具，被广泛应用于知识工程、数据挖掘、信 算法、Ganter算法、Nourine?算法等I6,其存在的问题 息检索和软件工程等领域，典型的应用有：Neuss和 是当形式背景发生变化时就要重新构造概念格.渐 Kent使用概念格进行Intemet_上文档元信息的自动 进式算法被认为是比较有前途的一类算法，可分为 分类和分析，Eklund和Martin展示了概念层次进 增加对象和增加属性2类概念格的渐进式构造.增 行Web文档索引和导航的能力；Corbetti和Burow 加对象的经典算法是Godin算法)，以及Godin算 提出使用概念格表示建筑早期设计软件支持环境 法的改进，例如，采用树结构组织格结点进行概念格 (SED)中的状态图，使得设计中获得的知识可以 的构造1：增加属性的典型算法是基于属性的概念 格渐进式生成算法，以及Add ntent算法io,.此 收稿日期：2008-03-21 基金项目：山西省自然科学基金资助项目(2006011041). 外，对概念格的研究热点还包括：规则提取、概 通信作者：杜秋香.Emai让anny1l23@163.com 念格的扩展以及与其他理论的融合35)、概念格的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 概念特化的概念格更新构造算法 杜秋香 ,张继福 ,张素兰 (太原科技大学 计算机科学与技术学院 ,山西 太原 030024) 摘 要 :概念格是形式概念分析中的核心数据结构 ,概念格应用的瓶颈之一是其构造效率. 针对形式背景的某个属 性分解为多个新属性得到更加特化的概念 ,给出了一种基于概念特化的渐进式更新构造算法. 该算法利用分解后的 新属性及其相应的形式背景 ,构造出的概念格与原概念格的某个子概念格作比较 ,来更新构造概念格 ,从而减少了 比较次数 ,提高了更新构造的效率. 以天体光谱数据作为形式背景 ,实验验证了该算法的正确性和有效性. 关键词 :概念格 ;渐进式构造 ;概念特化 ;更新构造 中图分类号 : TP311 文献标识码 : A 文章编号 : 167324785 (2008) 0520443206 An improved algor ithm based on concept spec ialization for constructing concept lattices DU Q iu2xiang, ZHANG Ji2fu, ZHANG Su2lan ( School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China) Abstract:Concep t lattices are the core data structures in formal concep t analysis. The widesp read app lication of con2 cep t analysis is limited by the difficulty of constructing a concep t lattice. An incrementally updating construction algo2 rithm based on concep t spcialization was developed after itwas realized that the attributes in the formal context can be decomposed into several new attributes, ormore specialized concep ts. The algorithm, with decomposed attributes and a corresponding formal context, compares the concep t lattice formed with the new attributes and one of the sub2lattices of the original concep t lattice, then upgrades the concep t lattice according to results from the comparisons. In this way the number of comparisons is reduced and the efficiency of constructing the concep t lattice is imp roved. Experi2 ment results, with celestial spectrum data as the formal context, verified the validity of the algorithm. Keywords: concep t lattice; incremental constructing; concep t specialization; updating construction 收稿日期 : 2008203221. 基金项目 :山西省自然科学基金资助项目 (2006011041). 通信作者 :杜秋香. E2mail: janny123@163. com. “概念 ”的基本观点是由哲学理论中的概念发 展而来 ,是反应事物本质属性的思维产物. 形式概念 理论是 20世纪 80年代初由德国教授 R. W ille提出 的 [ 1 ] ,并通过 Hasse图生动简洁地体现了概念间的 泛化和特化关系 ,提供了一种数据分析和知识处理 的有力工具 ,被广泛应用于知识工程、数据挖掘、信 息检索和软件工程等领域 ,典型的应用有 : Neuss和 Kent使用概念格进行 Internet上文档元信息的自动 分类和分析 [ 2 ] ; Eklund和 Martin展示了概念层次进 行 Web文档索引和导航的能力 [ 3 ] ; Corbett和 Burrow 提出使用概念格表示建筑早期设计软件支持环境 (SEED)中的状态图 ,使得设计中获得的知识可以 重用 [ 4 ] ; Gordin等人还将概念格应用于类层次 ( class hierarchy)的设计上 [ 5 ] . 概念格构造效率一直是概念格应用的主要瓶颈 之一. 目前 ,概念格的构造算法主要分为批处理算法 和渐进式算法两大类 ,典型的批处理算法有 Bordat 算法、Ganter算法、Nourine算法等 [ 6 ] ,其存在的问题 是当形式背景发生变化时就要重新构造概念格. 渐 进式算法被认为是比较有前途的一类算法 ,可分为 增加对象和增加属性 2类概念格的渐进式构造. 增 加对象的经典算法是 Godin算法 [ 7 ] ,以及 Godin算 法的改进 ,例如 ,采用树结构组织格结点进行概念格 的构造 [ 8 ] ;增加属性的典型算法是基于属性的概念 格渐进式生成算法 [ 9 ] ,以及 Add Intent算法 [ 10 ] . 此 外 ,对概念格的研究热点还包括 :规则提取 [ 11212 ]、概 念格的扩展以及与其他理论的融合 [ 13215 ]、概念格的 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net