Abstract
A central task in formal concept analysis is the enumeration of a small base for the implications that hold in a formal context. The usual stem base algorithms have been proven to be costly in terms of runtime. Proper premises are an alternative to the stem base. We present a new algorithm for the fast computation of proper premises. It is based on a known link between proper premises and minimal hypergraph transversals. Two further improvements are made, which reduce the number of proper premises that are obtained multiple times and redundancies within the set of proper premises. We have evaluated our algorithms within an application related to refactoring of model variants. In this application an implicational base needs to be computed, and runtime is more crucial than minimal cardinality. In addition to the empirical tests, we provide heuristic evidence that an approach based on proper premises will also be beneficial for other applications. Finally, we show how our algorithms can be extended to an exploration algorithm that is based on proper premises.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Babin, M., Kuznetsov, S.: Recognizing pseudo-intents is coNP-complete. In: Kryszkiewicz, M., Obiedkov, S. (eds.) Proc. of the 7th Int. Conf. on Concept Lattices and Their Applications, vol. 672. CEUR Workshop Proceedings (2010)
Bailey, J., Manoukian, T., Ramamohanarao, K.: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In: ICDM, pp. 485–488. IEEE Computer Society (2003)
Berge, C.: Hypergraphs—combinatorics of finite sets. North-Holland, Amsterdam (1989)
Bertet, K., Monjardet, B.: The multiple facets of the canonical direct unit implicational basis. Theor. Comput. Sci. 411(22–24), 2155–2166 (2010)
Borchmann, D.: Conexp-clj—a general-purpose tool for formal concept analysis. See http://www.math.tu-dresden.de/~borch/conexp-clj/
Borchmann, D.: A General Form of Attribute Exploration. LTCS-Report 13-02, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany (2013). See http://lat.inf.tu-dresden.de/research/reports.html
Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett. 10, 253–266 (2000)
Boros, E., Elbassioni, K., Makino, K.: On berge multiplication for monotone boolean dualization. In: Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, ICALP ’08, pp. 48–59. Springer-Verlag, Berlin, Heidelberg (2008)
Cios, K.J., Kurgan, L.A., Goodenday, L.S.: UCI Machine Learning Repository: SPECT Heart Data Set (2001). http://archive.ics.uci.edu/ml/datasets/SPECT+Heart
Distel, F.: Hardness of enumerating pseudo-intents in the lectic order. In: Sertkaya, B., Kwuida, L. (eds.) Proc. of the 8th Int. Conf. on Formal Concept Analysis. Lecture Notes in Artificial Intelligence, vol. 5986, pp. 124–137. Springer (2010)
Distel, F.: Hardness of enumerating pseudo-intents in the lectic order. In: Kwuida, L., Sertkaya, B. (eds.) ICFCA. Lecture Notes in Computer Science, vol. 5986, pp. 124–137. Springer (2010)
Distel, F., Borchmann, D.: Expected Numbers of Proper Premises and Concept Intents. Preprint, Institut für Algebra, TU Dresden (2011)
Distel, F., Sertkaya, B.: On the complexity of enumerating pseudo-intents. Discret. Appl. Math. 159(6), 450–466 (2011)
Dong, G., Li, J.: Mining border descriptions of emerging patterns from dataset pairs. Knowl. Inf. Syst. 8(2), 178–202 (2005)
Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32, 514–537 (2003)
Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21(3), 618–628 (1996)
Ganter, B.: Two Basic Algorithms in Concept Analysis. Preprint 831, Fachbereich Mathematik, TU Darmstadt, Darmstadt, Germany (1984)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, New York (1999)
Guigues, J.L., Duquenne, V.: Familles minimales d’implications informatives résultant d’un tableau de données binaires. Math. Sci. Hum. 95, 5–18 (1986)
Gunopulos, D., Mannila, H., Khardon, R., Toivonen, H.: Data mining, hypergraph transversals, and machine learning (extended abstract). In: Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, PODS ’97, pp. 209–216. ACM, New York, NY, USA (1997). doi:10.1145/263661.263684
Hagen, M.: Algorithmic and Computational Complexity Issues of MONET. Ph.D. thesis, Friedrich-Schiller-Universität Jena (2008)
Kavvadias, D.J., Stavropoulos, E.C.: An efficient algorithm for the transversal hypergraph generation. J. Graph Algorithms Appl. 9(2), 239–264 (2005)
Kuznetsov, S.O.: On the intractability of computing the Duquenne-Guigues base. J. Univers. Comput. Sci. 10(8), 927–933 (2004)
Maier, D.: Theory of Relational Databases. Computer Science Pr (1983)
Mannila, H., Räihä, K.J.: Algorithms for inferring functional dependencies from relations. Data Knowl. Eng. 12(1), 83–99 (1994)
Obiedkov, S., Duquenne, V.: Attribute-incremental construction of the canonical implication basis. Ann. Math. Artif. Intell. 49(1–4), 77–99 (2007)
Reppe, H.: Attribute exploration using implications with proper premises. In: Eklund, P.W., Haemmerlé, O. (eds.) ICCS, Lecture Notes in Computer Science, vol. 5113, pp. 161–174. Springer (2008)
Rudolph, S.: Some notes on pseudo-closed sets. In: Kuznetsov, S.O., Schmidt, S. (eds.) Proc. of the 5th Int. Conf. on Formal Concept Analysis. Lecture Notes in Computer Science, vol. 4390, pp. 151–165. Springer (2007)
Ryssel, U., Ploennigs, J., Kabitzsch, K.: Automatic variation-point identification in function-block-based models. In: Proc. of the 9th Int. Conf. on Generative Programming and Component Engineering, pp. 23–32. ACM (2010)
Ryssel, U., Ploennigs, J., Kabitzsch, K.: Extraction of feature models from formal contexts. In: Proc. of the 15th Int. Software Product Line Conference, pp. 4:1–4:8. ACM (2011)
Schlimmer, J.: UCI Machine Learning Repository: 1984 United Stated Congressional Voting Records (1987). http://archive.ics.uci.edu/ml/datasets/Congressional+Voting+Records
Takata, K.: A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph. SIAM J. Discret. Math. 21(4), 936–946 (2007)
Zaki, M.J., Ogihara, M.: Theoretical foundations of association rules. In: Proceedings of the 3rd ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
The author Daniel Borchmann has been supported by DFG Graduiertenkolleg 1763 (QuantLA).
Rights and permissions
About this article
Cite this article
Ryssel, U., Distel, F. & Borchmann, D. Fast algorithms for implication bases and attribute exploration using proper premises. Ann Math Artif Intell 70, 25–53 (2014). https://doi.org/10.1007/s10472-013-9355-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-013-9355-9