Formal Concept Analysis

The foundational data structure of FCA, represented as a binary relation between a set of objects and a set of attributes. It is typically visualized as a cross-table where a mark indicates that an object possesses a given attribute.

• Objects (G): The entities being classified (e.g., documents, patients, species).
• Attributes (M): The properties or features (e.g., keywords, symptoms, traits).
• Incidence Relation (I): A subset of G × M defining which objects have which attributes.

A formal context is mathematically defined as the triple K := (G, M, I). This structure provides the raw data from which all concepts are derived.

A pair of Galois connection operators that map between sets of objects and sets of attributes, forming the core calculus of FCA. These operators define the closure relationship that generates formal concepts.

• Intent Derivation (↑): For a set of objects A ⊆ G, A↑ yields the set of all attributes common to those objects.
• Extent Derivation (↓): For a set of attributes B ⊆ M, B↓ yields the set of all objects possessing all those attributes.

Applying both operators sequentially—A↑↓ or B↓↑—produces a closure operator, ensuring that the resulting set is maximal and stable under the derivation.

A pair (A, B) consisting of an extent and an intent that are perfectly closed under the derivation operators. This represents a maximal cluster of objects sharing a maximal set of attributes.

• Extent (A): A set of objects A ⊆ G such that A = B↓.
• Intent (B): A set of attributes B ⊆ M such that B = A↑.
• Closure Condition: A↑ = B and B↓ = A must hold simultaneously.

A formal concept is the fundamental unit of thought in FCA, representing a natural conceptual grouping where the extent and intent uniquely determine each other.

The complete, hierarchically ordered set of all formal concepts derived from a formal context. The lattice is structured by the subconcept-superconcept relation, forming a partial order.

• Partial Order (≤): A concept (A₁, B₁) is a subconcept of (A₂, B₂) if A₁ ⊆ A₂ (equivalently, B₂ ⊆ B₁).
• Supremum and Infimum: Every pair of concepts has a unique least upper bound (join) and greatest lower bound (meet).
• Hasse Diagram: The standard visualization, where nodes represent concepts and edges represent direct subconcept relationships.

The lattice reveals the dual isomorphism between the generalization of objects and the specialization of attributes, making implicit taxonomic relationships explicit.

A logical dependency extracted from the formal context, stating that any object possessing a set of premise attributes must also possess a set of conclusion attributes. Implications form a non-redundant canonical base.

• Syntax: P → C, where P, C ⊆ M (e.g., {winged, beak} → {lays_eggs}).
• Semantic Validity: An implication holds in a context if every object having all attributes in P also has all attributes in C.
• Duguenne-Guigues Base: The minimal, canonical set of implications from which all other valid implications can be inferred.

Attribute implications are critical for ontology completion, identifying missing axioms, and detecting logical inconsistencies in a knowledge base.

The process of transforming many-valued attributes (e.g., numerical, nominal) into a binary formal context suitable for FCA. This bridges the gap between raw data and the binary incidence relation.

• Nominal Scaling: Each distinct value becomes a separate binary attribute, partitioning objects into mutually exclusive categories.
• Ordinal Scaling: Preserves the order of values by creating binary attributes for thresholds (e.g., ≥ 10, ≥ 20).
• Interordinal Scaling: Combines ascending and descending ordinal scales to capture interval relationships.

Scaling choices profoundly influence the structure of the resulting concept lattice, making it a critical design decision in applying FCA to real-world data.