一种多线程概念约简算法

A Multi-Thread Algorithm for Concept Reduction

针对现有概念约简算法计算过程较为繁琐且执行效率低的问题,提出了一种多线程概念约简算法MTCR。MTCR以提高计算概念约简的效率为首要目标,在多核环境下利用多线程技术并行计算概念约简。首先,MTCR算法使用两个线程分别计算单个对象的对象代表概念集和单个属性的属性代表概念集;然后,将形式背景中的对象(属性)依次放入p个队列,并为每个队列创建线程;最后,通过多线程方式并行计算任意对象的对象代表概念集和任意属性的属性代表概念集,以及两类代表概念集的交集,进而构建代表概念矩阵,据此计算出所有概念约简。在MTCR算法中,使用多线程的每个阶段的数据相对独立,使得多线程之间不需要频繁的同步操作,从而减少了线程之间的竞争和等待。这样可充分有效地利用计算资源,大大提升算法的性能。UCI数据集和随机数据集上的实验表明:MTCR算法可以准确得到概念约简结果,在使用单线程情况下执行速度与串行概念约简算法SCR相近;当线程数不超过8时,线程数每增加1倍,MTCR算法执行速度可提高30%以上。

Aiming at the issue that the existing concept reduction algorithms are complex and the efficiency is low,a multi-thread concept reduction algorithm(MTCR)is proposed.MTCR takes improving the efficiency of concept reduction algorithms as the primary goal and employs multi-thread technology to parallelly calculate concept reduction in a multi-core environment.The MTCR algorithm initially uses two threads to calculate the object representative concept set of a single object and the attribute representative concept set of a single attribute,then puts the objects(attributes)into p queues in turn,and creates a thread for each queue.Finally,the object representative concept set of any object and the attribute representative concept set of any attribute are calculated parallelly using multi-threaded technology,and the representative concept matrix is constructed by computing the intersection of these two different types of representative concept sets,on the basis of which all the concept reducts are computed.In the MTCR algorithm,the data of each stage using multiple threads is relatively independent,which avoids frequent synchronization operations between multiple threads,thereby reducing the competition and waiting time between threads.This mechanism enables the full and effective utilization of computing resources,which greatly improves the performance of the algorithm.Experiments on UCI datasets and random datasets show that the MTCR algorithm can accurately obtain all concept reduction,and the running time is close to the existing SCR algorithm when using a single thread.Specially,when the number of threads is less than 8,the running time of the MTCR algorithm can be improved by more than 30%for each doubling of the number of threads.