Fast Calculation Algorithm of Approximations in Rough Sets Based on Matrices

doi:10.19678/j.issn.1000-3428.0064581

Abstract

Abstract: The calculation of upper and lower approximations is the core issue in rough set theory. Matrices can provide an efficient method for calculating the upper and lower approximations of concepts in rough set models. However，in current matrix methods，each object in the universe must be operated on with all objects in the universe， resulting in a significant time cost.To improve the efficiency of calculating approximations using matrices，a matrix method is proposed for quickly calculating upper and lower approximations. For a given concept，a local relational matrix is constructed based on the extensions of the concept and its complement. Matrix operations are performed on the local relational and identity matrices to obtain positive and boundary domain Boolean matrices. Subsequently，matrix operations are performed on the transposition of the local relational and identity matrices to obtain negative and boundary domain Boolean matrices. In this matrix method，only calculating the approximation based on the local relational matrix is necessary，that is，each object in the universe can be divided into corresponding regions without needing to perform operations on all objects in the universe，which significantly reduces the number of operations of the algorithm compared with traditional matrix algorithms，thereby reducing the time cost. Experiments on eight open datasets show that，compared with four traditional matrix algorithms，the proposed matrix algorithm can improve the running speed by at least 70% and effectively improve the efficiency of the approximation calculation.

Key words: rough set, approximation, identity matrix, local relation matrix, matrix operation

摘要： 在粗糙集理论中，上、下近似集的计算是核心问题。矩阵能提供一种高效的方法来计算粗糙集模型中概念的上、下近似集，但是在目前的矩阵方法中，论域中每个对象都要与论域中全部对象进行运算，从而导致较大的时间代价。为提高使用矩阵计算近似集时的效率，提出一种快速计算上、下近似集的矩阵方法。对于一个给定的概念，基于概念的外延和概念补集的外延构建一个局部关系矩阵，对局部关系矩阵和单位矩阵进行矩阵运算得到正域和边界域布尔矩阵，对局部关系矩阵的转置和单位矩阵进行矩阵运算得到负域和边界域布尔矩阵。在该矩阵方法中，只需要根据局部关系矩阵就可以计算近似集，即论域中每个对象不必和论域中全部对象进行运算就可以被划分到相应的区域，使得算法的运算次数相比传统矩阵算法大幅减少，从而降低时间成本。在8个公开数据集上的实验结果表明，与4种传统的矩阵算法相比，该矩阵算法的运行速度至少提升70%，可以有效提高近似集计算效率。

关键词: 粗糙集, 近似集, 单位矩阵, 局部关系矩阵, 矩阵运算

CLC Number:

TP391

XU Yi, HOU Di. Fast Calculation Algorithm of Approximations in Rough Sets Based on Matrices[J]. Computer Engineering, 2023, 49(5): 22-28.

徐怡, 侯迪. 基于矩阵的粗糙集近似集快速计算算法[J]. 计算机工程, 2023, 49(5): 22-28.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0064581

http://www.ecice06.com/EN/Y2023/V49/I5/22

Figures/Tables 5

References

[1] PAWLAK Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356.
[2] PENG X S,WEN J Y,LI Z H,et al.Rough set theory applied to pattern recognition of partial discharge in noise affected cable data[J].IEEE Transactions on Dielectrics and Electrical Insulation,2017,24(1):147-156.
[3] SINHA A K,NAMDEV N.Feature selection and pattern recognition for different types of skin disease in human body using the rough set method[J].Network Modeling Analysis in Health Informatics and Bioinformatics,2020,9(1):27.
[4] JAYASURUTHI L,SHALINI A,KUMAR V V.Application of rough set theory in data mining market analysis using rough sets data explorer[J].Journal of Computational and Theoretical Nanoscience,2018,15(6):2126-2130.
[5] ABDELRAHMAN O,UNIVERSITY C,HEFNY H,et al.A novel data mining approach for big data based on rough sets and fuzzy logic[J].International Journal of Intelligent Engineering and Systems,2019,12(6):133-146.
[6] JEON G,ANISETTI M,DAMIANI E,et al.Real-time image processing systems using fuzzy and rough sets techniques[J].Soft Computing,2018,22(5):1381-1384.
[7] SAVCHENKO A V.Sequential three-way decisions in multi-category image recognition with deep features based on distance factor[J].Information Sciences,2019,489:18-36.
[8] INBARANI H H,AZAR A T,JOTHI G.Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis[J].Computer Methods and Programs in Biomedicine,2014,113(1):175-185.
[9] AL-SHAMI T M.An improvement of rough sets' accuracy measure using containment neighborhoods with a medical application[J].Information Sciences,2021,569:110-124.
[10] 郑文彬,李进金,张燕兰,等.基于矩阵的多粒度粗糙集粒度约简方法[J].南京大学学报(自然科学),2021,57(1):141-149. ZHENG W B,LI J J,ZHANG Y L,et al.Matrix-based granulation reduction method for multi-granulation rough sets[J].Journal of Nanjing University (Natural Science),2021,57(1):141-149.(in Chinese)
[11] WANG J Q,ZHANG X H.Matrix approaches for some issues about minimal and maximal descriptions in covering-based rough sets[J].International Journal of Approximate Reasoning,2019,104:126-143.
[12] SOWKUNTLA P,SAI PRASAD P S.MapReduce based parallel fuzzy-rough attribute reduction using discernibility matrix[J].Applied Intelligence,2022,52(1):154-173.
[13] XU Y,WANG Q,SUN W K.Matrix-based incremental updating approximations in multigranulation rough set under two-dimensional variation[J].International Journal of Machine Learning and Cybernetics,2021,12(4):1041-1065.
[14] MUTHUKUMAR P,KRISHNAN G.Generalized fuzzy soft rough matrices and their applications in decision-making problems[J].International Journal of Fuzzy Systems,2018,20(2):500-514.
[15] 郑文彬,李进金,于佩秋,等.变精度多粒度粗糙集近似集更新的矩阵算法[J].计算机应用,2019,39(11):3140-3145. ZHENG W B,LI J J,YU P Q,et al.Matrix-based algorithm for updating approximations in variable precision multi-granulation rough sets[J].Journal of Computer Applications,2019,39(11):3140-3145.(in Chinese)
[16] 刘文军,郭庆.粗糙集的矩阵刻画[J].模糊系统与数学,2019,33(3):169-174. LIU W J,GUO Q.The matrix depict approaches of rough sets[J].Fuzzy Systems and Mathematics,2019,33(3):169-174.(in Chinese)
[17] HUANG Q,LI T,HUANG Y,et al.Dynamic dominance rough set approach for processing composite ordered data[J].Knowledge-Based Systems,2020,187:104829.
[18] LUO C,LI T,YI Z,et al.Matrix approach to decision-theoretic rough sets for evolving data[J].Knowledge-Based Systems,2016,99:123-134.
[19] YANG X,LI T R,LIU D,et al.A unified framework of dynamic three-way probabilistic rough sets[J].Information Sciences,2017,420:126-147.
[20] CHEN J J,YU S H,WEI W J,et al.Matrix-based method for solving decision domains of neighbourhood multi-granulation decision-theoretic rough sets[J].CAAI Transactions on Intelligence Technology,2022,7(2):313-327.
[21] GAO Q,MA L.A novel notion in rough set theory:invariant subspace[J].Fuzzy Sets and Systems,2022,440:90-111.
[22] LI S Y,YU L,HONG Z Y,et al.Composition of rough approximations under the dominance-based relation[C]//Proceedings of IEEE International Conference on Intelligent Systems and Knowledge Engineering.Washington D.C.,USA:IEEE Press,2020:227-231.
[23] ZHANG J,ZHU Y,PAN Y,et al.Efficient parallel Boolean matrix based algorithms for computing composite rough set approximations[J].Information Sciences,2016,329:287-302.
[24] ZHANG J B,WONG J S,PAN Y,et al.A parallel matrix-based method for computing approximations in incomplete information systems[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(2):326-339.
[25] ZHU W.Generalized rough sets based on relations[J].Information Sciences,2007,177(22):4997-5011.
[26] PAWLAK Z.Rough sets,rough relations and rough functions[J].Fundamenta Informaticae,1996,27(2/3):103-108.
[27] UCI machine learning data repository[EB/OL].[2022-03-27].https://archive.ics.uci.edu/ml/index.html.
[28] Kaggle:your machine learning and data science community[EB/OL].[2022-03-27].https://www.kaggle.com.

Please choose a citation manager

Content to export