多线程并行构建三支概念

祁建军; 汪文威

doi:10.7652/xjtuxb201703020

您当前的位置：

首页 >

文章列表页 >

多线程并行构建三支概念

更新时间：2025-07-09

- 多线程并行构建三支概念
- A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts
- 西安交通大学学报 2017年51卷第3期页码：116-121
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
  
  : 2016-08-23。作者简介: 祁建军(1970—),男,副教授。基金项目: 国家自然科学基金资助项目(11371014,11071281);陕西省自然科学基础研究计划资助项目(2014JM8306)
- DOI：10.7652/xjtuxb201703020
  中图分类号： TP18
- 网络首发：2017-03-10，
  
  纸质出版：2017
- 稿件说明：
移动端阅览
祁建军, 汪文威. 多线程并行构建三支概念[J]. 西安交通大学学报, 2017,51(3):116-121.

A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts[J]. 2017, 51(3): 116-121.
祁建军, 汪文威. 多线程并行构建三支概念[J]. 西安交通大学学报, 2017,51(3):116-121. DOI： 10.7652/xjtuxb201703020.

A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts[J]. 2017, 51(3): 116-121. DOI： 10.7652/xjtuxb201703020.

摘要

针对三支概念分析理论中三支概念数量庞大、构建耗时的问题

提出了一种三支概念的并行构建算法PCbO3C。PCbO3C以提高三支概念的构建效率为目标

在三支概念串行构建算法CbO3C的基础上进行并行化改进

利用多线程技术并行计算给定形式背景的所有核心三支概念。并行化处理借鉴了算法PCbO的思想

通过串行算法CbO3C计算出第L层的所有三支概念

并存放到P个队列中

第L层当前生成的三支概念循环依次放入P个队列中

以使算法达到较高的负载均衡; 创建P个线程

利用CbO3C并行处理P个队列中的三支概念

使得CPU资源得到充分利用。由于多线程间没有同步操作

使得PCbO3C算法的整体效率得到了进一步提高。为了验证算法PCbO3C的效率

在8核CPU环境下对多组UCI和随机数据进行实验

实验结果表明:PCbO3C速度上明显优于CbO3C

当线程数不超过8时

线程数每增加1倍

并行算法的速度可以提高约67%。

Abstract

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.

关键词

Keywords

references

QI J, WEI L, YAO Y. Three-way formal concept analysis [C]∥Proceedings of 2014 International Conference on Rough Sets and Knowledge Technology. Berlin, Germany: Springer, 2014: 732-741.

QI J, QIAN T, WEI L. The connections between three-way and classical concept lattices [J]. Knowledge-Based Systems, 2016, 91: 143-151.

YAO Y. An outline of a theory of three-way decisions [C]∥Proceedings of 2012 International Conference on Rough Sets and Current Trends in Computing. Berlin, Germany: Springer, 2012: 1-17.

GANTER B, WILLE R. Formal concept analysis, mathematical foundations [M]. Berlin, Germany: Springer, 1999.

王德兴, 胡学钢, 刘晓平. 一种新颖的基于量化概念格的属性归纳算法 [J]. 西安交通大学学报, 2007, 41(2): 176-179.

WANG Dexing, HU Xuegang, LIU Xiaoping. Novel attribute induction algorithm based on quantized concept lattice [J]. Journal of Xi'an Jiaotong University, 2007, 41(2): 176-179.

LI J, REN Y, MEI C, et al. A comparative study of multigranulation rough sets and concept lattices via rule acquisition [J]. Knowledge-Based Systems, 2016, 91: 152-164.

REN R, WEI L. The attribute reductions of three-way concept lattices [J]. Knowledge-Based Systems, 2016, 99: 92-102.

刘琳, 钱婷, 魏玲. 基于属性导出三支概念格的决策背景规则提取 [J]. 西北大学学报(自然科学版), 2016, 46(4): 481-487.

LIU Lin, QIAN Ting, WEI Ling, et al. Rules extraction in formal decision contexts based on attribute-Induced three-way concept lattices [J]. Journal of Northwest University, Natural Science Edition, 2016, 46(4): 481-487.

YAO Y. Interval sets and three-way concept analysis in incomplete contexts [J/OL]. International Journal of Machine Learning Cybernetics, 2016: 1-18 [2016-06-26]. http: ∥link.springer.com/article/10.1007/s13042-016-0568-1.

汪文威, 祁建军. 三支概念的构建算法 [J]. 西安电子科技大学学报, 2017, 44(1): 71-76.

WANG Wenwei, QI Jianjun. An algorithm for constructing three-way concepts [J]. Journal of Xidian University, 2017, 44(1): 71-76.

NJIWOUA P, NGUIFO E M. A parallel algorithm to build concept lattice [C/OL]. Proceedings of the 4th Groningen International Information Technology Conference, 1997 [2016-06-18]. http:∥citeseerx.ist.psu. edu/viewdoc/summary?doi=10.1. 1.28.926.

FU H, NGUIFO E M. A parallel algorithm to generate formal concepts for large data [C]∥International Conference on Formal Concept Analysis. Berlin, Germany: Springer, 2004: 394-401.

KRAJCA P, OUTRATA J, VYCHODIL V. Parallel recursive algorithm for FCA [C/OL]. Proceedings of the 6th International Conference on Concept Lattices and Their Applications, 2008 [2016-06-20]. ∥http: ceur-ws.org/Vol-433/paper6.pdf.

KRAJCA P, OUTRATA J, VYCHODIL V, et al. Advances in algorithms based on CbO [C/OL]. Proceedings of the 7th International Conference on Concept Lattices and Their Applications, 2010 [2016-06-18]. http:∥ceur-ws.org/Vol-672/paper29. pdf.

GAJDO P, SNÁEL V. A new FCA algorithm enabling analyzing of complex and dynamic data sets [J]. Soft Computing, 2014, 18(4): 683-694.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

三支概念格中的关联规则提取算法

一种多线程概念约简算法

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析

面向高海拔空冷发电机防晕性能演化规律的电热耦合研究

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建