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    

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)

412

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] LI Jin-hai, HE Jian-jun, WU Wei-zhi. Optimization of class-attribute block in multi-granularity formal concept analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(5): 1-12.
[2] CHEN Dong-xiao, LI Jin-jin, LIN Rong-de, CHEN Ying-sheng. Rough approximation in multi-scale formal context [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(5): 22-31.
[3] LIU Ying-ying, MI Ju-sheng, LIANG Mei-she, LI Lei-jun. Three-way interval-set concept lattice [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 70-80.
[4] LIN Yan-li, LIU Xiao-dong. Research on local double relative quantitative decision-theoretic rough set for incomplete ordered information system [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 89-97.
[5] WAN Qing, MA Ying-cang, WEI Ling. Knowledge acquisition of multi-source data based on multigranularity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(1): 41-50.
[6] JING Yun-ge, JING Luo-xi, WANG Bao-li, CHENG Ni. An incremental attribute reduction approach when attribute values and attributes of the decision system change dynamically [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(1): 62-68.
[7] Xiu-mei HAO,Ning-ning LI. Quantitative characteristics and applications of P-information hidden mining [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 9-14.
[8] WANG Qi, LI Lian-zhong. Painlevé analysis, Lie symmetry and exact solutions to the generalized time-dependent coefficients Gardner equation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(4): 37-44.
[9] ZENG Xue-qiang, YE Zhen-lin, ZUO Jia-li, WAN Zhong-ying, WU Shui-xiu. A chunk increment partial least square algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(3): 93-101.
[10] ZHENG Li-ping, HU Min-jie, YANG Hong-he, LIN Yao-jin. Research on collaborative filtering algorithm based on rough set [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(2): 41-50.
[11] LI Jin-hai, WU Wei-zhi, DENG Shuo. Multi-scale theory in formal concept analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(2): 30-40.
[12] QIAN Ting, ZHAO Si-yu, HE Xiao-li. Rules acquisition of decision formal contexts based on attribute granular [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(10): 113-120.
[13] ZHAO Le-le, HAI Jin-ke. Coleman automorphisms of extensions of the finite groups by some groups [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(10): 109-112.
[14] . Ternary Montgomery algorithm on Hessian curve over GF(3m) [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(1): 96-102.
[15] ZUO Zhi-cui, ZHANG Xian-yong, MO Zhi-wen, FENG Lin. Block discernibility matrix based on decision classification and its algorithm finding the core [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 25-33.
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