形式概念分析中的同效关系与概念约简

doi:10.11896/jsjkx.221000169

摘要/Abstract

摘要： 2018年以来,学者们在形式概念分析中提出并研究了“概念约简”的新课题,包括不必要概念、核心概念、相对必要概念这3类概念的鉴别研究,以及概念约简算法的研究。文中提出了同效关系,研究了其重要性质,给出了通过同效关系鉴别3类概念的简单的方法,并给出了由同效关系子集补集的概念格来得到概念约简的新算法。多年来,“约简课题”的算法都是使用合取范式和析取范式相互转换的方法,很多学者甚至表示“约简问题”就等同于合取范式和析取范式的转换问题。文中研究了不使用合取范式和析取范式转换来解决“约简课题”的新方法。该新方法不论是在理论上还是在实践上都极具意义,是一次新的尝试。一个背景的“概念约简”往往非常多,全部求出没有太大意义,一般需要求包含某些概念的“概念约简”,而所提方法在这方面具有显著的优越性。

关键词: 形式概念, 概念约简, 同效关系, 对象概念, 属性概念

Abstract: Since 2018,scholars have proposed and studied a new topic of “concept reduction” in formal concept analysis.Including unnecessary concepts,core concepts,relatively necessary concepts,and the identification of three types of concepts,and research on concept reduction algorithm.In this paper,the same effect relation is proposed and its important properties are studied.It pre-sents a simple way to identify three types of concepts through the same effect relationship,and proposes a new algorithm for concept reduction which is based on the concept lattice of the complement set of subsets of the same effect relationship.For decades,the algorithm of “reduction topic” has adopted the method of conjunctive normal form and disjunctive normal form transformation.Many scholars even said that “reduction problem” was equivalent to the transformation of conjunctive paradigm and disjunctive paradigm.This paper studies a new method to solve the “reduction problem” without using the transformation between conjunctive normal form and disjunctive normal form.This new method is of significance both in theory and in practice.It is a new attempt.There are often many “concept reduction” in a background,so it is not very meaningful to find out all the results.Gene-rally,it is necessary to find out “concept reduction” containing some concepts,and the method in this paper has particular advantages in this respect.

Key words: Formal concept, Concept reduction, Same effect relation, Object concept, Attribute concept

中图分类号:

TP311

马文胜, 侯锡林. 形式概念分析中的同效关系与概念约简[J]. 计算机科学, 2023, 50(4): 63-76. https://doi.org/10.11896/jsjkx.221000169

MA Wensheng, HOU Xilin. Same Effect Relation and Concept Reduction in Formal Concept Analysis[J]. Computer Science, 2023, 50(4): 63-76. https://doi.org/10.11896/jsjkx.221000169

参考文献

[1]WILLE R.Restructuring lattice theory:an approach based on hierarchies of concepts[C]//Proceedings of the NATO Advanced Study Institute.1982:445-470.
[2]GANTER B,WILLE R.Formal concept analysis:Mathematical foundations[M].Berlin:Springer,1999.
[3]HU K Y,LU Y C,SHI C Y.Progress of concept lattice and its application[J].Journal of Tsinghua University(Science Edition),2000,40(9):77-81.
[4]CARPINETO C,ROMANO G.A lattice conceptual clustering system and its application to browsing retrieval[J].Machine Learning,1996:10,95-122.
[5]TONELLA P.Using a concept lattice of decomposition slices for program understanding and impact analysis[J].IEEE Transactions on Software Engineering,2003,29(6) 495-509.
[6]NGUYEN P H P,CORBETT D.A Basic Mathematical Framework for Conceptual Graphs[J].IEEE Transactions on Know-ledge and Data Engineering,2006,18(2):261-271.
[7]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.
[8]WEI L.Reduction Theory and Approach to Rough Set and Concept Lattice[D].Xi’an:Xi’an Jiaotong University,2005.
[9]WANG X,MA J M.A Novel Approach to Attribute Reduction in Concept Lattices[C]//Proceedings of the International Conference on Rough Sets and Knowledge Technology.Berlin:Springer,2006:522-529.
[10]MI J S,LEUNG Y,WU W Z.Approaches to Attribute Reduction in Concept Lattices Induced by Axialities[J].Knowledge-Based Systems,2010,23(6):504-511.
[11]LI T J,LI M Z,GAO Y.Attribute Reduction of Concept Lattice Based on Irreducible Elements[J].International Journal of Wavelets Multiresolution and Information Processing,2013,11(6):2792-2813.
[12]WEI L,QI J J,ZHANG W X.Attribute Reduction and Rules Extraction in Decision Formal Context Based on Concept Lattice[J].Science in China(Information Sciences),2008,38(2):195-208.
[13]LI J H,MEI C L,LU Y J.Knowledge Reduction in Formal Decision Contexts Based on an Order-Preserving Mapping[J].International Journal of General Systems,2012,41(2):143-161.
[14]LI J H,MEI C L,LU Y J.Knowledge Reduction in Real Decision Formal Contexts[J].Information Sciences,2012,189:191-207.
[15]SHAO M W,LI K W.Attribute Reduction in Generalized One-Sided Formal Contexts[J].Information Sciences,2017,378:317- 327.
[16]WANG Z,WEI L.Attribute Reduction of Partially-Known Formal Concept Lattices for Incomplete Contexts[J].Computer Science,2018,45(1):73-78.
[17]WANG Z.Attribute Reduction and Rule Acquisition of Incomplete Formal Contexts Based on Partially-Known Concept Lattices[D].Xi’an:Northwest University,2018.
[18]LIU M,SHAO M W,ZHANG W X,et al.Reduction Method for Concept Lattices Based on Rough Set Theory and Its Application[J].Computers and Mathematics with Applications,2007,53(9):1390-1410.
[19]QIN K Y,LI B,PEI Z.Attribute Reduction and Rule Acquisition of Formal Decision Context Based on Object(Property) Oriented Concept Lattices[J].International Journal of Machine Learning and Cybernetics,2019,10(10):2837-2850.
[20]ZOU L,PANG K,SONG X Y,et al.A Knowledge Reduction Approach for Linguistic Concept Formal Context[J].Information Sciences,2020,524:165-183.
[21]CORNEJO M E,MEDINA J,RAMIREZ- POUSSA E.Attribute and Size Reduction Mechanisms in Multi-Adjoint Concept Lattices[J].Journal of Computational and Applied Mathematics,2017,318:388-402.
[22]REN R S,WEI L.The Attribute Reductions of Three-Way Concept Lattices[J].Knowledge-Based Systems,2016,99:92-102.
[23]QI J J,QIAN T,WEI L.The Connections between Three-Way and Classical Lattices[J].Knowledge-Based Systems,2016,91:143-151.
[24]KEPRT A,SNASEL V.Binary factor analysis with help of formal concepts[C]//Proceedings of International Workshop on Concept Lattices and Their Applications.Ostrava,2004:90-101.
[25]BELOHLAVEK R,VYCHODIL V.On Boolean factor analysis with formal concept as factors[C]//SCIS & ISIS.2006:1054-1059.
[26]BELOHLAVEK R,VYCHODIL V.Discovery of optimal factors in binary data via a novel method of matrix decomposition[J].Journal of Computer & System Sciences,2010,76(1):3-20.
[27]BELOHLAVEK R,TRNECKA M.From-below approximations in Boolean matrix factorization:geometry and new algorithm[J].Journal of Computer & System Sciences,2015,81:1678-1697.
[28]TRNECKA M,TRNECKOVA M.Data reduction for Booleanmatrix factorization algorithms based on formal concept analysis[J].Knowledge-Based Systems,2018,158:75-80.
[29]CAO L,WEI L,QI J J.Concept reduction preserving binary relations[J].Pattern Recognition and Artificial Intelligence,2018,31(6):516-524.
[30]WEI L,CAO L,QI J J,et al.Concept reduction and conceptcharacteristics in formal concept analysis[J].Science in China(Information Sciences),2020,50:1817-1833.
[31]XIE X X,LI J J,CHEN D X,et al.Concept reduction of preserving binary relations based on Boolean matrix[J].Journal of Shandong University(Natural Science).2020,55(5):32-45.
[32]WANG X,PENG Z H,LI J Y,et al.Method of Concept Reduction Based on Concept Discernibility Matrix[J].Computer Science,2021,48(1):125-130.
[33]ZHOU J Q,YANG S C,WANG X F,et al.Concept and attri-bute reduction based on rectangle theory of formal concept[J].arXiv:2111.00005,2021.
[34]GANTER B.Two basic algorithms in concept analysis[C]//Proceedings of the International Conference on Formal Concept Analysis.Berlin:Springer,2010:312-390.
[35]BORDAT J P.Calcul pratique du treillisde Galoisd’ une corres-pondance[J].Mathematiques et Sci-ences Humaines,1986,96:31-47.
[36]GODIN R,MISSAOUI R,ALAOUI H.Incremental concept formation algorithms based on Galois(concept) Lattices[J].Computational Intelligence,1995,11(2):246-267.
[37]CARPINETO C,ROMANO G.A lattice conceptual clustering system and its application to browsing retrieva1[J].Machine Learning,1996,24(2):95-122.
[38]NOURINE L,RAYNAUD O.A fast algorithm for building lattices[J].Information Processing Letters,1999:71(5/6):199-204.
[39]STUMME G,TAOUIL R,BASTIDE Y,et al.Fast computationof concept lattices using data mining techniques[C]//Procee-dings of the 7th International Workshop on Knowledge Representation Meets Databases.Berlin:Technical University of Aachen.2000:129-139.
[40]XIE Z P,LIU Z T.A fast incremental algorithm for building concept lattice[J].Chinese Journal of Computers,2002,25(5):490-496.
[41]YU Y,QIAN X,ZHONG F,et al.Increment construction algorithm for concept lattice based on maximal concept[J].Compu-ter Engineering,2009,35(21):62-64.
[42]SHEN J B,LU Y J.A novel building algorithm of concept lattice[J].Journal of HeFei University of Technology,2010.33(2):301-303,307.
[43]GUO L Z,SONG Z M.A novel concept lattice acquisition approach based on the greatest full matrix of formal context[J].CAAI Transactions on Intelligent Systems,2015,10(6):838-842.

相关文章 15

[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]	王霞, 彭致华, 李俊余, 吴伟志. 一种基于概念可辨识矩阵的概念约简方法 Method of Concept Reduction Based on Concept Discernibility Matrix 计算机科学, 2021, 48(1): 125-130. https://doi.org/10.11896/jsjkx.200800013
[4]	岳晓威, 彭莎, 秦克云. 基于面向对象(属性)概念格的形式背景属性约简方法 Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice 计算机科学, 2020, 47(6A): 436-439. https://doi.org/10.11896/JsJkx.191100011
[5]	郑添健, 侯金宏, 张维, 王驹. 循环描述逻辑系统FL₀最大不动点模型的有穷基 Finite Basis of Implicational System Associated with Finite Models of Description Logic FL₀ Under the Greatest Fixed Point Semantics 计算机科学, 2020, 47(11A): 92-96. https://doi.org/10.11896/jsjkx.200300188
[6]	周超, 任志宇, 毋文超. 基于形式概念分析的语义角色挖掘算法 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
[7]	姜玉婷, 秦克云. 决策形式背景面向属性与面向对象的决策规则 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
[8]	曾望林, 折延宏. 面向对象的多粒度形式概念分析 Object-oriented Multigranulation Formal Concept Analysis 计算机科学, 2018, 45(10): 51-53. https://doi.org/10.11896／j.issn.1002-137X.2018.10.010
[9]	尚颖,程克,李征. 基于形式概念分析的依赖簇检测方法研究 Research on FCA Based Dependence Cluster Detection 计算机科学, 2017, 44(4): 144-147. https://doi.org/10.11896/j.issn.1002-137X.2017.04.031
[10]	王春月,王黎明,张卓. 基于二元关系消减的概念格维护算法 Algorithm of Maintaining Concept Lattice Based on Binary Relation Decrement 计算机科学, 2016, 43(Z11): 35-41. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.008
[11]	闫之焕,雷银彬. 改进的粗糙描述逻辑框架 Extended Rough Description Logic 计算机科学, 2016, 43(5): 214-218. https://doi.org/10.11896/j.issn.1002-137X.2016.05.039
[12]	张慧雯,刘文奇,李金海. 不完备形式背景下近似概念格的公理化方法 Axiomatic Characterizations of Approximate Concept Lattices in Incomplete Contexts 计算机科学, 2015, 42(6): 67-70. https://doi.org/10.11896/j.issn.1002-137X.2015.06.015
[13]	李想,王素格,李德玉,康向平,翟岩慧. 形式概念分析在不完备信息系统中的知识获取 Knowledge Acquisition in Incomplete Information System Based on Formal Concept Analysis 计算机科学, 2014, 41(7): 250-253. https://doi.org/10.11896/j.issn.1002-137X.2014.07.052
[14]	智慧来. 基于概念格的非数值型数据聚类稳定性分析 Clustering Stability Analysis for Non-numeric Data Based on Concept Lattice 计算机科学, 2014, 41(10): 244-248. https://doi.org/10.11896/j.issn.1002-137X.2014.10.051
[15]	周秀秀,李建卓. 基于粗糙集理论的面向属性概念格动态压缩 Dynamic Compression of Property Oriented Concept Lattices Based on Rough Set Theory 计算机科学, 2013, 40(Z11): 136-139.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed