Skip to main content
SpringerLink
Log in

Formal Concept Analysis

  • Chapter
  • First Online:
Book cover Handbook on Ontologies

Part of the book series: International Handbooks on Information Systems ((INFOSYS))

Summary

Formal concept analysis (FCA) is a mathematical theory about concepts and concept hierarchies. Based on lattice theory, it allows to derive concept hierarchies from datasets. In this survey, we recall the basic notions of FCA, including its relationship to folksonomies. The survey is concluded by a list of FCA based knowledge engineering solutions.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 349.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 449.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 449.99
Price excludes VAT (USA)
  • Durable hardcover 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

Notes

  1. 1.

    After a discussion of the three levels, DIN 2330 focusses on guidelines for good namings and definitions. It is thus a valuable resource for ontology engineers. An alternative source is the related international standard ‘ISO 704: Terminology Work – Principles and Methods’ [41].

  2. 2.

    http://www.informatik.uni-trier.de/ ∼ ley/db/conf/icfca/

  3. 3.

    http://www.informatik.uni-trier.de/ ∼ ley/db/conf/iccs/

  4. 4.

    http://www.bibsonomy.org/tag/fca

  5. 5.

    This is equivalent to requiring that A ×B ⊆ I such that neither A nor B can be enlarged without validating this condition.

  6. 6.

    That is, each subset of concepts has a unique greatest common subconcept (called its infimum ) and a unique least common superconcept (called its supremum ).

  7. 7.

    http://toscanaj.sourceforge.net/, see also [37] for its foundations and a description of its predecessor TOSCANA.

  8. 8.

    http://kdd.ics.uci.edu/

  9. 9.

    http://www.citeulike.org

  10. 10.

    http://www.connotea.org

  11. 11.

    http://www.43things.com

  12. 12.

    http://www.bibsonomy.org

  13. 13.

    http://www.bibsonomy.org/tag/triadic+fca

  14. 14.

    http://www.bibsonomy.org

  15. 15.

    http://www.informatik.uni-trier.de/~ley/db/

  16. 16.

    BibSonomy benchmark datasets are available for scientific purposes, see http://www.bibsonomy.org/faq.

  17. 17.

    See http://www.mail-sleuth.com/ for a commercial follow-up.

  18. 18.

    http://www.bibsonomy.org/user/stumme/OntologyHandbook+FCA

References

  1. R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD’93), pages 207–216. ACM, New York, 1993.

    Google Scholar 

  2. A. Arnauld and P. Nicole. La logique ou l’art de penser – Contenant, outre les règles communes, plusieurs observations nouvelles, propres à former le jugement. Ch. Saveux, 1668.

    Google Scholar 

  3. F. Baader. Computing a minimal representation of the subsumption lattice of all conjunctions of concepts defined in a terminology. In Proceedings of the International Symposium on Knowledge Retrieval, Use, and Storage for Efficiency, KRUSE 95, pages 168–178, Santa Cruz, USA, 1995.

    Google Scholar 

  4. F. Baader, B. Ganter, B. Sertkaya, and U. Sattler. Completing description logic knowledge bases using formal concept analysis. In M. M. Veloso, editor, Proc. IJCAI 2007, pages 230–235, 2007.

    Google Scholar 

  5. Y. Bastide, R. Taouil, N. Pasquier, G. Stumme, and L. Lakhal. Mining frequent patterns with counting inference. SIGKDD Explorations, Special Issue on Scalable Algorithms, 2(2):71–80, 2000.

    MATH  Google Scholar 

  6. K. Biedermann. How triadic diagrams represent conceptual structures. In D. Lukose, H. S. Delugach, M. Keeler, L. Searle, and J. F. Sowa, editors, Conceptual Structures: Fulfilling Peirce’s Dream, number 1257 in LNAI, pages 304–317. Springer, Heidelberg, 1997.

    Chapter  Google Scholar 

  7. K. Biedermann. Triadic Galois connections. In K. Denecke and O. Lders, editors, General Algebra and Applications in Discrete Mathematics, pages 23–33. Shaker, Aachen, 1997.

    Google Scholar 

  8. J.-F. Boulicaut, A. Bykowski, and C. Rigotti. Approximation of frequency queries by means of free-sets. In PKDD ’00: Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, pages 75–85. Springer, London, 2000.

    Google Scholar 

  9. A. Bykowski and C. Rigotti. A condensed representation to find frequent patterns. In PODS ’01: Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 267–273. ACM Press, New York, 2001.

    Google Scholar 

  10. T. Calders and B. Goethals. Mining all non-derivable frequent itemsets. In PKDD, pages 74–85, 2002.

    Google Scholar 

  11. C. Carpineto and G. Romano. Galois : An order-theoretic approach to conceptual clustering. In Proceedings of the 10th International Conference on Machine Learning (ICML’90), pages 33–40, July 1993.

    Google Scholar 

  12. C. Carpineto and G. Romano. Concept Data Analysis. Wiley, New York, 2004.

    Book  MATH  Google Scholar 

  13. L. Chaudron and N. Maille. Generalized formal concept analysis. In B. Ganter and G. W. Mineau, editors, ICCS, volume 1867 of Lecture Notes in Computer Science, pages 357–370. Springer, Berlin, 2000.

    Google Scholar 

  14. P. Cimiano, A. Hotho, and S. Staab. Learning concept hierarchies from text corpora using formal concept analysis. Journal on Artificial Intelligence Research, 24:305–339, 2005.

    MATH  Google Scholar 

  15. P. Cimiano, A. Hotho, G. Stumme, and J. Tane. Conceptual knowledge processing with formal concept analysis and ontologies. In P. Eklund, editor, Concept Lattices, volume 2961 of LNAI, pages 189–207, Heidelberg, 2004. Second International Conference on Formal Concept Analysis, ICFCA 2004, Springer, Berlin, 2004.

    Google Scholar 

  16. R. J. Cole, P. W. Eklund, and G. Stumme. Document retrieval for email search and discovery using formal concept analysis. Journal of Applied Artificial Intelligence (AAI), 17(3):257–280, 2003.

    Article  Google Scholar 

  17. F. Dau and R. Wille. On the modal understanding of triadic contexts. In R. Decker and W. Gaul, editors, Classification and Information Processing at the Turn of the Millennium, Proc. Gesellschaft für Klassifikation, 2001.

    Google Scholar 

  18. Deutsches Institut für Normung. DIN 2331: Begriffssysteme und ihre Darstellung, 1980.

    Google Scholar 

  19. Deutsches Institut für Normung. DIN 2330: Begriffe und Benennungen - Allgemeine Grundsätze, 1993.

    Google Scholar 

  20. J. Ducrou, B. Vormbrock, and P. W. Eklund. FCA-based browsing and searching of a collection of images. In Proc. of the 14th Int. Conference on Conceptual Structures. Springer, Berlin, 2006.

    Google Scholar 

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

    Google Scholar 

  22. S. Ferré and O. Ridoux. A file system based on concept analysis. In J. W. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. M. Pereira, Y. Sagiv, and P. J. Stuckey, editors, Computational Logic, volume 1861 of Lecture Notes in Computer Science, pages 1033–1047. Springer, Berlin, 2000.

    Google Scholar 

  23. S. Ferré and O. Ridoux. A logical generalization of formal concept analysis. In G. Mineau and B. Ganter, editors, Int. Conf. Conceptual Structures, LNCS 1867, pages 371–384. Springer, Berlin, 2000.

    Google Scholar 

  24. B. Ganter. Algorithmen zur Formalen Begriffsanalyse. In B. Ganter, R. Wille, and K. E. Wolff, editors, Beiträge zur Begriffsanalyse, pages 241–254. BI-Wissenschaftsverlag, Mannheim, 1987.

    Google Scholar 

  25. B. Ganter and S. A. Obiedkov. Implications in triadic contexts. In Conceptual Structures at Work: 12th International Conference on Conceptual Structures, volume 3127 of Lecture Notes in Computer Science, pages 186–195. Springer, Berlin, 2004.

    Google Scholar 

  26. B. Ganter, J. Stahl, and R. Wille. Conceptual measurement and many-valued contexts. In W. Gaul and M. Schader, editors, Classification as a Tool of Research, pages 169–176. North-Holland, Amsterdam, 1986.

    Google Scholar 

  27. B. Ganter and G. Stumme. Creation and merging of ontology top-levels. In A. de Moor, W. Lex, and B. Ganter, editors, Conceptual Structures for Knowledge Creation and Communication, volume 2746 of LNAI, pages 131–145. Springer, Heidelberg, 2003.

    Chapter  Google Scholar 

  28. B. Ganter, G. Stumme, and R. Wille, editors. Formal Concept Analysis – Foundations and Applications, volume 3626 of LNAI. Springer, Heidelberg, 2005.

    MATH  Google Scholar 

  29. B. Ganter and R. Wille. Contextual attribute logic. In W. M. Tepfenhart and W. R. Cyre, editors, ICCS, volume 1640 of Lecture Notes in Computer Science, pages 377–388. Springer, Berlin, 1999.

    Google Scholar 

  30. B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer, 1999. Translation of: Formale Begriffs analyse: Mathematische Grundlagen. Springer, Heidelberg, 1996.

    Google Scholar 

  31. R. Godin and P. Valtchev. Formal Concept Analysis-Based Class Hierarchy Design in Object-Oriented Software Development, volume 3626 of LNAI, pages 304–323. Springer, Berlin, 2005.

    MATH  Google Scholar 

  32. W. Hesse and T. A. Tilley. Formal Concept Analysis used for Software Analysis and Modelling, volume 3626 of LNAI, pages 288–303. Springer, Berlin, 2005.

    Google Scholar 

  33. A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme. BibSonomy: A social bookmark and publication sharing system. In Proc. of the ICCS 2006 Conceptual Structures Tool Interoperability Workshop, 2006.

    Google Scholar 

  34. A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme. Information retrieval in folksonomies: Search and ranking. In Proceedings of the 3rd European Semantic Web Conference, Lecture Notes in Computer Science. Springer, Berlin, 2006.

    Google Scholar 

  35. R. Jäschke, A. Hotho, C. Schmitz, B. Ganter, and G. Stumme. Trias – An algorithm for mining iceberg tri-lattices. In Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 06), pages 907–911. IEEE Computer Society, Hong Kong, December 2006.

    Google Scholar 

  36. R. Jäschke, A. Hotho, C. Schmitz, B. Ganter, and G. Stumme. Discovering shared conceptualizations in folksonomies. Journal of Web Semantics, 6(1):38–53, 2008.

    Article  Google Scholar 

  37. W. Kollewe, M. Skorsky, F. Vogt, and R. Wille. TOSCANA – ein Werkzeug zur begrifflichen Analyse und Erkundung von Daten. In R. Wille and M. Zickwolff, editors, Begriffliche Wissensverarbeitung-Grundfragen und Aufgaben, pages 267–288. BI-Wissenschaftsverlag, Mannheim, 1994.

    Google Scholar 

  38. F. Lehmann and R. Wille. A triadic approach to formal concept analysis. In G. Ellis, R. Levinson, W. Rich, and J. F. Sowa, editors, Conceptual Structures: Applications, Implementation and Theory, volume 954 of Lecture Notes in Artificial Intelligence, pages 32–43. Springer, Berlin, 1995.

    Chapter  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  40. G. Mineau and R. Godin. Automatic structuring of knowledge bases by conceptual clustering. IEEE Transactions on Knowledge and Data Engineering, 7(5):824–829, 1985.

    Article  Google Scholar 

  41. I. O. of Standardization. ISO 704. Terminology Work – Principles and Methods, 2000.

    Google Scholar 

  42. N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Pruning closed itemset lattices for association rules. In Actes des 14\grave{e}mes journées Bases de Donnes Avancées (BDA’98), pages 177–196, Octobre 1998.

    Google Scholar 

  43. N. Pasquier, R. Taouil, Y. Bastide, G. Stumme, and L. Lakhal. Generating a condensed representation for association rules. Journal of Intelligent Information Systems, 24(1):29–60, 2005.

    Article  MATH  Google Scholar 

  44. C. S. Peirce. Collected Papers of Charles Sanders Peirce. Harvard University Press, Cambridge, 1931–1935, 1958.

    Google Scholar 

  45. S. Prediger. Logical scaling in formal concept analysis. In D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. F. Sowa, editors, Conceptual Structures: Fulfilling Peirce’s Dream, number 1257 in Lecture Notes in Artificial Intelligence. Springer, Berlin, 1997.

    Google Scholar 

  46. S. Prediger and G. Stumme. Theory-driven logical scaling. In E. F. et al. editors, Proc. 6th Intl. Workshop Knowledge Representation Meets Databases (KRDB’99), volume CEUR Workshop Proc. 21, 1999. Also in P. Lambrix et al. editors, Proc. Intl. Workshop on Description Logics (DL’99). CEUR Workshop Proc. 22, 1999 http://ceur-ws.org/Vol-21.

  47. F. Rioult. Extraction de connaissances dans les bases de données comportant des valeurs manquantes ou un grand nombre d’attributs. PhD thesis, Université de Caen Basse-Normandie, 2005.

    Google Scholar 

  48. S. Rudolph. Relational Exploration – Combining Description Logics and Formal Concept Analysis for Knowledge Specification. Universitätsverlag Karlsruhe, 2006. Dissertation.

    Google Scholar 

  49. C. Schmitz, A. Hotho, R. Jäschke, and G. Stumme. Mining association rules in folksonomies. In Proceedings of the IFCS 2006 Conference, Lecture Notes in Computer Science. Springer, July 2006.

    Google Scholar 

  50. G. Snelting. Reengineering of configurations based on mathematical concept analysis. ACM Trans. Softw. Eng. Methodol., 5(2):146–189, 1996.

    Article  Google Scholar 

  51. G. Snelting. Concept Lattices in Software Analysis, volume 3626 of LNAI, pages 272–287. Springer, Berlin, 2005.

    Google Scholar 

  52. G. Snelting and F. Tip. Understanding class hierarchies using concept analysis. ACM Trans. Program. Lang. Syst., 22(3):540–582, 2000.

    Article  Google Scholar 

  53. J. F. Sowa. Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, Reading, MA, 1984.

    MATH  Google Scholar 

  54. S. Staab, S. Santini, F. Nack, L. Steels, and A. Maedche. Emergent semantics. Intelligent Systems, IEEE [see also IEEE Expert], 17(1):78–86, 2002.

    Google Scholar 

  55. L. Steels. The origins of ontologies and communication conventions in multi-agent systems. Autonomous Agents and Multi-agent Systems, 1(2):169–194, October 1998.

    Article  Google Scholar 

  56. S. Strahringer and R. Wille. Conceptual clustering via convex-ordinal structures. In O. Opitz, B. Lausen, and R. Klar, editors, Information and Classification, pages 85–98. Springer, Berlin, 1993.

    Chapter  Google Scholar 

  57. G. Stumme. Knowledge acquisition by distributive concept exploration. In G. Ellis, R. Levinson, W. Rich, and J. F. Sowa, editors, Conceptual Structures: Applications, Implementation and Theory, number 954 in Lecture Notes in Artificial Intelligence. Springer, Berlin, 1995.

    Google Scholar 

  58. G. Stumme. The concept classification of a terminology extended by conjunction and disjunction. In N. Foo and R. Goebel, editors, PRICAI’96: Topics in Artificial Intelligence. Proc. PRICAI’96, volume 1114 of LNAI, pages 121–131. Springer, Heidelberg, 1996.

    Google Scholar 

  59. G. Stumme. Exploration tools in formal concept analysis. In E. Diday, Y. Lechevallier, and O. Opitz, editors, Ordinal and Symbolic Data Analysis. Proc. OSDA’95. Studies in Classification, Data Analysis, and Knowledge Organization 8, pages 31–44. Springer, Heidelberg, 1996.

    Google Scholar 

  60. G. Stumme. Concept exploration – A tool for creating and exploring conceptual hierarchies. In D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. F. Sowa, editors, Conceptual Structures: Fulfilling Peirce’s Dream, Lecture Notes in Artificial Intelligence, volume 1257, pages 318–331. Springer, Berlin, 1997.

    Chapter  Google Scholar 

  61. G. Stumme. Conceptual knowledge discovery with frequent concept lattices. FB4-Preprint 2043, TU Darmstadt, 1999.

    Google Scholar 

  62. G. Stumme. A finite state model for on-line analytical processing in triadic contexts. In B. Ganter and R. Godin, editors, Proc. 3rd Intl. Conf. on Formal Concept Analysis, volume 3403 of LNCS, pages 315–328. Springer, Berlin, 2005.

    Google Scholar 

  63. G. Stumme and A. Maedche. FCA-Merge: Bottom-up merging of ontologies. In B. Nebel, editor, Proc. 17th Intl. Conf. on Artificial Intelligence (IJCAI ’01), pages 225–230, Seattle, WA, USA, 2001.

    Google Scholar 

  64. G. Stumme, R. Taouil, Y. Bastide, N. Pasqier, and L. Lakhal. Computing iceberg concept lattices with Titanic. Journal on Data and Knowledge Engineering, 42(2):189–222, 2002.

    Article  MATH  Google Scholar 

  65. G. Stumme, R. Taouil, Y. Bastide, N. Pasquier, and L. Lakhal. Intelligent structuring and reducing of association rules with formal concept analysis. In F. Baader, G. Brewker, and T. Eiter, editors, KI 2001: Advances in Artificial Intelligence, volume 2174 of LNAI, pages 335–350. Springer, Heidelberg, 2001.

    Chapter  Google Scholar 

  66. V. Takcs. Two applications of Galois graphs in pedagogical research. Manuscript of a lecture given at TH Darmstadt, 60 pages, February 1984.

    Google Scholar 

  67. J. Tane. Using a query-based multicontext for knowledge base browsing. In Formal Concept Analysis, Third International Conf., ICFCA 2005-Supplementary Volume, pages 62–78. IUT de Lens, Universite d Artois, FEB 2006.

    Google Scholar 

  68. J. Tane, P. Cimiano, and P. Hitzler. Query-based multicontexts for knowledge base browsing: An evaluation. In H. Schärfe, P. Hitzler, and P. Øhrstrøm, editors, Proc. 14th Intl. Conf. on Conceptual Structures, volume 4068 of LNCS, pages 413–426. Springer, Berlin, 2006.

    Google Scholar 

  69. J. Tane, C. Schmitz, and G. Stumme. Semantic resource management for the Web: An e-learning application. In Proc. 13th International World Wide Web Conference (WWW 2004), pages 1–10, 2004.

    Google Scholar 

  70. T. A. Tilley, R. J. Cole, P. Becker, and P. W. Eklund. A Survey of Formal Concept Analysis Support for Software Engineering Activities, volume 3626 of LNAI, pages 250–271. Springer, Berlin, 2005.

    MATH  Google Scholar 

  71. R. Wille. Restructuring lattice theory: An approach based on hierarchies of concepts. In I. Rival, editor, Ordered Sets, pages 445–470. Reidel, Dordrecht, 1982.

    Chapter  Google Scholar 

  72. R. Wille. The basic theorem of triadic concept analysis. Order, 12:149–158, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  73. R. Wille. Conceptual structures of multicontexts. In P. W. Eklund, G. Ellis, and G. Mann, editors, Conceptual Structures: Representation as Interlingua, pages 23–39. Springer, Berlin, 1996.

    Chapter  Google Scholar 

  74. R. Wille. Restructuring mathematical logic: An approach based on peirce’s pragmatism. In A. Ursini and P. Agliano, editors, Logic and Algebra, pages 267–281. Marcel Dekker, New York, 1996.

    Google Scholar 

  75. R. Wille. Conceptual graphs and formal concept analysis. In D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. F. Sowa, editors, Conceptual Structures: Fulfilling Peirce’s Dream, volume 1257 of Lecture Notes in Artificial Intelligence, pages 290–303. Springer, Heidelberg, 1997.

    Chapter  Google Scholar 

  76. M. J. Zaki. Generating non-redundant association rules. In Proc. KDD 2000, pages 34–43, 2000.

    Google Scholar 

  77. M. J. Zaki and C.-J. Hsiao. Charm: An efficient algorithm for closed association rule mining. technical report 99–10. Technical report, Computer Science Dept., Rensselaer Polytechnic, October 1999.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hertie Chair for Knowledge & Data Engineering, University of Kassel Wilhelmshöher, Allee 73, 34121, Kassel, Germany

    Gerd Stumme

  2. Research Center L3S, Appelstr. 9a, 30167, Hannover, Germany

    Gerd Stumme

Authors
  1. Gerd Stumme
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Inst. Informatik, Universität Koblenz-Landau, Universitaetsstr. 1, Koblenz, 56016, Germany

    Steffen Staab

  2. Inst. Angewandte Informatik und, Universität Karlsruhe, Karlsruhe, 76128, Germany

    Rudi Studer

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Stumme, G. (2009). Formal Concept Analysis. In: Staab, S., Studer, R. (eds) Handbook on Ontologies. International Handbooks on Information Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92673-3_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92673-3_8

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-70999-2

  • Online ISBN: 978-3-540-92673-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation