Abstract
An incremental concept lattice construction algorithm, called AddIntent, is proposed. In experimental comparison, AddIntent outperformed a selection of other published algorithms for most types of contexts and was close to the most efficient algorithm in other cases. The current best estimate for the algorithm’s upper bound complexity to construct a concept lattice L whose context has a set of objects G, each of which possesses at most max(|g′|) attributes, is O(|L||G|2 max(|g′|)).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, New York (1999)
Wille, R.: Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts. In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Reidel, Dordrecht (1982)
Bordat, J.: Calcul pratique du treillis de Galois d’une correspondance. Math. Sci. Hum. 96, 31–47 (1986)
Ganter, B.: Two Basic Algorithms in Concept Analysis. FB4-Preprint No. 831, TH Darmstadt (1984)
Godin, R., Missaoui, R., Alaoui, H.: Incremental Concept Formation Algorithms Based on Galois Lattices. Computation Intelligence 11, 246–267 (1995)
Norris, E.: An Algorithm for Computing the Maximal Rectangles in a Binary Relation. Revue Roumaine de Mathématiques Pures et Appliquées 23, 243–250 (1978)
Valtchev, P., Missaoui, R.: Building Concept (Galois) Lattices from Parts: Generalizing the Incremental Methods. In: Delugach, H.S., Stumme, G. (eds.) ICCS 2001. LNCS (LNAI), vol. 2120, pp. 290–303. Springer, Heidelberg (2001)
Kuznetsov, S., Obiedkov, S.: Comparing Performance of Algorithms for Generating Concept Lattices. J. Experimental and Theoretical Artificial Intelligence 14, 189–216 (2002)
Van Der Merwe, F., Kourie, D.: AddAtom: an Incremental Algorithm for Constructing Concept- and Concept Sublattices. Technical report of the Department of Computer Science, University of Pretoria, South Africa (2002)
Carpineto, C., Romano, G.: A Lattice Conceptual Clustering System and Its Application to Browsing Retrieval. Machine Learning 24, 95–122 (1996)
Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Information Processing Letters 71, 199–204 (1999)
Van Der Merwe, F.: Constructing Concept Lattices and Compressed Pseudo-Lattices. M.Sc. dissertation, University of Pretoria, South Africa (2003)
Obiedkov, S.: Algorithms and Methods of Lattice Theory and Their Application in Machine Learning. PhD thesis, Russian State University for the Humanities (2003)
Ferré, S.: Incremental Concept Formation Made More Efficient by the Use of Associative Concepts. INRIA Research Report no 4569 (2002)
Valtchev, P., Missaoui, R., Lebrun, P.: A Partition-Based Approach towards Building Galois (Concept) Lattices. Rapport de recherche no. 2000-08, Département d’Informatique, UQAM, Montréal, Canada (2000)
Blake, C., Merz, C.: UCI Repository of Machine Learning Databases. University of California, Department of Information and Computer Science, Irvine, CA (1998), http://www.ics.uci.edu/~mlearn/MLRepository.html
Grigoriev, P., Yevtushenko, S.: Elements of an Agile Discovery Environment. In: Grieser, G., Tanaka, Y., Yamamoto, A. (eds.) DS 2003. LNCS (LNAI), vol. 2843, pp. 309–316. Springer, Heidelberg (2003)
Grigoriev, P., Yevtushenko, S., Grieser, G.: QuDA, a Data Miner’s Discovery Environment. Technical Report AIDA–03–06, TU Darmstadt (2003), http://www.intellektik.informatik.tu-darmstadt.de/~peter/QuDA.pdf
Van Der Merwe, F., Kourie, D.: Compressed Pseudo-Lattices. J. Expt. Theor. Artif. Intell. 14, 229–254 (2002)
Valtchev, P., Missaoui, R., Godin, R., Meridji, M.: Generating Frequent Itemsets Incrementally: Two Novel Approaches Based on Galois Lattice Theory. J. Expt. Theor. Artif. Intell. 14, 115–142 (2002)
Mailing list on FCA-algorithms: http://www.aifb.uni-karlsruhe.de/mailman/listinfo/fca-algo , Internet site of the Workshop on Algorithms of Formal Concept Analysis: http://kvo.itee.uq.edu.au/twiki/bin/view/Tockit/AlgoWorkshop
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van der Merwe, D., Obiedkov, S., Kourie, D. (2004). AddIntent: A New Incremental Algorithm for Constructing Concept Lattices. In: Eklund, P. (eds) Concept Lattices. ICFCA 2004. Lecture Notes in Computer Science(), vol 2961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24651-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-24651-0_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21043-6
Online ISBN: 978-3-540-24651-0
eBook Packages: Springer Book Archive