摘要
针对三支概念分析理论中三支概念数量庞大、构建耗时的问题,提出了一种三支概念的并行构建算法PCbO3C。PCbO3C以提高三支概念的构建效率为目标,在三支概念串行构建算法CbO3C的基础上进行并行化改进,利用多线程技术并行计算给定形式背景的所有核心三支概念。并行化处理借鉴了算法PCbO的思想,通过串行算法CbO3C计算出第L层的所有三支概念,并存放到P个队列中,第L层当前生成的三支概念循环依次放入P个队列中,以使算法达到较高的负载均衡;创建P个线程,利用CbO3C并行处理P个队列中的三支概念,使得CPU资源得到充分利用。由于多线程间没有同步操作,使得PCbO3C算法的整体效率得到了进一步提高。为了验证算法PCbO3C的效率,在8核CPU环境下对多组UCI和随机数据进行实验,实验结果表明:PCbO3C速度上明显优于CbO3C,当线程数不超过8时,线程数每增加1倍,并行算法的速度可以提高约67%。
Aiming at the problems that the number of three-way concepts is large and the time constructing three-way concepts is lengthy, a parallel algorithm named PCbO3C was proposed to construct three-way concepts in this paper. In order to enhance the efficiency of constructing three-way concepts, PCbO3C is aimed at improving the sequential construction algorithm CbO3C by parallelization of using multithreading technology to compute all the core three-way concepts of a given formal context. This parallelization idea is similar to the algorithm PCbO. Firstly, PCbO3C computes all the three-way concepts of the Lth layer by CbO3C, and puts these three- way concepts into P queues in turn to get better load balance. Secondly, PCbO3C creates P threads and parallelly processes the three-way concepts in these P queues by CbO3C, i. e. , one thread deals with one queue. This can take full advantage of CPU resources. Since there is no synchronous operation, the running speed of the algorithm is improved efficiently. To verify the efficiency of PCbO3C, experiments on some UCI databases and random datasets were conducted in the situation of 8-core CPU. The results show that the speed of PCbO3C can be increased by approximately 67% with the number of threads doubled if the number of threads is no more than 8.
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
2017年第3期116-121,共6页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金资助项目(11371014
11071281)
陕西省自然科学基础研究计划资助项目(2014JM8306)
关键词
形式概念分析
三支概念分析
形式背景
多线程
formal concept analysis
three-way concept analysis
formal contexts
multithreading
