Abstract
We propose a new algorithm constructing the canonical implication basis of a formal context. Being incremental, the algorithm processes a single attribute of the context at a single step. Experimental results bear witness to its competitiveness.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Armstrong, W.W.: Dependency structure of data base relationships. In: Proc. IFIP Congress. Geneva, Switzerland, pp. 580–583 (1974)
Ausiello, G., D’Atri, A., Saccà, D.: Minimal representation of directed hypergraphs. SIAM J. Comput. 15(2), 418–431 (1986)
Birkhoff, G.: Lattice Theory. Amer. Math. Soc. Coll. Publ., Providence, R.I. (1973)
Blake, C.L., Merz, C.J.: UCI Repository of machine learning databases, Irvine, CA, University of California, Department of Information and Computer Science, Web Page http://www.ics.uci.edu/ mlearn/MLRepository.html (1998)
Carpineto, C., Romano, G.: A lattice conceptual clustering system and its application to browsing retrieval. Mach. Learn. 24(2), 95–122 (1996)
Day, A.: The lattice theory of functional dependencies and normal decompositions. Int. J. Algebra Comput. 2(4), 409–431 (1992)
Dowling, C.E.: On the irredundant generation of knowledge spaces. J. Math. Psychol. 37(1), 49–62 (1993)
Ferré, S.: Incremental concept formation made more efficient by the use of associative concepts, INRIA Research Report no. 4569 (2002)
Ganter, B.: Two Basic Algorithms in Concept Analysis, FB4-Preprint No. 831, TH Darmstadt (1984)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Berlin (1999)
Godin, R., Missaoui, R., Alaoui, H.: Incremental concept formation algorithms based on Galois lattices. Comput. Intell. 11(2), 246–267 (1995)
Guigues, J.-L., Duquenne, V.: Familles minimales d’implications informatives resultant d’un tableau de données binaires. Math. Sci. Hum. 95, 5–18 (1986)
Liquière, M., Ganter, B., Duquenne, V., Mephu Nguifo, E., Stumme, G.: ECAI 2002 International Workshop on Advances in Formal Concept Analysis for Knowledge Discovery in Databases. Lyon, France (2002)
Kuznetsov, S.: On the intractability of computing the Duquenne-Guigues base. J. Univers. Comput. Sci. 10(8), 927–933 (2004)
Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Intell. 14(2–3), 189–216 (2002)
Maier, D.: The Theory of Relational Databases. Computer Science, Rockville, MD (1983)
Mannila, H., Räihä, K.J.: The Design of Relational Databases. Addison Wesley, Boston, MA (1992)
Mephu Nguifo, E., Duquenne, V., Liquière, M.: ICCS-2001 International Workshop on Concept Lattices-Based Theory, Methods and Tools for Knowledge Discovery in Databases. Stanford CA, USA (2001)
Norris, E.M.: An algorithm for computing the maximal rectangles in a binary relation. Rev. Roum. Math. Pures. Appl. 23(2), 243–250 (1978)
Taouil, R., Bastide, Y.: Computing proper implications. In: Proc. ICCS-2001 International Workshop on Concept Lattices-Based Theory, Methods and Tools for Knowledge Discovery in Databases, pp. 49–61. Stanford CA, USA (2001)
Valtchev, P., Missaoui, R.: Building concept (Galois) lattices from parts: Generalizing the incremental methods. In: Proc. ICCS 2001, Lecture Notes in Artificial Intelligence, vol. 2120, pp. 290–303. Springer, Berlin (2001)
Van Der Merwe, F.J., Obiedkov, S., Kourie, D.G.: AddIntent: A new incremental lattice construction algorithm. Concept Lattices: Proc. of the 2nd Int. Conf. on Formal Concept Analysis, Lecture Notes in Artificial Intelligence, vol. 2961, pp. 372–385. Springer, Berlin (2004)
Wild, M.: Implicational bases for finite closure systems. In: Lex, W. (ed.) Arbeitstagung, Begriffsanalyse und Künstliche Intelligenz, pp. 147–169 Informatik-Bericht 89/3, TU Clausthal (1991)
Wild, M.: Computations with finite closure systems and implications, Preprint-Nr: 1708, TH Darmstadt (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Expanded version of a talk presented at Journées de l’Informatique Messine (Metz, France, September 2003).
Rights and permissions
About this article
Cite this article
Obiedkov, S., Duquenne, V. Attribute-incremental construction of the canonical implication basis. Ann Math Artif Intell 49, 77–99 (2007). https://doi.org/10.1007/s10472-007-9057-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-007-9057-2