一种多线程概念约简算法

摘要

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

关键词

形式概念分析 / 概念格 / 概念约简 / 多线程并行算法

基金资助

国家自然科学基金资助项目(12171392,61976244); 陕西省自然科学基础研究计划资助项目(2021JM-141)