Attribute Reduction in Multi-granularity Formal Decision Contexts
LI Jinhai1,2, ZHOU Xinran1,2
1. Data Science Research Center, Kunming University of Science and Technology, Kunming 650500; 2. Faculty of Science, Kunming University of Science and Technology, Kunming 650500
Abstract The existing attribute reduction methods for formal decision contexts cannot deal with multi-granularity data. Therefore, three attribute reduction methods are put forward in multi-granularity formal decision contexts to realize attribute reduction of an information system by removing the class-attribute blocks from the same category under each consistent granularity layer. Firstly, from the perspective of information granules, information entropy and conditional information entropy of the consistent granularity layer are introduced in the multi-granularity formal decision contexts to further measure the significance of attributes. Secondly, based on the average conditional information entropy and conditional information entropy in the coarsest and finest consistent formal decision contexts, the consistent granularity attribute reduction method and the coarsest and finest consistent granularity attribute reduction methods are proposed in multi-granularity formal decision contexts, and their corresponding implementation algorithms are developed. Finally, the experimental results show that the proposed attribute reduction methods are effective. In addition, it is concluded that the constraint of the consistent granularity attribute reduction method is too strict. Instead, the constraints of the coarsest and finest consistent granularity attribute reduction methods are relatively weaker.
Fund:National Natural Science Foundation of China(No.11971211,12171388)
Corresponding Authors:LI Jinhai, Ph.D., professor. His research interests include cognitive computing, granular computing, big data analysis, concept lattice and rough set.
About author:: ZHOU Xinran, master student. Her research interests include formal concept analysis, granular computing and rough set.
[1] WILLE R. Restructuring Lattice Theory: An Approach Based on Hie-rarchies of Concepts // RIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1982: 445-470. [2] 张玲,张钹.基于商空间的问题求解:粒度计算的理论基础.北京:清华大学出版社, 2014. (ZHANG L, ZHANG B.Quotient Space Based Problem Solving: A Theoretical Foundation of Granular Computing. Beijing, China: Tsinghua University Press, 2014.) [3] MULKAR-MEHTA R, HOBBS J, HOVY E. Granularity in Natural Language Discourse // Proc of the 9th International Conference on Computational Semantics. Stroudsburg, USA: ACL, 2011: 360-364. [4] WEI L, WAN Q. Granular Transformation and Irreducible Element Judgment Theory Based on Pictorial Diagrams. IEEE Transactions on Cybernetics, 2016, 46(2): 380-387. [5] YAO Y Y. Three-Way Decisions with Probabilistic Rough Sets. Information Sciences, 2010, 180(3): 341-353. [6] 苗夺谦,张清华,钱宇华,等.从人类智能到机器实现模型——粒计算理论与方法.智能系统学报, 2016, 11(6): 743-757. (MIAO D Q, ZHANG Q H, QIAN Y H, et al From Human Inte-lligence to Machine Implementation Model: Theories and Applications Based on Granular Computing. CAAI Transactions on Intelligent Systems, 2016, 11(6): 743-757.) [7] 曾望林,折延宏.面向对象的多粒度形式概念分析.计算机科学, 2018, 45(10): 51-53, 63. (ZENG W L, SHE Y H. Object-Oriented Multigranulation Formal Concept Analysis. Computer Science, 2018, 45(10): 51-53, 63.) [8] 李金海,吴伟志,邓硕.形式概念分析的多粒度标记理论.山东大学学报(理学版), 2019, 54(2): 30-40. (LI J H, WU W Z, DENG S. Multi-scale Theory in Formal Concept Analysis. Journal of Shandong University(Natural Science), 2019, 54(2): 30-40.) [9] 李金海,李玉斐,米允龙,等.多粒度形式概念分析的介粒度标记方法.计算机研究与发展, 2020, 57(2): 447-458. (LI J H, LI Y F, MI Y L, et al. Meso-Granularity Labeled Method for Multi-granularity Formal Concept Analysis. Journal of Computer Research and Development, 2020, 57(2): 447-458.) [10] PAWLAK Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356. [11] KUZNETSOV S O. Machine Learning on the Basis of Formal Concept Analysis. Automation and Remote Control, 2001, 62(10): 1543-1564. [12] 李金海,魏玲,张卓,等.概念格理论与方法及其研究展望.模式识别与人工智能, 2020, 33(7): 619-642. (LI J H, WEI L, ZHANG Z, et al. Concept Lattice Theory and Method and Their Research Prospect. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 619-642.) [13] KUMAR C A, SRINIVAS S. Mining Associations in Health Care Data Using Formal Concept Analysis and Singular Value Decomposition. Journal of Biological Systems, 2010, 18(4): 787-807. [14] LI J H, MEI C L, CHERUKURI A K, et al. On Rule Acquisition in Decision Formal Contexts. International Journal of Machine Learning and Cybernetics, 2013, 4(6): 721-731. [15] POELMANS J, IGNATOV D I, KUZNETSOV S O, et al. Formal Concept Analysis in Knowledge Processing: A Survey on Applications. Expert Systems with Applications, 2013, 40(16): 6538-6560. [16] SINGH P K, KUMAR C A. Bipolar Fuzzy Graph Representation of Concept Lattice. Information Sciences, 2014, 288: 437-448. [17] TAN A H, LI J J, LIN G P. Connections between Covering-Based Rough Sets and Concept Lattices. Informational Journal of Approximation Reasoning, 2015, 56(A): 43-58. [18] WANG L D, LIU X D. Concept Analysis via Rough Set and AFS Algebra. Information Sciences, 2008, 178(21): 4125-4137. [19] YAO Y Y. Concept Lattices in Rough Set Theory // Proc of the IEEE Annual Meeting of the Fuzzy Information. Washington, USA: IEEE, 2004, II: 796-801. [20] ZHANG W X, MA J M, FAN S Q. Variable Threshold Concept Lattices. Information Sciences, 2007, 177(22): 4883-4892. [21] 张文修,魏玲,祁建军.概念格的属性约简理论与方法.中国科学(信息科学), 2005, 35(6): 628-639. (ZHANG W X, WEI L, QI J J. Attribute Reduction Theory and Approach to Concept Lattice. Science in China(Information Sciences), 2005, 35(6): 628-639.) [22] 张文修,仇国芳,吴伟志.粗糙集属性约简的一般理论.中国科学(信息科学), 2005, 35(12): 1304-1313. (ZHANG W X, QIU G F, WU W Z. Generalized Theory of Attribute Reduction in Rough Sets. Science in China(Information Sciences), 2005, 35(12): 1304-1313.) [23] WU W Z, LEUNG Y, MI J S. Granular Computing and Knowledge Reduction in Formal Contexts. IEEE Transaction on Knowledge and Data Engineering, 2009, 10(21): 1461-1474. [24] 魏玲,祁建军,张文修.决策形式背景的概念格属性约简.中国科学(信息科学), 2008, 38(2): 195-208. (WEI L, QI J J, ZHANG W X. Attribute Reduction of Concept Lattice in Decision Formal Context. Science in China(Information Sciences), 2008, 38(2): 195-208.) [25] LI J H, MEI C L, LÜ Y J. Knowledge Reduction in Decision Formal Contexts. Knowledge-Based Systems, 2011, 24(5): 709-715. [26] 李进金,张燕兰,吴伟志,等.形式背景与协调决策形式背景属性约简与概念格生成.计算机学报, 2014, 37(8): 1768-1774. (LI J J, ZHANG Y L, WU W Z, et al. Attribute Reduction for Formal Context and Consistent Decision Formal Context and Con-cept Lattice Generation. Chinese Journal of Computers, 2014, 37(8): 1768-1774.) [27] SHANNON C E, WEARER W.The Mathematical Theory of Communication. Champaign, USA: University of Illinois Press, 1971. [28] DAI J H, HU H, ZHENG G J, et al. Attribute Reduction in Interval-Valued Information Systems Based on Information Entropies. Frontiers of Information Technology & Electronic Engineering, 2016, 17(9): 919-928. [29] ZHANG X, MEI C L, CHEN D G, et al. Active Incremental Feature Selection Using a Fuzzy-Rough-Set-Based Information Entropy. IEEE Transactions on Fuzzy Systems, 2020, 28(5): 901-915. [30] ZHANG X, MEI C L, CHEN D G, et al. Feature Selection in Mixed Data: A Method Using a Novel Fuzzy Rough Set-Based Information Entropy. Pattern Recognition, 2016, 56: 1-15. [31] THUY N N, WONGTHANAVASU S. On Reduction of Attributes in Inconsistent Decision Tables Based on Information Entropies and Stripped Quotient Sets. Expert Systems with Applications, 2019, 137: 308-323. [32] WANG F, LIANG J Y, QIAN Y H. Attribute Reduction: A Dimension Incremental Strategy. Knowledge-Based Systems, 2013, 39: 95-108. [33] HU Q H, XIE Z X, YU D R. Hybrid Attribute Reduction Based on a Novel Fuzzy-Rough Model and Information Granulation. Pa-ttern Recognition, 2007, 40(12): 3509-3521. [34] 王国胤,于洪,杨大春.基于条件信息熵的决策表属性约简.计算机学报, 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.) [35] 陈东晓,李进金,林荣德,等.基于信息熵的形式背景属性约简.模式识别与人工智能, 2020, 33(9): 786-798. (CHEN D X, LI J J, LIN R D, et al. Attribute Reductions of Formal Context Based on Information Entropy. Pattern Recognition and Artificial Intelligence, 2020, 33(9): 786-798.) [36] 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. [37] 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. [38] 张文修,仇国芳.基于粗糙集的不确定决策.北京:清华大学出版社, 2005. (ZHANG W X, QIU G F.Uncertain Decision Making Based on Rough Set. Beijing, China: Tshinghua University Press, 2005.) [39] 梁吉业,钱宇华.信息系统中的信息粒与熵理论.中国科学(信息科学), 2008, 38(12): 2048-2065. (LIANG J Y, QIAN Y H. Information Granularity and Entropy Theory in Information systems. Science in China(Information Sciences), 2008, 38(12): 2048-2065.) [40] 苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681-684. (MIAO D Q, HU G R. A Heuristic Algorithm for Reduction of Knowledge. Journal of Computer Research and Development, 1999, 36(6): 681-684.) [41] 高乐,王振,魏玲,等.基于属性分类的悲观概念格与乐观概念格.模式识别与人工智能, 2021, 34(8): 701-711. (GAO L, WANG Z, WEI L, et al. Pessimistic Concept Lattices and Optimistic Concept Lattices Based on Attribute Classification. Pattern Recognition and Artificial Intelligence, 2021, 34(8): 701-711.) [42] 李金海,贺建君,吴伟志.多粒度形式概念分析的类属性块优化.山东大学学报(理学版), 2020, 55(5): 1-12. (LI J H, HE J J, WU W Z. Optimization of Class-Attribute Block in Multi-granularity Formal Concept Analysis. Journal of Shandong University(Natural Science), 2020, 55(5): 1-12.) [43] HUANG C C, LI J H, DIAS S M. Attribute Significance, Consistency Measure and Attribute Reduction in Formal Concept Analysis. Neural Network World, 2016, 26(6): 607-623.
2022, Vol. 35 
