基于负载均衡的模糊概念并行构造算法

提高模糊概念格直接构造效率是形式概念分析领域的主要问题之一,而当前基于模糊伽罗瓦联系的闭包运算仍是构造模糊概念的主要计算负荷,为此,提出一种基于负载均衡的并行构造模糊概念算法.该算法使用树状结构组织,遍历由自然数区间简化的搜索空间,逐级并行产生模糊概念、缩减搜索区间,并通过重新划分子搜索空间,实现各个计算节点负载均衡.实验结果表明,所提出的算法在稀疏数据集上表现优秀,能够有效地提高模糊概念构造效率.

Load balance-based algorithm for parallelly generating fuzzy formal concepts

Directly constructing the fuzzy concept lattice is one of most important issues for formal concept analysis(FCA). However, most construction algorithms for fuzzy concept lattice are based on closure operation of fuzzy Galois connection. Therefore, a parallel algorithm based on load balance is proposed to improve the efficiency of building all fuzzy concepts. It utilizes the structure of complete tree to organize and parallelly breadth-first traverse search space which is represented with nature number interval. Along the height of the complete tree, the algorithm checks and reduces current sub-search spaces parallelly, meanwhile fuzzy concepts are produced. At the end of each iterations, search space is redivided so that all computing nodes share computing load fairly. Experiment results show that the algorithm has excellent performances on sparse data set, and it can effectively improve the efficiency of the construction of all fuzzy concepts.