Journal of Frontiers of Computer Science and Technology ›› 2008, Vol. 2 ›› Issue (6): 651-657.DOI: 10.3778/j.issn.1673-9418.2008.06.008

• 学术研究 • Previous Articles     Next Articles

A new parallel algorithm for construction of concept lattice

DONG Hui+, MA Yuan, GONG Xi   

  1. College of Computer Science and Engineering, University of Science and Technology Liaoning, Anshan, Liaoning 114051, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-12-06 Published:2008-12-06
  • Contact: DONG Hui

一种新的概念格并行构造算法

董 辉+,马 垣,宫 玺   

  1. 辽宁科技大学 计算机科学与工程学院,辽宁 鞍山 114051
  • 通讯作者: 董 辉

Abstract: Concept lattice, the core data structure of formal concept analysis, is widely used in KDD, software engineering, artificial intelligence, information retrieval and rough set[1], etc. However, with the sharp increasing of the data to deal with, its construction efficiency has become the key problem. A new concept lattice parallel construct algorithm—Para_Prun based on the idea of the dividing of the closure system of concept lattice is presented. The corresponding closure system of the concept lattice is divided into a number of independent closure systems and proceeds to the calculation of the concepts. It can improve the efficiency of the concept lattice’s construction. The experiment results prove the correctness and validity of the algorithm by taking random data as the formal context.

Key words: concept lattice, construction algorithm, parallel algorithm, partition, closure system

摘要: 概念格作为形式概念分析理论中的核心数据结构,在数据挖掘和知识发现、人工智能、信息检索、粗糙集[1]等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。提出了一种基于闭包系统划分的概念格并行构造算法——Para_Prun算法,它将概念集合看作初始闭包系统,引入了子闭包系统的有效性判断,迭代生成相互独立的多个子闭包系统,然后在每个子闭包系统中独立生成概念,有效地提高了概念的求解速度。最后用实验证明了算法的正确性和有效性。

关键词: 概念格, 构造算法, 并行算法, 划分, 闭包系统