Concept lattices

GALACTIC core concept

Concept

Formal Concept Analysis (FCA) is a mathematical framework used to analyze data in the form of objects and attributes. The central notion in FCA is that of a formal context and a concept lattice, which are derived using a (antitone) Galois connection.

Contexts

Definition

A formal context is a triple \(\left\langle G, M, I\right\rangle\) where:

• \(G\) is a set of objects.

• \(M\) is a set of attributes.

• \(I \subseteq G \times M\) is a binary relation between \(G\) and \(M\), indicating which objects possess which attributes.

Properties

(Antitone) Galois connection

For a set of objects \(A \subseteq G\), define \(\alpha(A)\) as the set of attributes common to all objects in \(A\):

\[ \alpha(A) = \{ m \in M \mid \forall g \in A, (g, m) \in I \} \]

For a set of attributes \(B \subseteq M\), define \(\beta(B)\) as the set of objects that possess all attributes in \(B\):

\[ \beta(B) = \{ g \in G \mid \forall m \in B, (g, m) \in I \} \]

The pair \(\left\langle \alpha,\beta\right\rangle\) form an (antitone) Galois connection between the power sets of \(G\) and \(M\), meaning that for any \(A \subseteq G\) and \(B \subseteq M\):

\[ A \subseteq \beta(B) \iff B \subseteq \alpha(A) \]

Concepts

Definition

A formal concept of the context \(\left\langle G, M, I\right\rangle\) is a pair \((A, B)\) where:

• \(A \subseteq G\) is a set of objects, called the extent.

• \(B \subseteq M\) is a set of attributes, called the intent.

• \(\alpha(A) = B\) and \(\beta(B) = A\).

Properties

Concept lattice

The set of all formal concepts forms a complete lattice, known as the concept lattice of the context. The partial order on this lattice is given by:

\[ (A_1, B_1) \leq (A_2, B_2) \iff A_1 \subseteq A_2 \iff B_1 \supseteq B_2 \]

AOC-posets

In Formal Concept Analysis (FCA), object concepts and attribute concepts are specific types of formal concepts that highlight the role of individual objects or attributes within the concept lattice. These concepts are crucial for understanding how particular objects or attributes are situated within the hierarchical structure of the lattice.

Definition

Object concept

An object concept is a formal concept associated with a particular object \(g \in G\). For an object \(g\), the object concept is defined as:

\[ (\beta\circ\alpha(\{g\}), \alpha(\{g\})) \]

The object concept \((\beta\circ\alpha(\{g\}), \alpha(\{g\}))\) represents the most specific concept in which the object \(g\) participates.

Attribute Concepts

An attribute concept is a formal concept associated with a particular attribute \(m \in M\). For an attribute \(m\), the attribute concept is defined as:

\[ (\beta(\{m\}), \alpha\circ\beta(\{m\})) \]

The attribute concept \((\beta(\{m\}), \alpha\circ\beta(\{m\}))\) represents the most general concept in which the attribute \(m\) participates.