Formal Concept Analysis (FCA) is a mathematical framework that extracts structured conceptual hierarchies from binary data. Here is how it works, step-by-step.
Step 1: The Formal Context (Data Table)
An FCA analysis starts with a Formal Context K = (G, M, I), where: - G is a set of objects (Spanish: objetos). - M is a set of attributes (Spanish: atributos). - I \subseteq G \times M is an incidence relation showing which objects have which attributes.
For example, let’s represent a small context of animals:
| Animals (G) | Warm-Blooded | Has Wings | Four Legs | Carnivore |
|---|---|---|---|---|
| Dog | X | X | X | |
| Cat | X | X | X | |
| Eagle | X | X | X | |
| Frog | X |
Step 2: The Derivation Operators (Galois Connections)
For any subset of objects A \subseteq G, we define A' as the set of attributes common to all objects in A: A' = \{ m \in M \mid \forall g \in A, (g, m) \in I \}
Similarly, for a subset of attributes B \subseteq M, we define B' as the set of all objects sharing all attributes in B: B' = \{ g \in G \mid \forall m \in B, (g, m) \in I \}
These operators form a Galois Connection between the powersets \mathcal{P}(G) and \mathcal{P}(M).
Step 3: Formal Concepts
A Formal Concept is a pair (A, B) where: - A \subseteq G is the extent (objects belonging to the concept). - B \subseteq M is the intent (attributes describing the concept). - And they satisfy: A' = B and B' = A.
This means the concept is maximal: you cannot add more objects without losing some attributes, and you cannot add more attributes without excluding some objects.
Step 4: The Concept Lattice
All formal concepts of a context can be ordered hierarchically by extent inclusion: (A_1, B_1) \le (A_2, B_2) \iff A_1 \subseteq A_2 \quad (\iff B_2 \subseteq B_1)
This partial order forms a mathematical structure called a Complete Lattice (retículo completo), where the supremum (join) and infimum (meet) always exist.
Below is a visualization of how these concepts form a hierarchy, showing how more specific concepts (e.g. Carnivorous Warm-Blooded Flying Animals) inherit attributes from more general concepts above them.
To run custom analyses, load matrices, or calculate Concept Lattices using R code directly in your browser, check out our Interactive WebR Console!