|
|
|
| A Parallel Algorithm Generating Fuzzy Formal Concepts |
| ZHANG Zhuo,CHAI Yu-Mei,WANG Li-Ming,FAN Ming |
| School of Information Engineering,Zhengzhou University,Zhengzhou 450001 |
|
|
|
|
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 fuzzy concepts,a parallel algorithm called Parallel Fuzzy Next Closure (ParaFuNeC) is presented. 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 present computing environment. It also avoids the time costs of synchronization and communication among parallel tasks. By the time complexity analysis and experimental evaluation of the proposed algorithm,it is proved that the speedup ratio of the proposed algorithm increases proportionally to the number of CPU in the case of large-scale computing tasks. Besides,the criterion of serial fraction is used to analyze the scalability of the proposed algorithm in experiments. The results show that the algorithm ParaFuNeC also has better scalability in the case of large-scale computing tasks.
|
|
Received: 01 April 2012
|
|
|
|
|
|
|
|
|
2013, Vol. 26 
