chapter  1
14 Pages

A Brief Introduction to Formal Concept Analysis

ByMarkus Krötzsch, Bernhard Ganter

Mathematics has, quite naturally, always been concerned not just with numbers and functions, but also with many other kinds of abstract objects and structures. Yet it became clear only in recent decades – especially with the advent of Computer Science – that approaches originating in algebra and discrete mathematics also find concrete practical use in many application domains where numerical methods are not satisfactory. A prominent example is the requirement to represent and process increasing amounts of computermediated “knowledge” in a formal way that allows for suitable algorithmic treatment. Modern discrete mathematics supplies a number of tools for addressing this

aspect, and previous decades saw the development of a rich theory of structures, comprising the theory of ordered sets and in particular the theory of lattices. Originally developed as a tool for describing mathematical structures, this field of research has since been found to be increasingly useful for much more applied disciplines. Formal Concept Analysis (FCA) provides a mathematical notion of concepts and concept hierarchies that is based on order and lattice theory. The basis of FCA are remarkably simple data structures, so-called “for-

mal contexts.” To each such data set, FCA associates hierarchies of “formal

concepts” which, as one can formaly show, carry the structure of complete lattices. In consequence, methods for processing and analyzing such data can draw from the extensive toolbox of lattice theory, which does provide both a rigorous formal foundation and insights for obtaining suitable algorithms. As we will see, one can also connect FCA with ideas from formal logic, which confirms the intuition that FCA is indeed an approach for representing and processing knowledge. This chapter ist structured as follows. In Section 1.2, we begin our introduc-

tion with (formal) contexts and concepts, the central notions of FCA. We also introduce some basic properties, and relate formal concepts to the concept of a closure operator. Concept lattices and the related graphical representation of conceptual knowledge are presented in Section 1.3, before Section 1.4 takes a more logical viewpoint by introducing attribute implications and their relationships with formal contexts. Section 1.5 then gives an intuitive introduction to the method of attribute exploration that is widely used to support the construction of contexts and implications when no complete description is available yet.