Optimizations in computing the Duquenne-Guigues basis of implications. (English) Zbl 1310.68193

Summary: In this paper, we consider algorithms involved in the computation of the Duquenne-Guigues basis of implications. The most widely used algorithm for constructing the basis is Ganter’s Next Closure, designed for generating closed sets of an arbitrary closure system. We show that, for the purpose of generating the basis, the algorithm can be optimized. We compare the performance of the original algorithm and its optimized version in a series of experiments using artificially generated and real-life datasets. An important computationally expensive subroutine of the algorithm generates the closure of an attribute set with respect to a set of implications. We compare the performance of three algorithms for this task on their own, as well as in conjunction with each of the two algorithms for generating the basis. We also discuss other approaches to constructing the Duquenne-Guigues basis.


68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68W05 Nonnumerical algorithms
68W40 Analysis of algorithms
Full Text: DOI


[1] Angluin, D, Queries and concept learning, Mach. Learn., 2, 319-342, (1988)
[2] Angluin, D; Frazier, M; Pitt, L, Learning conjunctions of Horn clauses, Mach. Learn., 9, 147-164, (1992) · Zbl 0766.68107
[3] Arias, M; Balcázar, JL, Construction and learnability of canonical Horn formulas, Mach. Learn., 85, 273-297, (2011) · Zbl 1237.68106
[4] Armstrong, W.W.: Dependency structures of data base relationships. In: Proc. IFIP Congress, pp. 580-583 (1974) · Zbl 0296.68038
[5] Baader, F., Ganter, B., Sertkaya, B., Sattler, U.: Description logic knowledge bases using formal concept analysis. In: Veloso, M.M. (ed.) Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), pp. 230-235 (2007)
[6] Babin, MA; Kuznetsov, SO; Kryszkiewicz, M (ed.); Obiedkov, S (ed.), Recognizing pseudo-intents is conp-complete, 294-301, (2010), Spain
[7] Beeri, C; Bernstein, P, Computational problems related to the design of normal form relational schemas, ACM Trans. Database Syst., 4, 30-59, (1979)
[8] Bertet, K; Monjardet, B, The multiple facets of the canonical direct unit implicational basis, Theor. Comput. Sci., 411, 2155-2166, (2010) · Zbl 1209.68187
[9] Blake, C., Merz, C.: UCI repository of machine learning databases (1998). http://archive.ics.uci.edu/ml · Zbl 1274.68489
[10] Day, A, The lattice theory of functional dependencies and normal decompositions, Int. J. Algebra Comput., 2, 409-431, (1992) · Zbl 0798.68049
[11] Demming, R., Duffy, D.: Introduction to the Boost C++ Libraries. Datasim Education Bv (2010). See http://www.boost.org. Accessed 3 May 2013 · Zbl 1214.68387
[12] Distel, F; Sertkaya, B, On the complexity of enumerating pseudo-intents, Discrete Appl. Math., 159, 450-466, (2011) · Zbl 1214.68387
[13] Ganter, B.: Two basic algorithms in concept analysis. Preprint 831, Technische Hochschule Darmstadt, Germany (1984) · Zbl 1274.68484
[14] Ganter, B, Attribute exploration with background knowledge, Theor. Comput. Sci., 217, 215-233, (1999) · Zbl 0914.68168
[15] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Berlin (1999) · Zbl 0909.06001
[16] Guigues, JL; Duquenne, V, Familles minimales d’implications informatives resultant d’un tableau de donnees binaires, Math. Sci. Hum., 95, 5-18, (1986)
[17] Kautz, H; Kearns, M; Selman, B, Horn approximations of empirical data, Artif. Intell., 74, 129-145, (1995) · Zbl 1014.03514
[18] Khardon, R, Translating between Horn representations and their characteristic models, J. Artif. Intell. Res., 3, 349-372, (1995) · Zbl 0900.68197
[19] Klimushkin, M; Obiedkov, S; Roth, C; Kwuida, L (ed.); Sertkaya, B (ed.), Approaches to the selection of relevant concepts in the case of noisy data, 255-266, (2010), Berlin/Heidelberg · Zbl 1274.68489
[20] Kuznetsov, S; Obiedkov, S, Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 14, 189-216, (2002) · Zbl 1024.68020
[21] Kuznetsov, SO; Obiedkov, S, Some decision and counting problems of the duquenne-guigues basis of implications, Discrete Appl. Math., 156, 1994-2003, (2008) · Zbl 1160.68031
[22] Maier, D.: The theory of relational databases. Computer software engineering series. Computer Science Press, Rockville (1983)
[23] Mannila, H., Räihä, K.J.: The design of relational databases. Addison-Wesley Longman Publishing Co., Inc., Boston, MA (1992) · Zbl 0777.68014
[24] Obiedkov, S; Duquenne, V, Attribute-incremental construction of the canonical implication basis, Ann. Math. Artif. Intell., 49, 77-99, (2007) · Zbl 1125.68121
[25] Obiedkov, S; Kourie, D; Eloff, J, Building access control models with attribute exploration, Comput. Secur., 28, 2-7, (2009)
[26] Reeg, S., Wei, W.: Properties of Finite Lattices. Diplomarbeit, TH Darmstadt (1990)
[27] Roth, C; Obiedkov, S; Kourie, DG, On succinct representation of knowledge community taxonomies with formal concept analysis, Int. J. Found. Comput. Sci., 19, 383-404, (2008) · Zbl 1156.68588
[28] Ryssel, U; Distel, F; Borchmann, D, Fast computation of proper premises, 101-113, (2011), France
[29] 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. 290-303 (2001)
[30] Valtchev, P; Duquenne, V; Medina, R (ed.); Obiedkov, S (ed.), On the merge of factor canonical bases, 182-198, (2008), New York · Zbl 1131.68548
[31] Wild, M.: Computations with finite closure systems and implications. In: Computing and Combinatorics, pp. 111-120 (1995)
[32] Yevtushenko, S.A.: System of data analysis “Concept Explorer” (in Russian). In: Proceedings of the 7th National Conference on Artificial Intelligence KII-2000, pp. 127-134. Russia (2000). http://conexp.sourceforge.net/. Accessed 3 May 2013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.