首页 | 本学科首页   官方微博 | 高级检索  
     

概念格的快速渐进式构造算法
引用本文:谢志鹏,刘宗田.概念格的快速渐进式构造算法[J].计算机学报,2002,25(5):490-496.
作者姓名:谢志鹏  刘宗田
作者单位:1. 新加坡国立大学计算机学院,新加坡,119260
2. 上海大学计算机学院,上海,200072
基金项目:国家自然科学基金 (69985 0 0 4)资助
摘    要:概念格作为形式概念分析理论中的核心数据结构,已经在知识工程和软件工程等领域得到了广泛的应用。概念格的快速构造在其应用过程中具有重要的意义,研究人员已经提出了一系列构造概念格的算法,其中渐进式算法是很有前途的一类。该文通过对概念格渐进式构造过程的分析,识别出要解决的基本问题,提出了采用树结构对概念格节点进行组织,研究了基于这种树状组织的概念格快速渐进式算法,并给出了算法的伪码。概念格节点的树结构组织有利于识别出格节点的类型以及约束新生格节点的父节点和子节点的搜索范围,从而可以有效地减少算法的执行时间。实验结果表明,基于这种树状索引的渐进式构造算法的时间性能要明确优于著名的Godin算法。

关 键 词:数据结构  树状结构  概念格  快速渐进式构造算法
修稿时间:2000年10月13

A Fast Incremental Algorithm for Building Concept Lattice
XIE Zhi Peng,LIU Zong Tian.A Fast Incremental Algorithm for Building Concept Lattice[J].Chinese Journal of Computers,2002,25(5):490-496.
Authors:XIE Zhi Peng  LIU Zong Tian
Affiliation:XIE Zhi Peng 1) LIU Zong Tian 2) 1)
Abstract:Concept lattice, the core data structure in formal concept analysis, has been used widely in knowledge engineering and software engineering. In its applications, building concept lattice efficiently is an important task, for which various algorithms have been developed. These algorithms can be divided into two main categories, batch construction and incremental construction, where the latter is thought of promising. To incrementally update the existing concept lattice with the inserted new object, this paper first identifies the basic problems to solve, through analyzing the process of incrementally updating. Then, tree structure is employed to organize the set of concepts in concept lattice. Based on the tree structure, a fast incremental algorithm is developed to incrementally update the existing concept lattice by traversing its set of concepts with the defined visiting order. On visiting each concept node, the node type will be identified and the corresponding updating operation will be executed. The organization of concepts in tree structure and the defined visiting order on it can greatly reduce the search space of parents and children of newborn concept node and help to identify the node type, and consequently improve the speed of the algorithm. In the end, experimental results on artificially generated datasets are produced, which manifest that the algorithm in this paper runs much faster than the famous Godin's algorithm.
Keywords:concept lattice  incremental algorithm  index tree
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号