Formal Concept Analysis

Origin. Wille (1982). Lattice-based knowledge. Objects and attributes. Concept hierarchies. Foundation of conceptual knowledge.

Models. Formal contexts. Concept lattices. Galois connections. Attribute implications. Structured knowledge.

Formalism.

Formal context: K = ⟨G, M, I⟩ where: G: objects. M: attributes. I ⊆ G × M: incidence. (g, m) ∈ I: object g has attribute m.

Derivation operators: A' = {m ∈ M : ∀g ∈ A. (g,m) ∈ I}. B' = {g ∈ G : ∀m ∈ B. (g,m) ∈ I}. A ⊆ G maps to attributes. B ⊆ M maps to objects.

Formal concept: (A, B) where A' = B and B' = A. A: extent (objects). B: intent (attributes). Closed pair.

Galois connection: A ⊆ B'' and B ⊆ A' for A ⊆ G, B ⊆ M. Closure operators. Duality.

Concept lattice: L(K): set of all concepts of K. Ordered: (A₁, B₁) ≤ (A₂, B₂) iff A₁ ⊆ A₂. Complete lattice. Subconcept relation.

Meet and join: (A₁, B₁) ∧ (A₂, B₂) = (A₁ ∩ A₂, (B₁ ∪ B₂)''). (A₁, B₁) ∨ (A₂, B₂) = ((A₁ ∪ A₂)'', B₁ ∩ B₂). Lattice operations.

Attribute implication: B₁ → B₂: objects with B₁ have B₂. If B₁ ⊆ g' then B₂ ⊆ g'. Horn clause form.

Stem base: Minimal set of implications. Duquenne-Guigues basis. Complete and non-redundant.

Symbols.

Symbol	Unicode	Name	Meaning
⟨	U+27E8	Mathematical left angle bracket	Opens the context triple
⟩	U+27E9	Mathematical right angle bracket	Closes the context triple
'	U+0027	Apostrophe / Derivation operator	Sends objects to their common attributes, and conversely
⊆	U+2286	Subset	Incidence inside G × M; extent inside G; intent inside M
×	U+00D7	Multiplication sign / Cartesian product	Incidence is a set of object-attribute pairs
∈	U+2208	Membership	Object, attribute or incident pair belongs to a set
∀	U+2200	Universal quantifier	Derivation quantifies over the whole set
≤	U+2264	Less-than or equal to / Subconcept order	Order of the lattice, given by extent inclusion
∧	U+2227	Logical and / Meet	Greatest common subconcept
∨	U+2228	Logical or / Join	Least common superconcept
∩	U+2229	Intersection	Extents meet by intersection; intents join by intersection
∪	U+222A	Union	Taken before closure in the lattice operations
→	U+2192	Rightwards arrow / Attribute implication	Every object with the left set carries the right set
₁	U+2081	Subscript one	Index on the first concept or attribute set
₂	U+2082	Subscript two	Index on the second concept or attribute set
ⁿ	U+207F	Superscript latin small letter n	Exponent counting concepts of a context of size n
K	—	Formal context	The triple ⟨G, M, I⟩
G	—	Objects	Gegenstände; the rows of the context
M	—	Attributes	Merkmale; the columns of the context
I	—	Incidence	Which objects carry which attributes
A	—	Extent	Objects of a concept
B	—	Intent	Attributes of a concept
L(K)	—	Concept lattice	All concepts of K under the subconcept order

Metatheory. The derivation operators form a Galois connection between the powersets of G and M, so their double applications are closure operators and the formal concepts are exactly the pairs of closed sets. Wille's basic theorem settles the scope of the construction in both directions: L(K) is always a complete lattice with infima and suprema given by the meet and join formulas, and conversely every complete lattice is isomorphic to the concept lattice of some context, so concept lattices and complete lattices are the same objects differently presented. The implication theory of a context is propositional Horn, and Duquenne and Guigues (1986) showed it has a canonical basis — the stem base, built from the pseudo-intents — which is complete, non-redundant and of minimum cardinality among complete sets of implications. Size is the recurring obstacle. A context on n objects and n attributes can have 2ⁿ concepts, counting them is #P-complete (Kuznetsov 2001), and while Ganter's NextClosure enumerates concepts with polynomial delay, Distel and Sertkaya (2011) proved the stem base cannot be enumerated in output-polynomial time unless P = NP.

Applies to. Knowledge representation. Data analysis. Ontologies. Lattice theory.

Limitations. Incidence is binary and total — an object either carries an attribute or does not — so numerical, ordinal and many-valued data must first be turned into a binary context by conceptual scaling, a choice made outside the theory that determines which lattice is obtained. There is no provision for missing values, for degrees, or for noise: a single spurious incidence yields a genuine concept, so the lattice is not stable under small perturbations of the context. The size problem is structural rather than an artefact of implementation, since the contranominal scale on n attributes has 2ⁿ concepts, counting concepts is #P-complete, and the canonical basis cannot be enumerated in output-polynomial time unless P = NP. Implications are Horn, so disjunctive and negative regularities are inexpressible, and there is no quantification over objects, which puts relations between objects outside the formalism and requires an extension such as relational concept analysis.