概念格的快速渐进式构造算法

A Fast Incremental Algorithm for Building Concept Lattice

概念格作为形式概念分析理论中的核心数据结构 ,已经在知识工程和软件工程等领域得到了广泛的应用 .概念格的快速构造在其应用过程中具有重要的意义 ,研究人员已经提出了一系列构造概念格的算法 ,其中渐进式算法是很有前途的一类 .该文通过对概念格渐进式构造过程的分析 ,识别出要解决的基本问题 ,提出了采用树结构对概念格节点进行组织 ,研究了基于这种树状组织的概念格快速渐进式算法 ,并给出了算法的伪码 .概念格节点的树结构组织有利于识别出格节点的类型以及约束新生格节点的父节点和子节点的搜索范围 ,从而可以有效地减少算法的执行时间 .实验结果表明 ,基于这种树状索引的渐进式构造算法的时间性能要明显优于著名的

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.