A Multi-Thread Algorithm for Concept Reduction

QI Bin; QI Jianjun; LI Jun'an; ZHAO Siyu; SHE Yanhong

doi:10.7652/xjtuxb202402017

您当前的位置：

首页 >

文章列表页 >

A Multi-Thread Algorithm for Concept Reduction

更新时间：2025-05-13

- A Multi-Thread Algorithm for Concept Reduction
- Vol. 58, Issue 2, Pages: 164-171(2024)
- 作者机构：
  
  1. 西安电子科技大学计算机科学与技术学院,西安,710071
  2. 新疆政法学院信息网络安全学院,新疆,图木舒克,844000
  3. 咸阳师范学院数学与统计学院,陕西,咸阳,712000
  4. 西安石油大学理学院,西安,710065
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb202402017
  CLC： TP18
- Online First：10 February 2024，
  
  Published：2024
- 稿件说明：
移动端阅览
QI Bin, QI Jianjun, LI Jun'an, et al. A Multi-Thread Algorithm for Concept Reduction[J]. 2024, 58(2): 164-171.
DOI：

QI Bin, QI Jianjun, LI Jun'an, et al. A Multi-Thread Algorithm for Concept Reduction[J]. 2024, 58(2): 164-171. DOI： 10.7652/xjtuxb202402017.

摘要

针对现有概念约简算法计算过程较为繁琐且执行效率低的问题

提出了一种多线程概念约简算法MTCR。MTCR以提高计算概念约简的效率为首要目标

在多核环境下利用多线程技术并行计算概念约简。首先

MTCR算法使用两个线程分别计算单个对象的对象代表概念集和单个属性的属性代表概念集; 然后

将形式背景中的对象(属性)依次放入p个队列

并为每个队列创建线程; 最后

通过多线程方式并行计算任意对象的对象代表概念集和任意属性的属性代表概念集

以及两类代表概念集的交集

进而构建代表概念矩阵

据此计算出所有概念约简。在MTCR算法中

使用多线程的每个阶段的数据相对独立

使得多线程之间不需要频繁的同步操作

从而减少了线程之间的竞争和等待。这样可充分有效地利用计算资源

大大提升算法的性能。UCI数据集和随机数据集上的实验表明:MTCR算法可以准确得到概念约简结果

在使用单线程情况下执行速度与串行概念约简算法SCR相近; 当线程数不超过8时

线程数每增加1倍

MTCR算法执行速度可提高30%以上。

Abstract

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.

关键词

Keywords

references

WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts [C]//Ordered Sets. Dordrecht: Springer Netherlands, 1982: 445-470.

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

RODRÍGUEZ-JIMÉNEZ J M, CORDERO P, ENCISO M, et al. Data mining algorithms to compute mixed concepts with negative attributes: an application to breast cancer data analysis [J]. Mathematical Methods in the Applied Sciences, 2016, 39(16): 4829-4845.

KUMAR CA. Fuzzy clustering-based formal concept analysis for association rules mining [J]. Applied Artificial Intelligence, 2012, 26(3): 274-301.

CARBONNEL J, HUCHARD M, NEBUT C. Modelling equivalence classes of feature models with concept lattices to assist their extraction from product descriptions [J]. Journal of Systems and Software, 2019, 152: 1-23.

AI-MSIE'DEEN R, BLASI A H. Software evolution understanding: automatic extraction of software identifiers map for object-oriented software systems [J]. Journal of Communications Software and Systems, 2021, 17(1): 20-28.

ANANIAS K H A, MISSAOUI R, RUAS P H B, et al. Triadic concept approximation [J]. Information Sciences, 2021, 572: 126-146.

KUMAR C. Knowledge discovery in data using formal concept analysis and random projections [J]. International Journal of Applied Mathematics and Computer Science, 2011, 21(4): 745-756.

MUANGPRATHUB J, BOONJING V, CHAMNONGTHAI K. Learning recommendation with formal concept analysis for intelligent tutoring system [J]. Heliyon, 2020, 6(10): E05227.

MEZNI H, ABDELJAOUED T. A cloud services recommendation system based on fuzzy formal concept analysis [J]. Data Knowledge Engineering, 2018, 116: 100-123.

AROUR K, YEFERNY T. Formal concept analysis based user model for distributed systems [J]. Multimedia Tools and Applications, 2017, 76(15): 16085-16105.

刘美玉, 祁建军, 刘伟. 三支概念格中的关联规则提取算法 [J]. 西安交通大学学报, 2021, 55(9): 189-196.

LIU Meiyu, QI Jianjun, LIU Wei. Extracting association rules in three-way concept lattices [J]. Journal of Xi'an Jiaotong University, 2021, 55(9): 189-196.

曹丽,魏玲,祁建军. 保持二元关系不变的概念约简 [J]. 模式识别与人工智能,2018,31(6):516-524.

CAO Li, WEI Ling, QI Jianjun. Concept reduction preserving binary relations [J]. Pattern Recognition and Artificial Intelligence, 2018, 31(6): 516-524.

魏玲, 曹丽, 祁建军, 等. 形式概念分析中的概念约简与概念特征 [J]. 中国科学(信息科学), 2020, 50(12): 1817-1833.

WEI Ling, CAO Li, QI Jianjun, et al. Concept reduction and concept characteristics in formal concept analysis [J]. Scientia Sinica(Informationis), 2020, 50(12): 1817-1833.

ZHAO Siyu, QI Jianjun, LI Junan, et al. Concept reduction in formal concept analysis based on representative concept matrix [J]. International Journal of Machine Learning and Cybernetics, 2023, 14(4): 1147-1160.

谢小贤, 李进金, 陈东晓, 等. 基于布尔矩阵的保持二元关系不变的概念约简 [J]. 山东大学学报(理学版), 2020, 55(5): 32-45.

XIE Xiaoxian, LI Jinjin, CHEN Dongxiao, et al. Concept reduction of preserving binary relations based on Boolean matrix [J]. Journal of Shandong University(Natural Science), 2020, 55(5): 32-45.

马文胜, 侯锡林. 形式概念分析中的同效关系与概念约简 [J]. 计算机科学, 2023, 50(4): 63-76.

MA Wensheng, HOU Xilin. Same effect relation and concept reduction in formal concept analysis [J]. Computer Science, 2023, 50(4): 63-76.

李俊余,李星璇,王霞,等.基于三元因子分析的三元概念约简 [J].南京大学学报(自然科学版),2020,56(4):480-493.

LI Junyu, LI Xingxuan, WANG Xia, et al. Reduction of triadic concepts based on triadic factor analysis [J]. Journal of Nanjing University(Natural Science), 2020, 56(4): 480-493.

王霞, 彭致华, 李俊余, 等. 一种基于概念可辨识矩阵的概念约简方法 [J]. 计算机科学, 2021, 48(1): 125-130.

WANG Xia, PENG Zhihua, LI Junyu, et al. Method of concept reduction based on concept discernibility matrix [J]. Computer Science, 2021, 48(1): 125-130.

刘津, 米据生, 李仲玲, 等. 基于概念复合的对偶三支概念格及其概念约简 [J]. 计算机科学, 2023, 50(6): 122-130.

LIU Jin, MI Jusheng, LI Zhongling, et al. Dual three-way concept lattice based on composition of concepts and its concept reduction [J]. Computer Science, 2023, 50(6): 122-130.

KUZNETSOV S O. A fast algorithm for computing all intersections of objects in a finite semi-lattice [J]. Automatic Documentation and Mathematical Linguistics, 1993, 27(5): 11-21.

KRAJCA P, OUTRATA J, VYCHODIL V. Advances in algorithms based on CbO [J]. Concept Lattices and Their Applications, 2010: 325-337.

ANDREWS S. In-close, a fast algorithm for computing formal concepts [C]//Proceedings of the 17th International Conference on Conceptual Structures. [S.l.]: [s.n.], 2009: 1-14.

ANDREWS S. A ‘Best-of-Breed' approach for designing a fast algorithm for computing fixpoints of Galois connections [J]. Information Sciences, 2015, 295: 633-649.

智慧来, 智东杰, 刘宗田. 从合取范式到析取范式的转换研究 [J]. 计算机工程与应用, 2012, 48(2): 15-17, 29.

ZHI Huilai, ZHI Dongjie, LIU Zongtian. Research on conversion from conjunctive normal form to disjunctive normal form [J]. Computer Engineering and Applications, 2012, 48(2): 15-17, 29.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Multithreaded Parallel Algorithm for Constructing Three-Way Concepts

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Numerical Simulation of Heat-Moisture Barrier Performance of a Horizontal Air Curtain in Cold Storage

Effects of Expansion Angle Crater Film Hole on the Film Cooling Characteristics of a Double-Wall Structure

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

Related Author

祁建军

汪文威

Related Institution

School of Computer Science and Technology, Xidian University

⁰