📘 Lattices of formal concepts

📘 Lattices of formal concepts#

Lattices are algebraic structures that capture the notions of order and hierarchy within a set. In the GALACTIC framework, concept lattices are implemented using the ExtensibleLattice class (or the FrozenLattice class) of the galactic.algebras.concept.core module, which allows for the creation, manipulation, and analysis of lattices.

Creating concept lattices#

The constructor of the ExtensibleLattice class takes a series of iterables of Concept, representing the generators of the lattice. These concepts can be created using the Concept class from a given GaloisConnection. The signature of the constructor makes the FrozenLattice class a closure operator over concepts.

from galactic.algebras.concept.core import (
    Concept,
    GaloisConnection,
    ExtensibleLattice,
    create_context_from_dataset
)
from galactic.algebras.concept.examples.animals.core import ANIMAL_ATTRS, ANIMAL_DATA
context = create_context_from_dataset(ANIMAL_DATA, ANIMAL_ATTRS)
connection = GaloisConnection(context)
cat_concept = Concept(connection=connection, items=[context.domain.item(key='Cat')])
dog_concept = Concept(connection=connection, items=[context.domain.item(key='Dog')])
lattice_1 = ExtensibleLattice([cat_concept, dog_concept])
display(
    lattice_1,
    list(lattice_1),
    list(list(str(item) for item in concept.extent)  for concept in lattice_1),
)

<galactic.algebras.concept.core.ExtensibleLattice object at 0x79bce1da3a60>

[<galactic.algebras.concept.core.Concept object at 0x79bce2871dc0>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1dfd840>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1dfd780>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1dfd740>]

[[],
 ['Cat'],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra']]

Iterables given to the constructor are used as generators of the lattice. Operation is optimized if an iterable is a lattice itself.

feathers_concept = Concept(
    connection=connection,
    attrs=[context.co_domain.attr(name='feathers')],
)
lattice_2 = ExtensibleLattice([feathers_concept])
display(
    lattice_2,
    list(lattice_2),
    list(list(str(item) for item in concept.extent) for concept in lattice_2),
)
lattice = ExtensibleLattice(lattice_1, lattice_2)
display(
    lattice,
    list(lattice),
    list(list(str(item) for item in concept.extent) for concept in lattice),
)

<galactic.algebras.concept.core.ExtensibleLattice object at 0x79bce1da3c40>

[<galactic.algebras.concept.core.Concept object at 0x79bce1e0e980>]

[['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

<galactic.algebras.concept.core.ExtensibleLattice object at 0x79bce28906d0>

[<galactic.algebras.concept.core.Concept object at 0x79bce1e10740>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e30b00>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e13c40>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e117c0>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e30780>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e30700>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow']]

Operating on concept lattices#

The ExtensibleLattice class (and the FrozenLattice class) provides methods to operate on lattices using the join (\(\vee\)) or meet (\(\wedge\)) operators.

join = lattice_1 | lattice_2
meet = lattice_1 & lattice_2
display(
    join,
    list(join),
    list(list(str(item) for item in concept.extent) for concept in join),
)
display(
    meet,
    list(meet),
    list(list(str(item) for item in concept.extent) for concept in meet),
)

<galactic.algebras.concept.core.ExtensibleLattice object at 0x79bce1da3e20>

[<galactic.algebras.concept.core.Concept object at 0x79bce1e27d80>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e0d9c0>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e0db40>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e0dc00>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e0d980>,
 <galactic.algebras.concept.core.Concept object at 0x79bce1e0d900>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow']]

<galactic.algebras.concept.core.ExtensibleLattice object at 0x79bce2890b80>

[]

[]

Accessing concept lattices#

In addition to the standard lattice properties and methods provided by the galactic.algebras.lattice.core module, the ExtensibleLattice class (and the FrozenLattice class) also provides specific properties related to concept lattices.

  • connection: returns the underlying antitone Galois connection associated to a concept lattice

  • context: returns the underlying context associated to a concept lattice

  • introduced_items(): returns the collection of items introduced at a specific concept

  • introduced_attrs(): returns the collection of attributes introduced at a specific concept

  • item_concepts(): return a mapping from items to the concepts that introduce them

  • attr_concepts(): return a mapping from attributes to the concepts that introduce them

lattice = ExtensibleLattice([cat_concept, dog_concept, feathers_concept])
display(
    lattice.connection,
    lattice.context,
    list(str(item) for item in lattice.introduced_items(cat_concept)),
    list(str(attr) for attr in lattice.introduced_attrs(feathers_concept)),
    dict(lattice.item_concepts),
    dict(lattice.attr_concepts),
)

<galactic.algebras.concept.core.GaloisConnection object at 0x79bce1dce9c0>

<galactic.algebras.concept.core.Context object at 0x79bce2885260>

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x79bce1dcea00>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Hen', value=<list object at 0x79bce1dced80>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Duck', value=<list object at 0x79bce1dce980>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Goose', value=<list object at 0x79bce1dcedc0>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Owl', value=<list object at 0x79bce1dcee00>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Hawk', value=<list object at 0x79bce1dcee40>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Eagle', value=<list object at 0x79bce1dcee80>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb180>,
 Item(key='Fox', value=<list object at 0x79bce1dceec0>): <galactic.algebras.concept.core.Concept object at 0x79bce1e31640>,
 Item(key='Dog', value=<list object at 0x79bce1dcef00>): <galactic.algebras.concept.core.Concept object at 0x79bce1e31640>,
 Item(key='Wolf', value=<list object at 0x79bce1dcef40>): <galactic.algebras.concept.core.Concept object at 0x79bce1e31640>,
 Item(key='Cat', value=<list object at 0x79bce1dcef80>): <galactic.algebras.concept.core.Concept object at 0x79bce1e30480>,
 Item(key='Tiger', value=<list object at 0x79bce1dcefc0>): <galactic.algebras.concept.core.Concept object at 0x79bce1e30780>,
 Item(key='Lion', value=<list object at 0x79bce1dcf000>): <galactic.algebras.concept.core.Concept object at 0x79bce1e30780>,
 Item(key='Horse', value=<list object at 0x79bce1dcf040>): <galactic.algebras.concept.core.Concept object at 0x79bce1e30780>,
 Item(key='Zebra', value=<list object at 0x79bce1dcf080>): <galactic.algebras.concept.core.Concept object at 0x79bce1e30780>,
 Item(key='Cow', value=<list object at 0x79bce1dcf0c0>): <galactic.algebras.concept.core.Concept object at 0x79bce1deb880>}

{<function small at 0x79bce1f88ae0>: <galactic.algebras.concept.core.Concept object at 0x79bce1e31040>,
 <function hunt at 0x79bce1de2340>: <galactic.algebras.concept.core.Concept object at 0x79bce1e31040>,
 <function medium at 0x79bce1de04a0>: <galactic.algebras.concept.core.Concept object at 0x79bce1e31200>,
 <function big at 0x79bce1de05e0>: <galactic.algebras.concept.core.Concept object at 0x79bce1deb8c0>,
 <function fly at 0x79bce1de1800>: <galactic.algebras.concept.core.Concept object at 0x79bce1deb8c0>,
 <function swim at 0x79bce1de1bc0>: <galactic.algebras.concept.core.Concept object at 0x79bce1deb8c0>,
 <function mane at 0x79bce1de2700>: <galactic.algebras.concept.core.Concept object at 0x79bce1deb8c0>,
 <function hooves at 0x79bce1de2ac0>: <galactic.algebras.concept.core.Concept object at 0x79bce1deb8c0>,
 <function twolegs at 0x79bce1de09a0>: <galactic.algebras.concept.core.Concept object at 0x79bce1e306c0>,
 <function feathers at 0x79bce1dcafc0>: <galactic.algebras.concept.core.Concept object at 0x79bce1e306c0>,
 <function fourlegs at 0x79bce1de0d60>: <galactic.algebras.concept.core.Concept object at 0x79bce1e317c0>,
 <function hair at 0x79bce1de1120>: <galactic.algebras.concept.core.Concept object at 0x79bce1e317c0>,
 <function run at 0x79bce1de1f80>: <galactic.algebras.concept.core.Concept object at 0x79bce1e317c0>}

Views of concept lattices#

The ItemFamily class and the AttrFamily class of the galactic.algebras.concept.core module provide specialized views (Moore families) of concept lattices that focus on the extents and intents of concepts, respectively.

from galactic.algebras.concept.core import ItemFamily, AttrFamily
item_family = ItemFamily(lattice)
attr_family = AttrFamily(lattice)
display(
    item_family,
    list(item_family),
    list(list(str(item) for item in closed) for closed in item_family),
)
display(
    attr_family,
    list(attr_family),
    list(list(str(attr) for attr in closed) for closed in attr_family),
)

<galactic.algebras.concept.core.ItemFamily object at 0x79bce1e50310>

[<galactic.algebras.concept.core.Extent object at 0x79bce2868580>,
 <galactic.algebras.concept.core.Extent object at 0x79bce1e4af80>,
 <galactic.algebras.concept.core.Extent object at 0x79bce2847dc0>,
 <galactic.algebras.concept.core.Extent object at 0x79bce1fd6d00>,
 <galactic.algebras.concept.core.Extent object at 0x79bce1e49ac0>,
 <galactic.algebras.concept.core.Extent object at 0x79bce1e4aec0>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow']]

<galactic.algebras.concept.core.AttrFamily object at 0x79bce1e505e0>

[<galactic.algebras.concept.core.Intent object at 0x79bce1deb480>,
 <galactic.algebras.concept.core.Intent object at 0x79bce1e13700>,
 <galactic.algebras.concept.core.Intent object at 0x79bce1e0fdc0>,
 <galactic.algebras.concept.core.Intent object at 0x79bce1dfd680>,
 <galactic.algebras.concept.core.Intent object at 0x79bce1e10a00>,
 <galactic.algebras.concept.core.Intent object at 0x79bce1e494c0>]

[['small',
  'medium',
  'big',
  'twolegs',
  'fourlegs',
  'hair',
  'feathers',
  'fly',
  'swim',
  'run',
  'hunt',
  'mane',
  'hooves'],
 ['twolegs', 'feathers'],
 ['small', 'fourlegs', 'hair', 'run', 'hunt'],
 ['medium', 'fourlegs', 'hair', 'run'],
 ['fourlegs', 'hair', 'run'],
 []]