您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (5): 32-45.doi: 10.6040/j.issn.1671-9352.c.2020.004

• • 上一篇    

基于布尔矩阵的保持二元关系不变的概念约简

谢小贤1,李进金1,2*,陈东晓1,林荣德1,3   

  1. 1.华侨大学数学科学学院, 福建 泉州 362021;2.闽南师范大学数学与统计学院, 福建 漳州 363000;3.福建省华侨大学计算科学重点实验室, 福建 泉州 362021
  • 发布日期:2020-05-06
  • 作者简介:谢小贤(1980— ),女,硕士,讲师,研究方向为粗糙集和概念格. E-mail:littlecn@hqu.edu.cn*通信作者简介:李进金(1960— ),男,博士,教授,博士生导师,研究方向为拓扑学与不确定性理论. E-mail:jinjinli@mnnu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(11871259);福建省自然科学基金资助项目(2017J01114,2016J01304);华侨大学人才启动资助项目(16BS814)

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

摘要: 通过布尔矩阵运算,研究保持二元关系不变的概念特征和概念约简问题。首先,用布尔矩阵表示形式背景,用关系矩阵生成对象\属性关系矩阵,并研究其相关性质。其次,通过矩阵运算获取概念约简中三种不同概念的概念特征。最后,用矩阵运算实现概念区间集的极小运算,简化辨识矩阵,给出概念约简的求解方法,与已有的形式背景的概念约简方法进行比较,该矩阵算法简单且时间复杂度更低。

关键词: 形式背景, 形式概念, 布尔矩阵, 约简, 特征

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

中图分类号: 

  • 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] 李金海,贺建君,吴伟志. 多粒度形式概念分析的类属性块优化[J]. 《山东大学学报(理学版)》, 2020, 55(5): 1-12.
[2] 贺晓丽,折延宏. 基于属性粒化的近似概念分析及规则提取[J]. 《山东大学学报(理学版)》, 2020, 55(5): 13-21.
[3] 陈东晓,李进金,林荣德,陈应生. 多尺度形式背景及其粗糙近似[J]. 《山东大学学报(理学版)》, 2020, 55(5): 22-31.
[4] 贾淑香,邓波,冶成福,付凤,陈辉龙. 图的Resolvent Estrada指标的上(下)界刻画[J]. 《山东大学学报(理学版)》, 2020, 55(4): 92-96.
[5] 林艳丽,刘晓东. 不完备序信息系统下的局部双量化决策粗糙集研究[J]. 《山东大学学报(理学版)》, 2020, 55(3): 89-97.
[6] 刘营营,米据生,梁美社,李磊军. 三支区间集概念格[J]. 《山东大学学报(理学版)》, 2020, 55(3): 70-80.
[7] 冉茂军,高承华. Sturm-Liouville问题的特征值与特征函数的渐近公式[J]. 《山东大学学报(理学版)》, 2020, 55(2): 57-62.
[8] 万青,马盈仓,魏玲. 基于多粒度的多源数据知识获取[J]. 《山东大学学报(理学版)》, 2020, 55(1): 41-50.
[9] 景运革,景罗希,王宝丽,程妮. 属性值和属性变化的增量属性约简算法[J]. 《山东大学学报(理学版)》, 2020, 55(1): 62-68.
[10] 王新乐,杨文峰,廖华明,王永庆,刘悦,俞晓明,程学旗. 基于多维度特征的主题标签流行度预测[J]. 《山东大学学报(理学版)》, 2020, 55(1): 94-101.
[11] 郝秀梅,李宁宁. P-信息隐藏挖掘的数量特征及应用[J]. 《山东大学学报(理学版)》, 2019, 54(9): 9-14.
[12] 廖祥文,徐阳,魏晶晶,杨定达,陈国龙. 基于双层堆叠分类模型的水军评论检测[J]. 《山东大学学报(理学版)》, 2019, 54(7): 57-67.
[13] 屈娟,冯玉明,李艳平,李丽. 可证明的基于扩展混沌映射的匿名多服务器身份认证协议[J]. 《山东大学学报(理学版)》, 2019, 54(5): 44-51.
[14] 王雪梅,陈兴蜀,王海舟,王文贤. 基于标签和分块特征的新闻网页关键信息自动抽取[J]. 《山东大学学报(理学版)》, 2019, 54(3): 67-74.
[15] 董哲瑾,王健,钱凌飞,林鸿飞. 一种用户成长性画像的建模方法[J]. 《山东大学学报(理学版)》, 2019, 54(3): 38-45.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!