📘 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, items=[context.domain.item(key='Cat')])
dog_concept = Concept(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 0x71186e6e84f0>

[<galactic.algebras.concept.core.Concept object at 0x7118887afd00>,
 <galactic.algebras.concept.core.Concept object at 0x71186e70df40>,
 <galactic.algebras.concept.core.Concept object at 0x71186e70de80>,
 <galactic.algebras.concept.core.Concept object at 0x71186e70de40>]

[[],
 ['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,
    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 0x71186e6e86d0>

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x71186e52ac00>,
 <galactic.algebras.concept.core.Concept object at 0x71186e52e4c0>,
 <galactic.algebras.concept.core.Concept object at 0x71186e52cc80>,
 <galactic.algebras.concept.core.Concept object at 0x71186e52cbc0>,
 <galactic.algebras.concept.core.Concept object at 0x71186e52e480>,
 <galactic.algebras.concept.core.Concept object at 0x71186e52dc80>]

[[],
 ['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 0x71186e6e88b0>

[<galactic.algebras.concept.core.Concept object at 0x71186e52bf00>,
 <galactic.algebras.concept.core.Concept object at 0x71186e553a80>,
 <galactic.algebras.concept.core.Concept object at 0x71186e553900>,
 <galactic.algebras.concept.core.Concept object at 0x71186e553880>,
 <galactic.algebras.concept.core.Concept object at 0x71186e553ac0>,
 <galactic.algebras.concept.core.Concept object at 0x71186e553b40>]

[[],
 ['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 0x71186e6e89a0>

[]

[]

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 0x711884121800>

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x71186e6c6fc0>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Hen', value=<list object at 0x71186e6db140>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Duck', value=<list object at 0x71186e6db180>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Goose', value=<list object at 0x71186e6db1c0>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Owl', value=<list object at 0x71186e6db200>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Hawk', value=<list object at 0x71186e6db240>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Eagle', value=<list object at 0x71186e6db280>): <galactic.algebras.concept.core.Concept object at 0x711884122600>,
 Item(key='Fox', value=<list object at 0x71186e6db2c0>): <galactic.algebras.concept.core.Concept object at 0x711884114440>,
 Item(key='Dog', value=<list object at 0x71186e6db300>): <galactic.algebras.concept.core.Concept object at 0x711884114440>,
 Item(key='Wolf', value=<list object at 0x71186e6db340>): <galactic.algebras.concept.core.Concept object at 0x711884114440>,
 Item(key='Cat', value=<list object at 0x71186e6db380>): <galactic.algebras.concept.core.Concept object at 0x71186e552fc0>,
 Item(key='Tiger', value=<list object at 0x71186e6db3c0>): <galactic.algebras.concept.core.Concept object at 0x71186e562040>,
 Item(key='Lion', value=<list object at 0x71186e6db400>): <galactic.algebras.concept.core.Concept object at 0x71186e562040>,
 Item(key='Horse', value=<list object at 0x71186e6db440>): <galactic.algebras.concept.core.Concept object at 0x71186e562040>,
 Item(key='Zebra', value=<list object at 0x71186e6db480>): <galactic.algebras.concept.core.Concept object at 0x71186e562040>,
 Item(key='Cow', value=<list object at 0x71186e6db4c0>): <galactic.algebras.concept.core.Concept object at 0x711884122880>}

{<function small at 0x7118842dbc40>: <galactic.algebras.concept.core.Concept object at 0x71186e551fc0>,
 <function hunt at 0x71186e6f19e0>: <galactic.algebras.concept.core.Concept object at 0x71186e551fc0>,
 <function medium at 0x71186e6d7b00>: <galactic.algebras.concept.core.Concept object at 0x71186e5522c0>,
 <function big at 0x71186e6d7c40>: <galactic.algebras.concept.core.Concept object at 0x7118841227c0>,
 <function fly at 0x71186e6f0ea0>: <galactic.algebras.concept.core.Concept object at 0x7118841227c0>,
 <function swim at 0x71186e6f1260>: <galactic.algebras.concept.core.Concept object at 0x7118841227c0>,
 <function mane at 0x71186e6f1da0>: <galactic.algebras.concept.core.Concept object at 0x7118841227c0>,
 <function hooves at 0x71186e6f2160>: <galactic.algebras.concept.core.Concept object at 0x7118841227c0>,
 <function twolegs at 0x71186e6f0040>: <galactic.algebras.concept.core.Concept object at 0x71186e552380>,
 <function feathers at 0x71186e6d6660>: <galactic.algebras.concept.core.Concept object at 0x71186e552380>,
 <function fourlegs at 0x71186e6f0400>: <galactic.algebras.concept.core.Concept object at 0x71186e52a8c0>,
 <function hair at 0x71186e6f07c0>: <galactic.algebras.concept.core.Concept object at 0x71186e52a8c0>,
 <function run at 0x71186e6f1620>: <galactic.algebras.concept.core.Concept object at 0x71186e52a8c0>}

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 0x71186e6e8c70>

[<galactic.algebras.concept.core.Extent object at 0x711884123840>,
 <galactic.algebras.concept.core.Extent object at 0x71186e56b7c0>,
 <galactic.algebras.concept.core.Extent object at 0x71186e56b600>,
 <galactic.algebras.concept.core.Extent object at 0x71186e56ad80>,
 <galactic.algebras.concept.core.Extent object at 0x71186e56b840>,
 <galactic.algebras.concept.core.Extent object at 0x71186e56b900>]

[[],
 ['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 0x71186e6e8a90>

[<galactic.algebras.concept.core.Intent object at 0x71186e52ca40>,
 <galactic.algebras.concept.core.Intent object at 0x71186e568840>,
 <galactic.algebras.concept.core.Intent object at 0x71186e568500>,
 <galactic.algebras.concept.core.Intent object at 0x71186e56b500>,
 <galactic.algebras.concept.core.Intent object at 0x71186e56bd40>,
 <galactic.algebras.concept.core.Intent object at 0x71186e563c00>]

[['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'],
 []]