JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2020, Vol. 55 ›› Issue (5): 32-45.doi: 10.6040/j.issn.1671-9352.c.2020.004

Previous Articles     Next Articles

Concept reduction of preserving binary relations based on Boolean matrix

XIE Xiao-xian1, LI Jin-jin1,2*, CHEN Dong-xiao1, LIN Rong-de1,3   

  1. 1. School of Mathematical Sciences, Huaqiao University, Quanzhou 362021, Fujian, China;
    2. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000, Fujian, China;
    3. Fujian Province University Key Laboratory of Computational Science, School of Mathematical Sciences, Huaqiao University, Quanzhou 362021, Fujian, China
  • Published:2020-05-06

PDF (PC)

788

Abstract: The problems of concept characteristics and concept reduction preserving binary relations are studied by Boolean matrix operation. Firstly, formal context is described as a Boolean matrix, the relation matrices of object\attribute are generated by using the binary relation matrix, and their related properties are studied. Further, concept characteristics of three different types of concepts in the processing of concept reduction are obtained by using Boolean matrix operation. Finally, the minimum operation of concept interval sets is done with Boolean matrix operation, the discernibility matrix is simplified, and a method of calculating concept reduction is given. Compared with the existed methods of concept reduction in formal context, the proposed matrix algorithm is simple and its time complexity is lower.

Key words: formal context, formal concept, Boolean matrix, reduction, characteristic

CLC Number: 

  • TP18
[1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C] //Ordered Sets. Berlin: Springer, 1982: 445-470.
[2] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin: Springer, 1999.
[3] YAO Yiyu. Concept lattices in rough set theory[C] //Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society. Washington, D.C.:IEEE, 2004: 796-801.
[4] 张文修,魏玲,祁建军.概念格的属性约简理论与方法[J].中国科学E辑:信息科学,2005, 35(6):628-639. ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice[J]. Science in China Series E: Information Science, 2005, 35(6):628-639.
[5] 魏玲.粗糙集与概念格约简理论与方法[D].西安:西安交通大学,2005. WEI Ling. Reduction theory and approach to rough set and concept lattice[D]. Xian: Xian Jiaotong University, 2005.
[6] WANG Xia, MA Jianmin. A novel approach to attribute reduction in concept lattices[C] //Proceedings of the First International Conference on Rough Sets and Knowledge Technology. Berlin: Springer, 2006: 522-529.
[7] WU Weizhi, LEUNG Yee, MI Jusheng. Granular computing and knowledge reduction in formal contexts[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10):1461-1474.
[8] 李金海,吴伟志.形式概念分析的粒计算方法及其研究展望[J].山东大学学报(理学版), 2017, 52(7):1-12. LI Jinhai, WU Weizhi. Granular computing approach for formal concept analysis and its research outlooks[J]. Journal of Shandong University(Natural Science), 2017,52(7):1-12.
[9] 张恩胜.区间集概念格属性约简的组成与结构[J].山东大学学报(理学版),2018,53(8):17-24. ZHANG Ensheng. Composition and structure on attribute reduction of interval-set concept lattices[J]. Journal of Shandong University(Natural Science), 2018, 53(8):17-24.
[10] 曹丽,魏玲,祁建军.保持二元关系不变的概念约简[J].模式识别与人工智能,2018,31(6):516-524. CAO Li, WEI Ling, QI Jianjun. Concept reduction preserving binary relations[J]. Pattern Recognition and Artifificial Intelligence, 2018, 31(6):516-524.
[11] 魏玲,曹丽,祁建军,等.形式概念分析中的概念约简与概念特征[J/OL].中国科学:信息科学,2019[2020-02-20]. http://engine.scichina.com/doi/10.1360/N112018-00272. WEI Ling, CAO Li, QI Jianjun, et al. Concept reduction and concept characteristics in formal concept analysis[J/OL]. Scientia Sinica Informationis, 2019[2020-02-20]. http://engine.scichina.com/doi/10.1360/N112018-00272.
[12] 魏玲,祁建军,张文修.决策形式背景的概念格属性约简[J].中国科学E辑:信息科学,2008, 38(2):195-208. WEI Ling, QI Jianjun, ZHANG Wenxiu. Attribute reduction theory of concept lattice based on decision formal contexts[J]. Science in China Series E: Information Science, 2008, 38(2):195-208.
[13] LI Jinhai, MEI Changlin, LV Yuejin. A heuristic knowledge-reduction method for decision formal contexts[J]. Computers & Mathematics with Applications, 2011, 61(4):1096-1106.
[14] BELOHLAVEK R, TRNECKA M. From-below approximations in Boolean matrix factorization: geometry and new algorithm[J]. Journal of Computer and System Sciences, 2015, 81:1678-1697.
[15] TRNECKA M, TRNECKOVA M. Data reduction for Boolean matrix factorization algorithms based on formal concept analysis[J]. Knowledge-Based Systems, 2018, 158:75-80.
[16] 张清新.基于布尔矩阵的决策形式背景协调集判断方法[J].漳州师范学院,2012, 75(1):22-25. ZHANG Qingxin. The judgment method of consistent sets in decision formal context based on Boolean matrix[J]. Journal of Zhangzhou Normal University(Natural Science), 2012, 75(1):22-25.
[17] 张清新.基于布尔矩阵的概念格属性约简方法[D].漳州:漳州师范学院,2012. ZHANG Qingxin. Attribute reduction method for concept lattices based on Boolean matrices[D]. Zhangzhou: Zhangzhou Normal University, 2012.
[18] 林艺东,李进金,张呈玲. 基于矩阵的模糊-经典概念格属性约简[J]. 模式识别与人工智能,2020, 33(1):21-31. LIN Yidong, LI Jinjin, ZHANG Chengling. Attribute reductions of fuzzy-crisp concept lattices based on matrix[J]. Pattern Recognition and Artifificial Intelligence, 2020, 33(1):21-31.
[19] KIM K H.布尔矩阵理论及其应用[M].何善堉,孔德涌,黄正篱,等译.北京:知识出版社,1987. KIM K H. Boolean matrix theory and applications[M]. HE Shanyu, KONG Deyong, HUANG Zhengli, et al. Beijing: Knowledge Publishing House, 1987.
[1] ZHU Mingyang, HUANG Yuxin, YU Zhengtao. Method for verbose queries reduction by integrating key and latent concepts [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(3): 66-74.
[2] MIAO Jingjing, SUN Tongjun. Adaptive finite element method for two-dimensional nonlinear convection-diffusion equations based on gradient reconstruction [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(2): 1-9.
[3] LI Xiaolan, LIU Zhonghui, MIN Fan. A network concept incorporated adjacency relationships between objects and its recommendation application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 56-68.
[4] XU Bing, YANG Sufen. Research on pricing and carbon emission reduction of platform supply chain under government subsidy and corporate social responsibility [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(6): 1-17.
[5] WANG Jing, GE Tongtong, SI Fengshan. Research on complexity of supply chain considering carbon emission reduction and two-way fairness concerns [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(6): 31-44.
[6] FENG Zhangwei, PANG Shiqi. Green production mode selection of low-value recyclable products considering low-carbon consumption preferences under “Dual Carbon” goals [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(6): 103-113.
[7] WU Hai, NIU Jiaojiao, TIE Wenyan, ZUO Jiankun. Concept lattice construction method based on granular concept network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 21-31.
[8] WANG Yutao, LIAN Yuechang, ZHAO Shengyuan, LIU Wendong. Research progress on fabrication and application of self-healing superhydrophobic materials [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(10): 59-78.
[9] WANG Yifan, JIN Ming, ZHANG Qin, WEI Ling. Rule acquisition based on concept reduction in strongly consistent formal decision context [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(1): 83-90.
[10] Wei SHAO,Gaoyu ZHU,Lei YU,Jiafeng GUO. Dimensionality reduction and retrieval algorithms for high dimensional data [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 27-43.
[11] FAN Min, QIN Qin, LI Jinhai. Neighborhood recommendation algorithm based on three-way causality force [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 12-22.
[12] SONG Suyang, YE Jun, ZENG Guangcai, SUN Qing. Multi-granularity rough set attribute reduction algorithm based on optimized discernibility matrix [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 52-62.
[13] WU Jiang, LIU Deshan,YU Yingying, PANG Kuo, LI Xiaofeng. Rule extraction based on linguistic concept lattice with fuzzy object [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 63-69.
[14] Zhonghui LIU,Shuai JIANG,Fan MIN. Heuristic construction method of fuzzy concept set and its recommended application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 14-26.
[15] Lianjie ZHANG,Wei LI,Ping YANG,Min ZENG,Qiuwang WANG. Effect of PCM-PCHE on SCO2 Brayton cycle under variable operating conditions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(11): 74-84.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd