Research on Two Main Construction Methods of Concept Lattices

doi:10.1007/s12204-019-2058-6

Abstract

Abstract: 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.

Key words: formal concept analysis (FCA)| concept lattice| batch processing| incremental processing

摘要： 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.

关键词: formal concept analysis (FCA)| concept lattice| batch processing| incremental processing

CLC Number:

TP 301.6

DONG Ying* (董颖), WU Yue (吴悦), LIU Zongtian (刘宗田). Research on Two Main Construction Methods of Concept Lattices[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(2): 243-253.

References 45

[1]	WILLE R. Restructing lattice theory: An approachbased on hierarchies of concepts [C]//Formal ConceptAnalysis. Dordrecht: Reidel Publishing Company,1982: 314-339.
[2]	XIE Z P, LIU Z T. Concept lattice and associationrule discovery [J]. Journal of Computer Research andDevelopment, 2000, 37(12): 1415-1421 (in Chinese).
[3]	HAN J W, CAI Y D, CERCONE N. Knowledge discoveryin databases: An attribute-oriented approach[C]//Proceedings of the 18th International Conferenceon Very Large Data Bases. Vancouver, Canada:Morgan Kaufmann, 1992: 547-559.
[4]	SOBIESKI S, ZIELI′NSKI B. Modelling role hierarchystructure 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 Galoisd’une correspondance [J]. Math′ematiques Et SciencesHumaines, 1986, 96: 31-47.
[6]	CHEIN M. Algorithme de recherche des sou-matricespremi`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 datamining techniques [C]//Proceedings of 7th InternationalWorkshop on Knowledge Representation MeetsDatabases. Berlin, Germany: [s.n.], 2000: 129-139.
[9]	NOURINE L, RAYNAUD O. A fast algorithm forbuilding lattices [J]. Information Processing Letters,1999, 71(5/6): 199-204.
[10]	GODIN R, MISSAOUI R, ALAOUI H. Incrementalconcept 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 onformal concept analysis [D]. Changchun, China: Collegeof Computer Science and Technology, Jilin University,2005 (in Chinese).
[13]	JIN Y. Research on algorithms for sequential patternmining 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 constructionof concept lattice [J]. Journal of Southwest JiaotongUniversity, 2005, 40(6): 837-841 (in Chinese).
[15]	XIE Z P. Research on knowledge discovery based onconcept lattice model [D]. Hefei, China: School ofComputer Science and information Engineering, HefeiUniversity of Technology China, 2001 (in Chinese).
[16]	KUZNETSOV S O. A fast algorithm for computing allintersections of objects in a finite semi-lattice [J]. AutomaticDocumentation and Mathematical Linguistics,1993, 27(5): 11-21.
[17]	OUTRATA J, VYCHODIL V. Fast algorithm for computingfixpoints of Galois connections induced byobject-attribute relational data [J]. Information Sciences,2012, 185(1): 114-127.
[18]	KRAJCA P, OUTRATA J, VYCHODIL V. Parallel algorithmfor 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 forgenerating concepts based on search space partition[J]. Journal of Software, 2005, 16(12): 2029-2035 (inChinese).
[20]	ZHANG K, HU Y F, WANG Y. An IRST-based algorithmfor construction of concept lattices [J]. Journalof 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, SouthwestJiaotong University, 2012 (in Chinese).
[22]	LI X, SHAO M W, ZHAO X M. Constructing latticebased on irreducible concepts [J]. InternationalJournal of Machine Learning and Cybernetics, 2017,8: 109-122.
[23]	CARPINETO C, ROMANO G. GALOIS: Anorder-theoretic approach to conceptual clustering[C]//Proceedings of the 10th International Conferenceon Machine Learning. Amherst, USA: [s.n.], 1993: 33-40.
[24]	MERWE D V D, OBIEDKOV S, KOURIE D. Addintent:A new incremental algorithm for constructingconcept lattices [C]//International Conference on FormalConcept Analysis. Berlin, Germany: Springer,2004: 372-385.
[25]	XIE R. Study on constructing algorithms of conceptlattice [D].Chengdu, China: School of Mathematics,Southwest Jiaotong University, 2006 (in Chinese).
[26]	XIE Z P, LIU Z T. A fast incremental algorithm forbuilding 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 incrementalformation algorithm of concept lattice [J].Mini-Micro Systems, 2004, 25(10): 1768-1771 (inChinese).
[28]	SHEN X J, HAN D J, LIU Z T, et al. Improvementon 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 constructingand 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 conceptlattice 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 incrementalalgorithm for constructing concept lattices [J]. ExpertSystems with Applications, 2015, 42(9): 4474-4481.
[32]	LIU L F, WU M D, WANG D, et al. Building conceptlattices based on attribute reduction [J]. ComputerEngineering and Science, 2007, 29(6): 140-142(in Chinese).
[33]	ZHAN L Q, LIU D X. Study on FCI mining algorithmsbased on concept lattice [J]. Journal of Harbin EngineeringUniversity, 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 andalgorithms 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: JohnWiley,2004.
[37]	ZHANG L, ZHANG H, SHEN X, et al. An incrementalrnal of Computational Information Systems, 2013,9: 3363-3372.
[38]	GODIN R, MILI H, MINEAU G W, et al. Design ofclass 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 structureof legacy code based on mathematical conceptanalysis [C]//Proceedings of the 19th internationalconference on Software engineering. Boston, USA:ACM, 1997: 349-359.
[40]	GODIN R, MISSAOUI R. An incremental concept formationapproach for learning from databases [J]. TheoreticalComputer Science, 1994, 133: 387-419.
[41]	PASQUIER N, BASTIDE Y, TAOUIL R, et al. Closedsets based discovery of small covers for associationrules [C]//BDA’1999 International Conference on AdvancedDatabases. Bordeaux, France: [s.n.], 1999: 361-381.
[42]	KROHN U, DAVIES N J, WEEKS R. Concept latticesfor knowledge management [J]. BT Technology Journal,1999, 17(4): 108-116.
[43]	COLE R, EKLUND PW. Scalability in formal conceptanalysis [J]. Computational Intelligence, 1999, 15(1):11-27.
[44]	KENT R E, BOWMAN C M. Digital libraries, conceptualknowledge 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 incrementalmethods [C]//Conceptual Structures: Broadening theBase. Berlin, Germany: Springer, 2001: 1-2.