A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts

doi:10.7652/xjtuxb201703020

您当前的位置：

首页 >

文章列表页 >

A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts

更新时间：2025-07-09

- A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts
- Vol. 51, Issue 3, Pages: 116-121(2017)
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201703020
  CLC： TP18
- Online First：10 March 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts[J]. 2017, 51(3): 116-121.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Extracting Association Rules in Three-Way Concept Lattices

A Multi-Thread Algorithm for Concept Reduction

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

A Structure-Semantics-Residual Collaborative Image Compression Framework：Towards Privacy Protection and High-Fidelity Reconstruction

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

Related Author

刘美玉

刘伟

QI Bin

QI Jianjun

LI Jun'an

ZHAO Siyu

SHE Yanhong

Related Institution

School of Computer Science and Technology, Xidian University

School of Information Network Security, Xinjiang University of Political Science and Law, Tumushuke

School of Mathematics and Statistics, Xianyang Normal University

College of Science, Xi'an Shiyou University

⁰