模糊形式概念并行构造算法.PDF

第26 卷摇 第 3 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 模式识别与人工智能摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Vol.26摇 No.3 摇 2013年3月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 PR AI摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Mar摇 摇 2013 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 模糊形式概念并行构造算法 张摇 卓摇 摇 柴玉梅摇 摇 王黎明摇 摇 范摇 明 (郑州大学 信息工程学院摇 郑州450001) 摘摇 要摇 形式概念分析理论已经广泛地应用于计算机诸多领域.当前,模糊概念格直接构造仍然是该领域主要问 题之一,其构造过程具有指数级时间复杂度.为了提高模糊概念格构造效率,文中对串行模糊概念构造算法进行并 行化改进,将模糊集合组合有哪些信誉好的足球投注网站空间映射为自然数区间,简化了有哪些信誉好的足球投注网站空间表示、划分和遍历过程,进而提出并行模 糊概念构造算法(Parallel Fuzzy Next Closure,ParaFuNeC).该算法对有哪些信誉好的足球投注网站空间均匀划分,子有哪些信誉好的足球投注网站空间彼此独立,从而 避免并行任务之间同步、通讯等时间耗费,达到提高模糊概念构造效率的目标.时间复杂度分析和实验结果表明该 算法在大规模计算任务情况下,加速比随着并行度的提高呈正比增长趋势.另外,串行比例指标表明ParaFuNeC算 法在大规模计算任务情况下具有更好的可扩展性. 关键词摇 模糊伽罗瓦联系,模糊形式概念构造, 自然数区间,模糊集,并行算法 中图法分类号摇 TP311 A Parallel Algorithm Generating Fuzzy Formal Concepts ZHANGZhuo,CHAI Yu鄄Mei,WANG Li鄄Ming,FAN Ming (School of Information Engineering,Zhengzhou University,Zhengzhou450001) ABSTRACT Formal concept analysis (FCA) is extensively applied in various fields of computer. Currently, constructing fuzzy concepts directly is still one of most important issues of the FCA field. However,the construction process is always with exponential time complexity. In order to improve the efficiency of building fuzzyconcepts,aparallelalgorithmcalledParallelFuzzyNext Closure (ParaFuNeC)ispresented. It is parallel developed from the serial construction algorithm of fuzzy concepts. The proposed method maps the combination search space of fuzzy set into the natural number interval,so that search space is simply expressed, divided and traversed through natural number. Moreover, the algorithm produces balanced and independent sub鄄search spaces according to the number of CPU in prese