Skip to main content
SpringerLink
Log in

Intelligent Structuring and Reducing of Association Rules with Formal Concept Analysis

  • Conference paper
  • First Online:
KI 2001: Advances in Artificial Intelligence (KI 2001)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2174))

Included in the following conference series:

Abstract

Association rules are used to investigate large databases. The analyst is usually confronted with large lists of such rules and has to find the most relevant ones for his purpose. Based on results about knowledge representation within the theoretical framework of Formal Concept Analysis, we present relatively small bases for association rules from which all rules can be deduced. We also provide algorithms for their calculation.1

This paper is a revised and extended version of a presentation given at the workshop “Bases de Données Avancées”, Bordeaux, France, 1999 [29], and of the technical report [37].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Reference

  1. R. Agrawal, T. Imielinski, A. Swami. Mining association rules between sets of items in large databases. Proc. SIGMOD Conf., 1993, 207–216

    Google Scholar 

  2. R. Agrawal and R. Srikant. Fast algorithms for mining association rules. Proc. VLDB Conf., 1994, 478–499 (Expanded version in IBM Report RJ9839)

    Google Scholar 

  3. F. Baader, R. Molitor: Building and structuring Description Logic knowledge bases using least common subsumers and Concept Analysis. In: B. Ganter, G. W. Mineau (eds.): Conceptual Structures: Logical, Linguistic, and Computational Issues. Proc. ICCS 2000. LNAI 1867, Springer, Heidelberg 2000, 292–305

    Chapter  Google Scholar 

  4. E. Baralis and G. Psaila. Designing templates for mining association rules. Journal of Intelligent Information Systems 9(1), 1997, 7–32

    Article  Google Scholar 

  5. Y. Bastide, N. Pasquier, R. Taouil, G. Stumme, L. Lakhal: Mining minimal nonredundant association rules using frequent closed itemsets. In: J. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. M. Pereira, Y. Sagiv, P. J. Stuckey (Eds.): Computational Logic-CL 2000. Proc. 1st Intl. Conf. on CL (6th Intl. Conf. on Database Systems). LNAI 1861, Springer, Heidelberg 2000, 972–986

    Chapter  Google Scholar 

  6. Y. Bastide, R. Taouil, N. Pasquier, G. Stumme, L. Lakhal: Mining Frequent Patterns with Counting Inference. SIGKDD Explorations 2(2), Special Issue on Scalable Algorithms, 2000, 66–75

    Article  Google Scholar 

  7. R. J. Bayardo. Efficiently mining long patterns from databases. Proc. SIGMOD Conf., 1998, 85–93

    Google Scholar 

  8. R. J. Bayardo, R. Agrawal, D. Gunopulos. Constraint-based rule mining in large, dense databases. Proc. ICDE Conf., 1999, 188–197

    Google Scholar 

  9. K. Becker, G. Stumme, R. Wille, U. Wille, M. Zickwolff: Conceptual Information Systems discussed through an IT-security tool. In: R. Dieng, O. Corby (Eds.): Knowledge Engineering and Knowledge Management. Methods, Models, and Tools. Proc. EKAW’ 00. LNAI 1937, Springer, Heidelberg 2000, 352–365

    Chapter  Google Scholar 

  10. S. Brin, R. Motwani, C. Silverstein: Beyond market baskets: Generalizing association rules to correlation. Proc. SIGMOD Conf., 1997, 265–276

    Google Scholar 

  11. S. Brin, R. Motwani, J. D. Ullman, S. Tsur: Dynamic itemset counting and implication rules for market basket data. Proc. SIGMOD Conf., 1997, 255–264

    Google Scholar 

  12. V. Duquenne, J.-L. Guigues: Famille minimale d’implication informatives résultant d’un tableau de données binaires. Mathématiques et Sciences Humaines 24(95), 1986, 5–18

    MathSciNet  Google Scholar 

  13. U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy (eds.): Advances in knowledge discovery and data mining. AAAI Press, Cambridge 1996

    Google Scholar 

  14. B. Ganter, K. Reuter: Finding all closed sets: A general approach. Order. Kluwer Academic Publishers, 1991, 283–290

    Google Scholar 

  15. B. Ganter, R. Wille: Formal Concept Analysis: Mathematical Foundations. Springer, Heidelberg 1999

    MATH  Google Scholar 

  16. A. Grosskopf and G. Harras: Eine TOSCANA-Anwendung für Sprechaktverben des Deutschen. In: G. Stumme and R. Wille (eds.), Begriffliche Wissensverarbeitung: Methoden und Anwendungen. Springer, Berlin-Heidelberg-New York 2000.

    Google Scholar 

  17. J. Han, Y. Fu: Discovery of multiple-level association rules from large databases. Proc. VLDB Conf., 1995, 420–431 1995.

    Google Scholar 

  18. J. Hereth, G. Stumme, U. Wille, R. Wille: Conceptual Knowledge Discovery and Data Analysis. In: B. Ganter, G. W. Mineau (eds.): Conceptual Structures: Logical, Linguistic, and Computational Issues. Proc. ICCS 2000. LNAI 1867, Springer, Heidelberg 2000, 421–437

    Chapter  Google Scholar 

  19. J. Hipp, A. Myka, R. Wirth, U. Güntzer: A new algorithm for faster mining of generalized association rules. LNAI 1510, Springer, Heidelberg 1998

    Google Scholar 

  20. U. Kaufmann: Begriffliche Analyse über Flugereignisse-Implementierung eines Erkundungs-und Analysesystems mit TOSCANA. Diplomarbeit, FB4, TU Darmstadt 1996.

    Google Scholar 

  21. M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, A. I. Verkamo: Finding interesting rules from large sets of discovered association rules. Proc. CIKM Conf., 1994, 401–407

    Google Scholar 

  22. M. Luxenburger: Implications partielles dans un contexte. Mathématiques, Informatique et Sciences Humaines, 29(113), 1991, 35–55

    MathSciNet  Google Scholar 

  23. M. Luxenburger: Partial implications. Part I of Implikationen, Abhängigkeiten und Galois Abbildungen. PhD thesis, TU Darmstadt. Shaker, Aachen 1993

    Google Scholar 

  24. H. Mannila, H. Toivonen: Multiple uses of frequent sets and condensed representations (Extended abstract). Proc. KDD 1996, 189–194

    Google Scholar 

  25. R. Meo, G. Psaila, S. Ceri: A new SQL-like operator for mining association rules. Proc. VLDB Conf., 1996, 122–133

    Google Scholar 

  26. R. T. Ng, V. S. Lakshmanan, J. Han, A. Pang: Exploratory mining and pruning optimizations of constrained association rules. Proc. SIGMOD Conf., 1998, 13–24

    Google Scholar 

  27. N. Pasquier: Data Mining: algorithmes d’extraction et de réduction des régles d’association dans les bases de données. PhD thesis. Université Blaise Pascal, Clermont-Ferrand II, 2000

    Google Scholar 

  28. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal: Pruning closed itemset lattices for association rules. Proc. 14iémes Journées Bases de Données Avancées (BDA’98), Hammamet, Tunisie, 177–196

    Google Scholar 

  29. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal: Closed set based discovery of small covers for association rules. Proc. 15émes Journées Bases de Données Avancées, Bordeaux, France, 25-27 October 1999, 361–381

    Google Scholar 

  30. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal: Discovering frequent closed itemsets for association rules. Proc. ICDT Conf., 1999, 398–416

    Google Scholar 

  31. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal: Efficient mining of association rules using closed itemset lattices. Journal of Information Systems, 24(1), 1999, 25–46

    Article  Google Scholar 

  32. J. Pei, J. Han, R. Mao:CLOSET: An efficient algorithm for mining frequent closed itemsets. Proc. ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery2000, 21–30

    Google Scholar 

  33. M. Roth-Hintz, M. Mieth, T. Wetter, S. Strahringer, B. Groh, R. Wille: Investgating SNOMED by Formal Concept Analysis. Preprint, FB4, TU Darmstadt 1997.

    Google Scholar 

  34. R. Srikant, R. Agrawal: Mining generalized association rules. Proc. VLDB Conf., 1995, 407–419

    Google Scholar 

  35. R. Srikant, Q. Vu, R. Agrawal: Mining association rules with item constraints. Proc. KDD Conf., 1997, 67–73

    Google Scholar 

  36. G. Stumme, R. Wille, U. Wille: Conceptual Knowledge Discovery in Databases Using Formal Concept Analysis Methods. In: J. M. Żytkow, M. Quafofou (eds.): Principles of Data Mining and Knowledge Discovery. Proc. 2nd European Symposium on PKDD’98, LNAI 1510, Springer, Heidelberg 1998, 450–458

    Chapter  Google Scholar 

  37. G. Stumme: Conceptual Knowledge Discoverywith Frequent Concept Lattices. FB4-Preprint 2043, TU Darmstadt 1999

    Google Scholar 

  38. G. Stumme, R. Taouil, Y. Bastide, N. Pasquier, L. Lakhal: Fast Computation of Concept Lattices Using Data Mining Techniques. Proc. 7th Intl. Workshop on Knowledge Representation Meets Databases, Berlin, 21 22. August 2000. CEUR-Workshop Proceeding. http://sunsite.informatik.rwthaachen. de/Publications/CEUR-WS/

  39. G. Stumme, R. Taouil, Y. Bastide, N. Pasquier, L. Lakhal: Computing Iceberg Concept Lattices with Titanic. J. on Knowledge and Data Engineering. (submitted)

    Google Scholar 

  40. F. Vogt, R. Wille: TOSCANA-A graphical tool for analyzing and exploring data. LNCS 894, Springer, Heidelberg 1995, 226–233

    Google Scholar 

  41. R. Wille: Restructuring lattice theory: an approach based on hierarchies of concepts. In: I. Rival (ed.). Ordered sets. Reidel, Dordrecht-Boston 1982, 445–470

    Google Scholar 

  42. M. J. Zaki, M. Ogihara: Theoretical Foundations of Association Rules, 3rd SIGMOD’ 98 Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD), Seattle, WA, June 1998, 7:1–7:8

    Google Scholar 

  43. M. J. Zaki, C.-J. Hsiao: ChARM: An efficient algorithm for closed association rule mining. Technical Report 99-10, Computer Science Dept., Rensselaer Polytechnic Institute, October 1999

    Google Scholar 

  44. M. J. Zaki: Generating non-redundant association rules. Proc. KDD 2000. 34–43

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB), Universität Karlsruhe (TH), D-76128, Karlsruhe, Germany

    Gerd Stumme

  2. INRIA Lorraine, LORIA, BP 239, F-54506, Vandoeuvre-lés-Nancy, France

    Rafik Taouil

  3. Laboratoire d’Informatique (LIMOS), Université Blaise Pascal, Complexe Scientifique des Cézeaux, 24 Av. des Landais, F-63177, Aubiére Cedex, France

    Yves Bastide

  4. I3S, CNRS UMR-6070, Université de Nice - Sophia Antipolis, Les Algorithmes, 2000 route des Lucioles, F-06903, Sophia Antipolis, France

    Nicolas Pasquier

  5. LIM, CNRS FRE-2246, Université de la Méditerranée, Case 90, 163 Avenue de Luminy, F-13288, Marseille Cedex 9, France

    Lotfi Lakhal

Authors
  1. Gerd Stumme
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rafik Taouil
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yves Bastide
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicolas Pasquier
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Lotfi Lakhal
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. RWTH Aachen, Theoretical Computer Science, Ahornstrasse 55, 52074, Aachen, Germany

    Franz Baader

  2. Intelligent Systems Department, University of Leipzig, Computer Science Institute, Augustusplatz 10-11, 04109, Leipzig, Germany

    Gerhard Brewka

  3. Institute of Information Systems Knowledge-Based Systems Group, Vienna University of Technology, Favoritenstrasse 11, 1040, Wien, Austria

    Thomas Eiter

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Stumme, G., Taouil, R., Bastide, Y., Pasquier, N., Lakhal, L. (2001). Intelligent Structuring and Reducing of Association Rules with Formal Concept Analysis. In: Baader, F., Brewka, G., Eiter, T. (eds) KI 2001: Advances in Artificial Intelligence. KI 2001. Lecture Notes in Computer Science(), vol 2174. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45422-5_24

Download citation

  • DOI: https://doi.org/10.1007/3-540-45422-5_24

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42612-7

  • Online ISBN: 978-3-540-45422-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation