Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (4): 63-76.doi: 10.11896/jsjkx.221000169

• Database & Big Data & Data Science • Previous Articles     Next Articles

Same Effect Relation and Concept Reduction in Formal Concept Analysis

MA Wensheng1, HOU Xilin2   

  1. 1 School of Electtronic and Information Engineering,Liaoning University of Science and Technology,Anshan,Liaoning 114051,China
    2 School of Business Administration,Liaoning University of Science and Technology,Anshan,Liaoning 114051,China
  • Received:2022-10-23 Revised:2022-11-27 Online:2023-04-15 Published:2023-04-06
  • About author:MA Wensheng,born in 1971,Ph.D candidate.His main research interest is big data application.
    HOU Xilin,born in 1960,Ph.D,professor.His main research interests include big data application and enterprise innovation system.

PDF (PC)

294

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

CLC Number: 

  • TP311
[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.
[1] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[2] SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set [J]. Computer Science, 2021, 48(4): 54-62.
[3] WANG Xia, PENG Zhi-hua, LI Jun-yu, WU Wei-zhi. Method of Concept Reduction Based on Concept Discernibility Matrix [J]. Computer Science, 2021, 48(1): 125-130.
[4] ZHENG Tian-jian, HOU Jin-hong, ZHANG Wei, WANG Ju. Finite Basis of Implicational System Associated with Finite Models of Description Logic FL0 Under the Greatest Fixed Point Semantics [J]. Computer Science, 2020, 47(11A): 92-96.
[5] ZHOU Chao, REN Zhi-yu, WU Wen-chao. Semantic Roles Mining Algorithms Based on Formal Concept Analysis [J]. Computer Science, 2018, 45(12): 117-122.
[6] JIANG Yu-ting, QIN Ke-yun. Property-oriented and Object-oriented Decision Rules in Decision Formal Contexts [J]. Computer Science, 2018, 45(10): 33-36.
[7] WANG Zhen and WEI Ling. Attribute Reduction of Partially-known Formal Concept Lattices for Incomplete Contexts [J]. Computer Science, 2018, 45(1): 73-78.
[8] SHANG Ying, CHENG Ke and LI Zheng. Research on FCA Based Dependence Cluster Detection [J]. Computer Science, 2017, 44(4): 144-147.
[9] WANG Chun-yue, WANG Li-ming and ZHANG Zhuo. Algorithm of Maintaining Concept Lattice Based on Binary Relation Decrement [J]. Computer Science, 2016, 43(Z11): 35-41.
[10] YAN Zhi-huan and LEI Yin-bin. Extended Rough Description Logic [J]. Computer Science, 2016, 43(5): 214-218.
[11] ZHANG Hui-wen, LIU Wen-qi and LI Jin-hai. Axiomatic Characterizations of Approximate Concept Lattices in Incomplete Contexts [J]. Computer Science, 2015, 42(6): 67-70.
[12] LI Xiang,WANG Su-ge,LI De-yu,KANG Xiang-ping and ZHAI Yan-hui. Knowledge Acquisition in Incomplete Information System Based on Formal Concept Analysis [J]. Computer Science, 2014, 41(7): 250-253.
[13] ZHI Hui-lai. Clustering Stability Analysis for Non-numeric Data Based on Concept Lattice [J]. Computer Science, 2014, 41(10): 244-248.
[14] . Quick Algorithm of Determining Arrow Relations of a Formal Context [J]. Computer Science, 2012, 39(9): 170-174.
[15] YANG Fan, ZHAI Yan-hui,QU Kai-she, LI De-yu. Study on Word Meaning Comprehension Based on Formal Concept Analysis [J]. Computer Science, 2011, 38(Z10): 189-191.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.