计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 125-130.doi: 10.11896/jsjkx.200800013

• 数据库&大数据&数据科学 • 上一篇    下一篇

一种基于概念可辨识矩阵的概念约简方法

王霞1,2, 彭致华1, 李俊余1,2, 吴伟志1,2   

  1. 1 浙江海洋大学数理与信息学院 浙江 舟山 316022
    2 浙江省海洋大数据挖掘与应用重点实验室(浙江海洋大学) 浙江 舟山 316022
  • 收稿日期:2020-08-03 修回日期:2020-09-23 出版日期:2021-01-15 发布日期:2021-01-15
  • 通讯作者: 王霞(bblylm@126.com)
  • 基金资助:
    国家自然科学基金项目(41631179,61773349,61976194);浙江省自然科学基金项目(LY18F030017)

Method of Concept Reduction Based on Concept Discernibility Matrix

WANG Xia1,2, PENG Zhi-hua1, LI Jun-yu1,2, WU Wei-zhi1,2   

  1. 1 School of Mathematics,Physics and Information Science,Zhejiang Ocean University,Zhoushan,Zhejiang 316022,China
    2 Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province (Zhejiang Ocean University),Zhoushan, Zhejiang 316022,China
  • Received:2020-08-03 Revised:2020-09-23 Online:2021-01-15 Published:2021-01-15
  • About author:WANG Xia,born in 1980,Ph.D,asso-ciate professor.Her main research intere-sts include formal concept analysis,rough set theory and granular computing.
  • Supported by:
    National Natural Science Foundation of China (41631179,61773349,61976194) and Zhejiang Provincial Natural Science Foundation of China (LY18F030017).

摘要: 基于布尔因子分析的概念约简能够保持形式背景的二元关系不变。借鉴概念格中基于可辨识矩阵求解属性约简的思想,在形式背景上定义概念可辨识矩阵,基于此给出保持二元关系不变的概念约简方法。 首先,在形式背景上定义一种新的可辨识矩阵,称之为概念可辨识矩阵。该矩阵的行和列都是形式概念,矩阵的每个元素是由属于所在行的形式概念的所有对象和属性对,但不属于所在列的形式概念的对象和属性对构成的集合。其次,研究概念可辨识矩阵与概念协调集之间的关系,利用概念可辨识矩阵给出概念协调集的判定方法。 然后,利用概念可辨识矩阵详细讨论核心概念、相对必要概念和不必要概念的特征,进而分别给出判断这3类形式概念的方法。最后,给出基于概念可辨识矩阵寻找概念约简的步骤。

关键词: 概念可辨识矩阵, 概念特征, 概念约简, 形式背景, 形式概念

Abstract: The concept reduction of a formal context based on Boolean factor analysis can preserve all binary relations of the formal context.That is the relations between objects and attributes contained in a concept reduction based on Boolean factor analysis are consistent with the binary relations represented by the formal context.Inspired by the idea of discernibility matrix solving attribute reduct in a concept lattice,a concept discernibility matrix is defined in a formal context,and a method of concept reduct based on the concept discernibility matrix is proposed to find all concept reducts.Firstly,a new discernibility matrix is defined in a formal context,which is called concept discernibility matrix of the formal context.Both the rows and columns of the matrix are the formal concepts.Each element of the matrix is a set consisted of all pairs of object and attribute,which belong to the formal concept in the corresponding row,but not to the formal concept in the corresponding column.Secondly,the relationship between the concept discernibility matrix and the concept consistent set is studied,and the method of judging concept consistent set is givenby using the concept discernibility matrix.Then,all formal concepts of a formal context are divided into three categories:core concept,relatively necessary concept and unnecessary concept according to their relationship to concept reducts.And characteristics of core concept,relatively necessary concept and unnecessary concept are discussed in detail.Moreover,methods of judging these three kinds of formal concepts are developed respectively by using the concept discernibility matrix.The detailed process of solving all concept reducts of a formal context is given by an example based on the concept discernibility matrix.Finally,solution steps to find all concept reducts are given by using the concept discernibility matrix,and the complexity of each step is simply analyzed.

Key words: Concept characteristic, Concept discernibility matrix, Concept reduction, Formal concept, Formal context

中图分类号: 

  • TP301
[1] WILLE R.Restructuring lattice theory:An approach based on hierarchies of concepts[M]//Ordered Sets.Dordrecht:Reidel,1982:445-470.
[2] GANTER B,WILLE R.Formal Concept Analysis:Mathematical Foundations[M].Berlin:Springer,1999:17-61.
[3] ZHANG W X,WEI L,QI J J.Attribute reduction theory and approach to concept lattice[J].Science in China (Series E),2005,35(6):628-639.
[4] ZHANG W X,WEI L,QI J J.Attribute reduction in concept lattice based on discernibility matrix[C]//10th International Conference Proceedings of Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing.Berlin:Springer,2005:157-165.
[5] WANG X,ZHANG W X.Knowledge reduction in concept lattices based on irreducible elements[J].Transaction on Computational Science V,2009,55(40):128-142.
[6] WU W Z,LEUNG Y,MI J S.Granular computing and knowledge reduction in formal contexts[J].IEEE Transactions on Knowledge and Data Engineer,2009,21(10):1461-1474.
[7] QI J J.Attribute reduction in formal contexts based on a new discernibility matrix[J].Journal of Applied Mathematics and Computing,2009,30(1):305-314.
[8] LIU J,MI J S.A novel approach to attribute reduction in formalconcept lattices,Rough Sets and Knowledge Technology[C]//Proceedings of Rough Sets and Knowledge Technology 3rd International Conference.Berlin:Springer,2008:426-433.
[9] WANG X,MA J M.A novel approach to attribute reduction in concept lattices[C]//Proceedings of Rough Sets and Knowledge Technology 1st International Conference.Berlin:Springer,2006,4062:522-529.
[10] LI L J,LI M Z,MI J S,et al.A simple discernibility matrix for attribute reduction in formal concept analysis based on granular concepts[J].Journal of Intelligent and Fuzzy Systems,2019,37(2):1-13.
[11] KONECNY J.On attribute reduction in concept lattices:me-thods based on discernibility matrix are outperformed by basic clarification and reduction[J].Information Sciences,2017,415-416:199-212.
[12] SKOWRON A,RAUSZER C.The discernibility matrices andfunctions in information systems[J].Intelligent Decision Support.Theory and Decision Library,1992,11:331-362.
[13] WEI L,QI J J,ZHANG W X.Attribute reduction theory of concept lattice based on decision formal contexts[J].Science in China (Series E),2008,32(2):195-208.
[14] CHEN J K,MI J S,XIE B,et al.A fast attribute reduction method for large formal decision contexts[J].International Journal of Approximate Reasoning,2019,106:1-17.
[15] JANOSTIK R,KONECNY J.General framework for consistencies in decision contexts[J].Information Sciences,2020,530:180-200.
[16] REN R S,WEI L.The attribute reductions of three-way concept lattices[J].Knowledge-Based Systems,2016,99:92-102.
[17] SHAO M W,LI K W.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences,2017,378:317-327.
[18] SHAO M W,YANG H Z,WU W Z.Knowledge reduction informal fuzzy contexts[J].Knowledge-Based Systems,2015,73:265-275.
[19] CAO L,WEI L,QI J J.Concept reduction preserving binary relations[J].Pattern Recognition and Artificial Intelligence,2018,31(6):516-524.
[20] BELOHLÁVEK R,VYCHODIL V.Discovery of optimal factors in binary data via a novel method of matrix decomposition[J].Journal of Computer and System Sciences,2010,76(1):3-20.
[1] 刘忠慧, 赵琦, 邹璐, 闵帆.
三元概念的启发式构建及其在社会化推荐中的应用
Heuristic Construction of Triadic Concept and Its Application in Social Recommendation
计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[2] 沈夏炯, 杨继勇, 张磊.
基于不相关属性集合的属性探索算法
Attribute Exploration Algorithm Based on Unrelated Attribute Set
计算机科学, 2021, 48(4): 54-62. https://doi.org/10.11896/jsjkx.200800082
[3] 郑添健, 侯金宏, 张维, 王驹.
循环描述逻辑系统FL0最大不动点模型的有穷基
Finite Basis of Implicational System Associated with Finite Models of Description Logic FL0 Under the Greatest Fixed Point Semantics
计算机科学, 2020, 47(11A): 92-96. https://doi.org/10.11896/jsjkx.200300188
[4] 林洪,秦克云.
决策形式背景基于三支决策规则的属性约简
Attribute Reduction for Decision Formal Contexts Based on Threek-way Decision Rules
计算机科学, 2019, 46(3): 248-252. https://doi.org/10.11896/j.issn.1002-137X.2019.03.037
[5] 李仲玲, 米据生, 解滨.
不协调决策形式背景的属性约简
Attribute Reduction in Inconsistent Decision Formal Contexts
计算机科学, 2019, 46(12): 257-260. https://doi.org/10.11896/jsjkx.181102137
[6] 延安, 闫心怡, 陈泽华.
一致决策信息系统规则提取的形式向量方法
Formal Vector Method of Rule Extraction for Consistent Decision Information System
计算机科学, 2019, 46(10): 236-241. https://doi.org/10.11896/jsjkx.190200270
[7] 郑书富,余高锋.
基于形式背景的属性转移与知识发现
Attribute Transfer and Knowledge Discovery Based on Formal Context
计算机科学, 2018, 45(6A): 117-119.
[8] 秦克云,林洪.
决策形式背景属性约简的关系
Relationships among Several Attribute Reduction Methods of Decision Formal Context
计算机科学, 2018, 45(4): 257-259. https://doi.org/10.11896/j.issn.1002-137X.2018.04.043
[9] 周超, 任志宇, 毋文超.
基于形式概念分析的语义角色挖掘算法
Semantic Roles Mining Algorithms Based on Formal Concept Analysis
计算机科学, 2018, 45(12): 117-122. https://doi.org/10.11896/j.issn.1002-137X.2018.12.018
[10] 常欣欣, 秦克云.
基于对象导出三支概念格的形式背景粒约简方法
Approach for Granular Reduction in Formal Context Based on Objects-induced Three-way Concept Lattices
计算机科学, 2018, 45(10): 225-228. https://doi.org/10.11896/j.issn.1002-137X.2018.10.041
[11] 任睿思, 魏玲, 祁建军.
三支类背景上的规则获取
Rules Acquisition on Three-way Class Contexts
计算机科学, 2018, 45(10): 21-26. https://doi.org/10.11896/j.issn.1002-137X.2018.10.004
[12] 姜玉婷, 秦克云.
决策形式背景面向属性与面向对象的决策规则
Property-oriented and Object-oriented Decision Rules in Decision Formal Contexts
计算机科学, 2018, 45(10): 33-36. https://doi.org/10.11896/j.issn.1002-137X.2018.10.006
[13] 林洪, 秦克云.
决策形式背景三支粒约简
Three-way Granular Reduction for Decision Formal Context
计算机科学, 2018, 45(10): 47-50. https://doi.org/10.11896/j.issn.1002-137X.2018.10.009
[14] 王振,魏玲.
基于单边区间集概念格的不完备形式背景的属性约简
Attribute Reduction of Partially-known Formal Concept Lattices for Incomplete Contexts
计算机科学, 2018, 45(1): 73-78. https://doi.org/10.11896/j.issn.1002-137X.2018.01.011
[15] 祖鸿娇,解滨,米据生.
不完备决策形式背景的概念构建与属性约简
Concept Construction and Attribute Reduction in Incomplete Decision Formal Contexts
计算机科学, 2017, 44(9): 83-87. https://doi.org/10.11896/j.issn.1002-137X.2017.09.017
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!