Attribute Reductions of Formal Context Based on Information Entropy
CHEN Dongxiao1, LI Jinjin1,2, LIN Rongde1, CHEN Yingsheng1
1. Fujian Province University Key Laboratory of Computational Science, School of Mathematical Sciences, Huaqiao University, Quanzhou 362021 2. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000
Abstract Attribute significances and attribute reduction are crucial in formal concept analysis. Some approaches to attribute reduction of formal context are proposed based on information entropy. Firstly, information entropy, conditional entropy and mutual information of formal context are defined, and attribute reduction by means of conditional entropy is conducted in consistent decision formal context. The equivalence between the granular consistency and the entropy consistency in decision formal context is produced. Secondly, limitary information entropy, limitary conditional entropy and limitary mutual information are proposed, and attribute reductions are conducted by means of limitary conditional entropy in inconsistent formal decision context. Finally, the attribute reduction algorithms of consistent and inconsistent formal decision contexts are proposed by the significance of attributes, and numerical experiments show the efficiency of the proposed algorithms.
Fund:National Natural Science Foundation of China(No.11871259,11701258), Program for Innovative Research Team in Science and Technology in University of Fujian Province, Quanzhou High-Level Talents Support Plan(No.2017ZT012)
Corresponding Authors:
LI Jinjin,Ph.D.,professor. His research interests include topology, rough set and concept lattice.
About author:: CHEN Dongxiao, master, lecturer. His research interests include rough set and concept lattice.LIN Rongde,Ph.D.,associate professor. His research interests include artificial intelligence and computer systems.CHEN Yingsheng, master, lecturer. His re-search interests include rough set and concept lattice.
[1] ZADEH L A. Fuzzy Sets and Information Granularity[T/OL]. [2020-05-22]. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1979/ERL-m-79-45.pdf. [2] WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts // RIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1982: 445-470. [3] DOIGNON J P, FALMAGNE J C. Spaces for the Assessment of Knowledge. International Journal of Man-Machine Studies, 1985, 23(2): 175-196. [4] 王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766. (WANG G Y, YU H, YANG D C. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759-766.) [5] YAO Y Y, YAO B X. Covering Based Rough Set Approximations. Information Sciences, 2012, 200: 91-107. [6] LI F, YIN Y Q. Approaches to Knowledge Reduction of Covering Decision Systems Based on Information Theory. Information Sciences, 2009, 179(11): 1694-1704. [7] XU W H, LI Y, LIAO X W. Approaches to Attribute Reductions Based on Rough Set and Matrix Computation in Inconsistent Ordered Information Systems. Knowledge-Based Systems, 2012, 27: 78-91. [8] DAI J H, WANG W T, TIAN H W, et al. Attribute Selection Based on a New Conditional Entropy for Incomplete Decision Systems. Knowledge-Based Systems, 2013, 39: 207-213. [9] LIU J N K, HU Y X, HE Y L, et al. A Set Covering Based Approach to Find the Reduct of Variable Precision Rough Set. Information Sciences, 2014, 275: 83-100. [10] D′EER L, RESTREPO M, CORNELIS C, et al. Neighborhood Operators for Covering-Based Rough Sets. Information Sciences, 2016, 336: 21-44. [11] 张燕兰,李长清.基于证据理论的覆盖决策信息系统的属性约简.模式识别与人工智能, 2018, 31(9): 797-808. (ZHANG Y L, LI C Q. Attribute Reduction of Covering Decision Information System Based on Evidence Theory. Pattern Recognition and Artificial Intelligence, 2018, 31(9): 797-808.) [12] 魏 玲,祁建军,张文修.决策形式背景的概念格属性约简.中国科学(信息科学), 2008, 38(2): 195-208. (WEI L, QI J J, ZHANG W X. Attribute Reduction Theory of Concept Lattice Based on Decision Formal Contexts. Science in China(Information Science), 2008, 38(2): 195-208.) [13] WU W Z, LEUNG Y, MI J S. Granular Computing and Knowledge Reduction in Formal Contexts. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1461-1474. [14] WANG X, MA J M. A Novel Approach to Attribute Reduction in Concept Lattices // Proc of the International Conference on Rough Sets and Knowledge Technology. Berlin, Heidelberg: Springer, 2006: 522-529. [15] LI T J, LI M Z, GAO Y. Attribute Reduction of Concept Lattice Based on Irreducible Elements. International Journal of Wavelets, Multiresolution and Information Processing, 2013, 11(6). DOI: 10.1142/S021969131350046X. [16] GANTER B, WILLE R. Formal Concept Analysis: Mathematical Foundations. Berlin, Germany: Springer, 1999. [17] LI J H, MEI C L, LÜ Y J. Knowledge Reduction in Decision Formal Contexts. Knowledge-Based Systems, 2011, 24(5): 709-715. [18] LI J H, KUMUMAR C A, MEI C L, et al. Comparison of Reduction in Formal Decision Contexts. International Journal of Approximate Reasoning, 2017, 80: 100-122. [19] QIN K Y, LIN H, JIANG Y T. Local Attribute Reductions of Formal Contexts. International Journal of Machine Learning and Cybernetics, 2020, 11(1): 81-93. [20] SHAO M W, WU W Z, WANG X Z, et al. Knowledge Reduction Methods of Covering Approximate Spaces Based on Concept La-ttice. Knowledge-Based Systems, 2020, 191. DOI: 10.1016/j.knosys.2019.105269. [21] 张晓鹤,米据生,李美争.粒协调决策形式背景的属性约简与规则融合.智能系统学报, 2019, 14(6): 1138-1143. (ZHANG X H, MI J S, LI M Z. Attribute Reduction and Rule Fusion in Granular Consistent Formal Decision Contexts. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1138-1143.) [22] LI J Y, WANG X, WU W Z, et al. Attribute Reduction in Inconsistent Formal Decision Contexts Based on Congruence Relations. International Journal of Machine Learning and Cybernetics, 2017, 8(1): 81-94. [23] 林艺东,李进金,张呈玲.基于矩阵的模糊-经典概念格属性约简.模式识别与人工智能, 2020, 33(1): 21-31. (LIN Y D, LI J J, ZHANG C L. Attribute Reductions of Fuzzy-Crisp Concept Lattices Based on Matrix. Pattern Recognition and Artificial Intelligence, 2020, 33(1): 21-31.) [24] 马 捷,葛 岩,蒲泓宇.属性约简方法研究综述.数据分析与知识发现, 2020, 4(1): 40-50. (MA J, GE Y, PU H Y. Survey of Attribute Reduction Methods. Data Analysis and Knowledge Discovery, 2020, 4(1): 40-50.) [25] YAO Y Y. A Triarchic Theory of Granular Computing. Granular Computing, 2016, 1(2): 145-157. [26] WEI L, QI J J. Relation between Concept Lattice Reduction and Rough Set Reduction. Knowledge-Based Systems, 2010, 23(8): 934-938. [27] CHEN J K, LI J J, LIN Y J, et al. Relations of Reduction between Covering Generalized Rough Sets and Concept Lattices. Information Sciences, 2015, 304: 16-27. [28] DIAS S M, VIEIRA N J. Concept Lattices Reduction: Definition, Analysis and Classification. Expert Systems with Application, 2015, 42(20): 7084-7097. [29] SHANNON C E. The Mathematical Theory of Communication. The Bell System Technical Journal, 1948, 27(3/4): 379-423. [30] LI J L, HE Z Y, ZHU Q L, et al. An Entropy-Based Weighted Concept Lattice for Merging Multi-source Geo-Ontologies. Entropy, 2013, 15(6): 2303-2318. [31] SINGH P K, CHERUKURI A K, LI J H. Concepts Reduction in Formal Concept Analysis with Fuzzy Setting Using Shannon Entropy. International Journal of Machine Learning and Cybernetics, 2017, 8(1): 179-189. [32] 李美争,李磊军,米据生,等.概念格中基于粗糙熵的属性约简方法.计算机科学, 2018, 45(1): 84-89. (LI M Z, LI L J, MI J S, et al. Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice. Computer Science, 2018, 45(1): 84-89.)
2020, Vol. 33 
