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.

Metatheory. Galois connections. Complete lattices. Implications. Closure systems.

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

Limitations. Binary attributes. Scalability. Crisp contexts. Noise sensitivity.