Research on Two Main Construction Methods of Concept Lattices
|
摘要
Because of the completeness of concept lattices, the time complexity of constructing concept lattices has become the main factor affecting the application of formal concept analysis(FCA). The key problems in the research of concept lattices are how to improve the generation efficiency and how to reduce the space and time complexity of constructing concept lattices. So far, reviews on lattice construction algorithms have not been comprehensive. In view of this situation, we give a detailed review on two categories of construction algorithms:batch methods and incremental methods. The first category is a formal context that cannot be updated once the concept lattice has been constructed; the second category is a formal context that can be updated after a new object being added to the formal context. We briefly introduce classical and improved construction methods, illustrate the deficiencies of some algorithms and point out the improvements of the follow-up algorithms. Furthermore, we compare and discuss several key algorithms, and also pay attention to the application of concept lattices. Finally,two further research directions of concept lattices are proposed, including parallel construction methods of concept lattices and research of heterogeneous data concept lattices.
Because of the completeness of concept lattices, the time complexity of constructing concept lattices has become the main factor affecting the application of formal concept analysis(FCA). The key problems in the research of concept lattices are how to improve the generation efficiency and how to reduce the space and time complexity of constructing concept lattices. So far, reviews on lattice construction algorithms have not been comprehensive. In view of this situation, we give a detailed review on two categories of construction algorithms:batch methods and incremental methods. The first category is a formal context that cannot be updated once the concept lattice has been constructed; the second category is a formal context that can be updated after a new object being added to the formal context. We briefly introduce classical and improved construction methods, illustrate the deficiencies of some algorithms and point out the improvements of the follow-up algorithms. Furthermore, we compare and discuss several key algorithms, and also pay attention to the application of concept lattices. Finally,two further research directions of concept lattices are proposed, including parallel construction methods of concept lattices and research of heterogeneous data concept lattices.
Because of the completeness of concept lattices, the time complexity of constructing concept lattices has become the main factor affecting the application of formal concept analysis(FCA). The key problems in the research of concept lattices are how to improve the generation efficiency and how to reduce the space and time complexity of constructing concept lattices. So far, reviews on lattice construction algorithms have not been comprehensive. In view of this situation, we give a detailed review on two categories of construction algorithms:batch methods and incremental methods. The first category is a formal context that cannot be updated once the concept lattice has been constructed; the second category is a formal context that can be updated after a new object being added to the formal context. We briefly introduce classical and improved construction methods, illustrate the deficiencies of some algorithms and point out the improvements of the follow-up algorithms. Furthermore, we compare and discuss several key algorithms, and also pay attention to the application of concept lattices. Finally,two further research directions of concept lattices are proposed, including parallel construction methods of concept lattices and research of heterogeneous data concept lattices.
引文
[1]WILLE R.Restructing lattice theory:An approach based on hierarchies of concepts[C]//Formal Concept Analysis.Dordrecht:Reidel Publishing Company,1982:314-339.
[2]XIE Z P,LIU Z T.Concept lattice and association rule discovery[J].Journal of Computer Research and Development,2000,37(12):1415-1421(in Chinese).
[3]HAN J W,CAI Y D,CERCONE N.Knowledge discovery in databases:An attribute-oriented approach[C]//Proceedings of the 18th International Conference on Very Large Data Bases.Vancouver,Canada:Morgan Kaufmann,1992:547-559.
[4]SOBIESKI S,ZIELI′NSKI B.Modelling role hierarchy structure using the formal concept analysis[C]//Annales UMCS Informatica AI X.[s.l.]:Versita,2010:143-159.
[5]BORDAT J P.Calcul pratique du treillis de Galois d’une correspondance[J].Math′ematiques Et Sciences Humaines,1986,96:31-47.
[6]CHEIN M.Algorithme de recherche des sou-matrices premi`eres d’une matrice[J].Bull Math Soe,Sci,1969,13:21-25.
[7]GANTER B,WILLE R.Formal concept analysis:Mathematical foundations[M].New York,USA:Springer-Verlag,1997.
[8]STUMME G,TAOUIL R,BASTIDE Y,et al.Fast computation of concept lattices using data mining techniques[C]//Proceedings of 7th International Workshop on Knowledge Representation Meets Databases.Berlin,Germany:[s.n.],2000:129-139.
[9]NOURINE L,RAYNAUD O.A fast algorithm for building lattices[J].Information Processing Letters,1999,71(5/6):199-204.
[10]GODIN R,MISSAOUI R,ALAOUI H.Incremental concept formation algorithms based on Galois(concept)lattices[J].Computational Intelligence,1995,11(2):246-267.
[11]LINDIG C,GBR G D.Fast concept analysis[EB/OL].[2018-08-23].https://www.researchgate.net/publication/2812391 Fast Concept Analysis
[12]QI H.Knowledge discovery methods research based on formal concept analysis[D].Changchun,China:College of Computer Science and Technology,Jilin University,2005(in Chinese).
[13]JIN Y.Research on algorithms for sequential pattern mining based on concept lattice[D].Changchun,China:College of Computer Science and Technology,Jilin University,2007(in Chinese).
[14]XIE R,LI H X,MA J,et al.Hierarchic construction of concept lattice[J].Journal of Southwest Jiaotong University,2005,40(6):837-841(in Chinese).
[15]XIE Z P.Research on knowledge discovery based on concept lattice model[D].Hefei,China:School of Computer Science and information Engineering,Hefei University of Technology China,2001(in Chinese).
[16]KUZNETSOV S O.A fast algorithm for computing all intersections of objects in a finite semi-lattice[J].Automatic Documentation and Mathematical Linguistics,1993,27(5):11-21.
[17]OUTRATA J,VYCHODIL V.Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data[J].Information Sciences,2012,185(1):114-127.
[18]KRAJCA P,OUTRATA J,VYCHODIL V.Parallel algorithm for computing fixpoints of Galois connections[J].Annals of Mathematics and Artificial Intelligence,2010,59(2):257-272.
[19]QI H,LIU D Y,HU C Q,et al.An algorithm for generating concepts based on search space partition[J].Journal of Software,2005,16(12):2029-2035(in Chinese).
[20]ZHANG K,HU Y F,WANG Y.An IRST-based algorithm for construction of concept lattices[J].Journal of Computer Research and Development,2004,41(9):1493-1499(in Chinese).
[21]CHENG K.Construction method of concept lattice[D].Chengdu,China:School of Mathematics,Southwest Jiaotong University,2012(in Chinese).
[22]LI X,SHAO M W,ZHAO X M.Constructing lattice based on irreducible concepts[J].International Journal of Machine Learning and Cybernetics,2017,8:109-122.
[23]CARPINETO C,ROMANO G.GALOIS:An order-theoretic approach to conceptual clustering[C]//Proceedings of the 10th International Conference on Machine Learning.Amherst,USA:[s.n.],1993:33-40.
[24]MERWE D V D,OBIEDKOV S,KOURIE D.Addintent:A new incremental algorithm for constructing concept lattices[C]//International Conference on Formal Concept Analysis.Berlin,Germany:Springer,2004:372-385.
[25]XIE R.Study on constructing algorithms of concept lattice[D].Chengdu,China:School of Mathematics,Southwest Jiaotong University,2006(in Chinese).
[26]XIE Z P,LIU Z T.A fast incremental algorithm for building concept lattice[J].Chinese Journal of Computers,2002,25(5):490-496(in Chinese).
[27]LI Y,LIU Z T,CHEN L,et al.Attribute-based incremental formation algorithm of concept lattice[J].Mini-Micro Systems,2004,25(10):1768-1771(in Chinese).
[28]SHEN X J,HAN D J,LIU Z T,et al.Improvement on constructing algorithms of concept lattices[J].Computer Engineering and Applications,2004,40(24):100-103(in Chinese).
[29]ZHI H L.Research on key technologies in constructing and application of concept lattice[D].Shanghai,China:School of Computer Engineering and Science,Shanghai University,2010(in Chinese).
[30]ZHI H L,ZHI D J.Theory and algorithms of concept lattice incremental construction based on attributes[J].Computer Engineering and Applications,2012,48(26):17-21(in Chinese).
[31]ZOU L G,ZHANG Z P,LONG J.A fast incremental algorithm for constructing concept lattices[J].Expert Systems with Applications,2015,42(9):4474-4481.
[32]LIU L F,WU M D,WANG D,et al.Building concept lattices based on attribute reduction[J].Computer Engineering and Science,2007,29(6):140-142(in Chinese).
[33]ZHAN L Q,LIU D X.Study on FCI mining algorithms based on concept lattice[J].Journal of Harbin Engineering University,2007,28(2):194-197(in Chinese).
[34]OUTRATA J.A lattice-free concept lattice update algorithm[J].International Journal of General Systems,2016,45(2):211-231.
[35]ZHANG L,ZHANG H L,YIN L H,et al.Theory and algorithms of attribute decrement for concept lattice[J].Journal of Computer Research and Development,2013,50(2):248-259(in Chinese).
[36]CARPINETO C,ROMANO G.Concept data analysis:Theory and applications[M].London,UK:John Wiley,2004.
[37]ZHANG L,ZHANG H,SHEN X,et al.An incremental algorithm for removing object from concept lattice[J].Journal of Computational Information Systems,2013,9:3363-3372.
[38]GODIN R,MILI H,MINEAU G W,et al.Design of class hierarchies based on concept(Galois)lattices[J].Theory and Practice of Object Systems,1998,4(2):117-133.
[39]LINDIG C,SNELTING G.Assessing modular structure of legacy code based on mathematical concept analysis[C]//Proceedings of the 19th international conference on Software engineering.Boston,USA:ACM,1997:349-359.
[40]GODIN R,MISSAOUI R.An incremental concept formation approach for learning from databases[J].Theoretical Computer Science,1994,133:387-419.
[41]PASQUIER N,BASTIDE Y,TAOUIL R,et al.Closed sets based discovery of small covers for association rules[C]//BDA’1999 International Conference on Advanced Databases.Bordeaux,France:[s.n.],1999:361-381.
[42]KROHN U,DAVIES N J,WEEKS R.Concept lattices for knowledge management[J].BT Technology Journal,1999,17(4):108-116.
[43]COLE R,EKLUND P W.Scalability in formal concept analysis[J].Computational Intelligence,1999,15(1):11-27.
[44]KENT R E,BOWMAN C M.Digital libraries,conceptual knowledge systems,and the Nebula interface[R].Conway,USA:University of Arkansas,1995.
[45]VALTCHEV P,MISSAOUI R.Building concept(Galois)lattices from parts:Generalizing the incremental methods[C]//Conceptual Structures:Broadening the Base.Berlin,Germany:Springer,2001:1-2.
[2]XIE Z P,LIU Z T.Concept lattice and association rule discovery[J].Journal of Computer Research and Development,2000,37(12):1415-1421(in Chinese).
[3]HAN J W,CAI Y D,CERCONE N.Knowledge discovery in databases:An attribute-oriented approach[C]//Proceedings of the 18th International Conference on Very Large Data Bases.Vancouver,Canada:Morgan Kaufmann,1992:547-559.
[4]SOBIESKI S,ZIELI′NSKI B.Modelling role hierarchy structure using the formal concept analysis[C]//Annales UMCS Informatica AI X.[s.l.]:Versita,2010:143-159.
[5]BORDAT J P.Calcul pratique du treillis de Galois d’une correspondance[J].Math′ematiques Et Sciences Humaines,1986,96:31-47.
[6]CHEIN M.Algorithme de recherche des sou-matrices premi`eres d’une matrice[J].Bull Math Soe,Sci,1969,13:21-25.
[7]GANTER B,WILLE R.Formal concept analysis:Mathematical foundations[M].New York,USA:Springer-Verlag,1997.
[8]STUMME G,TAOUIL R,BASTIDE Y,et al.Fast computation of concept lattices using data mining techniques[C]//Proceedings of 7th International Workshop on Knowledge Representation Meets Databases.Berlin,Germany:[s.n.],2000:129-139.
[9]NOURINE L,RAYNAUD O.A fast algorithm for building lattices[J].Information Processing Letters,1999,71(5/6):199-204.
[10]GODIN R,MISSAOUI R,ALAOUI H.Incremental concept formation algorithms based on Galois(concept)lattices[J].Computational Intelligence,1995,11(2):246-267.
[11]LINDIG C,GBR G D.Fast concept analysis[EB/OL].[2018-08-23].https://www.researchgate.net/publication/2812391 Fast Concept Analysis
[12]QI H.Knowledge discovery methods research based on formal concept analysis[D].Changchun,China:College of Computer Science and Technology,Jilin University,2005(in Chinese).
[13]JIN Y.Research on algorithms for sequential pattern mining based on concept lattice[D].Changchun,China:College of Computer Science and Technology,Jilin University,2007(in Chinese).
[14]XIE R,LI H X,MA J,et al.Hierarchic construction of concept lattice[J].Journal of Southwest Jiaotong University,2005,40(6):837-841(in Chinese).
[15]XIE Z P.Research on knowledge discovery based on concept lattice model[D].Hefei,China:School of Computer Science and information Engineering,Hefei University of Technology China,2001(in Chinese).
[16]KUZNETSOV S O.A fast algorithm for computing all intersections of objects in a finite semi-lattice[J].Automatic Documentation and Mathematical Linguistics,1993,27(5):11-21.
[17]OUTRATA J,VYCHODIL V.Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data[J].Information Sciences,2012,185(1):114-127.
[18]KRAJCA P,OUTRATA J,VYCHODIL V.Parallel algorithm for computing fixpoints of Galois connections[J].Annals of Mathematics and Artificial Intelligence,2010,59(2):257-272.
[19]QI H,LIU D Y,HU C Q,et al.An algorithm for generating concepts based on search space partition[J].Journal of Software,2005,16(12):2029-2035(in Chinese).
[20]ZHANG K,HU Y F,WANG Y.An IRST-based algorithm for construction of concept lattices[J].Journal of Computer Research and Development,2004,41(9):1493-1499(in Chinese).
[21]CHENG K.Construction method of concept lattice[D].Chengdu,China:School of Mathematics,Southwest Jiaotong University,2012(in Chinese).
[22]LI X,SHAO M W,ZHAO X M.Constructing lattice based on irreducible concepts[J].International Journal of Machine Learning and Cybernetics,2017,8:109-122.
[23]CARPINETO C,ROMANO G.GALOIS:An order-theoretic approach to conceptual clustering[C]//Proceedings of the 10th International Conference on Machine Learning.Amherst,USA:[s.n.],1993:33-40.
[24]MERWE D V D,OBIEDKOV S,KOURIE D.Addintent:A new incremental algorithm for constructing concept lattices[C]//International Conference on Formal Concept Analysis.Berlin,Germany:Springer,2004:372-385.
[25]XIE R.Study on constructing algorithms of concept lattice[D].Chengdu,China:School of Mathematics,Southwest Jiaotong University,2006(in Chinese).
[26]XIE Z P,LIU Z T.A fast incremental algorithm for building concept lattice[J].Chinese Journal of Computers,2002,25(5):490-496(in Chinese).
[27]LI Y,LIU Z T,CHEN L,et al.Attribute-based incremental formation algorithm of concept lattice[J].Mini-Micro Systems,2004,25(10):1768-1771(in Chinese).
[28]SHEN X J,HAN D J,LIU Z T,et al.Improvement on constructing algorithms of concept lattices[J].Computer Engineering and Applications,2004,40(24):100-103(in Chinese).
[29]ZHI H L.Research on key technologies in constructing and application of concept lattice[D].Shanghai,China:School of Computer Engineering and Science,Shanghai University,2010(in Chinese).
[30]ZHI H L,ZHI D J.Theory and algorithms of concept lattice incremental construction based on attributes[J].Computer Engineering and Applications,2012,48(26):17-21(in Chinese).
[31]ZOU L G,ZHANG Z P,LONG J.A fast incremental algorithm for constructing concept lattices[J].Expert Systems with Applications,2015,42(9):4474-4481.
[32]LIU L F,WU M D,WANG D,et al.Building concept lattices based on attribute reduction[J].Computer Engineering and Science,2007,29(6):140-142(in Chinese).
[33]ZHAN L Q,LIU D X.Study on FCI mining algorithms based on concept lattice[J].Journal of Harbin Engineering University,2007,28(2):194-197(in Chinese).
[34]OUTRATA J.A lattice-free concept lattice update algorithm[J].International Journal of General Systems,2016,45(2):211-231.
[35]ZHANG L,ZHANG H L,YIN L H,et al.Theory and algorithms of attribute decrement for concept lattice[J].Journal of Computer Research and Development,2013,50(2):248-259(in Chinese).
[36]CARPINETO C,ROMANO G.Concept data analysis:Theory and applications[M].London,UK:John Wiley,2004.
[37]ZHANG L,ZHANG H,SHEN X,et al.An incremental algorithm for removing object from concept lattice[J].Journal of Computational Information Systems,2013,9:3363-3372.
[38]GODIN R,MILI H,MINEAU G W,et al.Design of class hierarchies based on concept(Galois)lattices[J].Theory and Practice of Object Systems,1998,4(2):117-133.
[39]LINDIG C,SNELTING G.Assessing modular structure of legacy code based on mathematical concept analysis[C]//Proceedings of the 19th international conference on Software engineering.Boston,USA:ACM,1997:349-359.
[40]GODIN R,MISSAOUI R.An incremental concept formation approach for learning from databases[J].Theoretical Computer Science,1994,133:387-419.
[41]PASQUIER N,BASTIDE Y,TAOUIL R,et al.Closed sets based discovery of small covers for association rules[C]//BDA’1999 International Conference on Advanced Databases.Bordeaux,France:[s.n.],1999:361-381.
[42]KROHN U,DAVIES N J,WEEKS R.Concept lattices for knowledge management[J].BT Technology Journal,1999,17(4):108-116.
[43]COLE R,EKLUND P W.Scalability in formal concept analysis[J].Computational Intelligence,1999,15(1):11-27.
[44]KENT R E,BOWMAN C M.Digital libraries,conceptual knowledge systems,and the Nebula interface[R].Conway,USA:University of Arkansas,1995.
[45]VALTCHEV P,MISSAOUI R.Building concept(Galois)lattices from parts:Generalizing the incremental methods[C]//Conceptual Structures:Broadening the Base.Berlin,Germany:Springer,2001:1-2.