基于闭包系统划分的概念格并行构造算法

随着处理的形式背景的增大，概念格的时空复杂度也会随着急剧增大。研究新的方法和手段来构造概念格，是概念格技术应用于大型复杂数据系统的前提．提高其构造效率的一种有效途径是利用高性能并行计算机和网络并行计算的能力，因此概念格的并行构造算法已成为众多学者的一个新的研究方向。概念格的并行构造思想就是根据不同的原理，采用分治策略，通过对形式背景的拆分，形成分布存储的多个子背景，然后构造相应的子概念格，再由子概念格的合并得到所需的概念格。目前建格算法的分布处理研究主要有形式背景的并置和叠置以及形式背景的折叠搜索子空间划分两种方法，本文在总结研究这两种方法的基础上，基于偏序集上闭包系统分解的思想，对提出的闭包系统划分为多个子闭包系统的判定定理进行了证明．使闭包系统的分解既不会产生冗余信息，也不会使信息丢失，并把所提出的判定定理用于概念格的并行处理．提出了一个新的基于闭包划分的概念格并行生成算法——Para-Prumng算法。通过实验，利用随机生成的数据集同经典NextClosure算法进行比较分析，验证了新算法的正确性和有效性。

A Parallel Constructing Algorithm Based on Dividing of Closure System for Concept Lattice

With the increasing of the context, the time complexity and the space complexity of the construction of concept lattice will be dramatically increased accordingly. The new constructing of concept lattice has been paid much attention because it is the premise for being used in a large and complicated data system. The high-performance parallel computer and network parallel computing technology are normally used to enhance the structure efficiency. However, the parallel constructing of concept lattice should adopt the dividing and conquering method by considering different structuring principles to divide the context into subcontexts. The overall concept lattice is composed of a series of sub-concept lattices each of which is structured from its related subcontexL So far, there are mainly two structuring methods, collocation and overlay of context and folding search space partition of context. This paper introduces a new parallel structuring method based on the idea of the dividing of the closure system of poset to divide the whole closure system into sub--closure system. The method can eliminate the redundancy and loss of information during the process of the dividing of the closure system. The experiment result showed the accuracy and validity of the present method by comparing with the NextClosure algorithm.