Convex Lattices

Components

Characteristics are derived from raw data using components defined by a JMESPath expression. The find method returns an iterator of values extracted from the raw datum, representing partial imprecision. If the datum cannot be processed, an None value is returned, indicating complete imprecision (i.e., any value within the domain is possible).

from galactic.algebras.concept.core import Item
from galactic.algebras.convex.characteristics.core import Component

component = Component(expr="value")
component

Component(expr='value')

dataset = [
    {"value": 5},
    {"value": 10},
    {"value": 12},
    {"value": "15"},
    {},
]

component.find(Item(value=dataset[0]))

[5]

component.find(Item(value=dataset[1]))

[10]

component.find(Item(value=dataset[2]))

[12]

component.find(Item(value=dataset[3]))

['15']

component.find(Item(value=dataset[4]))

Characteristics

Characteristics are creating using several components and return for each data value a python object computed using the component raw values and some given parameters.

from galactic.algebras.convex.characteristics.core import Component, Integer

characteristic = Integer(components=(component,))

characteristic

<galactic.algebras.convex.characteristics.core.Integer object at 0x7a87dd47ef80>

[characteristic(Item(value=value)) for value in dataset]

[[5], [10], [12], [15], None]

Predicates

Predicates are creating using several characteristics and return for each data value either TernaryBool.TRUE, TernaryBool.FALSE or TernaryBool.UNKNOWN (representing undecidability).

from galactic.algebras.convex.characteristics.core import Component, Integer
from galactic.algebras.convex.predicates.examples.arithmetic.core import Multiple

dataset = [
    12,
    13,
    18,
    True,
    "abc",
]
predicate = Multiple(space=(Integer(components=(Component(),)),), number=4)

predicate

<galactic.algebras.convex.predicates.examples.arithmetic.core.Multiple object at 0x7a87dd47e080>

str(predicate)

'M(int(@),4)'

[predicate(Item(value=data)) for data in dataset]

[TernaryBool.TRUE,
 TernaryBool.FALSE,
 TernaryBool.FALSE,
 TernaryBool.FALSE,
 TernaryBool.UNKNOWN]

Description spaces

Description spaces allow for the precise characterization of a dataset using predicates derived from a convex geometry. Except for certain degenerate cases (such as an empty dataset to describe), the set of descriptors is unique.

from galactic.algebras.convex.characteristics.core import Component, Integer
from galactic.algebras.convex.descriptions.examples.arithmetic.core import (
    DivisorDescription,
)

description = DivisorDescription(space=(Integer(components=(Component(),)),))

description

<galactic.algebras.convex.descriptions.examples.arithmetic.core.DivisorDescription object at 0x7a87dd47e440>

dataset = [
    12,
    13,
    18,
    True,
    "abc",
]

[
    str(predicate)
    for predicate in description(
        [
            Item(value=dataset[0]),
            Item(value=dataset[1]),
            Item(value=dataset[2]),
            Item(value=dataset[3]),
            Item(value=dataset[4]),
        ],
    )
]

[]

[
    str(predicate)
    for predicate in description(
        [
            Item(value=dataset[0]),
            Item(value=dataset[2]),
        ],
    )
]

['D(int(@),36)']

[str(predicate) for predicate in description([Item(value=dataset[0])])]

['D(int(@),12)']

[str(predicate) for predicate in description([Item(value=dataset[2])])]

['D(int(@),18)']

Concepts

Convex concepts consist of a pair (extent, intent), where the extent is the maximal set of elements satisfying all the predicates contained in the intent (and conversely, the intent is the maximal set of predicates satisfied by all the elements contained in the extent).

Generally, in the case of convex concepts, the set of predicates contained in the intent can be infinite, and therefore it cannot be traversed, and its length cannot be calculated. Convex concepts are then described by a minimal set of predicates, called the borders, which are necessary and sufficient to uniquely describe the data of the elements in the extent. Some degenerate cases may occur, such as the case of the empty set; these are handled by appropriate predicates.

from galactic.algebras.concept.core import ItemUniverse
from galactic.algebras.convex.characteristics.core import Component, Integer
from galactic.algebras.convex.descriptions.core import (
    Concept,
    Context,
    GaloisConnection,
    PredicateUniverse,
)
from galactic.algebras.convex.descriptions.examples.arithmetic.core import (
    MultipleDescription,
)
from galactic.algebras.convex.predicates.examples.arithmetic.core import Multiple

characteristic = Integer(components=(Component(),))
descriptions = (
    DivisorDescription(space=(characteristic,)),
    MultipleDescription(space=(characteristic,)),
)
dataset = [36, 48, 16, 32]
context = Context(
    ItemUniverse(dataset),
    PredicateUniverse(descriptions=descriptions),
)
connection = GaloisConnection(context)

top = Concept(connection=connection)
top

<galactic.algebras.convex.descriptions.core.Concept object at 0x7a87dd3f66c0>

top.extent

<galactic.algebras.convex.descriptions.core.Extent object at 0x7a87dd461340>

top.intent

<galactic.algebras.convex.descriptions.core.Intent object at 0x7a87dd3de680>

[item.value for item in top.extent]

[36, 48, 16, 32]

[str(predicate) for predicate in top.intent]

['D(int(@),288)', 'M(int(@),4)']

bottom = Concept(connection=connection, items=[])
bottom

<galactic.algebras.convex.descriptions.core.Concept object at 0x7a87dd47ef30>

[item.value for item in bottom.extent]

[]

[str(predicate) for predicate in bottom.intent]

['⊥', '⊥']

concept1 = Concept(
    connection=connection,
    items=[context.domain[1], context.domain[2]],
)

[item.value for item in concept1.extent]

[48, 16]

[str(predicate) for predicate in concept1.intent]

['D(int(@),48)', 'M(int(@),16)']

Multiple(space=descriptions[1].space, number=4) in concept1.intent

True

Multiple(space=descriptions[1].space, number=3) in concept1.intent

False

concept2 = Concept(connection=connection, items=[context.domain[0]])

meet = concept1 & concept2

[item.value for item in meet.extent]

[]

[str(predicate) for predicate in meet.intent]

['⊥', '⊥']

join = concept1 | concept2

[item.value for item in join.extent]

[36, 48, 16]

[str(predicate) for predicate in join.intent]

['D(int(@),144)', 'M(int(@),4)']

Convex Lattices

Convex lattices are a collection of convex concepts that form a lattice structure, where each concept can be combined with others to form new concepts through meet and join operations. The lattice is defined by the Galois connection between the extent and intent of the concepts.

from galactic.algebras.concept.core import ExtensibleLattice
from galactic.algebras.concept.renderer import (
    ConceptRenderer,
    ConceptHasseDiagramDrawer,
)
from galactic.algebras.convex.descriptions.examples.arithmetic.core import (
    DivisorDescription,
    MultipleDescription,
)

characteristic = Integer(components=(Component(),))
descriptions = (
    DivisorDescription(space=(characteristic,)),
    MultipleDescription(space=(characteristic,)),
)
dataset = {str(n): n for n in (36, 48, 16, 32, 12, 24, 18, 30, 42, 60)}
context = Context(
    ItemUniverse(dataset),
    PredicateUniverse(descriptions=descriptions),
)
connection = GaloisConnection(context)
lattice = ExtensibleLattice()
drawer = ConceptHasseDiagramDrawer(domain_renderer=ConceptRenderer())

drawer.draw(lattice)

lattice.extend([Concept(connection=connection)])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[0]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[1]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[2]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[3]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[4]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[5]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[6]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[7]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[8]])])
drawer.draw(lattice)

lattice.extend([Concept(connection=connection, items=[context.domain[9]])])
drawer.draw(lattice)

Strategies

Strategies are algorithms for constructing convex lattices. They take as input a concept and return an iterable of sub-concepts that are related to the input concept.

By iteratively applying a strategy to the concepts in the lattice, we can construct the entire lattice.

from galactic.algebras.convex.strategies.core import NaiveStrategy, RecursiveStrategy

lattice = ExtensibleLattice()
drawer = ConceptHasseDiagramDrawer(domain_renderer=ConceptRenderer())
drawer.draw(lattice)

top = Concept(connection=connection)
lattice.extend([top])
drawer.draw(lattice)

strategy = NaiveStrategy(descriptions=descriptions)
lattice.extend(list(strategy(top)))
drawer.draw(lattice)

strategy = RecursiveStrategy(strategies=(strategy,))
lattice.extend(list(strategy(top)))
drawer.draw(lattice)

Measures

The SelectiveStrategy is a measure-driven strategy that applies an inner strategy and keeps only sub-concepts whose measure is at least ratio * best_measure, where best_measure is the highest measure value among all generated sub-concepts.

This is useful when you want to explore only the most relevant branches of the lattice, based on a quality criterion such as support.

from galactic.algebras.convex.measures.core import Support
from galactic.algebras.convex.strategies.core import SelectiveStrategy

support = Support()

With ratio=1, only sub-concepts reaching the maximum support are kept:

selective_best = SelectiveStrategy(
    strategies=(NaiveStrategy(descriptions=descriptions),),
    measure=support,
    ratio=1,
)
top = Concept(connection=connection)
selected_best = list(selective_best(top))
display(f"ratio=1: {len(selected_best)} concepts kept (only the best)")
for concept in selected_best:
    display(f"  support={support(concept, top):.0f}", end="")
    display(f"  items={[item.value for item in concept.extent]}")

'ratio=1: 2 concepts kept (only the best)'

'  support=9'

'  items=[36, 48, 16, 12, 24, 18, 30, 42, 60]'

'  support=9'

'  items=[36, 48, 16, 32, 12, 24, 18, 30, 60]'

With ratio=0.8, sub-concepts within 80% of the best support are kept:

selective_80 = SelectiveStrategy(
    strategies=(NaiveStrategy(descriptions=descriptions),),
    measure=support,
    ratio=0.8,
)
selected_80 = list(selective_80(top))
display(f"ratio=0.8: {len(selected_80)} concepts kept")
for concept in selected_80:
    display(f"  support={support(concept, top):.0f}", end="")
    display(f"  items={[item.value for item in concept.extent]}")

'ratio=0.8: 4 concepts kept'

'  support=9'

'  items=[36, 48, 16, 12, 24, 18, 30, 42, 60]'

'  support=9'

'  items=[36, 48, 16, 32, 12, 24, 18, 30, 60]'

'  support=8'

'  items=[48, 16, 32, 12, 24, 30, 42, 60]'

'  support=8'

'  items=[36, 48, 16, 32, 12, 24, 18, 42]'

With ratio=0, all sub-concepts are kept regardless of their measure, yielding the same result as NaiveStrategy:

selective_all = SelectiveStrategy(
    strategies=(NaiveStrategy(descriptions=descriptions),),
    measure=support,
    ratio=0,
)
selected_all = list(selective_all(top))
display(f"ratio=0: {len(selected_all)} concepts kept (all, like NaiveStrategy)")
for concept in selected_all:
    display(f"  support={support(concept, top):.0f}", end="")
    display(f"  items={[item.value for item in concept.extent]}")

'ratio=0: 4 concepts kept (all, like NaiveStrategy)'

'  support=8'

'  items=[48, 16, 32, 12, 24, 30, 42, 60]'

'  support=9'

'  items=[36, 48, 16, 12, 24, 18, 30, 42, 60]'

'  support=8'

'  items=[36, 48, 16, 32, 12, 24, 18, 42]'

'  support=9'

'  items=[36, 48, 16, 32, 12, 24, 18, 30, 60]'

We can also combine SelectiveStrategy with RecursiveStrategy to traverse the full lattice while pruning low-quality branches:

selective_recursive = RecursiveStrategy(
    strategies=(
        SelectiveStrategy(
            strategies=(NaiveStrategy(descriptions=descriptions),),
            measure=support,
            ratio=1,
        ),
    ),
)
lattice2 = ExtensibleLattice()
top = Concept(connection=connection)
all_selective = list(selective_recursive(top))
lattice2.extend([top, *all_selective])
display(f"Selective recursive lattice: {len(lattice2)} concepts")
drawer.draw(lattice2)

'Selective recursive lattice: 24 concepts'