📘 Descriptions

The galactic.algebras.convex.descriptions.core module implements Formal Concept Analysis theory adapted to convex algebras, providing a mathematical framework for analyzing relationships between objects (items) and their properties (predicates) through the lens of generalized convex hulls.

Core Components

Descriptions

The Description protocol is the foundational abstraction that defines description spaces. It accepts a tuple of characteristics and provides methods to compute minimal descriptors (borders) for collections of values. The _call() abstract method must be implemented by subclasses to compute predicates that describe items, while the _contains() method verifies predicate membership in the description space. The class enforces constraints on the minimum and maximum number of characteristics that can be reasonably handled.

from galactic.algebras.concept.core import Item
from galactic.algebras.convex.characteristics.core import Integer
from galactic.algebras.convex.descriptions.examples.arithmetic.core import (
    MultipleDescription,
)

characteristic = Integer()
description = MultipleDescription(characteristic=characteristic)
display(
    [
        str(predicate)
        for predicate in description(
            [
                Item(value=36),
                Item(value=48),
            ]
        )
    ]
)
display(
    [
        str(predicate)
        for predicate in description(
            [
                Item(value=1),
            ]
        )
    ]
)
display(
    [
        str(predicate)
        for predicate in description(
            [
                Item(value=0),
            ]
        )
    ]
)
display(
    [
        str(predicate)
        for predicate in description([])
    ]
)
display(
    [
        str(predicate)
        for predicate in description(
            [
                Item(value="abc"),
            ]
        )
    ]
)

['M(int(@),4)', 'M(int(@),3)']

[]

['M(int(@),0)']

['⊥']

[]

Contexts

The Context class represents the fundamental FCA context—a binary relation between an item universe and a predicate universe (represented by the PredicateUniverse class). It extends the binary relation abstraction to establish which items satisfy which predicates. The PredicateUniverse maintains an extensible Moore family of known predicates, growing dynamically as new predicates are discovered during concept computation. Together, they form the incidence structure upon which all concept analysis operations are built.

Galois Connection Components

The module implements a complete antitone Galois connection through five interconnected classes:

• Extent: Represents a closed set of items sharing common predicates. Items are stored as bitmaps for efficient set operations. The extent computes its associated intent by determining which predicates are satisfied by all items in the set. It supports meet (intersection) and join (union with closure) operations that maintain the lattice structure.

• Intent: Represents a closed set of predicates (borders) shared by common items. The intent actively maintains minimality—keeping only predicates not implied by others through a priority queue algorithm. It dynamically extends the predicate universe as new predicates are discovered. The intent computes its associated extent by intersecting the item sets satisfying each predicate.

• ItemPolarity and PredicatePolarity: Provide the two mappings of the Galois connection. PredicatePolarity maps sets of items to their shared predicates (computing intents), while ItemPolarity maps sets of predicates to items satisfying all of them (computing extents). These polarities ensure that applying both directions produces closures in their respective ordered sets.

• GaloisConnection: Orchestrates the entire connection, maintaining references to the context and providing access to both polarities. It serves as the central coordinator for all FCA operations.

Concept

Represents formal concepts in the convex FCA framework. A concept consists of an extent (maximal set of items sharing properties) and an intent (maximal set of properties shared by items). Concepts form a complete lattice under the natural ordering, with meet and join operations corresponding to logical conjunction and disjunction. The borders property provides the predicate boundaries that define the concept’s intent, essential for understanding the concept’s position in the description space.

Operational Workflow

The module operates through a sophisticated interplay: when computing concepts from items, the system first applies characteristics to extract values, then uses the Description’s _call method to compute border predicates. These predicates are registered in the PredicateUniverse and indexed in the Context’s binary relation. The Intent class identifies minimal predicates through predecessors analysis, while the Extent class efficiently computes item sets using bitmap operations. The GaloisConnection ensures that extent-intent pairs always form valid closed sets, maintaining the fundamental FCA property that applying both polarities yields the same concept.

This architecture enables efficient exploration of concept lattices for convex pattern mining, supporting applications in data analysis, knowledge discovery, and formal ontology construction where convex structures naturally arise.